AS October 2020 Q2
2. The highest common factor of 963 and 657 is \(c\).
(a) Use the Euclidean algorithm to find the value of \(c\). (3)
(b) Hence find integers \(a\) and \(b\) such that\[963a + 657b = c\] (3)
| Scheme | Marks | AO |
|---|---|---|
| \(963 = 657 \times 1 + 306 \qquad 657 = 306 \times 2 + 45\) | M1 | 1.2 |
| \(306 = 45 \times 6 + 36\) \(45 = 36 \times 1 + 9\) \(36 = 9 \times 4 + 0\) | A1 | 1.1b |
| \(\text{HCF}(963, 657) = 9\) or \(c = 9\) | A1 | 1.1b |
| (3) |
Notes
M1: Starts the process by showing 2 correct stages
A1: Completes the algorithm correctly
A1: Correct HCF
| Scheme | Marks | AO |
|---|---|---|
| \(9 = 45 - 36 \times 1 \qquad 9 = 45 - (306 - 45 \times 6)\) | M1 | 1.1b |
| \(9 = 7 \times 45 - 306\) \(= 7 \times (657 - 2 \times 306) - 306 = 7 \times 657 - 15 \times 306\) \(= 7 \times 657 - 15 \times (963 - 1 \times 657)\) | A1 | 2.1 |
| \(9 = -15 \times 963 + 22 \times 657\) | A1 | 1.1b |
| (3) | ||
| (6 marks) |
Notes
M1: Starts the reversal process by completing at least 2 stages
A1: Completes the algorithm correctly
A1: Correct values for \(a\) and \(b\)