Given the linear congruence \(ax \equiv b({\rm{mod}}p)\) , where \(a\) , \(b \in \mathbb{Z} \) , \(p\) is a prime and \({\rm{gcd}}(a,p) = 1\) , show that \(x \equiv {a^{p - 2}}b({\rm{mod}}p)\) .

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

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

\(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]

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.