View source for Two-term congruence

<!--
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''

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)|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 [[#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  $  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====
<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====
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====
<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>