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.