Namespaces
Variants
Actions

Difference between revisions of "Two-term congruence"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
t0946201.png
 +
$#A+1 = 49 n = 0
 +
$#C+1 = 49 : ~/encyclopedia/old_files/data/T094/T.0904620 Two\AAhterm congruence,
 +
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}}
 +
 
''binomial congruence, power congruence''
 
''binomial congruence, power congruence''
  
 
An algebraic congruence of the form
 
An algebraic 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/t/t094/t094620/t0946201.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
x  ^ {n}  \equiv  a  ( \mathop{\rm mod}  m ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t0946202.png" /> are coprime integers and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t0946203.png" /> is a natural number. If the congruence (1) is solvable, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t0946204.png" /> is called an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t0946205.png" />-th power residue modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t0946206.png" />; otherwise, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t0946207.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t0946208.png" />-th power non-residue modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t0946209.png" />.
+
where $  a , m $
 +
are coprime integers and $  n \geq  2 $
 +
is a natural number. If the congruence (1) is solvable, $  a $
 +
is called an $  n $-
 +
th power residue modulo $  m $;  
 +
otherwise, $  a $
 +
is an $  n $-
 +
th power non-residue modulo $  m $.
  
The problem of solvability of a two-term congruence to a composite modulus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462010.png" /> can be reduced to the study of the corresponding problem to a prime modulus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462011.png" /> (cf. [[Congruence (in algebra)|Congruence (in algebra)]]). For the prime modulus power congruence problem there is a solvability criterion, due to L. Euler: For the congruence
+
The problem of solvability of a two-term congruence to a composite modulus $  m $
 +
can be reduced to the study of the corresponding problem to a prime modulus $  p $(
 +
cf. [[Congruence (in algebra)|Congruence (in algebra)]]). For the prime modulus power congruence problem there is a solvability criterion, due to L. Euler: For 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/t/t094/t094620/t09462012.png" /></td> </tr></table>
+
$$
 +
x  ^ {n}  \equiv  a  (  \mathop{\rm mod}  p )
 +
$$
  
 
to be solvable, it is necessary that
 
to be solvable, it is necessary that
  
<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/t/t094/t094620/t09462013.png" /></td> </tr></table>
+
$$
 +
a ^ {( p - 1 ) / \delta }  \equiv  1  (  \mathop{\rm mod}  p ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462014.png" /> is the greatest common divisor of the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462016.png" />; if this condition is met, the congruence in question has exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462017.png" /> solutions.
+
where $  \delta $
 +
is the greatest common divisor of the numbers $  n $
 +
and $  p - 1 $;  
 +
if this condition is met, the congruence in question has exactly $  \delta $
 +
solutions.
  
It follows immediately from Euler's criterion that the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462018.png" /> have exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462019.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462020.png" />-th power residues and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462021.png" /> non-residues modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462022.png" />.
+
It follows immediately from Euler's criterion that the numbers $  1 \dots p - 1 $
 +
have exactly $  ( p - 1 ) / \delta $
 +
$  n $-
 +
th power residues and $  ( \delta - 1 ) ( p - 1 ) / \delta $
 +
non-residues modulo $  p $.
  
The converse problem is much more complicated: To find all moduli <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462023.png" /> to which a given number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462024.png" /> is a residue (or a non-residue) of power <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462025.png" />. It was established by Euler that the solvability or non-solvability of the congruence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462026.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462027.png" />) depends on whether or not the prime modulus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462028.png" /> forms part of certain arithmetical progressions. A rigorous proof of this result was given first by C.F. Gauss in 1801 (see [[#References|[4]]] and [[Gauss reciprocity law|Gauss reciprocity law]]; [[Quadratic reciprocity law|Quadratic reciprocity law]]). Gauss further noted that a complete solution of the problem for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462029.png" /> is only possible if the ring of rational integers is extended somewhat. Thus, in establishing the reciprocity law for biquadratic residues he was forced to extend the ring of rational integers to the ring of complex integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462030.png" />. The solvability or non-solvability of the biquadratic congruence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462031.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462032.png" />) in the ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462033.png" /> for a given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462034.png" /> will depend on the value of the residue of the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462035.png" /> to some constant modulus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462036.png" /> of the ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462037.png" />.
+
The converse problem is much more complicated: To find all moduli $  p $
 +
to which a given number $  a $
 +
is a residue (or a non-residue) of power $  n \geq  2 $.  
 +
It was established by Euler that the solvability or non-solvability of the congruence $  x  ^ {2} \equiv a $(
 +
$  \mathop{\rm mod}  p $)  
 +
depends on whether or not the prime modulus $  p $
 +
forms part of certain arithmetical progressions. A rigorous proof of this result was given first by C.F. Gauss in 1801 (see [[#References|[4]]] and [[Gauss reciprocity law|Gauss reciprocity law]]; [[Quadratic reciprocity law|Quadratic reciprocity law]]). Gauss further noted that a complete solution of the problem for $  n \geq  3 $
 +
is only possible if the ring of rational integers is extended somewhat. Thus, in establishing the reciprocity law for biquadratic residues he was forced to extend the ring of rational integers to the ring of complex integers $  \mathbf Z [ i] $.  
 +
The solvability or non-solvability of the biquadratic congruence $  x  ^ {4} \equiv \omega $(
 +
$  \mathop{\rm mod}  p $)  
 +
in the ring $  \mathbf Z [ i] $
 +
for a given $  \omega \in \mathbf Z [ i] $
 +
will depend on the value of the residue of the number $  p $
 +
to some constant modulus $  D $
 +
of the ring $  \mathbf Z [ i] $.
  
A new stage in the study of two-term congruences and their applications to other theoretical problems was initiated by I.M. Vinogradov, who showed in 1914 that the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462038.png" /> of quadratic residues to the prime modulus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462039.png" /> among the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462040.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462041.png" />, is given by the formula
+
A new stage in the study of two-term congruences and their applications to other theoretical problems was initiated by I.M. Vinogradov, who showed in 1914 that the number $  R $
 +
of quadratic residues to the prime modulus $  p $
 +
among the numbers $  1 \dots Q $,  
 +
$  Q \leq  p - 1 $,  
 +
is given by the formula
  
<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/t/t094/t094620/t09462042.png" /></td> </tr></table>
+
$$
 +
=
 +
\frac{1}{2}
 +
Q + \theta \sqrt {p }  \mathop{\rm ln}  p ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462043.png" />. A similar result was subsequently obtained by Vinogradov for a more general problem on the number of solutions of the congruence
+
where $  | \theta | \leq  1 $.  
 +
A similar result was subsequently obtained by Vinogradov for a more general problem on 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/t/t094/t094620/t09462044.png" /></td> </tr></table>
+
$$
 +
x  ^ {n}  \equiv  y  ( { \mathop{\rm mod}  p } ) ,\  n \geq  2 ,
 +
$$
  
when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462045.png" /> runs through an incomplete system of residues <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462046.png" />.
+
when $  y $
 +
runs through an incomplete system of residues $  1 \leq  y \leq  Q $.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  B.A. Venkov,  "Elementary number theory" , Wolters-Noordhoff  (1970)  (Translated from Russian)</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)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  I.M. Vinogradov,  "Selected works" , Springer  (1985)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  C.F. Gauss,  "Untersuchungen über höhere Arithmetik" , A. Maser  (1889)  (Translated from Latin)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  B.A. Venkov,  "Elementary number theory" , Wolters-Noordhoff  (1970)  (Translated from Russian)</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)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  I.M. Vinogradov,  "Selected works" , Springer  (1985)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  C.F. Gauss,  "Untersuchungen über höhere Arithmetik" , A. Maser  (1889)  (Translated from Latin)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
In [[#References|[a2]]] it is shown that the smallest non-quadratic residue modulo a prime <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462047.png" /> is smaller than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462048.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094620/t09462049.png" />.
+
In [[#References|[a2]]] it is shown that the smallest non-quadratic residue modulo a prime $  p $
 +
is smaller than $  c ( \alpha ) p  ^  \alpha  $
 +
for any $  \alpha > 1/4 \sqrt e $.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G.H. Hardy,  E.M. Wright,  "An introduction to the theory of numbers" , Oxford Univ. Press  (1979)  pp. Chapt. 6</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D.A. Burgess,  "The distribution of quadratic residues and non-residues"  ''Mathematica'' , '''4'''  (1957)  pp. 106–112</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G.H. Hardy,  E.M. Wright,  "An introduction to the theory of numbers" , Oxford Univ. Press  (1979)  pp. Chapt. 6</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D.A. Burgess,  "The distribution of quadratic residues and non-residues"  ''Mathematica'' , '''4'''  (1957)  pp. 106–112</TD></TR></table>

Latest revision as of 08:27, 6 June 2020


binomial congruence, power congruence

An algebraic congruence of the form

$$ \tag{1 } x ^ {n} \equiv a ( \mathop{\rm mod} m ) , $$

where $ a , m $ are coprime integers and $ n \geq 2 $ is a natural number. If the congruence (1) is solvable, $ a $ is called an $ n $- th power residue modulo $ m $; otherwise, $ a $ is an $ n $- th power non-residue modulo $ m $.

The problem of solvability of a two-term congruence to a composite modulus $ m $ can be reduced to the study of the corresponding problem to a prime modulus $ p $( cf. Congruence (in algebra)). For the prime modulus power congruence problem there is a solvability criterion, due to L. Euler: For the congruence

$$ x ^ {n} \equiv a ( \mathop{\rm mod} p ) $$

to be solvable, it is necessary that

$$ a ^ {( p - 1 ) / \delta } \equiv 1 ( \mathop{\rm mod} p ) , $$

where $ \delta $ is the greatest common divisor of the numbers $ n $ and $ p - 1 $; if this condition is met, the congruence in question has exactly $ \delta $ solutions.

It follows immediately from Euler's criterion that the numbers $ 1 \dots p - 1 $ have exactly $ ( p - 1 ) / \delta $ $ n $- th power residues and $ ( \delta - 1 ) ( p - 1 ) / \delta $ non-residues modulo $ p $.

The converse problem is much more complicated: To find all moduli $ p $ to which a given number $ a $ is a residue (or a non-residue) of power $ n \geq 2 $. It was established by Euler that the solvability or non-solvability of the congruence $ x ^ {2} \equiv a $( $ \mathop{\rm mod} p $) depends on whether or not the prime modulus $ p $ forms part of certain arithmetical progressions. A rigorous proof of this result was given first by C.F. Gauss in 1801 (see [4] and Gauss reciprocity law; Quadratic reciprocity law). Gauss further noted that a complete solution of the problem for $ n \geq 3 $ is only possible if the ring of rational integers is extended somewhat. Thus, in establishing the reciprocity law for biquadratic residues he was forced to extend the ring of rational integers to the ring of complex integers $ \mathbf Z [ i] $. The solvability or non-solvability of the biquadratic congruence $ x ^ {4} \equiv \omega $( $ \mathop{\rm mod} p $) in the ring $ \mathbf Z [ i] $ for a given $ \omega \in \mathbf Z [ i] $ will depend on the value of the residue of the number $ p $ to some constant modulus $ D $ of the ring $ \mathbf Z [ i] $.

A new stage in the study of two-term congruences and their applications to other theoretical problems was initiated by I.M. Vinogradov, who showed in 1914 that the number $ R $ of quadratic residues to the prime modulus $ p $ among the numbers $ 1 \dots Q $, $ Q \leq p - 1 $, is given by the formula

$$ R = \frac{1}{2} Q + \theta \sqrt {p } \mathop{\rm ln} p , $$

where $ | \theta | \leq 1 $. A similar result was subsequently obtained by Vinogradov for a more general problem on the number of solutions of the congruence

$$ x ^ {n} \equiv y ( { \mathop{\rm mod} p } ) ,\ n \geq 2 , $$

when $ y $ runs through an incomplete system of residues $ 1 \leq y \leq Q $.

References

[1] B.A. Venkov, "Elementary number theory" , Wolters-Noordhoff (1970) (Translated from Russian)
[2] I.M. [I.M. Vinogradov] Winogradow, "Elemente der Zahlentheorie" , R. Oldenbourg (1956) (Translated from Russian)
[3] I.M. Vinogradov, "Selected works" , Springer (1985) (Translated from Russian)
[4] C.F. Gauss, "Untersuchungen über höhere Arithmetik" , A. Maser (1889) (Translated from Latin)

Comments

In [a2] it is shown that the smallest non-quadratic residue modulo a prime $ p $ is smaller than $ c ( \alpha ) p ^ \alpha $ for any $ \alpha > 1/4 \sqrt e $.

References

[a1] G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapt. 6
[a2] D.A. Burgess, "The distribution of quadratic residues and non-residues" Mathematica , 4 (1957) pp. 106–112
How to Cite This Entry:
Two-term congruence. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Two-term_congruence&oldid=12675
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article