# 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?)

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

• Apart from their existence its also necessary that a be positive and b be negative or else the remainder when divided by n will be "-1" instead of "1" (technically speaking) i.e. not 1 at all right ?
– alex
Jun 26, 2014 at 11:06
• Not at all, if a is negative say a = -b then of course b mod n is not the inverse but I am talking about a mod n, which is the inverse. Let me take an example: m = 3, n = 7. The equation is: (-2)(3) + (1)(7) = 1. -2 mod 7 = 5. 5 is the inverse of 3 modulo 7. Jun 26, 2014 at 11:11

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

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.