(a)     Write down Fermat’s little theorem.

(b)     In base 5 the representation of a natural number X is ${\left( {k00013(5 - k)} \right)_5}$.

This means that $X = k \times {5^6} + 1 \times {5^2} + 3 \times 5 + (5 - k)$.

In base 7 the representation of X is ${({a_n}{a_{n - 1}} \ldots {a_2}{a_1}{a_0})_7}$.

Find ${a_0}$.

(c)     Given that k = 2, find X in base 7.

(a)     EITHER

if p is a prime ${a^p} \equiv a(\bmod p)$     A1A1

OR

if p is a prime and $a$ $0(\bmod p)$ then ${a^{p - 1}} \equiv 1(\bmod p)$     A1A1

Note: Award A1 for p being prime and A1 for the congruence.

 

[2 marks]

 

(b)     ${a_0} \equiv X(\bmod 7)$     M1

$X = k \times {5^6} + 25 + 15 + 5 - k$

by Fermat ${5^6} \equiv 1(\bmod 7)$     R1

$X = k + 45 - k(\bmod 7)$     (M1)

$X = 3(\bmod 7)$     A1

${a_0} = 3$     A1

[5 marks]

 

(c)     $X = 2 \times {5^6} + 25 + 15 + 3 = 31\,293$     A1

EITHER

$X - {7^5} = 14\,486$     (M1)

$X - {7^5} - 6 \times {7^4} = 80$

$X - {7^5} - 6 \times {7^4} - {7^2} = 31$

$X - {7^5} - 6 \times {7^4} - {7^2} - 4 \times 7 = 3$

$X = {7^5} + 6 \times {7^4} + {7^2} + 4 \times 7 + 3$     (A1)

$X = {(160\,143)_7}$     A1

OR

$31\,293 = 7 \times 4470 + 3$     (M1)

$4470 = 7 \times 638 + 4$

$638 = 7 \times 91 + 1$

$91 = 7 \times 13 + 0$

$13 = 7 \times 1 + 6$     (A1)

$X = {(160\,143)_7}$     A1

[4 marks]

 

Total [11 marks]

Fermat’s little theorem was reasonably well known. Not all candidates took the hint to use this in the next part and this part was not done well. Part (c) could and was done even if part (b) was not.