sufficient condition of identical congruence


Theorem.  Let  f(X):=anXn++a1X+a0  be a polynomialMathworldPlanetmathPlanetmath in X with integer coefficients ai and m a positive integer.  If the congruenceMathworldPlanetmathPlanetmathPlanetmathPlanetmath

f(x) 0(modm) (1)

is satisfied by m successive integers x, then it is satisfied by all integers x, in other words it is an identical congruence.

Proof.  There is an integer x0 such that (1) is satisfied by

x:=x0+1,x0+2,,x0+m.

But these values form a complete residue systemMathworldPlanetmath modulo m.  Thus, if x is an arbitrary integer, one has

xx0+r(modm)where  1rm.

This implies

aixiai(x0+r)i(modm)fori=0, 1,,n

and consequently

i=0naixif(x)i=0nai(x0+r)i=f(x0+r) 0(modm).

Accordingly, (1) is true for any integer x, Q.E.D.

Note.  Though the congruence (1) is identical, it need not be a question of a formal congruence

f(X)¯ 0(modm), (2)

i.e. all coefficients ai need not be congruent to 0 modulo m.

Title sufficient condition of identical congruence
Canonical name SufficientConditionOfIdenticalCongruence
Date of creation 2013-03-22 18:56:03
Last modified on 2013-03-22 18:56:03
Owner pahio (2872)
Last modified by pahio (2872)
Numerical id 8
Author pahio (2872)
Entry type Theorem
Classification msc 11C08
Classification msc 11A07
Related topic Sufficient
Related topic CongruenceOfArbitraryDegree
Related topic PolynomialCongruence