User interface language: English | Español

Date May 2018 Marks available 3 Reference code 18M.3dm.hl.TZ0.2
Level HL only Paper Paper 3 Discrete mathematics Time zone TZ0
Command term Use and Show that Question number 2 Adapted from N/A

Question

Consider the linear congruence axb(modp)axb(modp) where a,b,p,xZ+p is prime and a is not a multiple of p.

State Fermat’s little theorem.

[2]
a.

Use Fermat’s little theorem to show that xap2b(modp).

[3]
b.i.

Hence solve the linear congruence 5x7(mod13).

[3]
b.ii.

Markscheme

EITHER

if p is prime (and a is any integer) then apa(modp)    A1A1 

Note: Award A1 for p prime and A1 for the congruence or for stating that p|apa.

OR

   A1A1 

Note: Award A1 for p prime and A1 for the congruence or for stating that p|ap11.

Note: Condone use of equals sign provided (modp) is seen.

[2 marks]

 

a.

multiplying both sides of the linear congruence by ap2     (M1)

ap1xap2b(modp)      A1

as ap11(modp)     R1

xap2b(modp)     AG

[3 marks]

b.i.

x511×7(mod13)     (M1)

341796875(mod13)     (A1)

Note: Accept equivalent calculation eg, using 521mod13.

4(mod13)     A1

[3 marks]

b.ii.

Examiners report

[N/A]
a.
[N/A]
b.i.
[N/A]
b.ii.

Syllabus sections

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

View options