May 2025 Paper 2 Q4
4.
(a) Use the Euclidean algorithm to find \(d\), the greatest common divisor of 1118 and 416. [1]
(b) Hence find integers \(a\) and \(b\) such that \(1118a+416b=d\). [2]
| Mark | Generic scheme | Illustrative scheme |
|---|---|---|
| •1 | obtain and identify \(d\) 1,2 | eg \(1118=2\times416+286\) leading to eg 26, gcd=26 |
| (1) |
Notes:
- The gcd must be clearly identified in (a) or implied by the use of 26 in (b).
- There must be evidence of the Euclidean algorithm or a related process.
| Mark | Generic scheme | Illustrative scheme |
|---|---|---|
| •2 | express gcd in terms of 286 and 416 1,2 | eg \(\begin{aligned}26&=286-2\times130\\&=286-2\times\left(416-1\times286\right)\end{aligned}\) |
| •3 | determine \(a\) and \(b\) 3,4 | \(a=3,\ b=-8\) |
| (2) |
Notes:
- For the correct answer with no working, award 0/2.
- At •2, the expression may involve 286, 416 and 1118.
- At •3, the minimum requirement is \(26=1118\times(3)+416\times(-8)\).
- Do not accept \(26=3\times1118-8\times416\) as a final response.