How to prove the existence of inverse in modulo

Question

Let n be a prime number

Z is set of Integer and Zn indicate equvalence class for n

[

for example, if n=3, Z={[0], [1], [2]}.

Because 1mod3 2mod3 3mod3 4mod3 .... = 0 1 2 0 1 2 ......

]

Show that m inverse always exist which satisfy m inverse * m=[1] in Zn

[

for example if m=10 and n=7, m inverse is 5 because

10*5mod7=1

]

Answer 1

If you want the inverse of $a$, then look at the classes of $a\cdot1, a\cdot 2,...,a\cdot (n-1)$. If two of them, $a\cdot i$ and $a\cdot j$ with $i>j$, were the same, then $a(i-j)$ would be divisible by $n$. But since $a$ is not divisible by $n$, $0<i-j<n$ is. Contradiction.

Also, none of them is the class of $0$, because if $ai$ is divisible by $n$, then $i$ should be divisible by $n$, which is not because $0<i<n$.

Therefore those classes are $n-1$ different non-zero classes. One of them must be the class of $1$.

Answer 2

You can use Bezout's identity:

Let $m\in \{1,2,3,...,n\}$. Since $n$ is prime, then $gcd(m,n)=1$.

Using Bezout's identity, there exists integers $x,y$ such that $mx+ny=1 \implies mx=-ny+1$.

You can then take the $n$ modulo of both sides.