May 2024 Paper 2 Q2
2. Use the Euclidean algorithm to find integers \(a\) and \(b\) such that \(533a+455b=13\). [3]
| Mark | Generic scheme | Illustrative scheme |
|---|---|---|
| •1 | complete algorithm 1 | \(\begin{aligned}533&=455\times1+78\\455&=78\times5+65\\78&=65\times1+13\\(65&=13\times5)\end{aligned}\) |
| •2 | express gcd in terms of 455 and 533 | eg \(13=(533-455\times1)\times6-455\) |
| •3 | obtain \(a\) and \(b\) 2,3 | \(a=6\ ,\ b=-7\) |
| (3) |
Notes:
- At •1 the gcd and the final line of working do not have to be stated explicitly.
- The minimum requirement for •3 is \(13=533\times6+455\times(-7)\).
- Do not accept \(13=6\times533-7\times455\) where the values of \(a\) and \(b\) have not been explicitly stated.