## Question

Write 57128 as a product of primes.

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

**Answer/Explanation**

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

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

## Examiners report

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

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

## 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 *A1* for the conclusion.

* *

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

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

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

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

**Answer/Explanation**

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

**marks have been awarded.**

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

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

## Examiners report

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

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

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

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]