1
$\begingroup$

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.

  • 0
    Yes. You may proceed.2012-01-03

1 Answers 1

6

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'|. 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.

  • 0
    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.2012-01-04