# sufficient condition of identical congruence

Let  $f(X):=a_{n}X^{n}+\ldots+a_{1}X+a_{0}$  be a polynomial in $X$ with integer coefficients $a_{i}$ and $m$ a positive integer.  If the congruence

 $\displaystyle f(x)\;\equiv\;0\pmod{m}$ (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 $x_{0}$ such that (1) is satisfied by

 $x\;:=\;x_{0}\!+\!1,\,x_{0}\!+\!2,\,\ldots,\,x_{0}\!+\!m.$

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

 $x\;\equiv\;x_{0}\!+\!r\pmod{m}\quad\mbox{where}\;\;1\leqq r\leqq m.$

This implies

 $a_{i}x^{i}\;\equiv\;a_{i}(x_{0}\!+\!r)^{i}\pmod{m}\quad\mbox{for}\;\;i=0,\,1,% \,\ldots,\,n$

and consequently

 $\underbrace{\sum_{i=0}^{n}a_{i}x^{i}}_{f(x)}\;\equiv\;\sum_{i=0}^{n}a_{i}(x_{0% }\!+\!r)^{i}\;=\;f(x_{0}\!+\!r)\;\equiv\;0\pmod{m}.$

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

 $\displaystyle f(X)\;\underline{\equiv}\;0\pmod{m},$ (2)

i.e. all coefficients $a_{i}$ need not be congruent to 0 modulo $m$.

Title sufficient condition of identical congruence SufficientConditionOfIdenticalCongruence 2013-03-22 18:56:03 2013-03-22 18:56:03 pahio (2872) pahio (2872) 8 pahio (2872) Theorem msc 11C08 msc 11A07 Sufficient CongruenceOfArbitraryDegree PolynomialCongruence