Fermat, Euler, Lagrange, Legendre, and other number theorists of the 17th and 18th centuries established theorems[1] and formed conjectures[2] about quadratic residues, but the first systematic treatment is § IV of Gauss's Disquisitiones Arithmeticae (1801).
For a given n, a list of the quadratic residues modulo n may be obtained by simply squaring all the numbers 0, 1, ..., n − 1.
But the obtained list is not composed of mutually incongruent quadratic residues (mod n) only.
Thus, the number of mutually noncongruent quadratic residues modulo n cannot exceed n/2 + 1 (n even) or (n + 1)/2 (n odd).
Modulo an odd prime number p there are (p + 1)/2 residues (including 0) and (p − 1)/2 nonresidues, by Euler's criterion.
Gauss[11] used R and N to denote residuosity and non-residuosity, respectively; Although this notation is compact and convenient for some purposes,[12][13] a more useful notation is the Legendre symbol, also called the quadratic character, which is defined for all integers a and positive odd prime numbers p as There are two reasons why numbers ≡ 0 (mod p) are treated specially.
Although quadratic residues appear to occur in a rather random pattern modulo n, and this has been exploited in such applications as acoustics and cryptography, their distribution also exhibits some striking regularities.
The CRT says that this is the same as p ≡ 1 (mod 840), and Dirichlet's theorem says there are an infinite number of primes of this form.
2521 is the smallest, and indeed 12 ≡ 1, 10462 ≡ 2, 1232 ≡ 3, 22 ≡ 4, 6432 ≡ 5, 872 ≡ 6, 6682 ≡ 7, 4292 ≡ 8, 32 ≡ 9, and 5292 ≡ 10 (mod 2521).The first of these regularities stems from Peter Gustav Lejeune Dirichlet's work (in the 1830s) on the analytic formula for the class number of binary quadratic forms.
[17] Let q be a prime number, s a complex variable, and define a Dirichlet L-function as Dirichlet showed that if q ≡ 3 (mod 4), then Therefore, in this case (prime q ≡ 3 (mod 4)), the sum of the quadratic residues minus the sum of the nonresidues in the range 1, 2, ..., q − 1 is a negative number.
[citation needed] Dirichlet also proved that for prime q ≡ 3 (mod 4), This implies that there are more quadratic residues than nonresidues among the numbers 1, 2, ..., (q − 1)/2.
[23] Specifically, Pólya and Vinogradov proved[24] (independently) in 1918 that for any nonprincipal Dirichlet character χ(n) modulo q and any integers M and N, in big O notation.
The question of the magnitude of the least quadratic non-residue n(p) is more subtle, but it is always prime, with 7 appearing for the first time at 71.
[28] Linnik showed that the number of p less than X such that n(p) > Xε is bounded by a constant depending on ε.
[29] That is, given a number a and a modulus n, how hard is it An important difference between prime and composite moduli shows up here.
Tonelli[33] (in 1891) and Cipolla[34] found efficient algorithms that work for all prime moduli.
Say there were an efficient algorithm for finding square roots modulo a composite number.
The article congruence of squares discusses how finding two numbers x and y where x2 ≡ y2 (mod n) and x ≠ ±y suffices to factorize n efficiently.
The efficiency of the factoring algorithm depends on the exact characteristics of the root-finder (e.g. does it return all roots?
[35]Determining whether a is a quadratic residue or nonresidue modulo n (denoted a R n or a N n) can be done efficiently for prime n by computing the Legendre symbol.
In general, to determine if a is a quadratic residue modulo composite n, one can use the following theorem:[37] Let n > 1, and gcd(a,n) = 1.
Also notice that if gcd(a,n) = m, then the congruence can be reduced to a/m ≡ x2/m (mod n/m), but then this takes the problem away from quadratic residues (unless m is a square).
[38] Sound diffusers have been based on number-theoretic concepts such as primitive roots and quadratic residues.
The fact that finding a square root of a number modulo a large composite n is equivalent to factoring (which is widely believed to be a hard problem) has been used for constructing cryptographic schemes such as the Rabin cryptosystem and the oblivious transfer.
The Solovay–Strassen primality test for whether a given number n is prime or composite picks a random a and computes (a|n) using a modification of Euclid's algorithm,[40] and also using Euler's criterion.
There is a deterministic version of it, but the proof that it works depends on the generalized Riemann hypothesis; the output from this test is "n is definitely composite" or "either n is prime or the GRH is false".
If the second output ever occurs for a composite n, then the GRH would be false, which would have implications through many branches of mathematics.
The following table (sequence A096008 in the OEIS) lists the quadratic residues mod 1 to 75 (a red number means it is not coprime to n).
The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German.
The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.