
Re: proof of Wilson's theorem
Posted:
Sep 26, 2011 5:32 PM


divcurl <divcurl@europe.com> wrote: > > Theorem: Let p be a prime. Then (p1)! ? 1 (mod p) > > Proof: U(p), p prime, is {1, 2, 3, ..., p  1} a group under > multiplication modulo p. Let a in U(p) and suppose > a^2 = 1(In the group U(p)). Then a^2 ? 1 (mod p) in Z, > so p divides (a^2  1). Since p is prime, it follows that > either a = 1 or a = p  1. > > Comments: If we do suppose a^2 = 1 in U(p) then > 2 is the least positive integer such that a^j = e, e > identity. Hence, 2 is the order of 'a' here? Thus, > a^2 would be a multiple of 'p'? Therefore, we can > view (a^2  1) as a length of 'p' (hopefully that made sense)? > > Continuing with the proof: > Hence, for every a in U(p) other than 1 and p1, a^1 != a. > > Comments: Surely 1 is the inverse of 1. But it isn't so clear > that (p1) is an inverse of itself. Considering (p1)^2, we get > p^2  2p + 1, hence, the remainder will be 1. So it is indeed > an inverse of itself. Now is there a way to think about that > without carrying out the analytical process of inspecting > (p1)^2 and seeing it would have a remainder of 1? > > Also, at this point in the proof, it isn't so clear to me > what is guiding the author's reasoning here. If you were > to put this proof out of your mind(if you happen to know > how it already unfolds) and try and see it from the > perspective of fresh eyes, what is the idea that is motivating > us to consider the inverses of the 'a'? > > Continuing with proof: > So, if we pair each such 'a' with its inverse, the product > (p1)! (in the group U(p) ) can be > expressed as: > > (p1)! = 1 * 2 * ... * (p1) = 1 * (2 * 2^1) * ... * (p  1) = (p  > 1) > > Hence (p1)! ? 1 (mod p). > > Proof complete. > > Comments: > The author used that critical idea, whatever it was, to > carry out the aforementioned product to arrive at > p  1. It isn't even clear to me why (p1)! would equal > 1 * (2 * 2^1) ... * (p  1)  I know that 2*2^1 would be 1 > but why is this the same as writing it as 1*2*3*...*(p1) ? > > Elaboration welcomed.
The idea is more familiar in the additive case, e.g. to compute the sum of a geometric progression one pairs up each summand x with its reflection cx around the average value c, a technique made famous in Gauss's gradeschool trick for quickly summing the first 100 integers. Above, if we do the same for a reflection about an arbitrary element c (vs. c=1 above), pairing x with c/x, then precisely the same proof as above yields Euler's criterion: c is a square (mod p) iff c^((p1)/2) = 1 (mod p), for p prime.
The same pairingup is effected by the orbits of any reflection (or involution), i.e. a nonidentity map whose square = identity. For further examples and discussion see my posts here http://math.stackexchange.com/search?q=user%3A242+wilson
Bill Dubuque

