Solve, by any method, the following system of linear congruences

     $x \equiv 9(\bmod 11)$

     $x \equiv 1(\bmod 5)$

Find the remainder when ${41^{82}}$ is divided by 11.

Using your answers to parts (a) and (b) find the remainder when ${41^{82}}$ is divided by $55$.

METHOD 1

listing $9,{\rm{ }}20,{\rm{ }}31$, $\ldots$ and $1,{\rm{ }}6,11,16,{\rm{ }}21,{\rm{ }}26,{\rm{ }}31$, $\ldots$     M1

one solution is $31$     (A1)

by the Chinese remainder theorem the full solution is

$x \equiv 31(\bmod 55)$     A1 N2

METHOD 2

$x \equiv 9(\bmod 11) \Rightarrow x = 9 + 11t$     M1

$\Rightarrow 9 + 11t \equiv 1(\bmod 5)$

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

$\Rightarrow t = 2 + 5s$

$\Rightarrow x = 9 + 11(2 + 5s)$

$\Rightarrow x = 31 + 55s{\text{ }}\left( { \Rightarrow x \equiv 31(\bmod 55)} \right)$     A1

Note:     Accept other methods eg formula, Diophantine equation.

Note:     Accept other equivalent answers e.g. $- 79(\bmod 55)$.

[3 marks]

${41^{82}} \equiv {8^{82}}(\bmod 11)$

by Fermat’s little theorem ${8^{10}} \equiv 1(\bmod 11)\;\;\;\left( {{\text{or }}{{41}^{10}} \equiv 1(\bmod 11)} \right)$     M1

${8^{82}} \equiv {8^2}(\bmod 11)$     M1

$\equiv 9(\bmod 11)$     (A1)

remainder is $9$     A1

Note:     Accept simplifications done without Fermat.

[4 marks]

${41^{82}} \equiv {1^{82}} \equiv 1(\bmod 5)$     A1

so ${41^{82}}$ has a remainder $1$ when divided by $5$ and a remainder $9$ when divided by $11$     R1

hence by part (a) the remainder is $31$     A1

[3 marks]

Total [10 marks]

A variety of methods were used here. The Chinese Remainder Theorem method (Method 2 on the mark-scheme) is probably the most instructive. Candidates who tried to do it by formula often (as usual) made mistakes and got it wrong. Marks were lost by just saying 31 and not giving mod (55).

Time was lost here by not using Fermat’s Little Theorem as a starting point, although the ad hoc methods will work.

Although it said use parts (a) and (b) not enough candidates saw the connection.