# $p$ is irreducible in $\mathbb Z_n$ if and only if $p^2$ divides $n$.

I'm reading Gallian's Contemporary Abstract Algebra and I came across this question:

Let $$p$$ be a prime divisor of a positive integer $$n$$. Prove that $$p$$ is irreducible in $$\mathbb Z_n$$ if and only if $$p^2$$ divides $$n$$.

Here's my attempt at a proof:

$$(\leftarrow)$$: Suppose that $$p^2\mid n$$ but $$p$$ is reducible in $$\mathbb Z_n$$. That is, $$p \equiv ab \pmod{n}$$ for some non-units $$a,b\in\mathbb Z_n$$. So we can write $$ab = p + kn$$ for some integer $$k$$. This means $$p|a$$ or $$p|b$$. Without loss of generality, we may suppose $$p|a$$, in which case $$p(1) \equiv p(jb) \pmod{n}$$ for some integer $$j$$. I'd like to conclude from this that $$b$$ is a unit but the problem is that $$\mathbb Z_n$$ need not be an Integral Domain, so the cancellation law need not hold.

For the other direction I'm not even sure where to begin.

Any help would be greatly appreciated,

Thanks.

($$\Rightarrow$$): If $$p^2\nmid n$$, then $$(p,\frac{n}{p})=1$$, so there are $$a,b\in\mathbb{Z}$$ such that $$ap+b\frac{n}{p}=1,$$ i.e., $$p=ap^2+bn,$$ hence $$p\equiv ap^2\pmod{n}.$$ Note that both $$ap$$ and $$p$$ are not invertible in $$\mathbb{Z}_n$$, a contradiction.

($$\Leftarrow$$): Suppose $$p\equiv ab\pmod{n}$$ and $$p|a$$, then $$1-ub\equiv 0\pmod{\frac{n}{p}}$$ where $$u=\frac{a}{p}$$. Since $$p|\frac{n}{p}$$, $$1-ub\equiv 0\pmod{p},$$therefore $$(1-ub)^2\equiv 0\pmod{n},$$ i.e., $$1\equiv -b(u^2b-2u)\pmod{n}$$, hence $$b$$ is a unit.

Lemma: If $$a, b, c \in \mathbb{Z}^+$$, $$\gcd(a, b) = 1$$ and $$a|bc$$, then $$a|c$$.

Suppose first that $$p^2|n$$. Let $$p = bc$$ in $$\mathbb Z_n$$. Suppose that $$p|b$$, then $$p\not \mid c$$. Otherwise $$p^2|bc$$. Then $$\exists k ,s, r \in \mathbb{Z}$$ such that $$p^2s = bc = p + kn = p + kp^2r$$. In particular, $$p^2|p$$, which is impossible.

Let $$d := \gcd(c, n)$$, then $$\gcd(p, d) = 1$$ by the argument above.

Since $$d|bc$$, $$d|p + kp^2r = p(1 + kpr)$$. By our Lemma, $$d|1 + kpr$$. Similarly, $$d|n = p^2r$$ gives that $$d|r$$. Putting these two equalities together, one get $$d|1$$. Hence $$d = 1$$ and $$c$$ is a unit.

Conversely, let $$p$$ be an irreducible and suppose for contradiction that $$p^2\not \mid n$$. Then $$p \not \mid \frac{n}{p}$$. In particular, $$\gcd(p, \frac{n}{p}) = 1$$. Hence $$\exists a, b \in \mathbb{Z}$$ s.t $$ap + bn/p = 1$$. ie, $$ap^2 + bn = 1$$. Then we have $$p(ap + bk) = 1$$, where $$n = pk$$ for some $$k$$. Since $$p$$ is not invertible in $$\mathbb Z_n$$, this is a contradiction.

• In $\mathbb Z_n$ the elements are residue classes modulo $n$, not numbers. I suggest to write $p\equiv bc\bmod n$. Jun 5, 2021 at 7:01