Lagrange's theorem (number theory)
<templatestyles src="Module:Hatnote/styles.css"></templatestyles>
In number theory, Lagrange's theorem is a statement named after Joseph-Louis Lagrange about how frequently a polynomial over the integers may evaluate to a multiple of a fixed prime. More precisely, it states that if p is a prime number and is a polynomial with integer coefficients, then either:
- every coefficient of f(x) is divisible by p, or
has at most deg f(x) incongruent solutions.
Solutions are "incongruent" if they do not differ by a multiple of p. If the modulus is not prime, then it is possible for there to be more than deg f(x) solutions.
A proof of Lagrange's theorem
The two key ideas are the following. Let be the polynomial obtained from
by taking the coefficients
. Now (i)
is divisible by
if and only if
; (ii)
has no more roots than its degree.
More rigorously, start by noting that if and only if each coefficient of
is divisible by
. Assume
is not 0; its degree is thus well-defined. It's easy to see
. To prove (i), first note that we can compute
either directly, i.e. by plugging in (the residue class of)
and performing arithmetic in
, or by reducing
. Hence
if and only if
, i.e. if and only if
is divisible by
. To prove (ii), note that
is a field, which is a standard fact; a quick proof is to note that since
is prime,
is a finite integral domain, hence is a field. Another standard fact is that a non-zero polynomial over a field has at most as many roots as its degree; this follows from the division algorithm.
Finally, note that two solutions are incongruent if and only if
. Putting it all together: the number of incongruent solutions by (i) is the same as the number of roots of
, which by (ii) is at most
, which is at most
.
References
- Lua error in package.lua at line 80: module 'strict' not found.
- Lua error in package.lua at line 80: module 'strict' not found.