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

1. ## 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!

2. 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
then $n=(ax-kn)q+r\Leftrightarrow -axq+(kq+1)n=r\Leftrightarrow -axq\mod n=r$,but $r,which will make contradiction.
The only possible case is $r=0$,so $d|n$
So $d=1$

3. $\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.

,

,

,

,

,

,

,

,

,

,

# prove zn is a field iff n is prime

Click on a term to search for related topics.