(i)     One version of Fermat’s little theorem states that, under certain conditions,

\[{a^{p - 1}} \equiv 1(\bmod p).\]

Show that this result is not valid when a = 4, p = 9 and state which

condition is not satisfied.

(ii)     Given that \({5^{64}} \equiv n(\bmod 7)\), where \(0 \leqslant n \leqslant 6\), find the value of n.

Find the general solution to the simultaneous congruences

\[x \equiv 3(\bmod 4)\]

\[3x \equiv 2(\bmod 5).\]

(i)     \({4^8} = 65536 \equiv 7(\bmod 9)\)     A1

not valid because 9 is not a prime number     R1

Note: The R1 is independent of the A1.

(ii)     using Fermat’s little theorem     M1

\({5^6} \equiv 1(\bmod 7)\)     A1

therefore

\({({5^6})^{10}} = {5^{60}} \equiv 1(\bmod 7)\)     A1

also, \({5^4} = 625\)     M1

\( \equiv 2(\bmod 7)\)     A1

therefore

\({5^{64}} \equiv 1 \times 2 \equiv 2(\bmod 7)\,\,\,\,\,{\text{(so }}n = 2)\)     A1

Note: Accept alternative solutions not using Fermat.

[8 marks]

EITHER

solutions to \(x \equiv 3(\bmod 4)\) are

3, 7, 11, 15, 19, 23, 27, …     A1

solutions to \(3x \equiv 2(\bmod 5).\) are

4, 9, 14, 19 …     (M1)A1

so a solution is x =19     A1

using the Chinese remainder theorem (or otherwise)     (M1)

the general solution is \(x = 19 + 20n{\text{ }}(n \in \mathbb{Z})\)     A1

\(\left( {{\text{accept }}19(\bmod 20)} \right)\)

OR

\(x = 3 + 4t \Rightarrow 9 + 12t \equiv 2(\bmod 5)\)     M1A1

\( \Rightarrow 2t \equiv 3(\bmod 5)\)     A1

\( \Rightarrow 6t \equiv 9(\bmod 5)\)

\( \Rightarrow t \equiv 4(\bmod 5)\)     A1

so \(t = 4 + 5n{\text{ and }}x = 19 + 20n{\text{ }}(n \in \mathbb{Z})\)     M1A1

\(\left( {{\text{accept }}19(\bmod 20)} \right)\)

Note: Also accept solutions done by formula.

[6 marks]

Part (a) was generally well answered with a variety of methods seen in (a)(ii). This was set with Fermat’s Little Theorem in mind but in the event many candidates started off with many different powers of 5, eg \({5^4} \equiv 2,{\text{ }}{5^8} \equiv 4\) and \({5^3}\equiv- 1(\bmod 7)\) were all seen. A variety of methods was also seen in (b), ranging from use of the Chinese Remainder Theorem, finding tables of numbers congruent to \(3(\bmod 4)\)and \(4(\bmod 5)\) and the use of an appropriate formula.

Part (a) was generally well answered with a variety of methods seen in (a)(ii). This was set with Fermat’s Little Theorem in mind but in the event many candidates started off with many different powers of 5, eg \({5^4} \equiv 2,{\text{ }}{5^8} \equiv 4\) and \({5^3}\equiv - 1(\bmod 7)\) were all seen. A variety of methods was also seen in (b), ranging from use of the Chinese Remainder Theorem, finding tables of numbers congruent to \(3(\bmod 4)\)and \(4(\bmod 5)\) and the use of an appropriate formula.