Use the result $2003 = 6 \times 333 + 5$ and Fermat’s little theorem to show that ${2^{2003}} \equiv 4(\bmod 7)$ .

Find ${2^{2003}}(\bmod 11)$ and ${2^{2003}}(\bmod 13)$.

Use the Chinese remainder theorem, or otherwise, to evaluate ${2^{2003}}(\bmod 1001)$, noting that $1001 = 7 \times 11 \times 13$.

${2^{2003}} = {2^5} \times {({2^6})^{333}}$     M1A1

$\equiv 32 \times 1(\bmod 7)$ by Fermat’s little theorem     A1

$\equiv 4(\bmod 7)$     AG

[3 marks]

$2003 = 3 + 10 \times 200$     (M1)

${2^{2003}} = {2^3} \times {({2^{10}})^{200}}\left( { \equiv 8 \times 1(\bmod 11)} \right) \equiv 8(\bmod 11)$     A1

${2^{2003}} = {2^{11}} \times {({2^{12}})^{166}} \equiv 7(\bmod 13)$     A1

[3 marks]

form ${M_1} = \frac{{1001}}{7} = 143;{\text{   }}{M_2} = \frac{{1001}}{{11}} = 91;{\text{   }}{M_3} = \frac{{1001}}{{13}} = 77$     M1

solve $143{x_1} \equiv 1(\bmod 7) \Rightarrow {x_1} = 5$     M1A1

${x_2} = 4;{\text{ }}{x_3} = 12$     A1A1

$x = 4 \times 143 \times 5 + 8 \times 91 \times 4 + 7 \times 77 \times 12 = 12240 \equiv 228(\bmod 1001)$     M1A1

[7 marks]

Many candidates were able to complete part (a) and then went on to part (b). Some candidates raced through part (c). Others, who attempted part (c) using the alternative strategy of repeatedly solving linear congruencies, were sometimes successful.

Many candidates were able to complete part (a) and then went on to part (b). Some candidates raced through part (c). Others, who attempted part (c) using the alternative strategy of repeatedly solving linear congruencies, were sometimes successful.

Many candidates were able to complete part (a) and then went on to part (b). Some candidates raced through part (c). Others, who attempted part (c) using the alternative strategy of repeatedly solving linear congruencies, were sometimes successful.