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!