I like that, though have no idea whether it's original. I've come across similar combinatorial proofs of number theoretic results in the past; I wonder if it's occurred to anybody to attempt a comprehensive survey? WFL On 6/17/12, Adam P. Goucher <apgoucher@gmx.com> wrote:
Consider a p*p chessboard, and place an arrangement of p non- attacking rooks on it. There are clearly p! ways in which this can be done.
If we interpret the chessboard instead as a torus, and let translations of the board be considered equivalent, then there are fewer unique arrangements. Out of the p² symmetries, 1 (the identity) fixes p! arrangements; 2(p-1) (vertical/horizontal translations) fix no arrangements; and the remaining (p-1)² each fix p arrangements.
Hence, there are [p!+p(p-1)²]/p² = [(p-1)!+(p-1)²]/p unique arrangements, up to toroidal translations of the board, by Burnside's Lemma. This must be an integer, so (p-1)! is congruent to -1 modulo p.
QED.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun