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 ax≡b(modp) , where a , b∈Z , p is a prime and gcd(a,p)=1 , show that x≡ap−2b(modp) .
(i) Solve 17x≡14(mod .
(ii) Use the solution found in part (i) to find the general solution to the Diophantine equation 17x + 21y = 14 .
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]
(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]
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.
(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.