Question
Use the Euclidean Algorithm to find the greatest common divisor of 7854 and 3315.
Hence state the number of solutions to the diophantine equation 7854x + 3315y = 41 and justify your answer.
▶️Answer/Explanation
Markscheme
\(7854 = 2 \times 3315 + 1224\) M1A1
\(3315 = 2 \times 1224 + 867\) A1
\(1224 = 1 \times 867 + 357\)
\(867 = 2 \times 357 + 153\)
\(357 = 2 \times 153 + 51\)
\(153 = 3 \times 51\) A1
The gcd is 51. A1
Since 51 does not divide 41, R1
there are no solutions. A1
[7 marks]
Examiners report
Most candidates were able to use the Euclidean Algorithm correctly to find the greatest common divisor. Candidates who used the GCD button on their calculators were given no credit. Some candidates seemed unaware of the criterion for the solvability of Diophantine equations.
Question
(a) Use the Euclidean algorithm to find the gcd of 324 and 129.
(b) Hence show that \(324x + 129y = 12\) has a solution and find both a particular solution and the general solution.
(c) Show that there are no integers x and y such that \(82x + 140y = 3\) .
▶️Answer/Explanation
Markscheme
(a) \(324 = 2 \times 129 + 66\) M1
\(129 = 1 \times 66 + 63\)
\(66 = 1 \times 63 + 3\) A1
hence gcd (324, 129) = 3 A1
[3 marks]
(b) METHOD 1
Since \(\left. 3 \right|12\) the equation has a solution M1
\(3 = 1 \times 66 – 1 \times 63\) M1
\(3 = – 1 \times 129 + 2 \times 66\)
\(3 = 2 \times (324 – 2 \times 129) – 129\)
\(3 = 2 \times 324 – 5 \times 129\) A1
\(12 = 8 \times 324 – 20 \times 129\) A1
\((x,\,y) = (8,\, – 20)\) is a particular solution A1
Note: A calculator solution may gain M1M1A0A0A1.
A general solution is \(x = 8 + \frac{{129}}{3}t = 8 + 43t,{\text{ }}y = – 20 – 108t,{\text{ }}t \in \mathbb{Z}\) A1
METHOD 2
\(324x + 129y = 12\)
\(108x + 43y = 4\) A1
\(108x \equiv 4(\bmod 43) \Rightarrow 27x \equiv 1(\bmod 43)\) A1
\(x = 8 + 43t\) A1
\(108(8 + 43t) + 43y = 4\) M1
\(864 + 4644t + 43y = 4\)
\(43y = – 860 – 4644t\)
\(y = – 20 – 108t\) A1
a particular solution (for example \(t = 0\)) is \((x,\,y) = (8,\, – 20)\) A1
[6 marks]
(c) EITHER
The left side is even and the right side is odd so there are no solutions M1R1AG
[2 marks]
OR
\(\gcd (82,\,140) = 2\) A1
2 does not divide 3 therefore no solutions R1AG
[2 marks]
Total [11 marks]
Examiners report
This problem was not difficult but presenting a clear solution and doing part (b) alongside part (a) in two columns was. The simple answer to part (c) was often overlooked.
Question
(a) Use the Euclidean algorithm to find gcd(\(12\,306\), 2976) .
(b) Hence give the general solution to the diophantine equation \(12\,306\)x + 2976y = 996 .
▶️Answer/Explanation
Markscheme
(a) \(12\,306 = 4 \times 2976 + 402\) M1
\(2976 = 7 \times 402 + 162\) M1
\(402 = 2 \times 162 + 78\) A1
\(162 = 2 \times 78 + 6\) A1
\(78 = 13 \times 6\)
therefore gcd is 6 R1
[5 marks]
(b) \(6|996\) means there is a solution
\(6 = 162 – 2(78)\) (M1)(A1)
\( = 162 – 2\left( {402 – 2(162)} \right)\)
\( = 5(162) – 2(402)\) (A1)
\( = 5(2976) – 7(402)} \right) – 2(402)\)
\( = 5(2976) – 37(402)\) (A1)
\( = 5(2976) – 37\left( {12\,306 – 4(2976)} \right)\)
\( = 153(2976) – 37(12\,306)\) (A1)
\(996 = 25\,398(2976) – 6142(12\,306)\)
\( \Rightarrow {x_0} = – 6142,{\text{ }}{y_0} = 25\,398\) (A1)
\( \Rightarrow x = – 6142 + \left( {\frac{{2976}}{6}} \right)t = – 6142 + 496t\)
\( \Rightarrow y = 25\,398 – \left( {\frac{{12\,306}}{6}} \right)t = 25\,398 – 2051t\) M1A1A1
[9 marks]
Total [14 marks]
Examiners report
Part (a) of this question was the most accessible on the paper and was completed correctly by the majority of candidates. Most candidates were able to start part (b), but a number made errors on the way and quite a number failed to give the general solution.
Question
An arithmetic sequence has first term 2 and common difference 4. Another arithmetic sequence has first term 7 and common difference 5. Find the set of all numbers which are members of both sequences.
▶️Answer/Explanation
Markscheme
the mth term of the first sequence \( = 2 + 4(m – 1)\) (M1)(A1)
the nth term of the second sequence \( = 7 + 5(n – 1)\) (A1)
EITHER
equating these, M1
\(5n = 4m – 4\)
\(5n = 4(m – 1)\) (A1)
4 and 5 are coprime (M1)
\( \Rightarrow 4|n\) so \(n = 4s\) or \(5|(m – 1)\) so \(m = 5s + 1\) , \(s \in {\mathbb{Z}^ + }\) (A1)A1
thus the common terms are of the form \(\{ 2 + 20s;{\text{ }}s \in {\mathbb{Z}^ + }\} \) A1
OR
the numbers of both sequences are
2, 6, 10, 14, 18, 22
7, 12, 17, 22 A1
so 22 is common A1
identify the next common number as 42 (M1)A1
the general solution is \(\{ 2 + 20s;{\text{ }}s \in {\mathbb{Z}^ + }\} \) (M1)A1
[9 marks]
Examiners report
Solutions to this question were extremely variable with some candidates taking several pages to give a correct solution and others taking several pages and getting nowhere. Some elegant solutions were seen including the fact that the members of the two sets can be represented as \(2\bmod 4\) and \(2\bmod 5\) respectively so that common members are \(2\bmod 20\).
Question
An arithmetic sequence has first term 2 and common difference 4. Another arithmetic sequence has first term 7 and common difference 5. Find the set of all numbers which are members of both sequences.
▶️Answer/Explanation
Markscheme
the mth term of the first sequence \( = 2 + 4(m – 1)\) (M1)(A1)
the nth term of the second sequence \( = 7 + 5(n – 1)\) (A1)
EITHER
equating these, M1
\(5n = 4m – 4\)
\(5n = 4(m – 1)\) (A1)
4 and 5 are coprime (M1)
\( \Rightarrow 4|n\) so \(n = 4s\) or \(5|(m – 1)\) so \(m = 5s + 1\) , \(s \in {\mathbb{Z}^ + }\) (A1)A1
thus the common terms are of the form \(\{ 2 + 20s;{\text{ }}s \in {\mathbb{Z}^ + }\} \) A1
OR
the numbers of both sequences are
2, 6, 10, 14, 18, 22
7, 12, 17, 22 A1
so 22 is common A1
identify the next common number as 42 (M1)A1
the general solution is \(\{ 2 + 20s;{\text{ }}s \in {\mathbb{Z}^ + }\} \) (M1)A1
[9 marks]
Examiners report
Solutions to this question were extremely variable with some candidates taking several pages to give a correct solution and others taking several pages and getting nowhere. Some elegant solutions were seen including the fact that the members of the two sets can be represented as \(2\bmod 4\) and \(2\bmod 5\) respectively so that common members are \(2\bmod 20\).
Question
a.Use the Euclidean algorithm to find the greatest common divisor of 259 and 581.[4]
b.Hence, or otherwise, find the general solution to the diophantine equation 259x + 581y = 7 .[5]
▶️Answer/Explanation
Markscheme
\(581 = 2 \times 259 + 63\) M1A1
\(259 = 4 \times 63 + 7\) A1
\(63 = 9 \times 7\)
the GCD is therefore 7 A1
[4 marks]
consider
\(7 = 259 – 4 \times 63\) M1
\( = 259 – 4 \times (581 – 2 \times 259)\) A1
\( = 259 \times 9 + 581 \times ( – 4)\) A1
the general solution is therefore
\(x = 9 + 83n;{\text{ }}y = – 4 – 37n{\text{ where }}n \in \mathbb{Z}\) M1A1
Notes: Accept solutions laid out in tabular form. Dividing the diophantine equation by 7 is an equally valid method.
[5 marks]
Examiners report
[N/A]
[N/A]