conditional congruences

Consider congruences (http://planetmath.org/Congruences) of the form

\displaystyle f(x)\;:=\;a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots+a_{0}\;\equiv\;0\pmod% {m}

(1)

where the coefficients $a_{i}$ and $m$ are rational integers. Solving the congruence means finding all the integer values of $x$ which satisfy (1).

•

If $a_{i}\equiv 0\pmod{m}$ for all $i$ ’s, the congruence is satisfied by each integer, in which case the congruence is identical (cf. the formal congruence). Therefore one can assume that at least

$a_{n}\not\equiv 0\pmod{m},$

since one would otherwise have $a_{n}x^{n}\equiv 0\pmod{m}$ and the first term could be left out of (1). Now, we say that the degree of the congruence (1) is $n$ .
•

If $x=x_{0}$ is a solution of (1) and $x_{1}\equiv x_{0}\pmod{m}$ , then by the properties of congruences (http://planetmath.org/Congruences),

$f(x_{1})\;\equiv\;f(x_{0})\;\equiv\;0\pmod{m},$

and thus also $x=x_{1}$ is a solution. Therefore, one regards as different roots of a congruence modulo $m$ only such values of $x$ which are incongruent modulo $m$ .
•

One can think that the congruence (1) has as many roots as is found in a complete residue system modulo $m$ .