Proving existence of multiplicative inverses for certain sets with multiplication defined modulo $ n $ Let $ Z_n=\{0,1,2...n-1\}$ and multiplication be defined modulo $n$ . I have to find the $n$s for which all non zero elements of  $Z_n$ have a "multiplicative" inverse from within $Z_n$. I conjectured that all prime $n$s fit his category and its easy to show that only primes can do so ( as it is impossible for any non $1$ factors of $n$ to have an inverse). But how can I show that ALL primes fit this category ?(And if they dont then how do I find out which $n$s do?)
 A: Suppose n is a prime and m is an element from $Z_n$. gcd(m, n) = 1, so there exist a and b so that am + bn = 1 (why? just see the working of Euclid's algorithm). (a mod n) is then the inverse of m from $Z_n$.
A: The numbers you are looking for are those $a\in \{0,1,\cdots,n-1\}$ for which $\gcd(a,n)=1$.
In fact, for any such number, it is well known that you can find integers $r$ and $s$ such
that $$ar+ns=1.$$
Now reducing ($\mod n$) both sides of the above equality, you get
$$\overline{a}\cdot \overline{r}=\overline{1}$$
That is,  $(r \mod n) \in \{0,1,\cdots,n-1\}$  is the multiplicative inverse of $a\in \{0,1,\cdots,n-1\}$.
A: Hint $ $ The following may help to comprehend, step-by-step, why the equivalence holds, by using  $\,\rm\color{#c00}{P} = $ Pigeonhole principle (where all congruence arithmetic is $\!\bmod n$)
$$\begin{align} &\color{#0a0}{ab\equiv 1}\, \ {\rm for\ some}\ b \ \  [\![\text{ i.e. $\,a\,$  is } {\bf invertible}\,]\!]\\[.4em]
\iff\ &a\mapsto ax\ \ {\rm is\,\ onto\ \ \ \ \ Proof\!:\ (\Leftarrow)\ \ clear.\ \ (\Rightarrow)\ \ } c \equiv a(bc)\\[.4em]   
\smash[t]{\overset{\rm\color{#c00}P}\iff}\ \ & a\mapsto ax\ \ \rm is\,\ 1\!-\!1 \ \ \ \ \ [\![\,\text{ i.e. $\,a\,$  is } {\bf cancellable}\!:\ ax\equiv ay\,\Rightarrow\, x\equiv y\,]\!]\\[.4em]  
\iff\ & ax\equiv 0\Rightarrow x\equiv 0\ \ \ \ [\![\,\text{ i.e. $\,a\,$ is }{\bf\text{not a zero-divisor }} {\rm i.e.}\ \ker(a\mapsto ax) = 0\,]\!]\\[.4em] 
\iff\ &\  \color{#90f}{n\mid ax\,\Rightarrow\  n\mid x}
\end{align}$$
So, by above, all $\,a\not\equiv0\,$ are $\:\!\color{#0a0}{\rm invertible}\bmod n$ $\iff [n\nmid a,\,\color{#90f}{n\mid ax\,\Rightarrow\, n\mid x}]\!\iff n$ is prime, by Euclid's Lemma.
