Mathematics 
Mathematics Meta
While teaching a largely student-discovery style elementary number theory course to high schoolers at the Summer@Brown program, we were looking for instructive but interesting problems to challenge our students. By we, I mean Alex Walker, my academic little brother, and me, David Lowry-Duda. After a bit of experimentation with generators and orders, we stumbled across a proof of Wilson’s Theorem, different than the standard proof.
Wilson’s theorem is a classic result of elementary number theory, and is used in some elementary texts to prove Fermat’s Little Theorem, or to introduce primality testing algorithms that give no hint of the factorization.
Theorem 1 (Wilson’s Theorem) For a prime number \({p}\), we have $$ (p-1)! \equiv -1 \pmod p. \tag{1}$$
The theorem is clear for \({p = 2}\), so we only consider proofs for “odd primes \({p}\).”
The standard proof of Wilson’s Theorem included in almost every elementary number theory text starts with the factorial \({(p-1)!}\), the product of all the units mod \({p}\). Then as the only elements which are their own inverses are \({\pm 1}\) (as \({x^2 \equiv 1 \pmod p \iff p \mid (x^2 – 1) \iff p\mid x+1}\) or \({p \mid x-1}\)), every element in the factorial multiples with its inverse to give \({1}\), except for \({-1}\). Thus \({(p-1)! \equiv -1 \pmod p.} \diamondsuit\)
Now we present a different proof.
Take a primitive root \({g}\) of the unit group \({(\mathbb{Z}/p\mathbb{Z})^\times}\), so that each number \({1, \ldots, p-1}\) appears exactly once in \({g, g^2, \ldots, g^{p-1}}\). Recalling that \({1 + 2 + \ldots + n = \frac{n(n+1)}{2}}\) (a great example of classical pattern recognition in an elementary number theory class), we see that multiplying these together gives \({(p-1)!}\) on the one hand, and \({g^{(p-1)p/2}}\) on the other.
As \({g^{(p-1)/2}}\) is a solution to \({x^2 \equiv 1 \pmod p}\), and it is not \({1}\) since \({g}\) is a generator and thus has order \({p-1}\). So \({g^{(p-1)/2} \equiv -1 \pmod p}\), and raising \({-1}\) to an odd power yields \({-1}\), completing the proof \(\diamondsuit\).
After posting this, we have since seen that this proof is suggested in a problem in Ireland and Rosen’s extremely good number theory book. But it was pleasant to see it come up naturally, and it’s nice to suggest to our students that you can stumble across proofs.
It may be interesting to question why \({x^2 \equiv 1 \pmod p \iff x \equiv \pm 1 \pmod p}\) appears in a fundamental way in both proofs.
This post appears on the author’s personal website davidlowryduda.com and on the Math.Stackexchange Community Blog math.blogoverflow.com.
Filed under Advanced High School expository
Tagged: number-theory
The proof is not really that different from the standard proof. Including an initial term $0$ for symmetry, a standard argument for the identity $0+1+\cdots+n=\frac{(n+1)n}2$ would be to add $n +(n-1)+\cdots+0$ in a second row, and to observe that each of the $n+1$ columns add up to $n$. If $n$ is even, as $n=p-1$ is here, then a slight variation of the argument is: the middle term is $\frac n2$, and every pair of terms symmetric about it contributes $n$ to the sum, for a total of $\frac n2+\frac n2n$. Now passing to powers of $g$, the middle factor is $g^{n/2}=-1$, and each pair symmetric about it contributes $g^n=1$, so they are inverses: a pair also matched up in the standard argument. [I’ve cheated a bit: the outermost pair is is fact twice the same element $g^0=1$, but this does not contribute anything anyway.]
This proof is in my old Lithuanian book on math olympiads.
It presents 3 proofs, two of which are the ones shown in this blog and the other one is: $$f(x)\equiv x^{p-1}-1\equiv (x-1)(x-2)\cdots (x-(p-1))\pmod{p}\implies f(0)\equiv -1\equiv (p-1)!\pmod{p}\ \ \ \square$$
That is brilliant! Probably worth mentioning that it uses Euler’s (?) theorem that $x^{p-1} = 1$ for all $x /neq 0$, where $p$ is prime. But I love that proof!
That happens to be the proof that my first number theory instructor showed me (when I was younger and still bounced when I fell). It led nicely into more general polynomial congruences, ultimately leading all the way up to understanding the AKS primality test, if I recall correctly.
I’d love to see a purely combinatorial proof. $(p-1)!$ is the number of elements of $\Sigma_p$ of order $p$. But I’m a little unclear on where to go from there.
Hi, How does one contribute to this blog?
Hi! I’m glad you’re interested. Check out the Math Community Blog FAQ at meta.math.se. In short, go to math.blogoverflow.com/wp-admin and login with your math.stackexchange information, and then let one of the administrators know you’re interested in the blog chat. We’re looking for content!