State Fermat’s little theorem.

Use Fermat’s little theorem to show that \(x \equiv {a^{p - 2}}b\left( {{\text{mod}}\,p} \right)\).

Hence solve the linear congruence \(5x \equiv 7\left( {{\text{mod}}\,13} \right)\).

EITHER

if \(p\) is prime (and \(a\) is any integer) then \({a^p} \equiv a\left( {{\text{mod}}\,p} \right)\)    A1A1 

Note: Award A1 for \(p\) prime and A1 for the congruence or for stating that \(p\left| {{a^p} - a} \right.\).

OR

   A1A1 

Note: Award A1 for \(p\) prime and A1 for the congruence or for stating that \(p\left| {{a^{p - 1}} - 1} \right.\).

Note: Condone use of equals sign provided \(\left( {{\text{mod}}\,p} \right)\) is seen.

[2 marks]

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

\({a^{p - 1}}x \equiv {a^{p - 2}}b\left( {{\text{mod}}\,p} \right)\)      A1

as \({a^{p - 1}} \equiv 1\left( {{\text{mod}}\,p} \right)\)     R1

\(x \equiv {a^{p - 2}}b\left( {{\text{mod}}\,p} \right)\)     AG

[3 marks]

\(x \equiv {5^{11}} \times 7\left( {{\text{mod}}\,13} \right)\)     (M1)

\( \equiv 341796875\left( {{\text{mod}}\,13} \right)\)     (A1)

Note: Accept equivalent calculation eg, using \({5^2} \equiv  - 1\,{\text{mod}}\,13\).

\( \equiv 4\left( {{\text{mod}}\,13} \right)\)     A1

[3 marks]