Prove Wilson's theorem by Lagrange's theorem

  • Thread starter kingwinner
  • Start date
  • #1
1,270
0
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]
 

Answers and Replies

  • #2
402
1
If a polynomial with at most p-2 roots has, in fact, p-1, then it must be identically 0.
 
  • #3
1,270
0
If a polynomial with at most p-2 roots has, in fact, p-1, then it must be identically 0.

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...
 
  • #4
402
1
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:
  • #5
1,270
0
Thanks! I think I got it!
 

Related Threads on Prove Wilson's theorem by Lagrange's theorem

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
22
Views
15K
  • Last Post
Replies
3
Views
3K
Replies
2
Views
910
  • Last Post
Replies
6
Views
2K
Replies
6
Views
2K
Replies
4
Views
850
  • Last Post
Replies
8
Views
6K
Replies
2
Views
8K
Top