Use the above result to show that if p is prime then \({a^p} \equiv a(\bmod p)\) where a is any positive integer.

Show that \({2^{341}} \equiv 2(\bmod 341)\).

(i)     State the converse of the result in part (a).

(ii)     Show that this converse is not true.

consider two cases     M1

let a and p be coprime

\({a^{p - 1}} \equiv 1(\bmod p)\)     R1

\( \Rightarrow {a^p} \equiv a(\bmod p)\)

let a and p not be coprime

\(a \equiv 0(\bmod p)\)     M1

\({a^p} = 0(\bmod p)\)     R1

\( \Rightarrow {a^p} = a(\bmod p)\)

so \({a^p} = a(\bmod p)\) in both cases     AG

[4 marks]

\(341 = 11 \times 31\)     (M1)

we know by Fermat’s little theorem

\({2^{10}} \equiv 1(\bmod 11)\)     M1

\( \Rightarrow {2^{341}} \equiv {({2^{10}})^{34}} \times 2 \equiv {1^{34}} \times 2 \equiv 2(\bmod 11)\)     A1

also \({2^{30}} \equiv 1(\bmod 31)\)     M1

\( \Rightarrow {2^{341}} \equiv {({2^{30}})^{11}} \times {2^{11}}\)     A1

\( \equiv {1^{11}} \times 2048 \equiv 2(\bmod 31)\)     A1

since 31 and 11 are coprime     R1

\({2^{341}} \equiv 2(\bmod 341)\)     AG

[7 marks]

(i)     converse: if \({a^p} = a(\bmod p)\) then p is a prime     A1

(ii)     from part (b) we know \({2^{341}} \equiv 2(\bmod 341)\)

however, 341 is composite

hence 341 is a counter-example and the converse is not true     R1

[2 marks]

There were very few fully correct answers. In (b) the majority of candidates assumed that 341 is a prime number and in (c) only a handful of candidates were able to state the converse.

There were very few fully correct answers. In (b) the majority of candidates assumed that 341 is a prime number and in (c) only a handful of candidates were able to state the converse.

There were very few fully correct answers. In (b) the majority of candidates assumed that 341 is a prime number and in (c) only a handful of candidates were able to state the converse.