Lagrange's theorem (number theory)
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 formula_1 is a polynomial with integer coefficients, then either: where is the degree of . 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 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: More rigorously, start by noting that if and only if each coefficient of is divisible by . Assume ; its degree is thus well-defined. It is easy to see . To prove (1), 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 (2), 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 formula_2 . Putting everything together, the number of incongruent solutions by (1) is the same as the number of roots of , which by (2) is at most , which is at most .