A2 June 2023 Q4
4.
| Scheme | Marks | AO |
|---|---|---|
| \(168 = 66 \times 2 + 36\) \(66 = 36 \times 1 + 30\) \(36 = 30 \times 1 + 6\) \(\{30 = 5 \times 6 + 0\}\) | M1 | 2.1 |
| {Last non-zero remainder is 6} so highest common factor is 6.* | A1* | 2.4 |
| (2) |
Notes
M1: Attempt at the Euclidean algorithm to find the gcd of 168 and 66, condone a numerical slip.
A1*: A fully correct application of the Euclidean algorithm and explains that the highest common factor is 6.
| Scheme | Marks | AO |
|---|---|---|
| \(6 = 36 - 30 \times 1\) \(= 36 - (66 - 36 \times 1) = 2 \times 36 - 1 \times 66\) \(= 2(168 - 66 \times 2) - 1 \times 66\) | M1 A1 | 2.1 1.1b |
| \(\Rightarrow 6 = 168 \times 2 - 66 \times 5\) so \(a = 2,\ b = -5\) | A1 | 2.2a |
| (3) |
Notes
M1: Attempts to apply back substitution to find suitable values.
A1: Correct expression in just the numbers 168 and 66 reached (all remainders eliminated). Need not be fully simplified.
A1: Deduces the correct values of \(a\) and \(b\). Allow if only seen in the expression.
| Scheme | Marks | AO |
|---|---|---|
| As \(168x + 66y\) will always be an integer multiple of 6, but 10 is not a multiple of 6, there can be no integer solutions. or \(\gcd(168, 66) = 6\) and as \(6 \nmid 10\) | B1 | 2.4 |
| (1) |
Notes
B1: Correct explanation. Must refer to 10 not being a multiple of 6.
| Scheme | Marks | AO |
|---|---|---|
| From (b) we deduce \(1 = 28 \times 2 - 11 \times 5\) | B1 | 2.2a |
| Hence \(8 \times 11 \times -5 \equiv -5 \times 8 \pmod{28}\) | M1 | 1.1b |
| \(v \equiv -40 \equiv 16 \pmod{28}\) | A1 | 1.1b |
| (3) | ||
| (9 marks) |
Notes
B1: Uses the result in (b) and divides through by 6 to form a correct statement between 11 and 28. Alternatively uses Euclidean algorithm for 28 and 11 to form an equation for 1 as multiples of 28 and 11. Allow this mark for a correct unsimplified equation.
M1: Multiplies through in their equation by 8 or the original equation through by \(-5\) (or other multiplicative inverse).
A1: Deduces the correct solutions. Accept either \(-40 \pmod{28}\) or \(16 \pmod{28}\), or any other correct congruence.
Alternative 1
| Scheme | Marks | AO |
|---|---|---|
| Forms an expression of the form \(8 = 28A + 11B\) | M1 | 1.1b |
| e.g. \(8 = 5 \times 28 - 12 \times 11 \qquad 8 = 16 \times 28 - 40 \times 11\) | B1 | 2.2a |
| e.g. \(v \equiv -12 \pmod{28} \qquad v \equiv -40 \pmod{28}\) | A1 | 1.1b |
| (3) |
Note the order of marks has changed
M1: forms an equation for 8 in terms of multiples of 28 and 11
B1: Correct equation, allow this mark for a correct unsimplified equation.
A1: Correct solution
Alternative 2
| Scheme | Marks | AO |
|---|---|---|
| \(11v \equiv 8 \pmod{28} \Rightarrow 44v \equiv 32 \pmod{28} \Rightarrow 11v \equiv 8 \pmod{7}\) | B1 | 1.1b |
| \(v \equiv 11^5 \times 8 \pmod{7} \Rightarrow \{v \equiv 2 \pmod{7}\}\) | M1 | 1.1b |
| \(v \equiv 16 \pmod{28}\) | A1 | 2.2a |
| (3) |
B1: Correct equation
M1: Uses Fermat’s little theorem
A1: Correct solution
Trial and error approach
(d) – likely to score B0M1A1.
B1: Gives some kind of proof that the solution is unique. E.g. by reference to hcf(11,28) = 1 or trial of every possible value.
M1: Applies trial and improvement method to find one solution.
A1: Correct solution found.
Correct answer stated with no supportive working scores B0M1A1