Past exam of the mathematics course of the University of Cambridge / 2019 / ia / Paper 4 / 6E (Numbers and Sets)

The inclusion-exclusion principle states that for finite sets $A_1,\dots ,A_k$,For each prime $p\mid n$, exclude pairs whose two coordinates are divisible by $p$. For a set of distinct prime divisors $p_1,\dots ,p_j$, exactly $n^2/(p_1\cdots p_j{)}^2$ pairs have both coordinates divisible by their product. Inclusion-exclusion therefore gives

The condition $\gcd (a,b,n)=1$ says that the ideal of $\mathbb{Z}$ generated by $a,b,n$ is all of $\mathbb{Z}$. The multi-integer Bezout identity therefore supplies integers $r,s,t$ such thatEquivalently, first apply Bézout's identity to $a,b$ and then to $\gcd (a,b),n$.

Assume $ad\equiv bc(\mathrm{mod}n)$ and choose $r,s$ as in part (b). Put $\lambda =rc+sd$. Multiplying $ra+sb\equiv 1$ by $c$ and using $ad\equiv bc$ givesSimilarly, multiplication by $d$ gives $\lambda b\equiv d(\mathrm{mod}n)$.

Moreover, $\lambda$ is a unit modulo n: if a prime divided both $\lambda$ and $n$, the two congruences would make it divide $c,d,n$, contrary to $(c,d)\in Y$. Thus $R$ means precisely that two pairs differ by multiplication by a unit modulo $n$. Reflexivity, symmetry using ${\lambda }^{-1}$, and transitivity using products of units now show that $R$ is an equivalence relation.

The class of $(1,1)$ isso its size is Euler's totient functionThe 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 \equiv 1(\mathrm{mod}n)$. Hence every equivalence class has size $\phi (n)$. Dividing the answer from part (a) by this size gives