# A particular combinatorial proof of Wilson's theorem

I (probably re)invented a very short combinatorial proof of Wilson's theorem that I perennially teach my students. If it occurs in the literature and someone can tell me where first (or even at all), I would like to attribute credit properly.

I actually prove $p! - p(p-1) \equiv 0 \mod p^2$.

$p!$ counts bijective function from ${\Bbb Z}/p$ to ${\Bbb Z}/p$ and ${\Bbb Z}/p \times {\Bbb Z}/p$ acts on these by $f(x)\stackrel{(a,b)}{\rightarrow} f(x-a)+b$. Excluding functions of the form $cx+d, c\not=0$, all orbits have size $p^2$.

-
With some minor adjustments (and interpretation in terms of counting colored necklaces) this seems to be the same as the proof of George Andrews in his book Number Theory (proof visible on google books) books.google.com/… – j.c. Feb 1 '11 at 21:01
I invented the same proof in grad school, and someone I showed it to --- probably Rick Miranda --- found a published reference to it. That was 25 years ago, so the reference has to be at least that old --- though I'm not recalling any more details. – Steven Landsburg Feb 1 '11 at 22:00
Thanks jc - that's just what I was looking for! – David Feldman Feb 1 '11 at 23:14

According to Dickson's History of the Theory of Numbers, this proof was first found by J. Petersen, Tidsskrift for Mathematik (3), 2, 1872, 64-5. (Petersen divides everything by 2, but the idea is the same.) Dickson gives a number of references to rediscoveries of Petersen's proof in the 19th century. Petersen was also apparently the first to discover the combinatorial proof of Fermat's theorem.

-
Thanks so much! – David Feldman Feb 2 '11 at 5:12
To add to Ira's answer, Petersen's proof counted paths on the vertices of a regular polygon. The (equivalent) proof counting bijections of $\mathbf{Z}/p\mathbf{Z}$ was given by Dickson himself (Annals of Math (1), 11, 1896-7, 120). – François Brunault Feb 2 '11 at 10:29

Is not it just the same proof as usual (oriented, with labeled startpoint) closed broken lines, joining vertices of regular $p$-gon? Rotations correspond to shifts of the argument of the bijective function, and changing the starting point correspond to $f(x)\rightarrow f(x)+b$.

-
Right, and I didn't know that formulation before, thanks. But I see that jc got there sooner, in the comments above, right? – David Feldman Feb 1 '11 at 23:15
Ah, yes, jc is sooner, it's exactly the same proof. – Fedor Petrov Feb 1 '11 at 23:51

I can't find my copy of Elementary number theory: A problem oriented approach at the moment but it has numerous proofs of various theorems so it would be worth a look. It is sadly out of print. It is all written in a lovely calligraphic hand. Google books actually has a searchable scan of it, but does not reveal enough to show me the proof(s) there.

later Thanks to Igor I can say that problem 14 page 64 gives the polygon argument also seen in George Andrews book along with the information that (Dickson's History V I p 75-76) says that this is due to a Danish mathematician J. Peterson (1872) and independently A. Cayley (1882).

Is it the same proof? That is theology... but let's look: ...never mind I see that others have described that. But did you know that $(m+n-1)! \equiv (-1)^nm!(n-1)! \mod m+n$?

Note: Evidently from the numbers $p! - p(p-1) \equiv\ 0 \mod (p-1)p^2$. As a consequence, $(p-2)!-1 \equiv 0 \mod p.$ I suppose we know that anyway..but what are the bijections?

-
@Aaron: Enjoy: dl.dropbox.com/u/5188175/entproblems.pdf – Igor Rivin Feb 1 '11 at 21:28
Couldn't find the argument there, but thanks Igor for this in any case!! – David Feldman Feb 1 '11 at 23:16
Julius Petersen was Danish, not Dutch. – Ira Gessel Sep 18 '13 at 13:30
Thanks, corrected. – Aaron Meyerowitz Sep 18 '13 at 17:31