A2 October 2021 Q3
3.
| Scheme | Marks | AO |
|---|---|---|
| \(125 = 87 \times 1 + 38\) \(87 = 38 \times 2 + 11 \ldots\) | M1 | 1.1b |
| \(38 = 11 \times 3 + 5\) \(11 = 5 \times 2 + 1\) | M1 A1 | 1.1b 1.1b |
| \(1 = 11 - 5 \times 2\) \(= 11 - (38 - 11 \times 3) \times 2 = 11 \times 7 - 38 \times 2\) \(= (87 - 38 \times 2) \times 7 - 38 \times 2 = 87 \times 7 - 38 \times 16\) | M1 | 2.1 |
| \(1 = 87 \times 7 - (125 - 87 \times 1) \times 16 = -16 \times 125 + 23 \times 87\) (So \(a = -16\) and \(b = 23\)) | A1 | 1.1b |
| (5) |
Notes
M1: Begins the process of applying the Euclidean algorithm, with attempt at the first two steps. Allow slips.
M1: Completes the process to the stage shown – if errors have been made at least three steps should have been made in reaching their final line (ending +1) to score this mark.
A1: Algorithm correctly carried out – as shown.
M1: Starts the process of back substitution – at least two substitutions made.
A1: Completes the process and finds the correct values for \(a\) and \(b\).
| Scheme | Marks | AO |
|---|---|---|
| From (a) \(23 \times 87 \equiv 1 \pmod{125}\) so multiplicative inverse of 87 is 23. | B1ft | 2.2a |
| (1) |
Notes
B1ft: Deduces correct multiplicative inverse. Accept 23 or anything congruent to 23 modulo 125 or follow through their \(b\).
| Scheme | Marks | AO |
|---|---|---|
| \(x \equiv 23 \times 16 \pmod{125}\) | M1 | 1.1b |
| \(x \equiv 368 \equiv 118 \pmod{125}\) | A1 | 1.1b |
| (2) | ||
| (8 marks) |
Notes
M1: Multiplies 16 by their multiplicative inverse or any other full method to proceed to the solution, e.g. multiplying the identity found in (a) through by 16 and reducing modulo 125.
A1: \(x \equiv 118 \pmod{125}\). Accept 118 or anything congruent to 118 modulo 125 as long as it is part of a correct modulo statement. (Do not accept just 368 on its own.)