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.(adsbygoogle = window.adsbygoogle || []).push({});

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 hasat mostp-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 hasat leastp-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 thejustificationfor this step?

I hope someone can explain this proof.

Thank you very much!

[also under discussion in math help forum]

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

**Physics Forums | Science Articles, Homework Help, Discussion**