Consider the linear congruence $ax \equiv b(\bmod p)$ where $a,{\text{ }}b \in {\mathbb{Z}^ + },{\text{ }}p$ is a prime and $\gcd (a,{\text{ }}p) = 1$. Using Fermat’s little theorem, show that $x \equiv {a^{p - 2}}b(\bmod p)$.

Hence find the smallest value of $x$ greater than 100 satisfying the linear congruence $3x \equiv 13(\bmod 19)$.

multiplying both sides by ${a^{p - 2}}$,     M1

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

using ${a^{p - 1}} \equiv 1(\bmod p)$     R1

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

[3 marks]

using the above result,

$x \equiv {3^{17}} \times 13(\bmod 19){\text{ }}\left( { \equiv 16\,7882\,2119(\bmod 19)} \right)$     A1

$\equiv 17(\bmod 19)$     (M1)A1

$x = 112$     A1

[4 marks]