= Solution
The class of $(1,1)$ is
$$
\{(\lambda,\lambda):\lambda\in(\mathbb Z/n\mathbb Z)^\times\},
$$
so its size is <Euler's totient function>
$$
\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right).
$$
The unit group acts freely on every pair in $Y$: if $\lambda a\equiv a$ and $\lambda b\equiv b$, multiplying the <Bezout identity> by $\lambda-1$ gives $\lambda\equiv1\pmod n$. Hence every equivalence class has size $\varphi(n)$. Dividing the answer from part (a) by this size gives
$$
\boxed{\frac{|Y|}{\varphi(n)}
=n\prod_{p\mid n}\frac{1-p^{-2}}{1-p^{-1}}
=n\prod_{p\mid n}\left(1+\frac1p\right)}.
$$
Back to article page
