## Question

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

(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) .

**Answer/Explanation**

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

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

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

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.

## Question

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

(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* .

**Answer/Explanation**

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

**for the conclusion.**

*A1** *

*[4 marks]*

(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

**for “uniquely”.**

*A1*

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

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

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.

## Question

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

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

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

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

**Answer/Explanation**

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

**EITHER**

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

**OR**

\(x = – 706 + 2347n\) ** M1A1**

solution: 1641 *A1*

*[3 marks]*

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

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

*[1 mark]*

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

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.

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.

## 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\).

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\).

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.

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.

**Answer/Explanation**

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

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

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

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

## Examiners report

[N/A]

[N/A]

[N/A]

[N/A]

## Question

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

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

Use the Euclidean algorithm to find

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

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

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

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

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

**Answer/Explanation**

## Markscheme

\(240,{\rm{ }}1020,{\rm{ }}3120\) *A2*

**Note: **Award ** A2 **for three correct answers,

**for two correct answers.**

*A1***[2 marks]**

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

by Fermat’s little theorem with \(p = 5\) *R1*

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

so 5 divides \(f(n)\)

**[1 mark]**

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

**for justification of \(3\).**

*R1*And therefore \(f(n)\) is a multiple of \(6\). *AG*

*[4 marks]*

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

## Examiners report

Well answered.

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

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.

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

Only the better candidates realised that they had to find another factor of \(2\).

## Question

State the Fundamental theorem of arithmetic for positive whole numbers greater than \(1\).

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.

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

**Answer/Explanation**

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

**for “uniquely”.**

*A1***[2 marks]**

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

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

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

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)\).

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

## 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\).

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

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

**Answer/Explanation**

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

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

**[1 mark]**

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

**[1 mark]**

## Examiners report

[N/A]

[N/A]

[N/A]