# Integers mod n is a field if and only if n is prime

• Aug 30th 2009, 07:10 PM
Last_Singularity
Integers mod n is a field if and only if n is prime
Define $\displaystyle \mathbb{Z}_n$ as the set of integers mod n: $\displaystyle \{0,1,...,n-1\}$ which is endowed with the operations $\displaystyle a+b = (a+b) \mod n$ and $\displaystyle a \cdot b = ab \mod n$. It appears that this ring with identity is a field if and only if $\displaystyle n$ is prime. The key is whether or not elements of $\displaystyle \mathbb{Z}_n$ have inverses (they don't when $\displaystyle n$ is composite).

So I managed to prove that: if $\displaystyle n$ is not prime, then $\displaystyle a \in \mathbb{Z}_n$ has no inverse mod n. Now I am having trouble going the opposite way: how do I show that if $\displaystyle n$ is prime, i.e. - $\displaystyle gcd(a,n)=1$, then for all $\displaystyle a \in \mathbb{Z}_n$, $\displaystyle a$ has an inverse mod n? Thanks!
• Aug 30th 2009, 07:41 PM
ynj
Quote:

Originally Posted by Last_Singularity
Define $\displaystyle \mathbb{Z}_n$ as the set of integers mod n: $\displaystyle \{0,1,...,n-1\}$ which is endowed with the operations $\displaystyle a+b = (a+b) \mod n$ and $\displaystyle a \cdot b = ab \mod n$. It appears that this ring with identity is a field if and only if $\displaystyle n$ is prime. The key is whether or not elements of $\displaystyle \mathbb{Z}_n$ have inverses (they don't when $\displaystyle n$ is composite).

So I managed to prove that: if $\displaystyle n$ is not prime, then $\displaystyle a \in \mathbb{Z}_n$ has no inverse mod n. Now I am having trouble going the opposite way: how do I show that if $\displaystyle n$ is prime, i.e. - $\displaystyle gcd(a,n)=1$, then for all $\displaystyle a \in \mathbb{Z}_n$, $\displaystyle a$ has an inverse mod n? Thanks!

This is because in number theory, if $\displaystyle \gcd (a,n)=1$, then there exists $\displaystyle x,ax\mod n=1$.
if not, we suppose $\displaystyle d=\min\{ax-kn|ax-kn>0\},d>1$.now we will show that $\displaystyle d|n$,which is impossible.
suppose $\displaystyle ax-kn=d$
Suppose $\displaystyle n=dq+r,0<r<d$
then $\displaystyle n=(ax-kn)q+r\Leftrightarrow -axq+(kq+1)n=r\Leftrightarrow -axq\mod n=r$,but $\displaystyle r<d$,which will make contradiction.
The only possible case is $\displaystyle r=0$,so $\displaystyle d|n$
So $\displaystyle d=1$
• Aug 30th 2009, 07:42 PM
o_O
$\displaystyle \gcd (a,n) = 1 \ \Leftrightarrow \ ax + ny = 1$ for some $\displaystyle x, y \in \mathbb{Z}$

which by definition means: $\displaystyle ax \equiv 1 \ (\text{mod } n)$

The least residue of $\displaystyle x$ is then a solution and is therefore the inverse.