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

 Title conditional congruences Canonical name ConditionalCongruences Date of creation 2013-03-22 18:52:23 Last modified on 2013-03-22 18:52:23 Owner pahio (2872) Last modified by pahio (2872) Numerical id 6 Author pahio (2872) Entry type Topic Classification msc 11A07 Classification msc 11A05 Related topic LinearCongruence Related topic QuadraticCongruence Defines degree of congruence Defines root of congruence Defines root