# IB DP Maths Topic 10.4 Modular arithmetic HL Paper 3

## Question

Define what is meant by the statement $$x \equiv y(\bmod n){\text{ where }}x{\text{, }}y{\text{, }}n \in {\mathbb{Z}^ + }$$ .

[1]
a.

Hence prove that if $$x \equiv y(\bmod n)$$ then $${x^2} \equiv {y^2}(\bmod n)$$ .

[4]
b.

Determine whether or not $${x^2} \equiv {y^2}(\bmod n)$$ implies that $$x \equiv y(\bmod n)$$ .

[4]
c.

## Markscheme

$$x \equiv y(\bmod n) \Rightarrow x = y + kn,{\text{ }}(k \in \mathbb{Z})$$     A1

[1 mark]

a.

$$x \equiv y(\bmod n)$$

$$\Rightarrow x = y + kn$$     M1

$${x^2} = {y^2} + 2kny + {k^2}{n^2}$$     A1

$$\Rightarrow {x^2} = {y^2} + (2ky + {k^2}n)n$$     M1A1

$$\Rightarrow {x^2} \equiv {y^2}(\bmod n)$$     AG

[4 marks]

b.

EITHER

$${x^2} \equiv {y^2}(\bmod n)$$

$$\Rightarrow {x^2} – {y^2} = 0(\bmod n)$$     M1

$$\Rightarrow (x – y)(x + y) = 0(\bmod n)$$     A1

This will be the case if

$$x + y = 0(\bmod n){\text{ or }}x = – y(\bmod n)$$     R1

so $$x \ne y(\bmod n)$$ in general     R1

[4 marks]

OR

Any counter example, e.g. $$n = 5,{\text{ }}x = 3,{\text{ }}y = 2,$$ in which case     R2

$${x^2} \equiv {y^2}(\bmod n)$$ but $$x \ne y(\bmod n)$$. (false)     R1R1

[4 marks]

c.

## Examiners report

While most candidates gave a correct meaning to $$x \equiv y(\bmod n)$$ , there were some incorrect statements, the most common being $$x \equiv y(\bmod n)$$ means that when x is divided by n, there is a remainder y. The true statement $$8 \equiv 5(\bmod 3)$$ shows that this statement is incorrect. Part (b) was solved successfully by many candidates but (c) caused problems for some candidates who thought that the result in (c) followed automatically from the result in (b).

a.

While most candidates gave a correct meaning to $$x \equiv y(\bmod n)$$ , there were some incorrect statements, the most common being $$x \equiv y(\bmod n)$$ means that when x is divided by n, there is a remainder y. The true statement $$8 \equiv 5(\bmod 3)$$ shows that this statement is incorrect. Part (b) was solved successfully by many candidates but (c) caused problems for some candidates who thought that the result in (c) followed automatically from the result in (b).

b.

While most candidates gave a correct meaning to $$x \equiv y(\bmod n)$$ , there were some incorrect statements, the most common being $$x \equiv y(\bmod n)$$ means that when x is divided by n, there is a remainder y. The true statement $$8 \equiv 5(\bmod 3)$$ shows that this statement is incorrect. Part (b) was solved successfully by many candidates but (c) caused problems for some candidates who thought that the result in (c) followed automatically from the result in (b).

c.

## Question

Given that $$a,{\text{ }}b,{\text{ }}c,{\text{ }}d \in \mathbb{Z}$$, show that

$(a – b)(a – c)(a – d)(b – c)(b – d)(c – d) \equiv 0(\bmod 3).$

## Markscheme

EITHER

we work modulo 3 throughout

the values of a, b, c, d can only be 0, 1, 2     R2

since there are 4 variables but only 3 possible values, at least 2 of the variables must be equal $$(\bmod 3)$$     R2

therefore at least 1 of the differences must be $$0(\bmod 3)$$     R2

the product is therefore $$0(\bmod 3)$$     R1AG

OR

we attempt to find values for the differences which do not give $$0(\bmod 3)$$ for the product

we work modulo 3 throughout

we note first that none of the differences can be zero     R1

ab can therefore only be 1 or 2     R1

suppose it is 1, then bc can only be 1

since if it is 2, $$(a – b) + (b – c) \equiv 3 \equiv 0(\bmod 3)$$     R1

cd cannot now be 1 because if it is

$$(a – b) + (b – c) + (c – d) = a – d \equiv 3 \equiv 0(\bmod 3)$$     R1

cd cannot now be 2 because if it is

$$(b – c) + (c – d) = b – d \equiv 3 \equiv 0(\bmod 3)$$     R1

we cannot therefore find values of c and d to give the required result     R1

a similar argument holds if we suppose ab is 2, in which case bc must be 2 and we cannot find a value of cd     R1

the product is therefore $$0(\bmod 3)$$     AG

[7 marks]

## Examiners report

Most candidates who solved this question used the argument that there are four variables which can take only one of three different values modulo 3 so that at least two must be equivalent modulo 3 which leads to the required result. This apparently simple result, however, requires a fair amount of insight and few candidates managed it.

## Question

Use the Euclidean algorithm to find the greatest common divisor of the numbers 56 and 315.

[4]
a.

(i)     Find the general solution to the diophantine equation $$56x + 315y = 21$$.

(ii)     Hence or otherwise find the smallest positive solution to the congruence $$315x \equiv 21$$ (modulo 56) .

[9]
b.

## Markscheme

$$315 = 5 \times 56 + 35$$     M1

$$56 = 1 \times 35 + 21$$

$$35 = 1 \times 21 + 14$$     A1

$$21 = 1 \times 14 + 7$$

$$14 = 2 \times 7$$     A1

therefore gcd = 7     A1

[4 marks]

a.

(i)     $$7 = 21 – 14$$     M1

$$= 21 – (35 – 21)$$

$$= 2 \times 21 – 35$$     (A1)

$$= 2 \times (56 – 35) – 35$$

$$= 2 \times 56 – 3 \times 35$$     (A1)

$$= 2 \times 56 – 3 \times (315 – 5 \times 56)$$

$$= 17 \times 56 – 3 \times 315$$     (A1)

therefore $$56 \times 51 + 315 \times (- 9) = 21$$     M1

$$x = 51,{\text{ }}y = – 9$$ is a solution     (A1)

the general solution is $$x = 51 + 45N$$ , $$y = – 9 – 8N$$ , $$N \in \mathbb{Z}$$     A1A1

(ii)     putting N = –2 gives y = 7 which is the required value of x     A1

[9 marks]

b.

## Examiners report

This question was generally well answered although some candidates were unable to proceed from a particular solution of the Diophantine equation to the general solution.

a.

This question was generally well answered although some candidates were unable to proceed from a particular solution of the Diophantine equation to the general solution.

b.

## Question

Given that a , $$b \in \mathbb{N}$$ and $$c \in {\mathbb{Z}^ + }$$, show that if $$a \equiv 1(\bmod c)$$ , then $$ab \equiv b(\bmod c)$$ .

[2]
a.

Using mathematical induction, show that $${9^n} \equiv 1(\bmod 4)$$ , for $$n \in \mathbb{N}$$ .

[6]
b.

The positive integer M is expressed in base 9. Show that M is divisible by 4 if the sum of its digits is divisible by 4.

[4]
c.

## Markscheme

$$a = \lambda c + 1$$     M1

so $$ab = \lambda bc + b \Rightarrow ab \equiv b(\bmod c)$$     A1AG

[2 marks]

a.

the result is true for n = 0 since $${9^0} = 1 \equiv 1(\bmod 4)$$     A1

assume the result is true for n = k , i.e. $${9^k} \equiv 1(\bmod 4)$$     M1

consider $${9^{k + 1}} = 9 \times {9^k}$$     M1

$$\equiv 9 \times 1(\bmod 4)$$ or $$1 \times {9^k}(\bmod 4)$$     A1

$$\equiv 1(\bmod 4)$$     A1

so true for $$n = k \Rightarrow$$ true for n = k + 1 and since true for n = 0 result follows by induction     R1

Note: Do not award the final R1 unless both M1 marks have been awarded.

Note: Award the final R1 if candidates state n = 1 rather than n = 0

[6 marks]

b.

let $$M = {({a_n}{a_{n – 1}}…{a_0})_9}$$     (M1)

$$= {a_n} \times {9^n} + {a_{n – 1}} \times {9^{n – 1}} + … + {a_0} \times {9^0}$$     A1

EITHER

$$\equiv {a_n}(\bmod 4) + {a_{n – 1}}(\bmod 4) + … + {a_0}(\bmod 4)$$     A1

$$\equiv \sum {{a_i}(\bmod 4)}$$     A1

so M is divisible by 4 if $$\sum {{a_i}}$$ is divisible by 4     AG

OR

$$= {a_n}({9^n} – 1) + {a_{n – 1}}({9^{n – 1}} – 1) + … + {a_1}({9^1} – 1)$$

$$+ {a_n} + {a_{n – 1}} + … + {a_1} + {a_0}$$     A1

Since $${9^n} \equiv 1(\bmod 4)$$ , it follows that $${9^n} – 1$$ is divisible by 4,     R1

so M is divisible by 4 if $$\sum {{a_i}}$$ is divisible by 4     AG

[4 marks]

c.

## Examiners report

Part (a) was generally well answered. In (b), many candidates tested the result for n = 1 instead of n = 0. It has been suggested that the reason for this was a misunderstanding of the symbol N with some candidates believing it to denote the positive integers. It is important for candidates to be familiar with IB notation in which N denotes the positive integers and zero. In some scripts the presentation of the proof by induction was poor.

a.

Part (a) was generally well answered. In (b), many candidates tested the result for n = 1 instead of n = 0. It has been suggested that the reason for this was a misunderstanding of the symbol N with some candidates believing it to denote the positive integers. It is important for candidates to be familiar with IB notation in which N denotes the positive integers and zero. In some scripts the presentation of the proof by induction was poor.

b.

Part (a) was generally well answered. In (b), many candidates tested the result for n = 1 instead of n = 0. It has been suggested that the reason for this was a misunderstanding of the symbol N with some candidates believing it to denote the positive integers. It is important for candidates to be familiar with IB notation in which N denotes the positive integers and zero. In some scripts the presentation of the proof by induction was poor.

c.

## Question

Anna is playing with some cars and divides them into three sets of equal size. However, when she tries to divide them into five sets of equal size, there are four left over. Given that she has fewer than 50 cars, what are the possible numbers of cars she can have?

## Markscheme

METHOD 1

let x be the number of cars

we know $$x \equiv 0(\bmod 3)$$     (A1)

also $$x \equiv 4(\bmod 5)$$     (A1)

so $$x = 3t \Rightarrow 3t \equiv 4(\bmod 5)$$     M1

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

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

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

$$\Rightarrow x = 9 + 15s$$     A1

since there must be fewer than 50 cars, x = 9, 24, 39     A1A1A1

Note: Only award two of the final three A1 marks if more than three solutions are given.

[7 marks]

METHOD 2

x is a multiple of 3 that ends in 4 or 9     R4

therefore x = 9, 24, 39     A1A1A1     N3

Note: Only award two of the final three A1 marks if more than three solutions are given.

[7 marks]

## Examiners report

There were a number of totally correct solutions to this question, but some students were unable to fully justify their results.

## Question

Use the Euclidean algorithm to express gcd (123, 2347) in the form 123p + 2347q, where $$p,{\text{ }}q \in \mathbb{Z}$$.

[8]
a.

Find the least positive solution of $$123x \equiv 1(\bmod 2347)$$ .

[3]
b.

Find the general solution of $$123z \equiv 5(\bmod 2347)$$ .

[3]
c.

State the solution set of $$123y \equiv 1(\bmod 2346)$$ .

[1]
d.

## Markscheme

$$2347 = 19 \times 123 + 10$$     M1A1

$$(123 = 12 \times 10 + 3)$$

$$10 = 3 \times 3 + 1$$     A1

$$1(\gcd ) = 10 – 3 \times 3 = 10 – 3 \times (123 – 12 \times 10)$$     M1A1

$$= 37 \times 10 – 3 \times 123$$     A1

$$= 37 \times (2347 – 19 \times 123) – 3 \times 123$$ (for continuation)     M1

$$= 37 \times 2347 – 706 \times 123$$     A1

[8 marks]

a.

EITHER

$$1(\bmod 2347) = ( – 706 \times 123)(\bmod 2347)$$     M1A1

OR

$$x = – 706 + 2347n$$     M1A1

solution: 1641     A1

[3 marks]

b.

$$5(\bmod 2347) = ( – 3530 \times 123)(\bmod 2347)$$     (M1)

$${\text{GS}}:z = – 3530 + k2347$$     A1A1

Note: Other common possibilities include $$1164 + k2347$$ and $$8205 + k2347$$ .

[3 marks]

c.

empty set (123 and 2346 both divisible by 3)     A1

[1 mark]

d.

## Examiners report

The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.

a.

The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.

b.

The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.

c.

The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.

d.

## 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

Let the greatest common divisor of 861 and 957 be h .

Using the Euclidean algorithm, find h .

[4]
a.

Hence find integers A and B such that 861+ 957B = h .

[3]
b.

Using part (b), solve $$287w \equiv 2(\bmod 319$$) , where $$w \in \mathbb{N},{\text{ }}w < 319$$ .

[5]
c.

Find the general solution to the diophantine equation $$861x + 957y = 6$$ .

[6]
d.

## Markscheme

METHOD 1

by the above working on the left (or similar)     M1A1A1

Note: Award A1 for 96 and A1 for 93.

h = 3 (since 3 divides 93)     A1

[4 marks]

METHOD 2

$$957 = 861 + 96$$     M1A1

$$861 = 8 \times 96 + 93$$     A1

$$96 = 93 + 3$$

so h = 3 (since 3 divides 93)     A1

[4 marks]

a.

METHOD 1

if method 1 was used for part (a)

by the above working on the right (or equivalent)     M1

$$– 10 \times 861 + 9 \times 957 = 3$$

so A = –10 and B = 9     A1A1

[3 marks]

METHOD 2

$$3 = 96 – 93$$

$$= 96 – (861 – 8 \times 96) = 9 \times 96 – 861$$     M1

$$= 9 \times (957 – 861) – 861$$

$$= – 10 \times 861 + 9 \times 957$$

so A = –10 and B = 9     A1A1

[3 marks]

b.

from (b) $$– 10 \times 287 + 9 \times 319 = 1$$ so     A1

$$– 10 \times 287 \equiv 1(\bmod 319)$$     A1

$$287w \equiv 2(\bmod 319) \Rightarrow – 10 \times 287w \equiv – 10 \times 2(\bmod 319)$$     M1

$$\Rightarrow w \equiv – 20(\bmod 319)$$     A1

so $$w = 299$$     A1

[5 marks]

c.

from (b) $$– 10 \times 861 + 9 \times 957 = 3 \Rightarrow – 20 \times 861 + 18 \times 957 = 6$$     M1A1

so general solution is $$x = – 20 + 319t$$     A1A1

$$y = 18 – 287t\,\,\,\,\,(t \in \mathbb{Z})$$     A1A1

[6 marks]

d.

## Examiners report

The Euclidean algorithm was well applied. If it is done in the format shown in the mark scheme then the keeping track method of the linear combinations of the 2 original numbers makes part (b) easier.

a.

Again well answered but not quite as good as (a).

b.

Surprisingly, since it is basic bookwork, this part was answered very badly indeed. Most candidates did not realise that $$– 10$$ was the number to multiply by. Sadly, of the candidates that did do it, some did not read the question carefully enough to see that a positive integer answer was required.

c.

Again this is standard bookwork. It was answered better than part (c). There were the usual mistakes in the final answer e.g. not having the two numbers, with the parameter, co-prime.

d.

## Question

Show that $$30$$ is a factor of $${n^5} – n$$ for all $$n \in \mathbb{N}$$.

[5]
a.

(i)     Show that $${3^{{3^m}}} \equiv 3({\text{mod}}4)$$ for all $$m \in \mathbb{N}$$.

(ii)     Hence show that there is exactly one pair $$(m,{\text{ }}n)$$ where $$m,{\text{ }}n \in \mathbb{N}$$, satisfying the equation $${3^{{3^m}}} = {2^{{2^n}}} + {5^2}$$.

[8]
b.

## Markscheme

METHOD 1

$${n^5} – n = \underbrace {n(n – 1)(n + 1)}_{{\text{3 consecutive integers}}}({n^2} + 1) \equiv 0({\text{mod}}6)$$     M1

at least a factor is multiple of 3 and at least a factor is multiple of 2     R1

$${n^5} – n = n({n^4} – 1) \equiv 0({\text{mod}}5)$$ as $${n^4} \equiv 1({\text{mod}}5)$$ by FLT     R1

therefore, as $${\text{(5, 6)}} = 1$$,     R1

$${n^5} – n \equiv 0\left( {\bmod \underbrace {5 \times 6}_{30}} \right)$$     A1

ie 30 is a factor of $${n^5} – n$$     AG

METHOD 2

let $${\text{P}}(n)$$ be the proposition: $${n^5} – n = 30\alpha$$ for some $$\alpha \in \mathbb{Z}$$

$${0^5} – 0 = 30 \times 0$$, so $${\text{P}}(0)$$ is true     A1

assume $${\text{P}}(k)$$ is true for some $$k$$ and consider $${\text{P}}(k + 1)$$

$${(k + 1)^5} – (k + 1) = {k^5} + 5{k^4} + 10{k^3} + 10{k^2} + 5k + 1 – k – 1$$     M1

$$= ({k^5} – k) + 5k\left( {\underbrace {{k^3} + 3{k^2} + 3k + 1}_{{{(k + 1)}^3}} – ({k^2} + k)} \right)$$

$$= ({k^5} – k) + 5k\left( {{{(k + 1)}^3} – k(k + 1)} \right)$$

$$= 30\alpha + \underbrace {5k(k + 1)\left( {\underbrace {{k^2} + k + 1}_{k(k + 1) + 1}} \right)}_{{\text{multiple of 6}}}$$     M1

$$= 30\alpha + 30\beta$$     A1

as $${\text{P}}(0)$$ is true and $${\text{P}}(k)$$ true implies $${\text{P}}(k + 1)$$ true, by PMI $${\text{P}}(n)$$ is true for all values $$n \in \mathbb{N}$$     R1

Note: Award the first M1 only if the correct induction procedure is followed and the correct first line is seen.

Note: Award R1 only if both M marks have been awarded.

METHOD 3

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

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

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

$$= (n – 2)(n – 1)n(n + 1)(n + 2) + 5(n – 1)n(n + 1)$$     A1

each term is multiple of 2, 3 and 5     R1

therefore is divisible by 30     AG

[5 marks]

a.

(i)     METHOD 1

case 1: $$m = 0$$ and $${3^{{3^0}}} \equiv 3{\text{mod}}4$$ is true     A1

case 2: $$m > 0$$

let $$N = {3^m} \geqslant 3$$ and consider the binomial expansion     M1

$${3^N} = {(1 + 2)^N} = \sum\limits_{k = 0}^N {}$$ $$\left( \begin{array}{c}N\\k\end{array} \right){2^k} = 1 + 2N + \underbrace {\sum\limits_{k = 2}^N {\left( \begin{array}{c}N\\k\end{array} \right){2^k}} }_{ \equiv ({\text{mod}}4)} \equiv 1 + 2N({\text{mod}}4)$$     A1

as $$\underbrace {{3^m}}_N \equiv {( – 1)^m}({\text{mod}}4) \Rightarrow 1 + 2N \equiv 1 + 2{( – 1)^m}({\text{mod}}4)$$     R1

therefore $$\underbrace {{3^{{3^m}}}}_{{3^N}} \equiv 1 + 2{( – 1)^m}({\text{mod}}4) \Rightarrow$$ $$\left\{ \begin{array}{l}\underbrace {{3^{{3^m}}}}_{{3^N}} \equiv \underbrace {1 + 2}_3({\text{mod}}4){\rm{for\,}} m {\rm{\,even}}\\\underbrace {{3^{{3^m}}}}_{{3^N}} \equiv \underbrace {1 – 2}_{ – 1 \equiv 3({\text{mod}}4)}({\text{mod}}4){\rm{for\,}} m {\rm{\,odd}}\end{array} \right.$$     R1

which proves that $${3^{{3^m}}} \equiv 3({\text{mod}}4)$$ for any $$m \in \mathbb{N}$$     AG

METHOD 2

let $${\text{P}}(n)$$ be the proposition: $${3^{{3^n}}} – 3 \equiv 0({\text{mod }}4,{\text{ or }}24)$$

$${3^{{3^0}}} – 3 = 3 – 3 \equiv 0({\text{mod }}4{\text{ or }}24)$$, so $${\text{P}}(0)$$ is true     A1

assume $${\text{P}}(k)$$ is true for some $$k$$     M1

consider $${3^{{3^{^{k + 1}}}}} – 3 = {3^{{3^k} \times 3}} – 3$$     M1

$$= {(3 + 24r)^3} – 3$$

$$\equiv 27 + 24t – 3$$     R1

$$\equiv 0({\text{mod }}4{\text{ or }}24)$$

as $${\text{P}}(0)$$ is true and $${\text{P}}(k)$$ true implies $${\text{P}}(k + 1)$$ true, by PMI $${\text{P}}(n)$$ is true for all values $$n \in \mathbb{N}$$     R1

METHOD 3

$${3^{{3^m}}} – 3 = 3({3^{{3^m} – 1}} – 1)$$     M1A1

$$= 3({3^{2k}} – 1)$$     R1

$$= 3({9^k} – 1)$$

$$= 3\underbrace {\left( {{{(8 + 1)}^k} – 1} \right)}_{{\text{multiple of 8}}}$$     R1

$$\equiv 0({\text{mod}}24)$$     A1

which proves that $${3^{{3^m}}} \equiv 3({\text{mod}}4)$$ for any $$m \in \mathbb{N}$$     AG

(ii)     for $$m \in \mathbb{N},{\text{ }}{3^{{3^m}}} \equiv 3({\text{mod}}4)$$ and, as $${2^{{2^n}}} \equiv 0({\text{mod}}4)$$ and $${5^2} \equiv 1({\text{mod}}4)$$ then $${2^{{2^n}}} + {5^2} \equiv 1({\text{mod}}4)$$ for $$n \in {\mathbb{Z}^ + }$$

there is no solution to $${3^{{3^m}}} = {2^{{2^n}}} + {5^2}$$ for pairs $$(m,{\text{ }}n) \in \mathbb{N} \times {\mathbb{Z}^ + }$$     R1

when $$n = 0$$, we have $${3^{{3^m}}} = {2^{{2^0}}} + {5^2} \Rightarrow {3^{{3^m}}} = 27 \Rightarrow m = 1$$     M1

therefore $$(m,{\text{ }}n) = (1,{\text{ }}0)$$     A1

is the only pair of non-negative integers that satisfies the equation     AG

[8 marks]

b.

## Examiners report

Many students were able to get partial credit for part (a), although few managed to gain full marks.

a.

There seemed to be very few good attempts at part (b), many failing at the outset to understand what was meant by $${3^{{3^m}}}$$.

b.

## Question

Consider the integers $$a = 871$$ and $$b= 1157$$, given in base $$10$$.

(i)     Express $$a$$ and $$b$$ in base $$13$$.

(ii)     Hence show that $${\text{gcd}}(a,{\text{ }}b) = 13$$.

[7]
a.

A list $$L$$ contains $$n+ 1$$ distinct positive integers. Prove that at least two members of $$L$$leave the same remainder on division by $$n$$.

[4]
b.

Consider the simultaneous equations

$$4x + y + 5z = a$$

$$2x + z = b$$

$$3x + 2y + 4z = c$$

where $$x,{\text{ }}y,{\text{ }}z \in \mathbb{Z}$$.

(i)     Show that 7 divides $$2a + b – c$$.

(ii)     Given that a = 3, b = 0 and c = −1, find the solution to the system of equations modulo 2.

[6]
c.

Consider the set $$P$$ of numbers of the form $${n^2} – n + 41,{\text{ }}n \in \mathbb{N}$$.

(i)     Prove that all elements of P are odd.

(ii)     List the first six elements of P for n = 0, 1, 2, 3, 4, 5.

(iii)     Show that not all elements of P are prime.

[6]
d.

## Markscheme

(i)     METHOD 1

using a relevant list of powers of 13: (1), 13, 169, (2197)     M1

$$871 = 5 \times {13^2} + 2 \times 13$$     A1

$$871 = {520_{13}}$$     A1

$$1157 = 6 \times {13^2} + 11 \times 13$$     A1

$$1157 = 6{\text{B}}{{\text{0}}_{13}}$$     A1

METHOD 2

attempted repeated division by 13     M1

$$871 \div 13 = 67;{\text{ }}67 \div 13 = 5{\text{rem}}2$$     A1

$$871 = {520_{13}}$$     A1

$$1157 \div 13 = 89;{\text{ }}89 \div 13 = 6{\text{rem11}}$$     A1

$$1157 = 6{\text{B}}{{\text{0}}_{13}}$$     A1

Note:     Allow (11) for B only if brackets or equivalent are present.

(ii)     $$871 = 13 \times 67;{\text{ }}1157 = 13 \times 89$$     (M1)

67 and 89 are primes (base 10) or they are co-prime     A1

So $$\gcd (871,{\text{ }}1157) = 13$$     AG

Note:     Must be done by hence not Euclid’s algorithm on 871 and 1157.

[7 marks]

a.

let K be the set of possible remainders on division by n     (M1)

then $$K = \{ {\text{0, 1, 2, }} \ldots n – 1\}$$ has n members     A1

because $$n < n + 1{\text{ }}\left( { = n(L)} \right)$$     A1

by the pigeon-hole principle (appearing anywhere and not necessarily mentioned by name as long as is explained)     R1

at least two members of L correspond to one member of K     AG

[4 marks]

b.

(i)     form the appropriate linear combination of the equations:     (M1)

$$2a + b – c = 7x + 7z$$     A1

$$= 7(x + z)$$     R1

so 7 divides $$2a + b – c$$     AG

(ii)     modulo 2, the equations become     M1

$$y + z = 1$$

$$z = 0$$     A1

$$x = 1$$

solution: (1, 1, 0)     A1

Note:     Award full mark to use of GDC (or done manually) to solve the system giving $$x = – 1,{\text{ }}y = – 3,{\text{ }}z = 2$$ and then converting mod 2.

[6 marks]

c.

(i)     separate consideration of even and odd n     M1

$${\text{eve}}{{\text{n}}^2} – {\text{even}} + {\text{odd is odd}}$$     A1

$${\text{od}}{{\text{d}}^2} – {\text{odd}} + {\text{odd is odd}}$$     A1

all elements of P are odd     AG

Note:     Allow other methods eg, $${n^2} – n = n(n – 1)$$ which must be even.

(ii)     the list is [41, 41, 43, 47, 53, 61]     A1

(iii)     $${41^2} – 41 + 41 = {41^2}$$ divisible by 41     A1

but is not a prime     R1

the statement is disproved (by counterexample)  AG

[6 marks]

d.

[N/A]

a.

[N/A]

b.

[N/A]

c.

[N/A]

d.

## 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

Given a sequence of non negative integers $$\{ {a_r}\}$$ show that

(i)     $$\sum\limits_{r = 0}^n {{a_r}{{(x + 1)}^r}(\bmod x) = \sum\limits_{r = 0}^n {{a_r}(\bmod x)} }$$ where $$x \in \{ 2,{\text{ }}3,{\text{ }}4 \ldots \}$$.

(ii)     $$\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}} }$$.

[5]
a.

Hence determine whether the base $$3$$ number $$22010112200201$$ is divisible by $$8$$.

[5]
b.

## Markscheme

(i)     $$(x + 1)(\bmod x) \equiv 1(\bmod x)$$     (M1)

$${(x + 1)^r}(\bmod x)\left( { \equiv {1^r}(\bmod x)} \right) = 1(\bmod x)$$     A1

$$\sum\limits_{r – 0}^n {{a_r}{{(x + 1)}^r}(\bmod x) \equiv \sum\limits_{r = 0}^n {{a_r}(\bmod x)} }$$     AG

(ii)     METHOD 1

$$\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = \sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){3^{2r}}} }$$     M1

$$= \sum\limits_{r = 0}^n {({3^{2r + 1}}{a_{2r + 1}} + {3^{2r}}{a_{2r}})}$$     M1A1

$$= \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}}$$     AG

METHOD 2

$$\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = 3{a_1} + {a_0} + 9(3{a_3} + {a_2}) + \ldots + {9^n}(3{a_{2n + 1}} + {a_{2n}})}$$     A1

$$= {a_0} + 3{a_1} + {3^2}{a_2} + {3^3}{a_3} + \ldots + {3^{2n + 1}}{a_{2n + 1}}$$     M1A1

$$= \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}}$$     AG

[5 marks]

a.

METHOD 1

using part (a) (ii) to separate the number into pairs of digits     (M1)

$$22010112200201{\text{ }}({\text{base }}3) \equiv 8115621{\text{ }}({\text{base }}9)$$     A1

using the sum of digits identity from part (a) (i)     (M1)

Note:     Award M1 if result from a(i) is used to show that the number is divisible by $$2$$, even if no other valid working given.

$${\text{sum}} = 24$$     A1

which is divisible by $$8$$     A1

hence $$22010112200201$$ (base $$3$$) is divisible by $$8$$

METHOD 2

$$\sum\limits_{r = 0}^{13} {{a_r}{3^r}\sum\limits_{r = 0}^6 {(3{a_{2r + 1}} + {a_{2r}}){9^r}} }$$     (M1)

$$\equiv \sum\limits_{r = 0}^6 {(3{a_{2r + 1}} + {a_{2r}})(\bmod 8)}$$     A1

$$= {a_0} + 3{a_1} + {a_2} + 3{a_3} + \ldots + {a_{12}} + 3{a_{13}}(\bmod 8)$$     M1

$$= (1 + 3 \times 0 + 2 + 3 \times 0 + \ldots + 3 \times 2)(\bmod 8) \equiv 24(\bmod 8)$$     A1

$$\equiv 0$$ OR divisible by $$8$$     A1

hence $$22010112200201$$ (base $$3$$) is divisible by $$8$$

[5 marks]

Total [10 marks]

b.

[N/A]

a.

[N/A]

b.

## Question

Consider the system of linear congruences

$\begin{array}{*{20}{l}} {x \equiv 2(\bmod 5)} \\ {x \equiv 5(\bmod 8)} \\ {x \equiv 1(\bmod 3).} \end{array}$

With reference to the integers 5, 8 and 3, state why the Chinese remainder theorem guarantees a unique solution modulo 120 to this system of linear congruences.

[2]
a.

Hence or otherwise, find the general solution to the above system of linear congruences.

[7]
b.

## Markscheme

5, 8 and 3 are pairwise relatively prime (or equivalent)     R1

120 is the product of 5, 8 and 3     R1

[2 marks]

a.

METHOD 1

$$x = 2 + 5t,{\text{ }}t \in \mathbb{Z}$$ and $$2 + 5t \equiv 5(\bmod 8)$$     M1

$$5t \equiv 3(\bmod 8) \Rightarrow 5t \equiv 35(\bmod 8)$$     (M1)

$$t = 7 + 8u,{\text{ }}u \in \mathbb{Z}$$     (A1)

$$x = 2 + 5(7 + 8u) \Rightarrow x = 37 + 40u$$     (A1)

$$37 + 40u \equiv 1(\bmod 3) \Rightarrow u \equiv 0(\bmod 3)$$     (A1)

$$u = 3v,{\text{ }}v \in \mathbb{Z}$$     (A1)

$$x = 37 + 40(3v)$$

$$x = 37 + 120v{\text{ }}\left( {x \equiv 37(\bmod 120)} \right)$$     A1

METHOD 2

attempting systematic listing of possibilities     M1

solutions to $$x \equiv 2(\bmod 5)$$ are $$x = 2,{\text{ }}7,{\text{ }}12,{\text{ }} \ldots ,{\text{ }}37,{\text{ }} \ldots$$     (A1)

solutions to $$x \equiv 5(\bmod 8)$$ are $$x = 5,{\text{ }}13,{\text{ }}21,{\text{ }} \ldots ,{\text{ }}37,{\text{ }} \ldots$$     (A1)

solutions to $$x \equiv 1(\bmod 3)$$ are $$x = 1,{\text{ }}4,{\text{ }}7,{\text{ }} \ldots ,{\text{ }}37,{\text{ }} \ldots$$     (A1)

a solution is $$x = 37$$     (A1)

using the Chinese remainder theorem     (M1)

$$x = 37 + 120v{\text{ }}\left( {x \equiv 37(\bmod 120)} \right)$$     A1

METHOD 3

attempting to find $${M_i},{\text{ }}i = 1,{\text{ }}2,{\text{ 3}}$$

$${M_1} = 8 \times 3 = 24,{\text{ }}{M_2} = 5 \times 3 = 15$$ and $${M_3} = 5 \times 8 = 40$$     M1

using $${M_i}{x_i} \equiv 1(\bmod {m_i}),{\text{ }}i = 1,{\text{ }}2,{\text{ }}3$$ to obtain

$$24{x_1} \equiv 1(\bmod 5),{\text{ }}15{x_2} \equiv 1(\bmod 8)$$ and $$40{x_3} \equiv 1(\bmod 3)$$     M1

$${x_1} \equiv 4(\bmod 5),{\text{ }}{x_2} \equiv 7(\bmod 8)$$ and $${x_3} \equiv 1(\bmod 3)$$     (A1)(A1)(A1)

use of $$x \equiv {a_1}{x_1}{M_1} + {a_2}{x_2}{M_2} + {a_3}{x_3}{M_3}(\bmod M)$$ gives

$$x = (2 \times 4 \times 24 + 5 \times 7 \times 15 + 1 \times 1 \times 40)(\bmod 120)$$     (M1)

$$x \equiv 757(\bmod 120){\text{ }}\left( { \equiv 37(\bmod 120)} \right){\text{ }}(x = 37 + 120v,{\text{ }}v \in \mathbb{Z})$$     A1

[7 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.