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]