Irreducible elements mod $n$

Question

An element $r \ne 0$ in a ring $R$ is reducible when $r=ab$ with $a,b\in R$, both not units.

An element is irreducible when it is not reducible.

What is known about irreducible elements in the ring $\mathbb Z / n \mathbb Z$?

More specifically:

• How many irreducible elements are there in $\mathbb Z / n \mathbb Z$?

• Is there a characterization of all irreducibles in $\mathbb Z / n \mathbb Z$?

It seems that $\mathbb Z / n \mathbb Z$ has irreducible elements iff $n$ is not squarefree but I don't know a proof.

Here is a table of the number of irreducible elements mod $n$ for $n\le 100$.

$$\small \begin{array}{c} n & 4 & 8 & 9 & 12 & 16 & 18 & 20 & 24 & 25 & 27 & 28 & 32 & 36 & 40 & 44 & 45 & 48 & 49 & 50 & 52 & 54 & 56 & 60 & 63 & 64 & 68 & 72 & 75 & 76 & 80 & 81 & 84 & 88 & 90 & 92 & 96 & 98 & 99 & 100\\ &1 & 2 & 2 & 2 & 4 & 2 & 4 & 4 & 4 & 6 & 6 & 8 & 10 & 8 & 10 & 8 & 8 & 6 & 4 & 12 & 6 & 12 & 8 & 12 & 16 & 16 & 20 & 8 & 18 & 16 & 18 & 12 & 20 & 8 & 22 & 16 & 6 & 20 & 28 \end{array} $$

Answer 1

The characterization is:

$a$ is irreducible mod $n$ iff $\gcd(a,n)=p$ where $p$ is a prime such that $p^2$ divides $n$.

Therefore, the number of irreducible elements mod $n$ is $$F(n)=\sum_{p^2\,|\,n} \varphi \left( \frac np\right)$$

where the sum is taken over primes $p$ such that $p^2$ divides $n$.

Thus, for instance, $$F(12)=\varphi(6)=2\quad \&\quad F(36)=\varphi(18)+\varphi(12)=6+4=10$$

It's not too difficult to prove this from scratch, and a good reference for it can be found in Prime and irreducible elements of the ring of integers modulo n by Jafari and Madadi (also here).