# Congruence equation

*algebraic congruence*

A congruence of the form

$$ \tag{1 } F ( x _ {1} \dots x _ {n} ) \equiv 0 ( \mathop{\rm mod} m ), $$

where

$$ F ( x _ {1} \dots x _ {n} ) = \sum _ { i _ {1} = 0 } ^ { {m } _ {1} } \dots \sum _ {i _ {n} = 0 } ^ { {m _ n } } a _ {i _ {1} } \dots a _ {i _ {n} } x _ {1} ^ {i _ {1} } \dots x _ {n} ^ {i _ {n} } $$

is a polynomial in the variables $ x _ {1} \dots x _ {n} $ with integral rational coefficients $ a _ {i _ {1} } \dots a _ {i _ {n} } $ and $ m $ is an integer. The maximum value of the magnitude

$$ d ( i _ {1} \dots i _ {n} ) = i _ {1} + \dots + i _ {n,} $$

where the maximum is taken over all possible tuples $ i _ {1} \dots i _ {n} $ for which $ a _ {i _ {1} } \dots a _ {i _ {n} } \not\equiv 0 $( $ \mathop{\rm mod} m $), is called the degree with respect to the set of variables $ x _ {1} \dots x _ {n} $ or the degree of (1). The maximum value of the magnitudes $ i _ {s} $, $ i \leq s \leq n $, where the maximum is taken over the same tuples $ i _ {1} \dots i _ {n} $, is called the degree of the congruence equation with respect to the variable $ x _ {s} $.

The principal problem in the theory of congruence equations is the number of solutions of a given congruence. It is possible to restrict the problem to the case of a prime module, since the problem of the number of solutions of (1) by a composite module $ m $, except for a few degenerate cases, may be reduced to the problem of the number of solutions of the congruences $ F ( x _ {1} \dots x _ {n} ) \equiv 0 $( $ \mathop{\rm mod} p $) for the prime modules $ p $ that are divisors of $ m $.

The most thoroughly studied congruence equations $ F ( x) \equiv 0 $( $ \mathop{\rm mod} p $) in one variable are the two-term congruences (cf. Two-term congruence)

$$ x ^ {n} \equiv a ( \mathop{\rm mod} p ),\ a \not\equiv 0 \ ( \mathop{\rm mod} p ). $$

The study of the number of solutions of congruences in the case of a general polynomial $ F( x) $ is very difficult, and only isolated partial solutions have so far been obtained.

A system of congruences

$$ \tag{2 } F _ {i} ( x _ {1} \dots x _ {n} ) \equiv 0 ( \mathop{\rm mod} p ), \ i = 1 \dots m, $$

may be considered as a system of algebraic equations:

$$ F _ {i} ( x _ {1} \dots x _ {i} ) = 0,\ \ i = 1 \dots m, $$

over the finite prime field $ \mathbf Z / ( p ) $ consisting of $ p $ elements; the number of solutions of this system of congruences will be equal to the number of $ \mathbf Z / ( p ) $- rational points of the algebraic variety defined by the system of equations (2). Accordingly, together with number-theoretical methods, the methods of algebraic geometry are also used in the study of congruence equations or systems of such congruences.

The most extensively studied congruence equations in several variables were those of the form

$$ F ( x , y ) \equiv 0 ( \mathop{\rm mod} p). $$

The estimate

$$ \tag{3 } | N _ {p} - p | \leq 2g \sqrt p $$

was obtained for the number of solutions $ N _ {p} $ of a congruence of this type, where $ F ( x, y ) $ is an absolutely irreducible polynomial. The constant $ g $ depends only on the polynomial and is equal to the genus of the curve $ F ( x, y ) = 0 $. Such an estimate for the first non-trivial case, viz. for the elliptic congruence

$$ y ^ {2} \equiv x ^ {3} + ax + b ( \mathop{\rm mod} p ) , $$

was obtained by H. Hasse in 1934, who based his work on the formula for the addition of points on the Jacobi variety of the curve $ y ^ {2} = x ^ {3} + ax + b $. Hasse's method was subsequently extended by A. Weil [4] to the case of absolutely irreducible polynomials $ F $. This estimate was also obtained in [3] by elementary methods.

Studies of congruence equations with a number of variables $ n \geq 3 $ have been much less extensive. One general result is the theorem of Chevalley, according to which if $ F ( x _ {1} \dots x _ {n} ) $ is a form the degree of which is strictly smaller than the number of variables, then the number of solutions of the congruence

$$ F ( x _ {1} \dots x _ {n} ) \equiv 0 ( \mathop{\rm mod} p ) $$

is positive and is divisible by $ p $; in the case of non-homogeneous polynomials the existence of a solution is not guaranteed, but the divisibility by $ p $ remains valid (Warning's theorem). This last theorem has been generalized to systems of congruences.

The theory of congruence equations has numerous applications in other branches of number theory — the theory of Diophantine equations, problems in additive number theory, algebraic number theory, etc.

#### References

[1] | Z.I. Borevich, I.R. Shafarevich, "Number theory" , Acad. Press (1966) (Translated from Russian) (German translation: Birkhäuser, 1966) MR0195803 Zbl 0145.04902 |

[2] | I.M. [I.M. Vinogradov] Winogradow, "Elemente der Zahlentheorie" , R. Oldenbourg (1956) (Translated from Russian) MR0075964 Zbl 0070.03802 Zbl 0065.27003 |

[3] | S.A. Stepanov, "A constructive method in the theory of equations over finite fields" Trudy Mat. Inst. Steklov. , 132 (1973) pp. 237–246 (In Russian) |

[4] | A. Weil, "Courbes algébriques et variétés abéliennes. Sur les courbes algébriques et les varietés qui s'en deduisent" , Hermann (1948) |

#### Comments

A considerably more general result than (the generalization of) Warning's theorem was proved by P. Deligne (1973). He in fact proved the Riemann hypothesis for finite fields. This hypothesis, stated by Weil (1948), is closely connected with the zeta-function of (and the counting of points on) algebraic varieties over $ \mathbf Z / ( p) $. For Deligne's proof, see [a1] in the non-singular case and [a2] for the singular case. An overview of his result (and proofs) is in [a3]. For curves over finite fields the hard part of this Riemann hypothesis is the estimate (3). See [a4] for an easy proof of it. Estimates for the numbers of points on curves over $ \mathbf Z / ( p) $ are also important in coding theory.

#### References

[a1] | P. Deligne, "La conjecture de Weil, 1" Publ. Math. IHES , 43 (1974) pp. 273–307 MR340258 |

[a2] | P. Deligne, "La conjecture de Weil, 2" Publ. Math. IHES , 52 (1980) pp. 137–252 MR601520 |

[a3] | N.M. Katz, "An overview of Deligne's proof of the Riemann hypothesis for varieties over finite fields" F.E. Browder (ed.) , Mathematical developments arising from Hilbert problems , Proc. Symp. Pure Math. , 28 , Amer. Math. Soc. (1976) pp. 275–305 |

[a4] | E. Bombieri, "Counting points on curves over finite fields" Sém. Bourbaki , 430 (1972–1973) MR0429903 |

**How to Cite This Entry:**

Congruence equation.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Congruence_equation&oldid=46461