# Pairing off residues modulo $p$ with their inverses

I'm stumbling over this interesting proof:

Show that if $p$ is a prime number, the positive integers less than $p$, except $1$ and $p-1$, can be split into $(p-3)\over2$ pairs of integers such that each pair consists of integers that are inverses of each other modulo $p$.

Any help will be appreciated. Thanks.

-
Shah: Assuming I write to answer, I'm unable to assess what background to assume from the reader. Are you familiar with the basic properties of congruence notation for modular arithmetic? –  Srivatsan Jan 3 '12 at 3:54
Yes. You may proceed. –  Shah Tamzid Jan 3 '12 at 3:58

If $1 \le a \le p-1$, there is a unique $b$ with $1\le b\le p-1$ such that $ab\equiv 1 \pmod {p}$. This $b$ will be called the inverse of $a$ modulo $p$. The uniqueness follows from the fact that if $ab\equiv 1 \pmod p$ and $ab'\equiv 1\pmod p$, than $a(b-b')\equiv 0 \pmod p$. But if a prime divides a product, it divides at least one of the terms. Since $1\le a\le p-1$, $p$ cannot divide $a$. So $p$ divides $b-b'$. Since $1\le b,b' \le p-1$, we have $|b-b'|<p-1$. It follows that $b=b'$.

The existence is a bit more complicated. The easiest approach from first principles is to look at $a\cdot 1$, $a\cdot 2$, $\dots$, $a\cdot(p-1)$. Consider the remainders when these are divided by $p$. One shows that none of the remainders is $0$, and that all the remainders are different. That means that the remainders are $1, 2,\dots,p-1$ in some order. In particular, one of the remainders is $1$. So for some $x$ in the interval $1\le x\le p-1$, $x\cdot a$ has remainder $1$ on division by $p$. This $x$ is our desired inverse.

Once existence and uniqueness are established, the remaining components are not difficult.

(i) The inverse of the inverse of $a$ is $a$. This follows immediately from the definition.

(ii) The only numbers in the interval $1 \le a \le p-1$ which are their own inverse are $1$ and $p-1$. To prove (ii), suppose that $x^2 \equiv 1 \pmod p$. Then $p$ divides $x^2-1$, that is, $p$ divides $(x-1)(x+1)$. So $p$ divides $x-1$ (meaning in our case that $x=1$) or $p$ divides $x+1$ (meaning in our case that $x=p-1$.)

Comment: The pairing you referred to has an immediate attractive consequence. Look at $(p-1)!$. Divide the $p-1$ numbers in this product into mutually inverse pairs, leaving $1$ and $p-1$ alone. The product of pairs is congruent to $1$ modulo $p$. Thus $(p-1)!\equiv 1\cdot (p-1)\pmod{p}$. Equivalently, $(p-1)!\equiv -1\pmod{p}$. This is Wilson's Theorem. Wilson merely conjectured this result. The result was already known much earlier by Leibniz. The first proof, due to Lagrange, used relatively complicated properties of polynomials. The simplicity of the above proof testifies to the power of Gauss's notion of congruence.

-
+1, I don't have to write an answer now, thanks! :-) The existence of the inverse also follows from Bézout's lemma; of course, this only pushes the burden of proof somewhere else. –  Srivatsan Jan 3 '12 at 4:47
Thanks a lot for the elegant, educative and informative responses. –  Shah Tamzid Jan 3 '12 at 23:21
You are welcome. It may be useful to take a modest-sized prime $p$ and actually do the pairing explicitly. In looking for the $b$ that pairs with $a$, there is no need to use a general technique, though there is one, namely the Extended Euclidean Algorithm. Just hunt for the $b$. With say $p=13$ or $p=17$, you will soon find it. –  André Nicolas Jan 4 '12 at 0:57