# 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  to the case of absolutely irreducible polynomials $F$. This estimate was also obtained in  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.

How to Cite This Entry:
Congruence equation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Congruence_equation&oldid=46461
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article