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