Processing math: 100%

User interface language: English | Español

Date November 2011 Marks available 7 Reference code 11N.3dm.hl.TZ0.5
Level HL only Paper Paper 3 Discrete mathematics Time zone TZ0
Command term Show that Question number 5 Adapted from N/A

Question

A version of Fermat’s little theorem states that when p is prime, a is a positive integer and a and p are relatively prime, then ap11(modp).

Use the above result to show that if p is prime then apa(modp) where a is any positive integer.

[4]
a.

Show that 23412(mod341).

[7]
b.

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

(ii)     Show that this converse is not true.

[2]
c.

Markscheme

consider two cases     M1

let a and p be coprime

ap11(modp)     R1

apa(modp)

let a and p not be coprime

a0(modp)     M1

ap=0(modp)     R1

ap=a(modp)

so ap=a(modp) in both cases     AG

[4 marks]

a.

341=11×31     (M1)

we know by Fermat’s little theorem

2101(mod11)     M1

2341(210)34×2134×22(mod11)     A1

also 2301(mod31)     M1

2341(230)11×211     A1

111×20482(mod31)     A1

since 31 and 11 are coprime     R1

23412(mod341)     AG

[7 marks]

b.

(i)     converse: if ap=a(modp) then p is a prime     A1

 

(ii)     from part (b) we know 23412(mod341)

however, 341 is composite

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

[2 marks]

c.

Examiners report

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.

a.

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.

b.

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.

c.

Syllabus sections

Topic 10 - Option: Discrete mathematics » 10.6 » Fermat’s little theorem.

View options