21
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ 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/… $\endgroup$
    – j.c.
    Commented Feb 1, 2011 at 21:01
  • 2
    $\begingroup$ 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. $\endgroup$
    – Steven Landsburg
    Commented Feb 1, 2011 at 22:00

3 Answers 3

Reset to default
18
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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). $\endgroup$
    – François Brunault
    Commented Feb 2, 2011 at 10:29
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Right, and I didn't know that formulation before, thanks. But I see that jc got there sooner, in the comments above, right? $\endgroup$
    – David Feldman
    Commented Feb 1, 2011 at 23:15
  • $\begingroup$ Ah, yes, jc is sooner, it's exactly the same proof. $\endgroup$
    – Fedor Petrov
    Commented Feb 1, 2011 at 23:51
2
$\begingroup$

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?

Improve this answer
$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .