1
$\begingroup$

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

$\endgroup$

3 Answers 3

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$
    – alex
    Jun 26, 2014 at 11:06
  • $\begingroup$ 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. $\endgroup$
    – Wonder
    Jun 26, 2014 at 11:11
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ See also here. $\endgroup$ Sep 12, 2020 at 18:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .