lagrange'stheorem

Lagrange's Theorem

If p prime and f(x)=anx**n + a(n-1)x**(n-1) + … + a1x + a0 [an<>0 mod p], then congruence f(x)==0 [mod p] has at most n incongruent solutions

Proof:

Basis for induction:

n=1 => f(x)=a1x + a0

hcf (a1,p) = 1, so unique solution for f(x)==0 [mod p]

Inductive hypothesis:

WLOG f(x)==0 has at least one solution, x==a

f(x)=(x-a)g(x) + r, g(x) of degree k-1

Substituting x=a gives:

0==f(a)=(a-a)g(a) + r==r [mod p]

so, f(x)==(x-a)g(x) [mod p]

If b is another, incongruent, solution:

0==f(b)=(b-a)g(b) [mod p]

But b<>a [mod p], so g(b)==0 [mod p]

If there are at most k-1 such b’s, roots of g(x), by induction there are at most k (k-1 b’s and the a) roots of f(x)