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]