If $p$ is prime, then for any integer $m$, $0 < m < p$, there is a unique $n$, $0 < n < p$, such that $mn$ is congruent to $1\pmod p$

Question

So far I know that $1 \bmod p$ will always be $1$ as the lowest $p$ can be is $2$, meaning that $mn \bmod p$ will have to $= 1$. This means either $mn < p$ or $mn = p + 1$.

I've also figured out that to prove the above statement I would need to show the following

• $n$ exists (obviously)
• $n$ is unique
• $0 < n < p$

This is were I get stuck. I can see that this is the case (and show that there is an n such that this is the case,) however, I am having trouble proving that n is unique.

Answer 1

Suppose you have 0 < n < p and 0 < n' < p such that mn = mn' mod p = 1 mod p. Then you would get that m(n-n') = 0 mod p. But multiply this by n and you get n-n' = 0 mod p. So n - n' is a multiple of p, but -p < n-n' < p so n-n' can only be 0. Thus, we have n = n'

Answer 2

Hint:

Since $p$ is prime and $0<m<p$, $m$ and $p$ are coprime, hence there exists a Bézout's relation $um+vp=1\quad(u,v\in\mathbf Z)$.

Furthermore, all integer solutions of the equation $xm+yp=1$ satisfy the relations $$\begin{cases} x=u+kp\\ y=v-km \end{cases}\quad(k\in\mathbf Z). $$ There remains to show you can find an $x$ s.t. $0<x<p$.

Answer 3

Hint: Consider the map $x \mapsto mx$ in the classes mod $p$. Prove that it is injective. Conclude that it is bijective.