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

Printable View

August 30th 2009, 07:10 PM
Last_Singularity

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

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

So I managed to prove that: if $n$ is not prime, then $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 $n$ is prime, i.e. - $gcd(a,n)=1$ , then for all $a \in \mathbb{Z}_n$ , $a$ has an inverse mod n? Thanks!
August 30th 2009, 07:41 PM
ynj

Quote:

Originally Posted by Last_Singularity

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

So I managed to prove that: if $n$ is not prime, then $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 $n$ is prime, i.e. - $gcd(a,n)=1$ , then for all $a \in \mathbb{Z}_n$ , $a$ has an inverse mod n? Thanks!

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

$\gcd (a,n) = 1 \ \Leftrightarrow \ ax + ny = 1$ for some $x, y \in \mathbb{Z}$

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

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