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 ap−1≡1(modp).
Use the above result to show that if p is prime then ap≡a(modp) where a is any positive integer.
Show that 2341≡2(mod341).
(i) State the converse of the result in part (a).
(ii) Show that this converse is not true.
Markscheme
consider two cases M1
let a and p be coprime
ap−1≡1(modp) R1
⇒ap≡a(modp)
let a and p not be coprime
a≡0(modp) M1
ap=0(modp) R1
⇒ap=a(modp)
so ap=a(modp) in both cases AG
[4 marks]
341=11×31 (M1)
we know by Fermat’s little theorem
210≡1(mod11) M1
⇒2341≡(210)34×2≡134×2≡2(mod11) A1
also 230≡1(mod31) M1
⇒2341≡(230)11×211 A1
≡111×2048≡2(mod31) A1
since 31 and 11 are coprime R1
2341≡2(mod341) AG
[7 marks]
(i) converse: if ap=a(modp) then p is a prime A1
(ii) from part (b) we know 2341≡2(mod341)
however, 341 is composite
hence 341 is a counter-example and the converse is not true R1
[2 marks]
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.
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.