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)