Two-term congruence

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