conditional congruences

Consider congruencesMathworldPlanetmath ( of the form

f(x):=anxn+an-1xn-1++a0 0(modm) (1)

where the coefficients ai and m are rational integers.  Solving the congruence means finding all the integer values of x which satisfy (1).

  • If  ai0(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


    since one would otherwise have  anxn0(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=x0  is a solution of (1) and  x1x0(modm),  then by the properties of congruences (,

    f(x1)f(x0) 0(modm),

    and thus also  x=x1  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 systemMathworldPlanetmath 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