# IB DP Maths Topic 10.6 Fermat’s little theorem. HL Paper 3

## Question

(i)     Given that $$a \equiv d(\bmod n)$$ and $$b \equiv c(\bmod n)$$ prove that

$(a + b) \equiv (c + d)(\bmod n){\text{ .}}$

(ii)     Hence solve the system

$\left\{ {\begin{array}{*{20}{r}} {2x + 5y \equiv 1(\bmod 6)} \\ {x + y \equiv 5(\bmod 6)} \end{array}} \right.$

[11]
a.

Show that $${x^{97}} – x + 1 \equiv 0(\bmod 97)$$ has no solution.

[3]
b.

## Markscheme

(i)     $$a \equiv d(\bmod n){\text{ and }}b \equiv c(\bmod n)$$

so $$a – d = pn{\text{ and }}b – c = qn$$ ,     M1A1

$$a – d + b – c = pn + qn$$

$$(a + b) – (c + d) = n(p + q)$$     A1

$$(a + b) \equiv (c + d)(\bmod n)$$     AG

(ii)     $$\left\{ {\begin{array}{*{20}{r}} {2x + 5y \equiv 1(\bmod 6)} \\ {x + y \equiv 5(\bmod 6)} \end{array}} \right.$$

adding $$3x + 6y \equiv 0(\bmod 6)$$     M1

$$6y \equiv 0(\bmod 6){\text{ so }}3x \equiv 0(\bmod 6)$$     R1

$$x \equiv 0{\text{ or }}x \equiv 2{\text{ or }}x \equiv 4(\bmod 6)$$     A1A1A1

for $$x \equiv 0,{\text{ }}0 + y \equiv 5(\bmod 6){\text{ so }}y \equiv 5(\bmod 6)$$     A1

for $$x \equiv 2,{\text{ }}2 + y \equiv 5(\bmod 6){\text{ so }}y \equiv 3(\bmod 6)$$     A1

If $$x \equiv 4(\bmod 6),{\text{ }}4 + y \equiv 5(\bmod 6){\text{ so }}y \equiv 1(\bmod 6)$$     A1

[11 marks]

a.

Suppose x is a solution

97 is prime so $${x^{97}} \equiv x(\bmod 97)$$     M1

$${x^{97}} – x \equiv 0(\bmod 97)$$     A1

$${x^{97}} – x + 1 \equiv 1 \ne 0(\bmod 97)$$

Hence there are no solutions     R1

[3 marks]

b.

## Examiners report

Part (a) (i) was not found difficult but using it in part (a)(ii) resulted in two or three correct lines and then abandonment of the problem.

a.

Part (a) (i) was not found difficult but using it in part (a)(ii) resulted in two or three correct lines and then abandonment of the problem.

b.

## Question

Write 57128 as a product of primes.

[4]
a.

Prove that $$\left. {22} \right|{5^{11}} + {17^{11}}$$.

[4]
c.

## Markscheme

$$457\,128 = 2 \times 228\,564$$

$$228\,564 = 2 \times 114\,282$$

$$114\,282 = 2 \times 57\,141$$

$$57\,141 = 3 \times 19\,047$$

$$19\,047 = 3 \times 6349$$

$$6349 = 7 \times 907$$     M1A1

trial division by 11, 13, 17, 19, 23 and 29 shows that 907 is prime     R1

therefore $$457\,128 = {2^3} \times {3^2} \times 7 \times 907$$     A1

[4 marks]

a.

by a corollary to Fermat’s Last Theorem

$${5^{11}} \equiv 5(\bmod 11){\text{ and }}{17^{11}} \equiv 17(\bmod 11)$$     M1A1

$${5^{11}} + {17^{11}} \equiv 5 + 17 \equiv 0(\bmod 11)$$     A1

this combined with the evenness of LHS implies $$\left. {25} \right|{5^{11}} + {17^{11}}$$     R1AG

[4 marks]

c.

## Examiners report

Some candidates were obviously not sure what was meant by ‘product of primes’ which surprised the examiner.

a.

There were some reasonable attempts at part (c) using powers rather than Fermat’s little theorem.

c.

## Question

(a)     Using Fermat’s little theorem, show that, in base 10, the last digit of n is always equal to the last digit of $${n^5}$$ .

(b)     Show that this result is also true in base 30.

## Markscheme

(a)     using Fermat’s little theorem $${n^5} \equiv n(\bmod 5)$$     (M1)

$${n^5} – n \equiv 0(\bmod 5)$$     A1

now $${n^5} – n = n({n^4} – 1)$$     (M1)

$$= n({n^2} – 1)({n^2} + 1)$$

$$= n(n – 1)(n + 1)({n^2} + 1)$$     A1

hence one of the first two factors must be even     R1

i.e. $${n^5} – n \equiv 0(\bmod 2)$$

thus $${n^5} – n$$ is divisible by 5 and 2

hence it is divisible by 10     R1

in base 10, since $${n^5} – n$$ is divisible by 10, then $${n^5} – n$$ must end in zero and hence $${n^5}$$ and n must end with the same digit     R1

[7 marks]

(b)     consider $${n^5} – n = n(n – 1)(n + 1)({n^2} + 1)$$

this is divisible by 3 since the first three factors are consecutive integers     R1

hence $${n^5} – n$$ is divisible by 3, 5 and 2 and therefore divisible by 30

in base 30, since $${n^5} – n$$ is divisible by 30, then $${n^5} – n$$ must end in zero and hence $${n^5}$$ and n must end with the same digit     R1

[2 marks]

Total [9 marks]

## Examiners report

There were very few fully correct answers. If Fermat‟s little theorem was known, it was not well applied.

## Question

Show that a positive integer, written in base 10, is divisible by 9 if the sum of its digits is divisible by 9.

[7]
a.

The representation of the positive integer N in base p is denoted by $${(N)_p}$$ .

If $${({5^{{{(126)}_7}}})_7} = {({a_n}{a_{n – 1}} \ldots {a_1}{a_0})_7}$$ , find $${a_0}$$ .

[9]
b.

## Markscheme

consider the decimal number $$A = {a_n}{a_{n – 1}} \ldots {a_0}$$     M1

$$A = {A_n} \times {10^n} + {a_{n – 1}} \times {10^{n – 1}} + \ldots + {a_1} \times 10 + {a_0}$$     M1

$$= {a_n} \times ({10^n} – 1) + {a_{n – 1}} \times ({10^{n – 1}} – 1) + \ldots + {a_1} \times (10 – 1) + {a_n} + {a_{n – 1}} + \ldots + {a_0}$$     M1A1

$$= {a_n} \times 99 \ldots 9(n{\text{ digits}}) + {a_{n – 1}} \times 99 \ldots 9(n – 1{\text{ digits}}) + \ldots + 9{a_1} + {a_n} + {a_{n – 1}} + \ldots + {a_0}$$     A1

all the numbers of the form 99…9 are divisible by 9 (to give 11…1),     R1

hence A is divisible by 9 if $$\sum\limits_{i = 0}^n {{a_i}}$$ is divisible by 9     R1

Note: A method that uses the fact that $${10^t} \equiv 1(\bmod 9)$$ is equally valid.

[7 marks]

a.

by Fermat’s Little Theorem $${5^6} \equiv 1(\bmod 7)$$     M1A1

$${(126)_7} = {(49 + 14 + 6)_{10}} = {(69)_{10}}$$     M1A1

$${5^{{{(126)}_7}}} \equiv {5^{{{(11 \times 6 + 3)}_{10}}}} \equiv {5^{{{(3)}_{10}}}}(\bmod 7)$$     M1A1

$${5^{{{(3)}_{10}}}} = {(125)_{10}} = {(17 \times 7 + 6)_{10}} \equiv 6(\bmod 7)$$     M1A1

hence $${a_0} = 6$$     A1

[9 marks]

b.

## Examiners report

Questions similar to (a) have been asked in the past so it was surprising to see that solutions this time were generally disappointing.

a.

In (b), most candidates changed the base 7 number 126 to the base 10 number 69. After that the expectation was that Fermats little theorem would be used to complete the solution but few candidates actually did that. Many were unable to proceed any further and others used a variety of methods, for example working modulo 7,

$${5^{69}} = {({5^2})^{34}}.5 = {4^{34}}.5 = {({4^2})^{17}}.5 = {2^{17}}.5$$ etc

This is of course a valid method, but somewhat laborious.

b.

## Question

(i)     One version of Fermat’s little theorem states that, under certain conditions,

${a^{p – 1}} \equiv 1(\bmod p).$

Show that this result is not valid when a = 4, p = 9 and state which

condition is not satisfied.

(ii)     Given that $${5^{64}} \equiv n(\bmod 7)$$, where $$0 \leqslant n \leqslant 6$$, find the value of n.

[8]
a.

Find the general solution to the simultaneous congruences

$x \equiv 3(\bmod 4)$

$3x \equiv 2(\bmod 5).$

[6]
b.

## Markscheme

(i)     $${4^8} = 65536 \equiv 7(\bmod 9)$$     A1

not valid because 9 is not a prime number     R1

Note: The R1 is independent of the A1.

(ii)     using Fermat’s little theorem     M1

$${5^6} \equiv 1(\bmod 7)$$     A1

therefore

$${({5^6})^{10}} = {5^{60}} \equiv 1(\bmod 7)$$     A1

also, $${5^4} = 625$$     M1

$$\equiv 2(\bmod 7)$$     A1

therefore

$${5^{64}} \equiv 1 \times 2 \equiv 2(\bmod 7)\,\,\,\,\,{\text{(so }}n = 2)$$     A1

Note: Accept alternative solutions not using Fermat.

[8 marks]

a.

EITHER

solutions to $$x \equiv 3(\bmod 4)$$ are

3, 7, 11, 15, 19, 23, 27, …     A1

solutions to $$3x \equiv 2(\bmod 5).$$ are

4, 9, 14, 19 …     (M1)A1

so a solution is x =19     A1

using the Chinese remainder theorem (or otherwise)     (M1)

the general solution is $$x = 19 + 20n{\text{ }}(n \in \mathbb{Z})$$     A1

$$\left( {{\text{accept }}19(\bmod 20)} \right)$$

OR

$$x = 3 + 4t \Rightarrow 9 + 12t \equiv 2(\bmod 5)$$     M1A1

$$\Rightarrow 2t \equiv 3(\bmod 5)$$     A1

$$\Rightarrow 6t \equiv 9(\bmod 5)$$

$$\Rightarrow t \equiv 4(\bmod 5)$$     A1

so $$t = 4 + 5n{\text{ and }}x = 19 + 20n{\text{ }}(n \in \mathbb{Z})$$     M1A1

$$\left( {{\text{accept }}19(\bmod 20)} \right)$$

Note: Also accept solutions done by formula.

[6 marks]

b.

## Examiners report

Part (a) was generally well answered with a variety of methods seen in (a)(ii). This was set with Fermat’s Little Theorem in mind but in the event many candidates started off with many different powers of 5, eg $${5^4} \equiv 2,{\text{ }}{5^8} \equiv 4$$ and $${5^3}\equiv- 1(\bmod 7)$$ were all seen. A variety of methods was also seen in (b), ranging from use of the Chinese Remainder Theorem, finding tables of numbers congruent to $$3(\bmod 4)$$and $$4(\bmod 5)$$ and the use of an appropriate formula.

a.

Part (a) was generally well answered with a variety of methods seen in (a)(ii). This was set with Fermat’s Little Theorem in mind but in the event many candidates started off with many different powers of 5, eg $${5^4} \equiv 2,{\text{ }}{5^8} \equiv 4$$ and $${5^3}\equiv – 1(\bmod 7)$$ were all seen. A variety of methods was also seen in (b), ranging from use of the Chinese Remainder Theorem, finding tables of numbers congruent to $$3(\bmod 4)$$and $$4(\bmod 5)$$ and the use of an appropriate formula.

b.

## Question

(a)     Write down Fermat’s little theorem.

(b)     In base 5 the representation of a natural number X is $${\left( {k00013(5 – k)} \right)_5}$$.

This means that $$X = k \times {5^6} + 1 \times {5^2} + 3 \times 5 + (5 – k)$$.

In base 7 the representation of X is $${({a_n}{a_{n – 1}} \ldots {a_2}{a_1}{a_0})_7}$$.

Find $${a_0}$$.

(c)     Given that k = 2, find X in base 7.

## Markscheme

(a)     EITHER

if p is a prime $${a^p} \equiv a(\bmod p)$$     A1A1

OR

if p is a prime and $$a$$ $$0(\bmod p)$$ then $${a^{p – 1}} \equiv 1(\bmod p)$$     A1A1

Note: Award A1 for p being prime and A1 for the congruence.

[2 marks]

(b)     $${a_0} \equiv X(\bmod 7)$$     M1

$$X = k \times {5^6} + 25 + 15 + 5 – k$$

by Fermat $${5^6} \equiv 1(\bmod 7)$$     R1

$$X = k + 45 – k(\bmod 7)$$     (M1)

$$X = 3(\bmod 7)$$     A1

$${a_0} = 3$$     A1

[5 marks]

(c)     $$X = 2 \times {5^6} + 25 + 15 + 3 = 31\,293$$     A1

EITHER

$$X – {7^5} = 14\,486$$     (M1)

$$X – {7^5} – 6 \times {7^4} = 80$$

$$X – {7^5} – 6 \times {7^4} – {7^2} = 31$$

$$X – {7^5} – 6 \times {7^4} – {7^2} – 4 \times 7 = 3$$

$$X = {7^5} + 6 \times {7^4} + {7^2} + 4 \times 7 + 3$$     (A1)

$$X = {(160\,143)_7}$$     A1

OR

$$31\,293 = 7 \times 4470 + 3$$     (M1)

$$4470 = 7 \times 638 + 4$$

$$638 = 7 \times 91 + 1$$

$$91 = 7 \times 13 + 0$$

$$13 = 7 \times 1 + 6$$     (A1)

$$X = {(160\,143)_7}$$     A1

[4 marks]

Total [11 marks]

## Examiners report

Fermat’s little theorem was reasonably well known. Not all candidates took the hint to use this in the next part and this part was not done well. Part (c) could and was done even if part (b) was not.

## 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 $${a^{p – 1}} \equiv 1(\bmod p)$$.

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

[4]
a.

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

[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

$${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]

a.

$$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]

b.

(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]

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.

## Question

Use the result $$2003 = 6 \times 333 + 5$$ and Fermat’s little theorem to show that $${2^{2003}} \equiv 4(\bmod 7)$$ .

[3]
a.

Find $${2^{2003}}(\bmod 11)$$ and $${2^{2003}}(\bmod 13)$$.

[3]
b.

Use the Chinese remainder theorem, or otherwise, to evaluate $${2^{2003}}(\bmod 1001)$$, noting that $$1001 = 7 \times 11 \times 13$$.

[7]
c.

## Markscheme

$${2^{2003}} = {2^5} \times {({2^6})^{333}}$$     M1A1

$$\equiv 32 \times 1(\bmod 7)$$ by Fermat’s little theorem     A1

$$\equiv 4(\bmod 7)$$     AG

[3 marks]

a.

$$2003 = 3 + 10 \times 200$$     (M1)

$${2^{2003}} = {2^3} \times {({2^{10}})^{200}}\left( { \equiv 8 \times 1(\bmod 11)} \right) \equiv 8(\bmod 11)$$     A1

$${2^{2003}} = {2^{11}} \times {({2^{12}})^{166}} \equiv 7(\bmod 13)$$     A1

[3 marks]

b.

form $${M_1} = \frac{{1001}}{7} = 143;{\text{ }}{M_2} = \frac{{1001}}{{11}} = 91;{\text{ }}{M_3} = \frac{{1001}}{{13}} = 77$$     M1

solve $$143{x_1} \equiv 1(\bmod 7) \Rightarrow {x_1} = 5$$     M1A1

$${x_2} = 4;{\text{ }}{x_3} = 12$$     A1A1

$$x = 4 \times 143 \times 5 + 8 \times 91 \times 4 + 7 \times 77 \times 12 = 12240 \equiv 228(\bmod 1001)$$     M1A1

[7 marks]

c.

## Examiners report

Many candidates were able to complete part (a) and then went on to part (b). Some candidates raced through part (c). Others, who attempted part (c) using the alternative strategy of repeatedly solving linear congruencies, were sometimes successful.

a.

Many candidates were able to complete part (a) and then went on to part (b). Some candidates raced through part (c). Others, who attempted part (c) using the alternative strategy of repeatedly solving linear congruencies, were sometimes successful.

b.

Many candidates were able to complete part (a) and then went on to part (b). Some candidates raced through part (c). Others, who attempted part (c) using the alternative strategy of repeatedly solving linear congruencies, were sometimes successful.

c.

## Question

State Fermat’s little theorem.

## Markscheme

if p is a prime (and $$a \equiv 0(\bmod p)$$ with $$a \in \mathbb{Z}$$) then     A1

$${a^{p – 1}} \equiv 1(\bmod p)$$     A1

[2 marks]

Note: Accept $${a^p} \equiv a(\bmod p)$$ .

## Examiners report

Fermat’s little theorem was reasonably well known. Some candidates forgot to mention that p was a prime. Not all candidates took the hint to use this in the next part.

## Question

The positive integer p is an odd prime number.

Show that $$\sum\limits_{k = 1}^p {{k^p} \equiv 0(\bmod p)}$$.

[4]
a.

Given that $$\sum\limits_{k = 1}^p {{k^{p – 1}} \equiv n(\bmod p)}$$ where $$0 \leqslant n \leqslant p – 1$$, find the value of n.

[4]
b.

## Markscheme

using Fermat’s little theorem,

$${k^p} \equiv k(\bmod p)$$     (M1)

therefore,

$$\sum\limits_{k = 1}^p {{k^p} \equiv } \sum\limits_{k = 1}^p {k(\bmod p)}$$     M1

$$\equiv \frac{{p(p + 1)}}{2}(\bmod p)$$     A1

$$\equiv 0(\bmod p)$$     AG

since $$\frac{{(p + 1)}}{2}$$ is an integer (so that the right-hand side is a multiple of p)     R1

[4 marks]

a.

using the alternative form of Fermat’s little theorem,

$${k^{p – 1}} \equiv 1(\bmod p),{\text{ }}1 \leqslant k \leqslant p – 1$$     A1

$${k^{p – 1}} \equiv 0(\bmod p),{\text{ }}k = p$$     A1

therefore,

$$\sum\limits_{k = 1}^p {{k^{p – 1}} \equiv } \sum\limits_{k = 1}^{p – 1} {1{\text{ }}( + 0)(\bmod p)}$$     M1

$$\equiv p – 1(\bmod p)$$     A1

(so n = p − 1)

Note: Allow first A1 even if qualification on k is not given.

[4 marks]

b.

## Examiners report

Only the top candidates were able to produce logically, well thought-out proofs. Too many candidates struggled with the summation notation and were not able to apply Fermat’s little theorem. There was poor logic i.e. looking at a particular example and poor algebra.

a.

Only the top candidates were able to produce logically, well thought-out proofs. Too many candidates struggled with the summation notation and were not able to apply Fermat’s little theorem. There was poor logic i.e. looking at a particular example and poor algebra.

b.

## Question

Let $$f(n) = {n^5} – n,{\text{ }}n \in {\mathbb{Z}^ + }$$.

Find the values of $$f(3)$$, $$f(4)$$ and $$f(5)$$.

[2]
a.

Use the Euclidean algorithm to find

(i)     $$\gcd \left( {f(3),{\text{ }}f(4)} \right)$$;

(ii)     $$\gcd \left( {f(4),{\text{ }}f(5)} \right)$$.

[4]
b.

Explain why $$f(n)$$ is always exactly divisible by $$5$$.

[1]
c.

By factorizing $$f(n)$$ explain why it is always exactly divisible by $$6$$.

[4]
d.

Determine the values of $$n$$ for which $$f(n)$$ is exactly divisible by $$60$$.

[3]
e.

## Markscheme

$$240,{\rm{ }}1020,{\rm{ }}3120$$     A2

Note:     Award A2 for three correct answers, A1 for two correct answers.

[2 marks]

a.

(i)     $$1020 = 240 \times 4 + 60$$     (M1)

$$240 = 60 \times 4$$

$$\gcd (1020,{\text{ }}240) = 60$$     A1

(ii)     $$3120 = 1020 \times 3 + 60$$     (M1)

$$1020 = 60 \times 17$$

$$\gcd (1020,{\text{ }}3120) = 60$$     A1

Note:     Must be done by Euclid’s algorithm.

[4 marks]

b.

by Fermat’s little theorem with $$p = 5$$     R1

$${n^5} \equiv n(\bmod 5)$$

so 5 divides $$f(n)$$

[1 mark]

c.

$$f(n) = n({n^2} – 1)({n^2} + 1) = n(n – 1)(n + 1)({n^2} + 1)$$     (A1)A1

$$n – 1,{\text{ }}n,{\text{ }}n + 1$$ are consecutive integers and so contain a multiple of $$2$$ and $$3$$     R1R1

Note:     Award R1 for justification of $$2$$ and R1 for justification of $$3$$.

And therefore $$f(n)$$ is a multiple of $$6$$.     AG

[4 marks]

d.

from (c) and (d) $$f(n)$$ is always divisible by $$30$$     R1

considering the factorization, it is divisible by $$60$$ when $$n$$ is an odd number     A1

or when $$n$$ is a multiple of $$4$$     A1

Note:     Accept answers such as when $$n$$ is not congruent to $$2(\bmod 4)$$.

[3 marks]

Total [14 marks]

e.

## Examiners report

a.

Also well answered. A few candidates did not use the Euclidean algorithm to find the gcd as instructed.

b.

Many candidates essential said it was true because it was! There is only one mark which means one minute, so it must be a short answer which it is by using Fermat’s Little Theorem.

c.

Some good answers but too many did not factorize as instructed, so that they could then spot the consecutive numbers.

d.

Only the better candidates realised that they had to find another factor of $$2$$.

e.

## Question

Solve, by any method, the following system of linear congruences

$$x \equiv 9(\bmod 11)$$

$$x \equiv 1(\bmod 5)$$

[3]
a.

Find the remainder when $${41^{82}}$$ is divided by 11.

[4]
b.

Using your answers to parts (a) and (b) find the remainder when $${41^{82}}$$ is divided by $$55$$.

[3]
c.

## Markscheme

METHOD 1

listing $$9,{\rm{ }}20,{\rm{ }}31$$, $$\ldots$$ and $$1,{\rm{ }}6,11,16,{\rm{ }}21,{\rm{ }}26,{\rm{ }}31$$, $$\ldots$$     M1

one solution is $$31$$     (A1)

by the Chinese remainder theorem the full solution is

$$x \equiv 31(\bmod 55)$$     A1 N2

METHOD 2

$$x \equiv 9(\bmod 11) \Rightarrow x = 9 + 11t$$     M1

$$\Rightarrow 9 + 11t \equiv 1(\bmod 5)$$

$$\Rightarrow t \equiv 2(\bmod 5)$$     A1

$$\Rightarrow t = 2 + 5s$$

$$\Rightarrow x = 9 + 11(2 + 5s)$$

$$\Rightarrow x = 31 + 55s{\text{ }}\left( { \Rightarrow x \equiv 31(\bmod 55)} \right)$$     A1

Note:     Accept other methods eg formula, Diophantine equation.

Note:     Accept other equivalent answers e.g. $$– 79(\bmod 55)$$.

[3 marks]

a.

$${41^{82}} \equiv {8^{82}}(\bmod 11)$$

by Fermat’s little theorem $${8^{10}} \equiv 1(\bmod 11)\;\;\;\left( {{\text{or }}{{41}^{10}} \equiv 1(\bmod 11)} \right)$$     M1

$${8^{82}} \equiv {8^2}(\bmod 11)$$     M1

$$\equiv 9(\bmod 11)$$     (A1)

remainder is $$9$$     A1

Note:     Accept simplifications done without Fermat.

[4 marks]

b.

$${41^{82}} \equiv {1^{82}} \equiv 1(\bmod 5)$$     A1

so $${41^{82}}$$ has a remainder $$1$$ when divided by $$5$$ and a remainder $$9$$ when divided by $$11$$     R1

hence by part (a) the remainder is $$31$$     A1

[3 marks]

Total [10 marks]

c.

## Examiners report

A variety of methods were used here. The Chinese Remainder Theorem method (Method 2 on the mark-scheme) is probably the most instructive. Candidates who tried to do it by formula often (as usual) made mistakes and got it wrong. Marks were lost by just saying 31 and not giving mod (55).

a.

Time was lost here by not using Fermat’s Little Theorem as a starting point, although the ad hoc methods will work.

b.

Although it said use parts (a) and (b) not enough candidates saw the connection.

c.

## Question

Show that there are exactly two solutions to the equation $$1982 = 36a + 74b$$, with $$a,{\text{ }}b \in \mathbb{N}$$.

[8]
a.

Hence, or otherwise, find the remainder when $${1982^{1982}}$$ is divided by $$37$$.

[5]
b.

## Markscheme

$$74 = 2 \times 36 + 2$$ OR $$\gcd (36,{\text{ }}74) = 2$$     (A1)

$$2 = ( – 2)(36) + (1)(74)$$     M1

$$1982 = ( – 1982)(36) + (991)(74)$$     A1

so solutions are $$a = – 1982 + 37t$$ and $$b = 991 – 18t$$     M1A1

$$a,{\text{ }}b \in \mathbb{N}{\text{ so }}\frac{{1982}}{{37}} \le t \le \frac{{991}}{{18}}\;\;\;{\text{(}}15.56 \ldots \le t \le 55.055 \ldots )$$     (M1)(A1)

$$t$$ can take values $$54$$ or $$55$$ only     A1AG

(Or the solutions are $$(16,{\text{ }}19)$$ or $$(53,{\text{ }}1)$$)

Note:     Accept arguments from one solution of increasing/decreasing $$a$$ by $$37$$ and increasing/decreasing $$b$$ by $$18$$ to give the only possible positive solutions.

[8 marks]

a.

$$1982 = 53 \times 36 + 74$$

$$1982 = 55 \times 36 + 2$$     (M1)

$${1982^{36}} \equiv 1(\bmod 37){\text{ }}({\text{by FLT}})$$     (M1)

$${1982^{1982}} = {1982^{36 \times 55 + 2}} \equiv {1982^2}(\bmod 37)$$     (A1)

$$\equiv 34(\bmod 37)$$     A1

so the remainder is $$34$$     A1

Note:     $$1982$$ in the base can be replaced by $$21$$.

Note:     Award the first (M1) if the $$1982$$ in the experiment is correctly broken down to a smaller number.

[5 marks]

Total [13 marks]

b.

[N/A]

a.

[N/A]

b.

## Question

Consider the recurrence relation

$${u_n} = 5{u_{n – 1}} – 6{u_{n – 2}},{\text{ }}{u_0} = 0$$ and $${u_1} = 1$$.

Find an expression for $${u_n}$$ in terms of $$n$$.

[6]
a.

For every prime number $$p > 3$$, show that $$p|{u_{p – 1}}$$.

[4]
b.

## Markscheme

the auxiliary equation is $${\lambda ^2} – 5\lambda + 6 = 0$$     M1

$$\Rightarrow \lambda = 2,{\text{ }}3$$     (A1)

the general solution is $${u_n} = A \times {2^n} + B \times {3^n}$$     A1

imposing initial conditions (substituting $$n = 0,{\text{ }}1$$)     M1

$$A + B = 0$$ and $$2A + 3B = 1$$     A1

the solution is $$A = – 1,{\text{ }}B = 1$$

so that $${u_n} = {3^n} – {2^n}$$     A1

[6 marks]

a.

$${u_{p – 1}} = {3^{p – 1}} – {2^{p – 1}}$$

$$p > 3$$, therefore 3 or 2 are not divisible by $$p$$     R1

hence by FLT, $${3^{p – 1}} \equiv 1 \equiv {2^{p – 1}}(\bmod p)$$ for $$p > 3$$     M1A1

$${u_{p – 1}} \equiv 0(\bmod p)$$     A1

$$p|{u_{p – 1}}$$ for every prime number $$p > 3$$     AG

[4 marks]

b.

[N/A]

a.

[N/A]

b.

## Question

Consider the linear congruence $$ax \equiv b\left( {{\text{mod}}\,p} \right)$$ where $$a,\,b,\,p,\,x \in {\mathbb{Z}^ + }$$, $$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 $$x \equiv {a^{p – 2}}b\left( {{\text{mod}}\,p} \right)$$.

[3]
b.i.

Hence solve the linear congruence $$5x \equiv 7\left( {{\text{mod}}\,13} \right)$$.

[3]
b.ii.

## Markscheme

EITHER

if $$p$$ is prime (and $$a$$ is any integer) then $${a^p} \equiv a\left( {{\text{mod}}\,p} \right)$$    A1A1

Note: Award A1 for $$p$$ prime and A1 for the congruence or for stating that $$p\left| {{a^p} – a} \right.$$.

OR

A1A1

Note: Award A1 for $$p$$ prime and A1 for the congruence or for stating that $$p\left| {{a^{p – 1}} – 1} \right.$$.

Note: Condone use of equals sign provided $$\left( {{\text{mod}}\,p} \right)$$ is seen.

[2 marks]

a.

multiplying both sides of the linear congruence by $${a^{p – 2}}$$     (M1)

$${a^{p – 1}}x \equiv {a^{p – 2}}b\left( {{\text{mod}}\,p} \right)$$      A1

as $${a^{p – 1}} \equiv 1\left( {{\text{mod}}\,p} \right)$$     R1

$$x \equiv {a^{p – 2}}b\left( {{\text{mod}}\,p} \right)$$     AG

[3 marks]

b.i.

$$x \equiv {5^{11}} \times 7\left( {{\text{mod}}\,13} \right)$$     (M1)

$$\equiv 341796875\left( {{\text{mod}}\,13} \right)$$     (A1)

Note: Accept equivalent calculation eg, using $${5^2} \equiv – 1\,{\text{mod}}\,13$$.

$$\equiv 4\left( {{\text{mod}}\,13} \right)$$     A1

[3 marks]

b.ii.

[N/A]

a.

[N/A]

b.i.

[N/A]

b.ii.

## Question

One version of Fermat’s little theorem states that, under certain conditions, $${a^{p – 1}} \equiv 1(\bmod p)$$ .

(i)     Show that this result is not true when a = 2, p = 9 and state which of the conditions is not satisfied.

(ii)     Find the smallest positive value of k satisfying the congruence $${2^{45}} \equiv k(\bmod 9)$$ .

[6]
a.

Find all the integers between 100 and 200 satisfying the simultaneous congruences $$3x \equiv 4(\bmod 5)$$ and $$5x \equiv 6(\bmod 7)$$ .

[6]
b.

## Markscheme

(i)     $${2^8} = 256 \equiv 4(\bmod 9)$$ (so not true)     A1

9 is not prime     A1

(ii)     consider various powers of 2, e.g. obtaining     M1

$${2^6} = 64 \equiv 1(\bmod 9)$$     A1

therefore

$${2^{45}} = {({2^6})^7} \times {2^3}$$     M1

$$\equiv 8(\bmod 9){\text{ (so }}k = 8)$$     A1

[6 marks]

a.

EITHER

the solutions to $$3x \equiv 4(\bmod 5)$$ are 3, 8, 13, 18, 23,…     M1A1

the solutions to $$5x \equiv 6(\bmod 7)$$ are 4, 11, 18,…     A1

18 is therefore the smallest solution     A1

the general solution is

$$18 + 35n{\text{ , }}n \in \mathbb{Z}$$     M1

the required solutions are therefore 123, 158, 193     A1

OR

$$3x \equiv 4(\bmod 5) \Rightarrow 2 \times 3x \equiv 2 \times 4(\bmod 5) \Rightarrow x \equiv 3(\bmod 5)$$     A1

$$\Rightarrow x = 3 + 5t$$     M1

$$\Rightarrow 15 + 25t \equiv 6(\bmod 7) \Rightarrow 4t \equiv 5(\bmod 7) \Rightarrow 2 \times 4t \equiv 2 \times 5(\bmod 7) \Rightarrow t \equiv 3(\bmod 7)$$     A1

$$\Rightarrow t = 3 + 7n$$     A1

$$\Rightarrow x = 3 + 5(3 + 7n) = 18 + 35n$$     M1

the required solutions are therefore 123, 158, 193     A1

OR

using the Chinese remainder theorem formula method

first convert the congruences to $$x \equiv 3(\bmod 5)$$ and $$x \equiv 4(\bmod 7)$$     A1A1

$$M = 35{\text{, }}{M_1} = 7{\text{, }}{M_2} = 5{\text{, }}{m_1} = 5,{\text{ }}{m_2} = 7,{\text{ }}{a_1} = 3,{\text{ }}{a_2} = 4$$

$${x_1}$$ is the solution of $${M_2}{x_2} \equiv 1(\bmod {m_1})$$ , i.e. $$7{x_1} \equiv 1(\bmod 5)$$ so $${x_1} = 3$$

$${x_2}$$ is the solution of $${M_2}{x_2} \equiv 1(\bmod {m_2})$$ , i.e. $$5{x_2} \equiv 1(\bmod 7)$$ so $${x_2} = 3$$

a solution is therefore

$$x = {a_1}{M_1}{x_1} + {a_2}{M_2}{x_2}$$     M1

$$= 3 \times 7 \times 3 + 4 \times 5 \times 3 = 123$$     A1

the general solution is $$123 + 35n$$ , $$n \in \mathbb{Z}$$     M1

the required solutions are therefore 123, 158, 193     A1

[6 marks]

b.

[N/A]

a.

[N/A]

b.