(a) (i) By considering Euclid's algorithm, show that the highest common factor of two positive integers $a$ and $b$ can be written in the form $\alpha a+\beta b$ for suitable integers $\alpha$ and $\beta$. Find an integer solution of

$$15 x+21 y+35 z=1$$

Is your solution unique?

(ii) Suppose that $n$ and $m$ are coprime. Show that the simultaneous congruences

$$\begin{array}{ll} x \equiv a & (\bmod n) \\ x \equiv b & (\bmod m) \end{array}$$

have the same set of solutions as $x \equiv c(\bmod m n)$ for some $c \in \mathbb{N}$. Hence solve (i.e. find all solutions of) the simultaneous congruences

$$\begin{array}{ll} 3 x \equiv 1 & (\bmod 5) \\ 5 x \equiv 1 & (\bmod 7) \\ 7 x \equiv 1 & (\bmod 3) \end{array}$$

(b) State the inclusion-exclusion principle.

For integers $r, n \geqslant 1$, denote by $\phi_{r}(n)$ the number of ordered r-tuples $\left(x_{1}, \ldots, x_{r}\right)$ of integers $x_{i}$ satisfying $1 \leqslant x_{i} \leqslant n$ for $i=1, \ldots, r$ and such that the greatest common divisor of $\left\{n, x_{1}, \ldots, x_{r}\right\}$ is 1 . Show that

$$\phi_{r}(n)=n^{r} \prod_{p \mid n}\left(1-\frac{1}{p^{r}}\right)$$

where the product is over all prime numbers $p$ dividing $n$.