# Inverse product of residues of a prime

• Sep 9th 2009, 02:05 PM
Bingk
Inverse product of residues of a prime
Hi :)

I'm trying to prove that $\displaystyle \prod_{i=1}^{p-1}\Bigl(\displaystyle\frac{1}{i}\Bigr) \equiv -1 \ (mod \ p)$

The way I see it, the inverse of $\displaystyle 1$ is itself, and from $\displaystyle 2$ to $\displaystyle p-2$, the inverses are paired up, so we are left with the inverse of $\displaystyle p-1$ which is itself.

So, we have that $\displaystyle \prod_{i=1}^{p-1}\Bigl(\displaystyle\frac{1}{i}\Bigr) \equiv p-1 \equiv -1 \ (mod \ p)$

My problem (with this proof) is in showing that the inverses are all paired up from $\displaystyle 2$ to $\displaystyle p-2$.
a) Is there a way to prove/show this?

or
b) Is there another way to prove $\displaystyle \prod_{i=1}^{p-1}\Bigl(\displaystyle\frac{1}{i}\Bigr) \equiv -1 \ (mod \ p)$?
• Sep 9th 2009, 05:46 PM
PaulRS
That is Wilson's Theorem actually. - see here -

To show the inverses are 'paired' show that $\displaystyle f:\left\{ {2,...,p - 2} \right\} \to \left\{ {2,...,p - 2} \right\}$ defined by: $\displaystyle f\left( x \right) = \left( {x^{ - 1} \bmod .p} \right)$ is injective and that $\displaystyle f(x)=x$ can't happen. Then for each number 2 ... p-2 you will have a unique inverse there - different from itself-, which will be the inverse of that number and no other.
• Sep 9th 2009, 08:30 PM
Bruno J.
Here is one other possible proof. $\displaystyle (\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic of order $\displaystyle p-1$; let $\displaystyle \alpha$ be a generator. Then

$\displaystyle \prod_{j=1}^{p-1}j^{-1}=\alpha^{-(1+2+...+(p-1))}=\alpha^{-p(p-1)/2}=\alpha^{-(p-1)/2}=-1$

because $\displaystyle \alpha^{\pm (p-1)/2}$ is just the Legendre symbol, and a primitive root is obviously not a square (or else all elements of $\displaystyle \mathbb{Z}/p\mathbb{Z})$ would be squares).
• Sep 9th 2009, 10:31 PM
Bingk
Yes, it is indeed Wilson's theorem, written a little differently :). I didn't see that before, hehehe, my bad :)

$\displaystyle \prod_{i=1}^{p-1}\displaystyle\frac{1}{i} \equiv \prod_{j=1}^{p-1}j \equiv (p-1)! \equiv -1 \ (mod \ p)$

Hehehe ... I'm learning lots of interesting things, and I'm just in awe of how these things work out :), like how there's different ways of showing the same thing :)