Question
a.Use the Euclidean algorithm to find the greatest common divisor of the numbers 56 and 315.[4]
b.(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]
▶️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
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.Use the Euclidean algorithm to express gcd (123, 2347) in the form 123p + 2347q, where \(p,{\text{ }}q \in \mathbb{Z}\).[8]
b.Find the least positive solution of \(123x \equiv 1(\bmod 2347)\) .[3]
c.Find the general solution of \(123z \equiv 5(\bmod 2347)\) .[3]
d.State the solution set of \(123y \equiv 1(\bmod 2346)\) .[1]
▶️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.
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
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.[6]
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
Let \(f(n) = {n^5} – n,{\text{ }}n \in {\mathbb{Z}^ + }\).
a.Find the values of \(f(3)\), \(f(4)\) and \(f(5)\).[2]
b.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]
c.Explain why \(f(n)\) is always exactly divisible by \(5\).[1]
d.By factorizing \(f(n)\) explain why it is always exactly divisible by \(6\).[4]
e.Determine the values of \(n\) for which \(f(n)\) is exactly divisible by \(60\).[3]
▶️Answer/Explanation
Markscheme
\(240,{\rm{ }}1020,{\rm{ }}3120\) A2
Note: Award A2 for three correct answers, A1 for two correct answers.
[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 R1 for justification of \(3\).
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
a.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]
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]