# IB DP Maths Topic 10.2 The greatest common divisor, gcd(a,b), and the least common multiple, lcm(a,b), of integers a and b HL Paper 3

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

Explaining your method fully, determine whether or not 1189 is a prime number.

[4]
a.

(i)     State the fundamental theorem of arithmetic.

(ii)     The positive integers M and N have greatest common divisor G and least common multiple L . Show that GL = MN .

[6]
b.

## Markscheme

any clearly indicated method of dividing 1189 by successive numbers     M1

find that 1189 has factors 29 and/or 41     A2

it follows that 1189 is not a prime number     A1

Note: If no method is indicated, award A1 for the factors and A1 for the conclusion.

[4 marks]

a.

(i)     every positive integer, greater than 1, is either prime or can be expressed uniquely as a product of primes     A1A1

Note: Award A1 for “product of primes” and A1 for “uniquely”.

(ii)     METHOD 1

let M and N be expressed as a product of primes as follows

M = AB and N = AC     M1A1

where A denotes the factors which are common and B, C the disjoint factors which are not common

it follows that G = A     A1

and L = GBC     A1

from these equations, it follows that

$$GL = A \times ABC = MN$$     AG

METHOD 2

Let $$M = {2^{{x_1}}} \times {3^{{x_2}}} \times …p_n^{{x_n}}$$ and $$N = {2^{{y_1}}} \times {3^{{y_2}}} \times …p_n^{{y_n}}$$ where $${p_n}$$ denotes the $${n^{{\text{th}}}}$$ prime     M1

Then $$G = {2^{\min ({x_1},{y_1})}} \times {3^{\min ({x_2},{y_2})}} \times …p_n^{\min ({x_n},{y_n})}$$     A1

and $$L = {2^{\max ({x_1},{y_1})}} \times {3^{\max ({x_2},{y_2})}} \times …p_n^{\max ({x_n},{y_n})}$$     A1

It follows that $$GL = {2^{{x_1}}} \times {2^{{y_1}}} \times {3^{{x_2}}} \times {3^{{y_2}}} \times … \times p_n^{{x_n}} \times p_n^{{y_n}}$$     A1

= MN     AG

[6 marks]

b.

## Examiners report

In (a), some candidates tried to use Fermat’s little theorem to determine whether or not 1189 is prime but this method will not always work and in any case the amount of computation involved can be excessive. For this reason, it is strongly recommended that this method should not be used in examinations. In (b), it was clear from the scripts that candidates who had covered this material were generally successful and those who had not previously seen the result were usually unable to proceed.

a.

In (a), some candidates tried to use Fermat’s little theorem to determine whether or not 1189 is prime but this method will not always work and in any case the amount of computation involved can be excessive. For this reason, it is strongly recommended that this method should not be used in examinations. In (b), it was clear from the scripts that candidates who had covered this material were generally successful and those who had not previously seen the result were usually unable to proceed.

b.

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

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

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

State the Fundamental theorem of arithmetic for positive whole numbers greater than $$1$$.

[2]
a.

Use the Fundamental theorem of arithmetic, applied to $$5577$$ and $$99\,099$$, to calculate $$\gcd (5577,{\text{ }}99\,099)$$ and $${\text{lcm}}(5577,{\text{ }}99\,099)$$, expressing each of your answers as a product of prime numbers.

[3]
b.

Prove that $$\gcd (n,{\text{ }}m) \times {\text{lcm}}(n,{\text{ }}m) = n \times m$$ for all $$n,{\text{ }}m \in {\mathbb{Z}^ + }$$.

[6]
c.

## Markscheme

every positive integer, greater than $$1$$, is either prime or can be expressed uniquely as a product of primes     A1A1

Note:     Award A1 for “product of primes” and A1 for “uniquely”.

[2 marks]

a.

$$5577 = 3 \times 11 \times {13^2}{\text{ and }}99099 = {3^2} \times 7 \times {11^2} \times 13$$     M1

$$\gcd (5577,{\text{ }}99099) = 3 \times 11 \times 13,{\text{ lcm}}(5577,{\text{ }}99099) = {3^2} \times 7 \times {11^2} \times {13^2}$$     A1A1

[3 marks]

b.

METHOD 1

$$n = p_1^{{k_1}}p_2^{{k_2}} \ldots p_r^{{k_r}}$$ and $$m = p_1^{{j_1}}p_2^{{j_2}} \ldots p_r^{{j_r}}$$     M1

employing all the prime factors of $$n$$ and $$m$$, and inserting zero exponents if necessary     R1

define $${g_i} = \min ({k_i},{\text{ }}{j_i})$$ and $${h_i} = \max ({k_i},{\text{ }}{j_i})$$ for $$i = 1 \ldots r$$     (M1)

$$\gcd (n,{\text{ }}m) = p_1^{{g_1}}p_2^{{g_2}} \ldots p_r^{{g_r}}$$ and $${\text{lcm}}(n,{\text{ }}m) = p_1^{{h_1}}p_2^{{h_2}} \ldots p_r^{{h_r}}$$     A1A1

noting that $${g_i} + {h_i} = {k_i} + {j_i}$$ for $$i = 1 \ldots r$$     R1

$$\gcd (n,{\text{ }}m) \times {\text{lcm}}(n,{\text{ }}m) = n \times m$$ for all $$n,{\text{ }}m \in {\mathbb{Z}^ + }$$AG

METHOD 2

let $$m$$ and $$n$$ be expressed as a product of primes where $$m = ab$$ and $$n = ac$$     M1

$$a$$ denotes the factors that are common and $$b,{\text{ }}c$$ are the disjoint factors that are not common     R1

$$\gcd (n,{\text{ }}m) = a$$     A1

$${\text{lcm}}(n,{\text{ }}m) = \gcd (n,{\text{ }}m)bc$$     A1

$$\gcd (n,{\text{ }}m) \times {\text{lcm}}(n,{\text{ }}m) = a \times (abc)$$     M1

$$= ab \times ac$$ and $$m = ab$$ and $$n = ac$$ so     R1

$$\gcd (n,{\text{ }}m) \times 1{\text{ cm}}(n,{\text{ }}m) = n \times m$$ for all $$n,{\text{ }}m \in {\mathbb{Z}^ + }$$     AG

[6 marks]

Total [11 marks]

c.

## Examiners report

In part (a), most candidates omitted the ‘uniquely’ in their definition of the fundamental theorem of arithmetic. A few candidates defined what a prime number is.

a.

In part (b), a substantial number of candidates used the Euclidean algorithm rather than the fundamental theorem of arithmetic to calculate $$\gcd (5577,{\text{ }}99099)$$ and $${\text{lcm}}(5577,{\text{ }}99099)$$.

b.

In part (c), a standard proof that has appeared in previous examination papers, was answered successfully by candidates who were well prepared.

c.

## Question

Show that $${\text{gcd}}\left( {4k + 2,\,3k + 1} \right) = {\text{gcd}}\left( {k – 1,\,2} \right)$$, where $$k \in {\mathbb{Z}^ + },\,k > 1$$.

[4]
a.

State the value of $${\text{gcd}}\left( {4k + 2,\,3k + 1} \right)$$ for odd positive integers $$k$$.

[1]
b.i.

State the value of $${\text{gcd}}\left( {4k + 2,\,3k + 1} \right)$$ for even positive integers $$k$$.

[1]
b.ii.

## Markscheme

METHOD 1

attempting to use the Euclidean algorithm       M1

$$4k + 2 = 1\left( {3k + 1} \right) + \left( {k + 1} \right)$$      A1

$$3k + 1 = 2\left( {k + 1} \right) + \left( {k – 1} \right)$$      A1

$$K + 1 = \left( {k – 1} \right) + 2$$      A1

$$= {\text{gcd}}\left( {k – 1,\,2} \right)$$     AG

METHOD 2

$${\text{gcd}}\left( {4k + 2,\,3k + 1} \right)$$

$$= {\text{gcd}}\left( {4k + 2 – \left( {3k + 1} \right),\,3k + 1} \right)$$     M1

$$= {\text{gcd}}\left( {3k + 1,\,k + 1} \right)\,\,\left( { = {\text{gcd}}\left( {{\text{k + 1,}}\,{\text{3k + 1}}} \right)} \right)$$     A1

$$= {\text{gcd}}\left( {3k + 1 – 2\left( {k + 1} \right),\,k + 1} \right)\,\,\left( { = {\text{gcd}}\left( {k – 1{\text{,}}\,k + {\text{1}}} \right)} \right)$$     A1

$$= {\text{gcd}}\left( {k + 1 – \left( {k – 1} \right),\,k – 1} \right)\,\,\left( { = {\text{gcd}}\left( {{\text{2,}}\,k – {\text{1}}} \right)} \right)$$     A1

$$= {\text{gcd}}\left( {k – 1,\,2} \right)$$     AG

[4 marks]

a.

(for $$k$$ odd), $${\text{gcd}}\left( {4k + 2,\,3k + 1} \right) = 2$$     A1

[1 mark]

b.i.

(for $$k$$ even), $${\text{gcd}}\left( {4k + 2,\,3k + 1} \right) = 1$$     A1

[1 mark]

b.ii.

[N/A]

a.

[N/A]

b.i.

[N/A]

b.ii.