I'm tring to determine the prime elements in the ring $\mathbb{Z}/n\mathbb{Z}$.
Prime elements in $\mathbb{Z}/n\mathbb{Z}$
-
1Consider: 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? – 2012-08-31
3 Answers
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$.
-
0Ah, silly me. Thanks for pointing that out. – 2012-08-31
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$
This is a very special case of a general correspondence principle between prime ideals in a ring R and its quotient rings.