Lagrange's Theorem

Lagrange's Theorem
Let  
\[p\]
  be a prime and let  
\[P(x)\]
  be a polynomial of degree  
\[k\]
. The equation  
\[P(x) \equiv 0 \; (mod \; p)\]
  can have at most  
\[k\]
  solutions.
Modulus or not the equation  
\[P(x)=0 \]
  where  
\[P(x)\]
  has degree k has at most  
\[k\]
  solutions. Factorise  
\[P(x)\]
  so  
\[P(x)=(x-x_1)(x-x_2)...(x-x_r)P_r(x)\]
  where  
\[P_r(x)\]
  is a polynomial of degree  
\[k-r\]
. This can be written  
\[mod \; p\]
  by reducing all the  
\[x_i \; (mod \; p)\]
  then if  
\[r=k\]
   
\[P_r(x)\]
  is a constant and there are  
\[k\]
  solutions.
Proof
Suppose to the contrary that a polynomial congruence  
\[P(x) \equiv 0 \; (mos \; p)\]
  has incongruent solutions  
\[b_1, \; b_2,...., \; b_k, \; b_{l+1}\]
  then we can write
\[P(x) \equiv (x-b_1)(x-b_2)...(x-b_k)P_k(x) \; (mod \; p)\]

where  
\[P_k(x)\]
  has degree  
\[k-k=0\]
. Then  
\[P_k(x)\]
  is a constant, say  
\[P_k(x)=c\]
.
The leading term in  
\[P(x)\]
  will then be  
\[cx^k\]
.
\[b_{k+1}\]
  is a solution of  
\[P(x) \equiv 0 \; (mod \; p)\]
  so  
\[P(b_{k+1}) \equiv c(b_{k+1}-b_1)(b_{k+1}-b_2)...(b_{k+1}-b_k) \equiv 0 \; (nod \; p)\]
.
Then  
\[p | c(b_{k+1}-b_1)(b_{k+1}-b_2)...(b_{k+1}-b_k)\]
.
\[p\]
  is prime so Euclid's Lemma implies  
\[p\]
  divides one of the factors  
\[c, \; (b_{k+1}-b_1), \; (b_{k+1}-b_2),..., \; (b_{k+1}-b_k)\]
. Neither of these is possible since  
\[0 \lt c, b_i \lt p\]
  and the  
\[b_i\]
  are incongruent modulo  
\[p\]
.
Example:  
\[P(x) =x^2-9x+20=(x-4)(x-5)\]
  and  
\[p=3\]
.
The solutions of  
\[P(x)=0\]
  are  
\[x=4, \; 5\]
  and if we reduce  
\[P(x)\]
  modulo 3 we get  
\[P(x) \equiv x^2+2=(x+2)(x+1)\]
  and this equation has at most two solutions, which are  
\[x \equiv -2, \; -1 \; (mod \; ) \equiv 1, \; 2 \; (mod \; 3) \equiv 4, \; 5 \; (mod \; 3)\]
.

Add comment

Security code
Refresh