A2 June 2024 Q3
3.
In this question you must show all stages of your working.
Solutions relying on calculator technology are not acceptable.
| Scheme | Marks | AO |
|---|---|---|
| \(234 = 2 \times 96 + 42\) | M1 | 1.1b |
| \(96 = 2 \times 42 + 12; \quad 42 = 3 \times 12 + 6; \quad 12 = 2 \times 6 (+0)\) | M1 | 1.1b |
| Hence \(h = 6\) | A1 | 2.2a |
| (3) |
Notes
M1: Starts the process of using the algorithm, with attempt at \(234 = p \times 96 + q\).
M1: Continues the process until remainder zero is reached.
A1: Deduces the correct highest common factor from correct work.
| Scheme | Marks | AO |
|---|---|---|
| Using back substitution \(6 = 42 - 3 \times 12\) | M1 | 1.1b |
| \(= 42 - 3(96 - 2 \times 42) = 7 \times 42 - 3 \times 96\) \(= 7 \times (234 - 2 \times 96) - 3 \times 96\) | dM1 | 1.1b |
| \(= 7 \times 234 - 17 \times 96\) (so \(a = 7\) and \(b = -17\)) | A1 | 1.1b |
| (3) |
Notes
M1: Begins the process of back substitution by rearranging their equation with least positive remainder.
dM1: Completes the process.
A1: Correct expression or values of \(a\) and \(b\) identified.
| Scheme | Marks | AO |
|---|---|---|
| As 6 divides 36 the congruence is equivalent to \(16x \equiv 6 \pmod{39}\) | B1 | 2.2a |
| From (b) we deduce \(1 = 7 \times 39 - 17 \times 16\) so \(-17\) (or 22) is a multiplicative inverse of 16 modulo 39 or \(16x \equiv 6 \pmod{39} \Rightarrow 2 \times 8x \equiv 2 \times 3 \pmod{39} \Rightarrow 8x \equiv 3 \pmod{39}\) Finds multiplicative inverse of 8 e.g. \(1 = 5 \times 8 - 39\) | M1 | 3.1a |
| Hence \(22 \times 16x \equiv 22 \times 6 \pmod{39}\) or \(-17 \times 16x \equiv -17 \times 6 \pmod{39}\) or Hence \(5 \times 8x \equiv 5 \times 3 \pmod{39}\) Leading to \(x \equiv \ldots \pmod{39}\) | M1 | 1.1b |
| \(x \equiv 132 \equiv 15 \pmod{39}\) Accept just 15 | A1 | 1.1b |
| So the solution is \(x \equiv 15 \pmod{39}\) or \(x \equiv 15, 54, 93, 132, 171 \text{ or } 210 \pmod{234}\) | A1 | 2.3 |
| (5) | ||
| (11 marks) |
Notes
B1: Deduces the correct equivalent congruence.
M1: Chooses a suitable strategy to solve the reduced congruence. May use multiplicative inverse as per scheme or see alts for some variations, must be using their value for \(b\)
M1: Applies their multiplicative inverse to reach \(x \equiv \ldots \pmod{39}\)
In the alternative it is for reaching \(x \equiv \ldots \pmod{39}\) from a succession of multiples.
A1: For 15 as a solution, need not have the \((\text{mod } 39)\). (Accept one correct solution if an alternative method is used.
A1: For stating the solution is \(15 \pmod{39}\) as the answer (not just in working) or for listing all the solutions modulo 234. Either way of expressing the answer is fine (single answer mod 39, or all 6 mod 234), but must realise it is more than just the 15, so do not accept just 15 with no indication of the modulus being considered.
ISW if they achieve the correct answer and then try to list solutions
SPECIAL CASE: B1 For one correct value of \(x\) found
(c) Way 2
| Scheme | Marks | AO |
|---|---|---|
| From (b) we deduce \(1 = 7 \times 39 - 17 \times 16\) so \(-17\) (or 22) is a multiplicative inverse of 96 modulo 234 | B1 | 2.2a |
| Hence \(-17 \times 96x \equiv -17 \times 36 \pmod{234}\) or \(6x \equiv -612 \pmod{234}\) | M1 | 3.1a |
| As 6 divides the congruence \(6x \equiv 90 \pmod{234}\) to reach \(x \equiv \ldots \pmod{39}\) As 6 divides the congruence \(6x \equiv -612 \pmod{234}\) to reach \(x \equiv \ldots \pmod{39}\) | M1 | 1.1b |
| \(x \equiv 15 \pmod{39}\) Accept just 15 | A1 | 1.1b |
| So the solution is \(x \equiv 15 \pmod{39}\) or \(x \equiv 15, 54, 93, 132, 171 \text{ or } 210 \pmod{234}\) | A1 | 2.3 |
| (5) |
B1: Deduces the multiplicative inverse of 96
M1: Multiplies through by the multiplicative inverse of 96
M1: For using reaching \(x \equiv \ldots \pmod{39}\).
A1: For 15 as a solution, need not have the \((\text{mod } 39)\). (Accept one correct solution if an alternative method is used.
A1: For stating the solution is \(15 \pmod{39}\) as the answer (not just in working) or listing all the solutions modulo 234. As per main scheme do not accept just 15 with no indication of the modulus being considered.
(corrected from the printed mark scheme: the first line of this method says “modulo 239”; the modulus is 234)
(c) Way 3
| Scheme | Marks | AO |
|---|---|---|
| As 6 divides 36 the congruence is equivalent to \(16x \equiv 6 \pmod{39}\) | B1 | 2.2a |
| \(5 \times 16x \equiv 5 \times 6 \pmod{39} \Rightarrow 2x \equiv 30 \pmod{39}\) | M1 | 3.1a |
| \(\Rightarrow 20 \times 2x \equiv 20 \times 30 \pmod{39} \Rightarrow 1x \equiv 15 \pmod{39}\) | M1 | 1.1b |
| \(x \equiv 15 \pmod{39}\) Accept just 15 | A1 | 1.1b |
| So the solution is \(x \equiv 15 \pmod{39}\) or \(x \equiv 15, 54, 93, 132, 171 \text{ or } 210 \pmod{234}\) | A1 | 2.3 |
| (5) |
B1: Deduces the correct equivalent congruence.
M1: Tries multiplying by various numbers in an attempt to reduce the coefficient to 1. One example shown above but others are possible. Allow the M for an attempt at starting such a process.
M1: For using reaching \(x \equiv \ldots \pmod{39}\) from a succession of multiples.
A1: For 15 as a solution, need not have the \((\text{mod } 39)\). (Accept one correct solution if an alternative method is used.
A1: For stating the solution is \(15 \pmod{39}\) as the answer (not just in working) or listing all the solutions modulo 234. As per main scheme do not accept just 15 with no indication of the modulus being considered.
(c) Way 4
| Scheme | Marks | AO |
|---|---|---|
| As 6 divides 36 the congruence is equivalent to \(16x \equiv 6 \pmod{39}\) | B1 | 2.2a |
| So \(16x \equiv 6, 45, 84, 123, \ldots\) | M1 | 3.1a |
| \(16x \equiv \ldots, 240\) | M1 | 1.1b |
| \(240 = 16 \times 15 \Rightarrow x \equiv 15 \pmod{39}\) Accept just 15 | A1 | 1.1b |
| So the solution is \(x \equiv 15 \pmod{39}\) or \(x \equiv 15, 54, 93, 132, 171 \text{ or } 210 \pmod{234}\) | A1 | 2.3 |
| (5) |
B1: Deduces the correct equivalent congruence.
M1: Works out the possibilities for \(16x\) to try and find one that is divisible by 16. Look for the first few evaluated.
M1: For reaching a value for \(16x\) that is a multiple of 16.
A1: For 15 as a solution, need not have the \((\text{mod } 39)\). (Accept one correct solution if an alternative method is used.
A1: For stating the solution is \(15 \pmod{39}\) as the answer (not just in working) or listing all the solutions modulo 234. As per main scheme do not accept just 15 with no indication of the modulus being considered.
NB For students who try dividing though by 12 to get \(8x \equiv 3 \pmod{234}\) a maximum of B0M1M0A0A0 is possible for attempt to reach \(x \equiv \ldots \pmod{234}\) via valid method.