# Question 4:

## Part (a):
| Working | Mark | Guidance |
|---------|------|----------|
| $168 = 66 \times 2 + 36$, $66 = 36 \times 1 + 30$, $36 = 30 \times 1 + 6$, $\{30 = 5 \times 6 + 0\}$ | M1 | Attempt at Euclidean algorithm to find gcd of 168 and 66, condone numerical slip |
| Last non-zero remainder is 6, so highest common factor is 6 | A1* | Fully correct application and explains hcf is 6 |

## Part (b):
| Working | Mark | Guidance |
|---------|------|----------|
| $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 | Attempt back substitution; correct expression in just 168 and 66 |
| $\Rightarrow 6 = 168 \times 2 - 66 \times 5$, so $a=2$, $b=-5$ | A1 | Correct values of $a$ and $b$ |

## Part (c):
| Working | Mark | Guidance |
|---------|------|----------|
| $168x + 66y$ always an integer multiple of 6, but 10 is not a multiple of 6, so no integer solutions. Or: $\gcd(168,66)=6$ and $6 \nmid 10$ | B1 | Must refer to 10 not being a multiple of 6 |

## Part (d):
| Working | Mark | Guidance |
|---------|------|----------|
| From (b) deduce $1 = 28 \times 2 - 11 \times 5$ | B1 | Uses result in (b), divides through by 6 |
| Hence $8 \times 11 \times (-5) \equiv -5 \times 8 \pmod{28}$ | M1 | Multiplies through by 8 |
| $v \equiv -40 \equiv 16 \pmod{28}$ | A1 | Accept $-40\pmod{28}$ or $16\pmod{28}$ |

**Alternative 1:**
| Working | Mark | Guidance |
|---------|------|----------|
| Forms $8 = 28A + 11B$ | M1 | |
| e.g. $8 = 5\times28 - 12\times11$ or $8=16\times28-40\times11$ | B1 | Correct equation |
| $v \equiv -12\pmod{28}$ or $v\equiv-40\pmod{28}$ | A1 | |

**Alternative 2:**
| Working | Mark | Guidance |
|---------|------|----------|
| $11v \equiv 8\pmod{28} \Rightarrow 44v \equiv 32\pmod{28} \Rightarrow 11v \equiv 8\pmod{7}$ | B1 | |
| $v \equiv 11^5 \times 8\pmod{7} \Rightarrow \{v \equiv 2\pmod{7}\}$ | M1 | Uses Fermat's little theorem |
| $v \equiv 16\pmod{28}$ | A1 | |

---