Namespaces
Variants
Actions

Difference between revisions of "Congruence equation"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (MR/ZBL numbers added)
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
c0248601.png
 +
$#A+1 = 44 n = 0
 +
$#C+1 = 44 : ~/encyclopedia/old_files/data/C024/C.0204860 Congruence equation,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''algebraic congruence''
 
''algebraic congruence''
  
 
A congruence of the form
 
A congruence of the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c0248601.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
F ( x _ {1} \dots x _ {n} )  \equiv  0 ( \mathop{\rm mod}  m ),
 +
$$
  
 
where
 
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c0248602.png" /></td> </tr></table>
+
$$
 +
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c0248603.png" /> with integral rational coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c0248604.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c0248605.png" /> is an integer. The maximum value of the magnitude
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c0248606.png" /></td> </tr></table>
+
$$
 +
d ( i _ {1} \dots i _ {n} )  = i _ {1} + \dots + i _ {n,}  $$
  
where the maximum is taken over all possible tuples <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c0248607.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c0248608.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c0248609.png" />), is called the degree with respect to the set of variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486010.png" /> or the degree of (1). The maximum value of the magnitudes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486011.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486012.png" />, where the maximum is taken over the same tuples <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486013.png" />, is called the degree of the congruence equation with respect to the variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486014.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486015.png" />, except for a few degenerate cases, may be reduced to the problem of the number of solutions of the congruences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486016.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486017.png" />) for the prime modules <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486018.png" /> that are divisors of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486019.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486020.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486021.png" />) in one variable are the two-term congruences (cf. [[Two-term congruence|Two-term congruence]])
+
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|Two-term congruence]])
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486022.png" /></td> </tr></table>
+
$$
 +
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486023.png" /> is very difficult, and only isolated partial solutions have so far been obtained.
+
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
 
A system of congruences
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486024.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \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:
 
may be considered as a system of algebraic equations:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486025.png" /></td> </tr></table>
+
$$
 +
F _ {i} ( x _ {1} \dots x _ {i} )  = 0,\ \
 +
i = 1 \dots m,
 +
$$
  
over the finite prime field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486026.png" /> consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486027.png" /> elements; the number of solutions of this system of congruences will be equal to the number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486028.png" />-rational points of the [[Algebraic variety|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.
+
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|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
 
The most extensively studied congruence equations in several variables were those of the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486029.png" /></td> </tr></table>
+
$$
 +
F ( x , y )  \equiv  0 (  \mathop{\rm mod}  p).
 +
$$
  
 
The estimate
 
The estimate
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486030.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \tag{3 }
 +
| N _ {p} - p |  \leq  2g \sqrt p
 +
$$
  
was obtained for the number of solutions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486031.png" /> of a congruence of this type, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486032.png" /> is an absolutely irreducible polynomial. The constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486033.png" /> depends only on the polynomial and is equal to the genus of the curve <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486034.png" />. Such an estimate for the first non-trivial case, viz. for the elliptic congruence
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486035.png" /></td> </tr></table>
+
$$
 +
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|Jacobi variety]] of the curve <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486036.png" />. Hasse's method was subsequently extended by A. Weil [[#References|[4]]] to the case of absolutely irreducible polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486037.png" />. This estimate was also obtained in [[#References|[3]]] by elementary methods.
+
was obtained by H. Hasse in 1934, who based his work on the formula for the addition of points on the [[Jacobi variety|Jacobi variety]] of the curve $  y  ^ {2} = x  ^ {3} + ax + b $.  
 +
Hasse's method was subsequently extended by A. Weil [[#References|[4]]] to the case of absolutely irreducible polynomials $  F $.  
 +
This estimate was also obtained in [[#References|[3]]] by elementary methods.
  
Studies of congruence equations with a number of variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486038.png" /> have been much less extensive. One general result is the theorem of Chevalley, according to which if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486039.png" /> is a form the degree of which is strictly smaller than the number of variables, then the number of solutions of the congruence
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486040.png" /></td> </tr></table>
+
$$
 +
F ( x _ {1} \dots x _ {n} )  \equiv  0 (  \mathop{\rm mod}  p )
 +
$$
  
is positive and is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486041.png" />; in the case of non-homogeneous polynomials the existence of a solution is not guaranteed, but the divisibility by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486042.png" /> remains valid (Warning's theorem). This last theorem has been generalized to systems of congruences.
+
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.
 
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.
Line 57: Line 123:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> Z.I. Borevich, I.R. Shafarevich, "Number theory" , Acad. Press (1966) (Translated from Russian) (German translation: Birkhäuser, 1966) {{MR|0195803}} {{ZBL|0145.04902}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> I.M. [I.M. Vinogradov] Winogradow, "Elemente der Zahlentheorie" , R. Oldenbourg (1956) (Translated from Russian) {{MR|0075964}} {{ZBL|0070.03802}} {{ZBL|0065.27003}} </TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> 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)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> 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)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> Z.I. Borevich, I.R. Shafarevich, "Number theory" , Acad. Press (1966) (Translated from Russian) (German translation: Birkhäuser, 1966) {{MR|0195803}} {{ZBL|0145.04902}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> I.M. [I.M. Vinogradov] Winogradow, "Elemente der Zahlentheorie" , R. Oldenbourg (1956) (Translated from Russian) {{MR|0075964}} {{ZBL|0070.03802}} {{ZBL|0065.27003}} </TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> 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)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> 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)</TD></TR></table>
 
 
  
 
====Comments====
 
====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|zeta-function]] of (and the counting of points on) algebraic varieties over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486043.png" />. For Deligne's proof, see [[#References|[a1]]] in the non-singular case and [[#References|[a2]]] for the singular case. An overview of his result (and proofs) is in [[#References|[a3]]]. For curves over finite fields the hard part of this Riemann hypothesis is the estimate (3). See [[#References|[a4]]] for an easy proof of it. Estimates for the numbers of points on curves over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024860/c02486044.png" /> are also important in coding theory.
+
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|zeta-function]] of (and the counting of points on) algebraic varieties over $  \mathbf Z / ( p) $.  
 +
For Deligne's proof, see [[#References|[a1]]] in the non-singular case and [[#References|[a2]]] for the singular case. An overview of his result (and proofs) is in [[#References|[a3]]]. For curves over finite fields the hard part of this Riemann hypothesis is the estimate (3). See [[#References|[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====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> P. Deligne, "La conjecture de Weil, 1" ''Publ. Math. IHES'' , '''43''' (1974) pp. 273–307 {{MR|340258}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> P. Deligne, "La conjecture de Weil, 2" ''Publ. Math. IHES'' , '''52''' (1980) pp. 137–252 {{MR|601520}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> 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</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> E. Bombieri, "Counting points on curves over finite fields" ''Sém. Bourbaki'' , '''430''' (1972–1973) {{MR|0429903}} {{ZBL|}} </TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> P. Deligne, "La conjecture de Weil, 1" ''Publ. Math. IHES'' , '''43''' (1974) pp. 273–307 {{MR|340258}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> P. Deligne, "La conjecture de Weil, 2" ''Publ. Math. IHES'' , '''52''' (1980) pp. 137–252 {{MR|601520}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> 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</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> E. Bombieri, "Counting points on curves over finite fields" ''Sém. Bourbaki'' , '''430''' (1972–1973) {{MR|0429903}} {{ZBL|}} </TD></TR></table>

Latest revision as of 17:46, 4 June 2020


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
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article