May 2023 Paper 2 Q6
6.
(a) Use the Euclidean algorithm to find \(d\), the greatest common divisor of 703 and 399. [1]
(b) Find integers \(a\) and \(b\) such that \(d=703a+399b\). [2]
(c) Hence find integers \(p\) and \(q\) such that \(76=703p+399q\). [1]
| Mark | Generic scheme | Illustrative scheme |
|---|---|---|
| •1 | obtain \(d\) 1 | \(19\) |
| (1) |
Notes:
- For the award of •1, 19 must be clearly identified as the gcd in (a) or implied by its use in (b).
| Mark | Generic scheme | Illustrative scheme |
|---|---|---|
| •2 | express gcd in terms of 304 and 399 | \(\begin{aligned}19&=304-3\times95\\&=304-3\times(399-1\times304)\end{aligned}\) |
| •3 | find values of \(a\) and \(b\) 1 | \(a=4,\ b=-7\) |
| (2) |
Notes:
- At •3, where candidates do not explicitly communicate \(a\) and \(b\):
- accept \(19=4\times703+(-7)\times399\) and \(19=703\times4+399\times(-7)\)
- do not accept \(19=4\times703-7\times399\) or \(19=4\times703-399\times7\)
| Mark | Generic scheme | Illustrative scheme |
|---|---|---|
| •4 | find values of \(p\) and \(q\) 1,2 | \(p=16,\ q=-28\) |
| (1) |
Notes:
- Do not accept \(a=16,\ b=-28\).
- At •4, where candidates do not explicitly communicate \(p\) and \(q\):
- accept \(76=16\times703+(-28)\times399\) and \(76=703\times16+399\times(-28)\)
- do not accept \(76=16\times703-28\times399\) or \(76=16\times703-399\times28\) unless •3 has already been withheld on the same grounds.