Prove that for every number in ${1, 2, ..., p-1}$ there exists another within the same set such that their product is congruent to $1$ $mod$ $p$.

Question

Let $A = \{1, 2, 3, ..., p-1\}$ where $p$ is prime. Prove that for any $k \in A$ there exists another $l \in A$ such that $kl \equiv 1\pmod p$.

Here's an example where $p = 5$:

$1 \times 1 \equiv 1\pmod 5$

$2 \times 3 \equiv 1\pmod 5$

$4 \times 4 \equiv 1\pmod 5$

The solutions for $k = 1$ and $k = p-1$ are obvious, but I can't find a general formula for the other ones.

Answer 1

Consider the $p-1$ products $kl$ as $l$ ranges from $1$ to $p-1$. Clearly none of them is a multiple of $p$, and if none of them is congruent to $1$ either, then two of them must have the same residue, by the Pigeonhole Principle. Can you see why that is impossible?

Answer 2

Application of Bezout's Identity.

For any number $0<n<p$ then $gcd(n,p)=1$.

There exist $a,b\in \mathbb Z$ such that $an+bp=1$.

Now take the least positive residue (say $n_0$) of $a$ modulo $p$. Where $0<n_0<p$ and $a=n_0+kp$ for some $k\in \mathbb Z$. $\therefore an+bp=1\implies (n_0+kp)n+bp=1\implies n_0\cdot n+p(nk+b)=1$

There fore $p|n_0n-1$$\implies $ $n_0n \equiv 1\pmod p $

Answer 3

This is the well-known multiplicative group of units $\Bbb Z_p^*$ of $\Bbb Z_p$. Each of $k\in\{1,2,\dots,p-1\}$ is relatively prime to $p$. Thus by Bezout there exist $x,y$ such that $xk+yp=1$. Given such a solution $(x,y)$ to that linear diophantine equation, any other $(x+lp,y-kl)$ is also a solution. Take $l$ such that $x+lp\in\{1,2,\dots,p-1\}$. This is possible because equivalence $\bmod p$ is an equivalence relation on $\Bbb Z$. There are only $p$ congruence classes by the division algorithm.

Answer 4

Consider the powers of $k$. Since there are only finitely many residue classes mod $p$, there must be two powers that are congruent, say $k^m\equiv k^n$ mod $p$, with $m\lt n$. Rewriting this as $k^m(k^{n-m}-1)\equiv0$ mod $p$, and noting that $p\not\mid k$, we see that $k^{n-m}\equiv1$ mod $p$. Now let $\ell\equiv k^{n-m-1}$ mod $p$ and observe that $k\ell\equiv kk^{n-m-1}=k^{n-m}\equiv1$ mod $p$.

In point of fact, Fermat's Little Theorem tells us that $k^{p-1}\equiv1$ mod $p$ if $p\not\mid k$, so one always has $\ell\equiv k^{p-2}$ as the inverse of $k$. But that's a deeper theorem than what we've shown here.