(a)     Show that the solution to the linear congruence \(ax \equiv b(\bmod p)\), where \(a,{\text{ }}x,{\text{ }}b,{\text{ }}p \in {\mathbb{Z}^ + },{\text{ }}p\) is prime and \(a\), \(p\) are relatively prime, is given by \(x \equiv {a^{p - 2}}b(\bmod p)\).

(b)     Consider the congruences

     \(7x \equiv 13(\bmod 19)\)

     \(2x \equiv 1(\bmod 7)\).

(i)     Use the result in (a) to solve the first congruence, giving your answer in the form \(x \equiv k(\bmod 19)\) where \(1 \leqslant k \leqslant 18\).

(ii)     Find the set of integers which satisfy both congruences simultaneously.

(a)     using Fermat’s little theorem,     (M1)

\({a^{p - 1}} \equiv 1(\bmod p)\)     A1

multiplying both sides of the congruence by \({a^{p - 2}}\),     (M1)

\({a^{p - 1}}x \equiv {a^{p - 2}}b(\bmod p)\)     A1

\(x \equiv {a^{p - 2}}b(\bmod p)\)     AG

[4 marks]

(b)     (i)     the solution is

\(x \equiv {7^{17}} \times 13(\bmod 19)\)     A1

consider

\({7^3} = 343 \equiv 1(\bmod 19)\)     (A1)

Note: Other powers are possible.

therefore

\(x \equiv {\left( {{7^3}} \right)^5} \times {7^2} \times 13(\bmod 19)\)     (A1)

\( \equiv {7^2} \times 13(\bmod 19)\)     (A1)

\( \equiv 10(\bmod 19)\)     A1

(ii)     using any method, including trial and error, the solution to the second congruence is given by \(x \equiv 32(\bmod 7)\) (or equivalent)     (A1)

a simultaneous solution is \(x = 67\) (or equivalent, eg \(-66\))     A1

the full solution is \(x = 67 + 133N\) (where \(N \in \mathbb{Z}\)) (or equivalent)     A1

Note: Do not FT an incorrect answer from (i).

[8 marks]