# Prime elements in $\mathbb{Z}/n\mathbb{Z}$

I'm tring to determine the prime elements in the ring $\mathbb{Z}/n\mathbb{Z}$.

-
Consider: Prime ideals are generated by prime elements, and the factor of a ring with a prime ideal is an integral domain (in the commutative case, which this is). So, what are the ideals of $\mathbb{Z}/n\mathbb{Z}$, and which of them produce factor rings with no zero divisors? –  Kirk Boyer Aug 31 '12 at 20:02

Every ideal of $\mathbb{Z}/n\mathbb{Z}$ is of the form $m\mathbb{Z}/n\mathbb{Z}$, where $m$ is a divisor of $n$. And its residue ring is isomorphic to $\mathbb{Z}/m\mathbb{Z}$. Hence a prime ideal of $\mathbb{Z}/n\mathbb{Z}$ is of the form $p\mathbb{Z}/n\mathbb{Z}$, where $p$ is a prime divisor of $n$. Hence every prime element of $\mathbb{Z}/n\mathbb{Z}$ is of the form $p$ (mod $n$), where $p$ is a prime divisor of $n$.

-
Maybe I have this wrong, but I think it is the elements $m$ mod $n$ s.t $\frac{n}{m}$ is a prime divisor of $n$ –  Belgi Aug 31 '12 at 20:21
@Makoto Kato: This seems to be an example of when prime ideals are maximal in a principal ring (not a PID). Can you give a good example of when prime ideals fail to be maximal in a principal ring? Thanks. –  Isaac Solomon Aug 31 '12 at 20:33
@IsaacSolomon - $\langle 0 \rangle$ is prime but not maximal, this is the only example in a principal ring as far as I remember –  Belgi Aug 31 '12 at 20:34
Ah, silly me. Thanks for pointing that out. –  Isaac Solomon Aug 31 '12 at 20:36

The following is the same as the nice answer by Makoto Kato. It differs by not using the word ideal, and by being much longer, and harder to follow. So what's the point? Perhaps it can serve as a bridge to the more abstract point of view to someone who has seen some elementary number theory.

A prime element in a commutative ring is usually defined to be a non-zero non-unit object $q$ such that if $q$ divides $ab$ then $q$ divides $a$ or $q$ divides $b$.

Think of the elements of the ring as being the numbers $0$ to $n-1$ under addition and multiplication modulo $n$. Let $q \ne 0$, and let $d=\gcd(q,n)$. For primeness we must have $d \gt 1$, else $q$ is a unit.

If $d$ is an ordinary prime, then $q$ is a prime in our quotient ring. For suppose there is an $x$ such that $qx\equiv ab\pmod{n}$. Since $d$ is an ordinary prime, and $d$ divides $q$ and $n$, it divides $ab$, so it divides one of $a$ and $b$, say $a$. But then $d$ divides $a$ in our quotient ring.

If $d$ is not an ordinary prime, let $d=st$, where $s \gt 1$, $t\gt 1$. Clearly $d$ divides $st$. But it divides neither $s$ nor $t$ in our quotient ring. To show it does not divide $s$, suppose to the contrary that there is an $x$ such that $dx\equiv s\pmod{n}$. Then $d$ divides $s$ in the ordinary sense, which is impossible.

-
Hint $\rm\:\ (p,n) = 1\:\Rightarrow\:p\:$ is a unit in $\rm\: \Bbb Z/n.\:$ Else $\rm\:p\:|\:n\:$ therefore
$$\rm\: p\:|\: ab\ in\ \Bbb Z/n\:\Rightarrow\: pq = ab + kn\ in\ \Bbb Z\:\Rightarrow\:p\:|\:ab\ in\ \Bbb Z\:\Rightarrow\:p\:|\:a\,\ or\,\ p\:|\:b\ in\ \Bbb Z,\ so\ also\ in\ \Bbb Z/n$$