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