# Congruence modulo a prime number

A congruence in which the modulus is a prime number. A distinguishing feature of the theory of congruences modulo a prime number is the fact that the residue classes modulo $ p $
form a finite field of $ p $
elements. Congruences modulo a prime number can therefore be treated as equations over finite prime fields and algebraic-geometric methods, as well as methods of number theory, can be used to study them.

One of the basic questions in the theory of congruences with one variable $ x $, which is of great significance to algebraic number theory, coding theory and other branches of mathematics, is the question of the study of the laws of decomposition

$$ f( x) \equiv f _ {1} ( x) \dots f _ {r} ( x) ( \mathop{\rm mod} p) , $$

modulo a prime number $ p $, of arbitrary integer polynomials $ f( x) $ into irreducible factors.

A second basic question in the theory of congruences modulo a prime number $ p $ with $ n \geq 2 $ variables is the question of the number of solutions of a congruence equation

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

when $ x _ {i} $ $ ( 1 \leq i \leq n) $ vary independently of each other over either the whole set of residue classes modulo $ p $( problems of complete residue systems), or over a particular part of it (problems of incomplete residue systems).

The first results of the research into the question of the number of solutions of quadratic and bi-quadratic congruences with two variables were obtained by C.F. Gauss [1] and J.L. Lagrange [2]. E. Artin [3] established a link between the problem of the number of solutions of the hyper-elliptic congruences $ y ^ {2} \equiv f( x) $( $ \mathop{\rm mod} p $) on a complete residue system modulo the prime number $ p $ and the Riemann hypothesis for $ \zeta $- functions of algebraic function fields with a finite field of constants, which were introduced by him. In particular, he stated the hypothesis that for the number $ N _ {p} $ of solutions of the congruence $ y ^ {2} \equiv f( x) $( $ \mathop{\rm mod} p $), where the polynomial $ f( x) = x ^ {n} + a _ {1} x ^ {n-} 1 + \dots + a _ {n} $ is not the square of another polynomial modulo $ p $, the estimate

$$ | N _ {p} - p | \leq 2 \left [ n- \frac{1}{2} \right ] p ^ {1/2} $$

is correct (here $ [ x] $ is the integer part of the number $ x $).

Artin's hypothesis was first proved by H. Hasse [6] for the case of the elliptic congruences

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

A. Weil [8] subsequently extended the method of Hasse to cover the general case and obtained the estimate

$$ | N _ {q} - q | \leq c( f ) q ^ {1/2} $$

for the number $ N _ {q} $ of solutions of the equation $ f( x, y) = 0 $ in elements of the field $ F _ {q} $, consisting of $ q = p ^ {r} $ elements, where $ f( x, y) $ is an absolutely-irreducible polynomial with coefficients from $ F _ {q} $. The Hasse–Weil method is complicated and requires the use of modern abstract algebraic geometry. A simple and purely arithmetic method of proving the results of Hasse and Weil can be found in [7].

Congruences modulo a prime number with $ n $ variables are less widely studied. The following theorem can be used here as a general result. Let $ f( x _ {1} \dots x _ {n} ) $ be an absolutely-irreducible polynomial with integer coefficients. Then for the number $ N _ {p} $ of solutions of the congruence

$$ f( x _ {1} \dots x _ {n} ) \equiv 0 ( \mathop{\rm mod} p),\ \ n \geq 2, $$

the estimate

$$ | N _ {p} - p ^ {n-} 1 | \leq c( f ) p ^ {n-} 1- 1/2 $$

holds, where the constant $ c( f ) $ does not depend on $ p $. A better estimate has been obtained by P. Deligne [9].

For results on congruences modulo a prime number on an incomplete residue system, see Vinogradov hypotheses; Two-term congruence; Distribution of power residues and non-residues.

#### References

[1] | C.F. Gauss, "Untersuchungen über höhere Arithmetik" , Springer (1889) (Translated from Latin) MR0188045 Zbl 21.0166.04 |

[2] | J.L. Lagrange, "Démonstration d'un théorème d'arithmétique" , Oeuvres , 3 , Paris (1869) pp. 189–201 |

[3] | E. Artin, "Quadratische Körper in Gebiete der höheren Kongruenzen II" Math. Z. , 19 (1924) pp. 207–246 |

[4] | I.M. Vinogradov, "Selected works" , Springer (1985) (Translated from Russian) MR0807530 Zbl 0577.01049 |

[5] | H. Hasse, "Zahlentheorie" , Akademie Verlag (1963) MR0153659 Zbl 1038.11500 |

[6] | H. Hasse, "Abstrakte Begründung der komplexen multiplication und Riemannsche Vermutung in Funktionenkörpern" Abh. Math. Sem. Hamburg Univ. , 10 (1934) pp. 325–347 |

[7] | 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) |

[8] | 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) |

[9] | P. Deligne, "La conjecture de Weil I" Publ. Math. IHES , 43 (1974) pp. 273–307 MR0340258 Zbl 0314.14007 Zbl 0287.14001 |

#### Comments

A polynomial $ f ( x , y ) $ over $ F _ {q} $ is absolutely irreducible if it is still irreducible over the algebraic closure $ \overline{F}\; _ {q} $ of $ F _ {q} $. For some material on polynomials over finite fields and their factorizations in the context of coding theory cf. [a1].

#### References

[a1] | F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes" , I-II , North-Holland (1977) |

[a2] | G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapts. 5; 7; 8 MR0568909 Zbl 0423.10001 |

**How to Cite This Entry:**

Congruence modulo a prime number.

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