# IB DP Maths Topic 10.3 Linear Diophantine equations ax+by=c HL Paper 3

## Question

Use the Euclidean Algorithm to find the greatest common divisor of 7854 and 3315.

Hence state the number of solutions to the diophantine equation 7854x + 3315y = 41 and justify your answer.

## Markscheme

$$7854 = 2 \times 3315 + 1224$$     M1A1

$$3315 = 2 \times 1224 + 867$$     A1

$$1224 = 1 \times 867 + 357$$

$$867 = 2 \times 357 + 153$$

$$357 = 2 \times 153 + 51$$

$$153 = 3 \times 51$$     A1

The gcd is 51.     A1

Since 51 does not divide 41,     R1

there are no solutions.     A1

[7 marks]

## Examiners report

Most candidates were able to use the Euclidean Algorithm correctly to find the greatest common divisor. Candidates who used the GCD button on their calculators were given no credit. Some candidates seemed unaware of the criterion for the solvability of Diophantine equations.

## Question

(a)     Use the Euclidean algorithm to find the gcd of 324 and 129.

(b)     Hence show that $$324x + 129y = 12$$ has a solution and find both a particular solution and the general solution.

(c)     Show that there are no integers x and y such that $$82x + 140y = 3$$ .

## Markscheme

(a)     $$324 = 2 \times 129 + 66$$     M1

$$129 = 1 \times 66 + 63$$

$$66 = 1 \times 63 + 3$$     A1

hence gcd (324, 129) = 3     A1

[3 marks]

(b)     METHOD 1

Since $$\left. 3 \right|12$$ the equation has a solution     M1

$$3 = 1 \times 66 – 1 \times 63$$     M1

$$3 = – 1 \times 129 + 2 \times 66$$

$$3 = 2 \times (324 – 2 \times 129) – 129$$

$$3 = 2 \times 324 – 5 \times 129$$     A1

$$12 = 8 \times 324 – 20 \times 129$$     A1

$$(x,\,y) = (8,\, – 20)$$ is a particular solution     A1

Note: A calculator solution may gain M1M1A0A0A1.

A general solution is $$x = 8 + \frac{{129}}{3}t = 8 + 43t,{\text{ }}y = – 20 – 108t,{\text{ }}t \in \mathbb{Z}$$     A1

METHOD 2

$$324x + 129y = 12$$

$$108x + 43y = 4$$     A1

$$108x \equiv 4(\bmod 43) \Rightarrow 27x \equiv 1(\bmod 43)$$     A1

$$x = 8 + 43t$$     A1

$$108(8 + 43t) + 43y = 4$$     M1

$$864 + 4644t + 43y = 4$$

$$43y = – 860 – 4644t$$

$$y = – 20 – 108t$$     A1

a particular solution (for example $$t = 0$$) is $$(x,\,y) = (8,\, – 20)$$     A1

[6 marks]

(c)     EITHER

The left side is even and the right side is odd so there are no solutions     M1R1AG

[2 marks]

OR

$$\gcd (82,\,140) = 2$$     A1

2 does not divide 3 therefore no solutions     R1AG

[2 marks]

Total [11 marks]

## Examiners report

This problem was not difficult but presenting a clear solution and doing part (b) alongside part (a) in two columns was. The simple answer to part (c) was often overlooked.

## Question

(a)     Use the Euclidean algorithm to find gcd($$12\,306$$, 2976) .

(b)     Hence give the general solution to the diophantine equation $$12\,306$$x + 2976y = 996 .

## Markscheme

(a)     $$12\,306 = 4 \times 2976 + 402$$     M1

$$2976 = 7 \times 402 + 162$$     M1

$$402 = 2 \times 162 + 78$$     A1

$$162 = 2 \times 78 + 6$$     A1

$$78 = 13 \times 6$$

therefore gcd is 6     R1

[5 marks]

(b)     $$6|996$$ means there is a solution

$$6 = 162 – 2(78)$$     (M1)(A1)

$$= 162 – 2\left( {402 – 2(162)} \right)$$

$$= 5(162) – 2(402)$$     (A1)

$$= 5(2976) – 7(402)} \right) – 2(402)$$

$$= 5(2976) – 37(402)$$     (A1)

$$= 5(2976) – 37\left( {12\,306 – 4(2976)} \right)$$

$$= 153(2976) – 37(12\,306)$$     (A1)

$$996 = 25\,398(2976) – 6142(12\,306)$$

$$\Rightarrow {x_0} = – 6142,{\text{ }}{y_0} = 25\,398$$     (A1)

$$\Rightarrow x = – 6142 + \left( {\frac{{2976}}{6}} \right)t = – 6142 + 496t$$

$$\Rightarrow y = 25\,398 – \left( {\frac{{12\,306}}{6}} \right)t = 25\,398 – 2051t$$     M1A1A1

[9 marks]

Total [14 marks]

## Examiners report

Part (a) of this question was the most accessible on the paper and was completed correctly by the majority of candidates. Most candidates were able to start part (b), but a number made errors on the way and quite a number failed to give the general solution.

## Question

An arithmetic sequence has first term 2 and common difference 4. Another arithmetic sequence has first term 7 and common difference 5. Find the set of all numbers which are members of both sequences.

## Markscheme

the mth term of the first sequence $$= 2 + 4(m – 1)$$     (M1)(A1)

the nth term of the second sequence $$= 7 + 5(n – 1)$$     (A1)

EITHER

equating these,     M1

$$5n = 4m – 4$$

$$5n = 4(m – 1)$$     (A1)

4 and 5 are coprime     (M1)

$$\Rightarrow 4|n$$ so $$n = 4s$$ or $$5|(m – 1)$$ so $$m = 5s + 1$$ , $$s \in {\mathbb{Z}^ + }$$     (A1)A1

thus the common terms are of the form $$\{ 2 + 20s;{\text{ }}s \in {\mathbb{Z}^ + }\}$$     A1

OR

the numbers of both sequences are

2, 6, 10, 14, 18, 22

7, 12, 17, 22     A1

so 22 is common     A1

identify the next common number as 42     (M1)A1

the general solution is $$\{ 2 + 20s;{\text{ }}s \in {\mathbb{Z}^ + }\}$$     (M1)A1

[9 marks]

## Examiners report

Solutions to this question were extremely variable with some candidates taking several pages to give a correct solution and others taking several pages and getting nowhere. Some elegant solutions were seen including the fact that the members of the two sets can be represented as $$2\bmod 4$$ and $$2\bmod 5$$ respectively so that common members are $$2\bmod 20$$.

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

Use the Euclidean algorithm to find $$\gcd (752,{\text{ }}352)$$.

[4]
a.

A farmer spends £8128 buying cows of two different breeds, A and B, for her farm. A cow of breed A costs £752 and a cow of breed B costs £352.

(i)     Set up a diophantine equation to show this.

(ii)     Using your working from part (a), find the general solution to this equation.

(iii)     Hence find the number of cows of each breed bought by the farmer.

[10]
b.

## Markscheme

752 = 2(352) + 48     M1

352 = 7(48) +16     A1

48 = 3(16)     A1

therefore $$\gcd (752,{\text{ }}352)$$ is 16     R1

[4 marks]

a.

(i)     let x be the number of cows of breed A

let y be the number of cows of breed B

$$752x + 352y = 8128$$     A1

(ii)     $$16|8128$$ means there is a solution

$$16 = 352 – 7(48)$$     (M1)(A1)

$$16 = 352 – 7\left( {752 – 2(352)} \right)$$

$$16 = 15(352) – 7(752)$$     (A1)

$$8128 = 7620(352) – 3556(752)$$

$$\Rightarrow {x_0} = – 3556,{\text{ }}{y_0} = 7620$$     (A1)

$$\Rightarrow x = – 3556 + \left( {\frac{{352}}{{16}}} \right)t = – 3556 + 22t$$

$$\Rightarrow y = 7620 – \left( {\frac{{752}}{{16}}} \right)t = 7620 – 47t$$     M1A1A1

(iii)     for x, y to be $$\geqslant 0$$, the only solution is t = 162     M1

$$\Rightarrow x = 8,{\text{ }}y = 6$$     A1

[10 marks]

b.

## Examiners report

Part (a) of this question was the most accessible on the paper and was completed correctly by the majority of candidates. It was pleasing to see that candidates were not put off by the question being set in context and most candidates were able to start part (b). However, a number made errors on the way, quite a number failed to give the general solution and it was only stronger candidates who were able to give a correct solution to part (b) (iii).

a.

Part (a) of this question was the most accessible on the paper and was completed correctly by the majority of candidates. It was pleasing to see that candidates were not put off by the question being set in context and most candidates were able to start part (b). However, a number made errors on the way, quite a number failed to give the general solution and it was only stronger candidates who were able to give a correct solution to part (b) (iii).

b.

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

Using the Euclidean algorithm, show that $$\gcd (99,{\text{ }}332) = 1$$.

[4]
a.

(i)     Find the general solution to the diophantine equation $$332x – 99y = 1$$.

(ii)     Hence, or otherwise, find the smallest positive integer satisfying the congruence $$17z \equiv 1(\bmod 57)$$.

[11]
b.

## Markscheme

using the Euclidean Algorithm,

$$332 = 3 \times 99 + 35{\text{ }}$$     M1

$$99 = 2 \times 35 + 29$$     A1

$$35 = 1 \times 29 + 6$$

$$29 = 4 \times 6 + 5$$     A1

$$6 = 1 \times 5 + 1$$     A1

hence 332 and 99 have a gcd of 1     AG

Note: For both (a) and (b) accept layout in tabular form, especially the brackets method of keeping track of the linear combinations as the method proceeds.

[4 marks]

a.

(i)     working backwards,     (M1)

$$6 – 5 = 1$$

$$6 – (29 – 4 \times 6) = 1{\text{ or }}5 \times 6 – 29 = 1$$     A1

$$5 \times (35-29)-29 = 1{\text{ or }}5 \times 35-6 \times 29 = 1$$     A1

$$5 \times 35-6 \times (99-2 \times 35) = 1{\text{ or }}17 \times 35-6 \times 99 = 1$$

$$17 \times (332-3 \times 99)-6 \times 99 = 1{\text{ or }}17 \times 332-57 \times 99 = 1$$     A1

a solution to the Diophantine equation is therefore

$$x = 17,{\text{ }}y = 57$$     (A1)

the general solution is

$$x = 17 + 99N,{\text{ }}y = 57 + 332N$$     A1A1

Note: If part (a) is wrong it is inappropriate to give FT in (b) as the numbers will contradict, however the M1 can be given.

(ii)     it follows from previous work that

$$17 \times 332 = 1 + 99 \times 57$$     (M1)

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

z = 332 is a solution to the given congruence     (A1)

the general solution is 332 + 57N so the smallest solution is 47     A1

[11 marks]

b.

## Examiners report

Part (a) was well answered and (b) fairly well answered. There were problems with negative signs due to the fact that there was a negative in the question, so candidates had to think a little, rather than just remembering formulae by rote. The lay-out of the algorithm that keeps track of the linear combinations of the first 2 variables is recommended to teachers.

a.

Part (a) was well answered and (b) fairly well answered. There were problems with negative signs due to the fact that there was a negative in the question, so candidates had to think a little, rather than just remembering formulae by rote. The lay-out of the algorithm that keeps track of the linear combinations of the first 2 variables is recommended to teachers.

b.

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

Use the Euclidean algorithm to find the greatest common divisor of 259 and 581.

[4]
a.

Hence, or otherwise, find the general solution to the diophantine equation 259x + 581y = 7 .

[5]
b.

## Markscheme

$$581 = 2 \times 259 + 63$$     M1A1

$$259 = 4 \times 63 + 7$$     A1

$$63 = 9 \times 7$$

the GCD is therefore 7     A1

[4 marks]

a.

consider

$$7 = 259 – 4 \times 63$$     M1

$$= 259 – 4 \times (581 – 2 \times 259)$$     A1

$$= 259 \times 9 + 581 \times ( – 4)$$     A1

the general solution is therefore

$$x = 9 + 83n;{\text{ }}y = – 4 – 37n{\text{ where }}n \in \mathbb{Z}$$     M1A1

Notes: Accept solutions laid out in tabular form. Dividing the diophantine equation by 7 is an equally valid method.

[5 marks]

b.

[N/A]

a.

[N/A]

b.