Processing math: 18%

User interface language: English | Español

Date May 2011 Marks available 4 Reference code 11M.2.hl.TZ0.4
Level HL only Paper 2 Time zone TZ0
Command term Show that Question number 4 Adapted from N/A

Question

Given the linear congruence axb(modp) , where a , bZ , p is a prime and gcd(a,p)=1 , show that xap2b(modp) .

[4]
a.

(i)     Solve 17x14(mod .

(ii)     Use the solution found in part (i) to find the general solution to the Diophantine equation 17x + 21y = 14 .

[10]
b.

Markscheme

ax \equiv b({\rm{mod}}p)

\Rightarrow {a^{p - 2}} \times ax \equiv {a^{p - 2}} \times b({\rm{mod}}p)     M1A1

\Rightarrow {a^{p - 1}}x \equiv {a^{p - 2}} \times b({\rm{mod}}p)     A1

but {a^{p - 1}} \equiv 1({\rm{mod}}p) by Fermat’s little theorem     R1

\Rightarrow x \equiv {a^{p - 2}} \times b({\rm{mod}}p)     AG

Note: Award M1 for some correct method and A1 for correct statement.

[4 marks]

a.

(i)     17x \equiv 14(\bmod 21)

\Rightarrow x \equiv {17^{19}} \times 14(\bmod 21)     M1A1

{17^6} \equiv 1(\bmod21)     A1

\Rightarrow x \equiv {(1)^3} \times 17 \times 14(\bmod 21)     A1

\Rightarrow x \equiv 7(\bmod21)     A1

 

(ii)     x \equiv 7(mod21)

\Rightarrow x = 7 + 21t , t \in \mathbb{Z}     M1A1

\Rightarrow 17(7 + 21t) + 21y = 14     A1

\Rightarrow 119 + 357t + 21y = 14

\Rightarrow 21y = - 105 - 357t     A1

\Rightarrow y = - 5 - 17t     A1

 

[10 marks]

b.

Examiners report

Some creative ways of doing this part involved more work than four marks merited although there were many solutions that were less simple than that in the markscheme.

a.

(b)(i) Various ways were used and accepted.

(ii) Alternative valid solutions were found and in general this part was found to be within the reach of most candidates.

b.

Syllabus sections

Topic 6 - Discrete mathematics » 6.6 » Fermat’s little theorem.

View options