conditional congruences

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

$f(x):=a_n{x}^n+a_{n-1}{x}^{n-1}+\mathrm{\dots }+a_0\equiv \mathrm{\hspace{0.33em}0}(modm)$(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(modm)$  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(modm),$$

  since one would otherwise have  $a_n{x}^n\equiv 0(modm)$  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(modm)$,  then by the properties of congruences (http://planetmath.org/Congruences),

  $$f(x_1)\equiv f(x_0)\equiv \mathrm{\hspace{0.33em}0}(modm),$$

  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$.