Results 1 to 3 of 3

Math Help - Prove Wilson's theorem by Lagrange's theorem

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Lightbulb Prove Wilson's theorem by Lagrange's theorem

    Lagrange's Theorem: let p be any prime and f(x) = a_nx^n +a_{n-1}x^{n-1} + ... + a_1x + a_0 with a_n ≡/≡ 0 (mod p). Then f(x) 0 (mod p) has at most n solutions.

    Use the above theorem to prove Wilson's theorem.
    Hint: Let f(x) = (x-1)(x-2)...(x-(p-1)) - (x^{p-1} - 1) for an odd prime p.

    Proof:
    Expanding,
    f(x) = (x-1)(x-2)...(x-(p-1)) - (x^{p-1} - 1)
    = a_{p-2}x^{p-2} +...+ a_1x + a_0 where the a_i are some coefficients
    By the above theorem, f has at most p-2 roots mod p IF a_{p-2} ≡/≡ 0 (mod p). (*)
    But by Fermat's theorem, for a=1,2,...,p-1, a^{p-1} -1 ≡ 0 (mod p).
    So for a=1,2,...,p-1, f(a) ≡ 0 (mod p).
    So f has at least p-1 roots mod p. (**)
    (*) and (**) contradict unless f(x) ≡ 0 (mod p). Therefore, we must have f(x) ≡ 0 (mod p).
    => f(0)=(-1)(-2)...(-(p-1)) - (-1) ≡ 0 (mod p)
    => (-1)^{p-1} (p-1)! + 1 ≡ 0 (mod p)
    For odd primes p, p-1 is even, so (p-1)! ≡ -1 (mod p)
    (For p=2, check directly.)
    =========================================

    I don't understand the two lines in red.
    I understand that there is a contradiction, but why does this imply that f(x) ≡ 0 (mod p)? Why in this case, there will be no contradiction? I'm totally lost here...

    Also, f(x) ≡ 0 (mod p) doesn't necessarily mean it holds for EVERY integer x, so why can we substitute x=0 and say that f(0) ≡ 0 (mod p)? What is the justification for this step?

    I hope someone can explain this proof.
    Thank you very much!

    [also under discussion in math link forum]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Look at Lagrange's Theorem here. It's a tiny bit different than what you said. Hopefully that clears things up for you.
    Last edited by chiph588@; April 10th 2010 at 06:27 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2010
    Posts
    78
    A typical proof is that, use the same polynomial f(x), argue that it has degree at most p-2, so if f(x) is not the zero polynomial, then it must have at most p-2 roots. But then argue that 1~p-1 are all roots, so f(x)=0 (mod p) (here the equality means f(x) equals the zero polynomial, not LHS=RHS when you plug in every number mod p). Then compute the constant term of f(x) and you'll get Wilson.

    The proof that OP presents involves a_{p-2}, which is definitely confusing since it is always 0 mod p if p is odd prime, and it does nothing to prove the theorem.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 30th 2011, 10:26 AM
  2. Regarding Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: August 5th 2010, 01:53 PM
  3. Wilson theorem
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: May 16th 2009, 02:30 AM
  4. Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 23rd 2008, 07:52 AM
  5. prove by wilson theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 11th 2008, 07:52 AM

Search Tags


/mathhelpforum @mathhelpforum