One version of Fermat’s little theorem states that, under certain conditions, \({a^{p - 1}} \equiv 1(\bmod p)\) .

(i)     Show that this result is not true when a = 2, p = 9 and state which of the conditions is not satisfied.

(ii)     Find the smallest positive value of k satisfying the congruence \({2^{45}} \equiv k(\bmod 9)\) .

Find all the integers between 100 and 200 satisfying the simultaneous congruences \(3x \equiv 4(\bmod 5)\) and \(5x \equiv 6(\bmod 7)\) .

(i)     \({2^8} = 256 \equiv 4(\bmod 9)\) (so not true)     A1

9 is not prime     A1

(ii)     consider various powers of 2, e.g. obtaining     M1

\({2^6} = 64 \equiv 1(\bmod 9)\)     A1

therefore

\({2^{45}} = {({2^6})^7} \times {2^3}\)     M1

\( \equiv 8(\bmod 9){\text{ (so }}k = 8)\)     A1

[6 marks]

EITHER

the solutions to \(3x \equiv 4(\bmod 5)\) are 3, 8, 13, 18, 23,…     M1A1

the solutions to \(5x \equiv 6(\bmod 7)\) are 4, 11, 18,…     A1

18 is therefore the smallest solution     A1

the general solution is

\(18 + 35n{\text{ , }}n \in \mathbb{Z}\)     M1

the required solutions are therefore 123, 158, 193     A1

OR

\(3x \equiv 4(\bmod 5) \Rightarrow 2 \times 3x \equiv 2 \times 4(\bmod 5) \Rightarrow x \equiv 3(\bmod 5)\)     A1

\( \Rightarrow x = 3 + 5t\)     M1

\( \Rightarrow 15 + 25t \equiv 6(\bmod 7) \Rightarrow 4t \equiv 5(\bmod 7) \Rightarrow 2 \times 4t \equiv 2 \times 5(\bmod 7) \Rightarrow t \equiv 3(\bmod 7)\)     A1

\( \Rightarrow t = 3 + 7n\)     A1

\( \Rightarrow x = 3 + 5(3 + 7n) = 18 + 35n\)     M1

the required solutions are therefore 123, 158, 193     A1

OR

using the Chinese remainder theorem formula method

first convert the congruences to \(x \equiv 3(\bmod 5)\) and \(x \equiv 4(\bmod 7)\)     A1A1

\(M = 35{\text{, }}{M_1} = 7{\text{, }}{M_2} = 5{\text{, }}{m_1} = 5,{\text{ }}{m_2} = 7,{\text{ }}{a_1} = 3,{\text{ }}{a_2} = 4\)

\({x_1}\) is the solution of \({M_2}{x_2} \equiv 1(\bmod {m_1})\) , i.e. \(7{x_1} \equiv 1(\bmod 5)\) so \({x_1} = 3\)

\({x_2}\) is the solution of \({M_2}{x_2} \equiv 1(\bmod {m_2})\) , i.e. \(5{x_2} \equiv 1(\bmod 7)\) so \({x_2} = 3\)

a solution is therefore

\(x = {a_1}{M_1}{x_1} + {a_2}{M_2}{x_2}\)     M1

\( = 3 \times 7 \times 3 + 4 \times 5 \times 3 = 123\)     A1

the general solution is \(123 + 35n\) , \(n \in \mathbb{Z}\)     M1

the required solutions are therefore 123, 158, 193     A1

[6 marks]