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]