May 2022 Paper 2 Q3
3. Use the Euclidean algorithm to find integers \(a\) and \(b\) such that
\[634a+87b=1.\]
[3]
| Mark | Generic scheme | Illustrative scheme |
|---|---|---|
| \(634=7\times 87+25\) | ||
| •1 | start process and obtain remainder of 1 | \(87=3\times 25+12\) \(25=2\times 12+1\) |
| •2 | express gcd in terms of 87 and 25 | \(1=25-2\left(87-3\times 25\right)\) |
| •3 | obtain \(a\) and \(b\) 1 | \(a=7\quad b=-51\) |
| (3) |
Notes:
- At •3, where candidates do not explicitly communicate \(a\) and \(b\), accept eg \(634\times 7+87\times -51=1\) or \(634\times 7+-51\times 87=1\). Do not accept \(634\times 7-87\times 51=1\) or \(634\times 7-51\times 87=1\).