State the inclusion-exclusion principle.

Let $n \geqslant 2$ be an integer. Let $X=\{0,1,2, \ldots, n-1\}$ and

$$Y=\left\{(a, b) \in X^{2} \mid \operatorname{gcd}(a, b, n)=1\right\}$$

where $\operatorname{gcd}\left(x_{1}, \ldots, x_{k}\right)$ is the largest number dividing all of $x_{1}, \ldots, x_{k}$. Let $R$ be the relation on $Y$ where $(a, b) R(c, d)$ if $a d-b c \equiv 0(\bmod n)$.

(a) Show that

$$|Y|=n^{2} \prod_{p \mid n}\left(1-\frac{1}{p^{2}}\right)$$

where the product is over all primes $p$ dividing $n$.

(b) Show that if $\operatorname{gcd}(a, b, n)=1$ then there exist integers $r, s, t$ with $r a+s b+t n=1$.

(c) Show that if $(a, b) R(c, d)$ then there exists an integer $\lambda$ with $\lambda a \equiv c(\bmod n)$ and $\lambda b \equiv d(\bmod n)$. [Hint: Consider $\lambda=r c+s d$, where $r, s$ are as in part (b).] Deduce that $R$ is an equivalence relation.

(d) What is the size of the equivalence class containing $(1,1) ?$ Show that all equivalence classes have the same size, and deduce that the number of equivalence classes is

$$n \prod_{p \mid n}\left(1+\frac{1}{p}\right) \text {. }$$