Consider any \(\alpha \in \mathbb{Z_n} \setminus \mathbb{Z_n^*}\) and \(\alpha \ne [0]\). Then we have \(\alpha = [a]\) with \(d := \gcd(a,n) > 1\). Setting \(\beta := [\frac{n}{d}]\), what is \(\alpha \beta\) ?

\[ \begin{aligned} \alpha & \equiv a \equiv a_1 d\pmod n \mspace20pt \text{ for some } a_1 \in \mathbb{Z_n^*}\\ \beta & \equiv \frac{n}{d} \pmod n \\ \alpha \beta & \equiv a_1 d \frac{n}{d} \equiv a_1 n \pmod n \\ \end{aligned} \]

This means \(\alpha \beta\) is a multiple of \(n\). Setting \(\gamma := [0]\), we see that \(\alpha \beta = \alpha \gamma\) but \(\beta \ne \gamma\)! In contrast, if \(d := \gcd(a,n) = 1\), then \(\alpha \beta = \alpha \gamma\) and \(\beta = [n] = [0] = \gamma\). This stresses that in order for the cancellation law to apply in congruences, it requires \(\alpha \in \mathbb{Z_n^*}\).

# posted by rot13(Unafba Pune) @ 10:01 PM