Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove Wilson's theorem by Lagrange's theorem

  1. Apr 9, 2010 #1
    Lagrange's Theorem: let p be any prime and [tex]f(x) = a_nx^n +a_{n-1}x^{n-1} + ... + a_1x + a_0[/tex] with [tex]a_n[/tex] ≡/≡ 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 [tex]f(x) = (x-1)(x-2)...(x-(p-1)) - (x^{p-1} - 1)[/tex] for an odd prime p.

    Proof:
    Expanding,
    [tex]f(x) = (x-1)(x-2)...(x-(p-1)) - (x^{p-1} - 1)[/tex]
    = [tex]a_{p-2}x^{p-2} +...+ a_1x + a_0[/tex] where the [tex]a_i[/tex] are some coefficients
    By the above theorem, f has at most p-2 roots mod p IF [tex]a_{p-2}[/tex] ≡/≡ 0 (mod p). (*)
    But by Fermat's theorem, for a=1,2,...,p-1, [tex]a^{p-1} -1[/tex] ≡ 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)
    => [tex](-1)^{p-1} (p-1)! + 1[/tex] ≡ 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 help forum]
     
  2. jcsd
  3. Apr 10, 2010 #2
    If a polynomial with at most p-2 roots has, in fact, p-1, then it must be identically 0.
     
  4. Apr 10, 2010 #3
    Why? What is the reasoning?
    Polynomial with at most p-2 roots has, in fact, p-1 roots <----this is already a contradiction. The statement is inconsistent...
     
  5. Apr 10, 2010 #4
    Because the complete statement of Lagrange's theorem, is that, if f(x) is a nontrivial (not identically 0) polynomial with degree n, then it has at most n roots (mod p).

    This doesn't happen with your polynomial, so it must be the trivial one. What does this imply for f(0)(mod p)?
     
    Last edited: Apr 10, 2010
  6. Apr 10, 2010 #5
    Thanks! I think I got it!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook