## Question 3(a):

| Working/Answer | Mark | Guidance |
|---|---|---|
| $234 = 2 \times 96 + 42$ | M1 | Starts Euclidean algorithm with $234 = p \times 96 + q$ |
| $96 = 2 \times 42 + 12$; $\quad 42 = 3 \times 12 + 6$; $\quad 12 = 2 \times 6 (+0)$ | M1 | Continues until remainder zero reached |
| Hence $h = 6$ | A1 | Deduces correct HCF from correct working |

---

## Question 3(b):

| Working/Answer | Mark | Guidance |
|---|---|---|
| Using back substitution: $6 = 42 - 3 \times 12$ | M1 | Begins back substitution by rearranging equation with least positive remainder |
| $= 42 - 3(96 - 2\times 42) = 7\times 42 - 3\times 96$ $= 7\times(234 - 2\times 96) - 3\times 96$ | dM1 | Completes the process |
| $= 7\times 234 - 17\times 96 \quad$ (so $a=7$ and $b=-17$) | A1 | Correct values of $a$ and $b$ identified |

---

## Question 3(c):

**Main Scheme:**

| Working/Answer | Mark | Guidance |
|---|---|---|
| As 6 divides 36, congruence equivalent to $16x \equiv 6 \pmod{39}$ | B1 | Deduces correct equivalent congruence |
| From (b): $1 = 7\times 39 - 17\times 16$, so $-17$ (or 22) is multiplicative inverse of 16 mod 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 | Chooses suitable strategy using their value of $b$ |
| $22\times 16x \equiv 22\times 6\pmod{39}$ or $-17\times 16x \equiv -17\times 6\pmod{39}$; **or** $5\times 8x \equiv 5\times 3\pmod{39}$ | M1 | Applies multiplicative inverse to reach $x \equiv \ldots\pmod{39}$ |
| $x \equiv 132 \equiv 15\pmod{39}$ | A1 | Accept just 15 |
| Solution is $x\equiv 15\pmod{39}$ or $x \equiv 15, 54, 93, 132, 171, 210\pmod{234}$ | A1 | Must indicate modulus; do not accept just 15 with no modulus indicated |

---

**Way 2:**

| Working/Answer | Mark | Guidance |
|---|---|---|
| From (b): $-17$ (or 22) is multiplicative inverse of 96 mod 239 | B1 | Deduces multiplicative inverse of 96 |
| $-17\times 96x \equiv -17\times 36\pmod{234}$ or $6x\equiv -612\pmod{234}$ | M1 | Multiplies by multiplicative inverse of 96 |
| As 6 divides: $6x\equiv 90\pmod{234}$ to reach $x\equiv\ldots\pmod{39}$; or $6x\equiv -612\pmod{234}$ to reach $x\equiv\ldots\pmod{39}$ | M1 | Reaches $x\equiv\ldots\pmod{39}$ |
| $x\equiv 15\pmod{39}$ | A1 | Accept just 15 |
| $x\equiv 15\pmod{39}$ or $x\equiv 15,54,93,132,171,210\pmod{234}$ | A1 | Full solution with modulus |

---

**Way 3:**

| Working/Answer | Mark | Guidance |
|---|---|---|
| $16x\equiv 6\pmod{39}$ | B1 | Correct equivalent congruence |
| $5\times 16x \equiv 5\times 6\pmod{39} \Rightarrow 2x\equiv 30\pmod{39}$ | M1 | Attempts to reduce coefficient by multiplying |
| $20\times 2x \equiv 20\times 30\pmod{39} \Rightarrow x\equiv 15\pmod{39}$ | M1 | Reaches $x\equiv\ldots\pmod{39}$ from succession of multiples |
| $x\equiv 15\pmod{39}$ | A1 | Accept just 15 |
| $x\equiv 15\pmod{39}$ or $x\equiv 15,54,93,132,171,210\pmod{234}$ | A1 | Full solution with modulus |

---

**Way 4:**

| Working/Answer | Mark | Guidance |
|---|---|---|
| $16x\equiv 6\pmod{39}$ | B1 | Correct equivalent congruence |
| $16x \equiv 6, 45, 84, 123, \ldots$ | M1 | Works out possibilities for $16x$ to find one divisible by 16 |
| $16x = \ldots, 240$ | M1 | Reaches value of $16x$ that is multiple of 16 |
| $240 = 16\times 15 \Rightarrow x\equiv 15\pmod{39}$ | A1 | Accept just 15 |
| $x\equiv 15\pmod{39}$ or $x\equiv 15,54,93,132,171,210\pmod{234}$ | A1 | Full solution with modulus |

---