Question
a.State the Fundamental theorem of arithmetic for positive whole numbers greater than \(1\).[2]
b.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]
c.Prove that \(\gcd (n,{\text{ }}m) \times {\text{lcm}}(n,{\text{ }}m) = n \times m\) for all \(n,{\text{ }}m \in {\mathbb{Z}^ + }\).[6]
▶️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 A1 for “uniquely”.
[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
aShow that \({\text{gcd}}\left( {4k + 2,\,3k + 1} \right) = {\text{gcd}}\left( {k – 1,\,2} \right)\), where \(k \in {\mathbb{Z}^ + },\,k > 1\).[4]
b.i.State the value of \({\text{gcd}}\left( {4k + 2,\,3k + 1} \right)\) for odd positive integers \(k\).[1]
b.ii.State the value of \({\text{gcd}}\left( {4k + 2,\,3k + 1} \right)\) for even positive integers \(k\).[1]
▶️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]
Question
a. 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]
b.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]
c.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.
d.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]
▶️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
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 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]
(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
a.Explaining your method fully, determine whether or not 1189 is a prime number.[4]
b.(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]
▶️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
a.Write 57128 as a product of primes.[4]
c.Prove that \(\left. {22} \right|{5^{11}} + {17^{11}}\).[4]
▶️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.