|
|
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 (p-1)! ? -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 p-1, a^-1 != a.
>
> Comments: Surely 1 is the inverse of 1. But it isn't so clear
> that (p-1) is an inverse of itself. Considering (p-1)^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
> (p-1)^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
> (p-1)! (in the group U(p) ) can be
> expressed as:
>
> (p-1)! = 1 * 2 * ... * (p-1) = 1 * (2 * 2^-1) * ... * (p - 1) = (p -
> 1)
>
> Hence (p-1)! ? -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 (p-1)! 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*...*(p-1) ?
>
> 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 c-x around the average value c, a technique
made famous in Gauss's grade-school 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^((p-1)/2) = 1 (mod p), for p prime.
The same pairing-up is effected by the orbits of any reflection
(or involution), i.e. a non-identity map whose square = identity.
For further examples and discussion see my posts here
http://math.stackexchange.com/search?q=user%3A242+wilson
--Bill Dubuque
|
|
