In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:
x2\equivq\pmod{n}.
Otherwise, q is called a quadratic nonresidue modulo n.
Originally an abstract mathematical concept from the branch of number theory known as modular arithmetic, quadratic residues are now used in applications ranging from acoustical engineering to cryptography and the factoring of large numbers.
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). Article 95 introduces the terminology "quadratic residue" and "quadratic nonresidue", and states that if the context makes it clear, the adjective "quadratic" may be dropped.
For a given n, a list of the quadratic residues modulo n may be obtained by simply squaring all the numbers 0, 1, ..., . Since a≡b (mod n) implies a2≡b2 (mod n), any other quadratic residue is congruent (mod n) to some in the obtained list. But the obtained list is not composed of mutually incongruent quadratic residues (mod n) only. Since a2≡(n-a)2 (mod n), the list obtained by squaring all numbers in the list 1, 2, ..., (or in the list 0, 1, ..., n) is symmetric (mod n) around its midpoint, hence it is actually only needed to square all the numbers in the list 0, 1, ...,
\lfloor
\rfloor
The product of two residues is always a residue.
Modulo 2, every integer is a quadratic residue.
(Z/pZ)
Following this convention, the multiplicative inverse of a residue is a residue, and the inverse of a nonresidue is a nonresidue.[5]
Following this convention, modulo an odd prime number there are an equal number of residues and nonresidues.[4]
Modulo a prime, the product of two nonresidues is a residue and the product of a nonresidue and a (nonzero) residue is a nonresidue.[5]
The first supplement[6] to the law of quadratic reciprocity is that if p ≡ 1 (mod 4) then -1 is a quadratic residue modulo p, and if p ≡ 3 (mod 4) then -1 is a nonresidue modulo p. This implies the following:
If p ≡ 1 (mod 4) the negative of a residue modulo p is a residue and the negative of a nonresidue is a nonresidue.
If p ≡ 3 (mod 4) the negative of a residue modulo p is a nonresidue and the negative of a nonresidue is a residue.
All odd squares are ≡ 1 (mod 8) and thus also ≡ 1 (mod 4). If a is an odd number and m = 8, 16, or some higher power of 2, then a is a residue modulo m if and only if a ≡ 1 (mod 8).[7]
For example, mod (32) the odd squares are12 ≡ 152 ≡ 1
32 ≡ 132 ≡ 9
52 ≡ 112 ≡ 25
72 ≡ 92 ≡ 49 ≡ 17
and the even ones are
02 ≡ 82 ≡ 162 ≡ 0
22 ≡ 62≡ 102 ≡ 142≡ 4
42 ≡ 122 ≡ 16.
So a nonzero number is a residue mod 8, 16, etc., if and only if it is of the form 4k(8n + 1).
A number a relatively prime to an odd prime p is a residue modulo any power of p if and only if it is a residue modulo p.[8]
If the modulus is pn,
then pka
is a residue modulo pn if k ≥ n
is a nonresidue modulo pn if k < n is odd
is a residue modulo pn if k < n is even and a is a residue
is a nonresidue modulo pn if k < n is even and a is a nonresidue.[9]
Notice that the rules are different for powers of two and powers of odd primes.
Modulo an odd prime power n = pk, the products of residues and nonresidues relatively prime to p obey the same rules as they do mod p; p is a nonresidue, and in general all the residues and nonresidues obey the same rules, except that the products will be zero if the power of p in the product ≥ n.
Modulo 8, the product of the nonresidues 3 and 5 is the nonresidue 7, and likewise for permutations of 3, 5 and 7. In fact, the multiplicative group of the non-residues and 1 form the Klein four-group.
The basic fact in this case is
if a is a residue modulo n, then a is a residue modulo pk for every prime power dividing n.
if a is a nonresidue modulo n, then a is a nonresidue modulo pk for at least one prime power dividing n.
Modulo a composite number, the product of two residues is a residue. The product of a residue and a nonresidue may be a residue, a nonresidue, or zero.
For example, from the table for modulus 6 1, 2, 3, 4, 5 (residues in bold).The product of the residue 3 and the nonresidue 5 is the residue 3, whereas the product of the residue 4 and the nonresidue 2 is the nonresidue 2.
Also, the product of two nonresidues may be either a residue, a nonresidue, or zero.
For example, from the table for modulus 15 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 (residues in bold).The product of the nonresidues 2 and 8 is the residue 1, whereas the product of the nonresidues 2 and 7 is the nonresidue 14.
(Z/nZ)
The fact that, e.g., modulo 15 the product of the nonresidues 3 and 5, or of the nonresidue 5 and the residue 9, or the two residues 9 and 10 are all zero comes from working in the full ring
(Z/nZ)
For this reason some authors[10] add to the definition that a quadratic residue a must not only be a square but must also be relatively prime to the modulus n. (a is coprime to n if and only if a2 is coprime to n.)
Although it makes things tidier, this article does not insist that residues must be coprime to the modulus.
Gauss[11] used and to denote residuosity and non-residuosity, respectively;
for example, and, or and .
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 and positive odd prime numbers as
| \left( | a |
| p |
\right)=\begin{cases} 0&ifpdividesa\\+1&ifa\operatorname{R}pandpdoesnotdividea\\-1&ifa\operatorname{N}pandpdoesnotdividea\end{cases}
There are two reasons why numbers ≡ 0 (mod) are treated specially. As we have seen, it makes many formulas and theorems easier to state. The other (related) reason is that the quadratic character is a homomorphism from the multiplicative group of nonzero congruence classes modulo to the complex numbers under multiplication. Setting
(\tfrac{np}{p})=0
One advantage of this notation over Gauss's is that the Legendre symbol is a function that can be used in formulas.[15] It can also easily be generalized to cubic, quartic and higher power residues.[16]
There is a generalization of the Legendre symbol for composite values of, the Jacobi symbol, but its properties are not as simple: if is composite and the Jacobi symbol
(\tfrac{a}{m})=-1,
(\tfrac{a}{m})=1,
(\tfrac{a}{m})=1
(\tfrac{2}{15})=1
(\tfrac{4}{15})=1
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.
Using Dirichlet's theorem on primes in arithmetic progressions, the law of quadratic reciprocity, and the Chinese remainder theorem (CRT) it is easy to see that for any M > 0 there are primes p such that the numbers 1, 2, ..., M are all residues modulo p.
For example, if p ≡ 1 (mod 8), (mod 12), (mod 5) and (mod 28), then by the law of quadratic reciprocity 2, 3, 5, and 7 will all be residues modulo p, and thus all numbers 1 - 10 will be. 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
L(s)=
| ||||
| \sum | ||||
| n=1 |
\right)n-s.
Dirichlet showed that if q ≡ 3 (mod 4), then
L(1)=-
| \pi | |
| \sqrtq |
| q-1 | |
| \sum | |
| n=1 |
| n | \left( | |
| q |
| n | |
| q |
\right)>0.
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.
For example, modulo 11,1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (residues in bold)
1 + 4 + 9 + 5 + 3 = 22, 2 + 6 + 7 + 8 + 10 = 33, and the difference is -11.
In fact the difference will always be an odd multiple of q if q > 3.[18] In contrast, for prime q ≡ 1 (mod 4), the sum of the quadratic residues minus the sum of the nonresidues in the range 1, 2, ..., q - 1 is zero, implying that both sums equal
| q(q-1) | |
| 4 |
Dirichlet also proved that for prime q ≡ 3 (mod 4),
L(1)=
| \pi | ||||
|
| |||||
| \sum | \left( | ||||
| n=1 |
| n | |
| q |
\right)>0.
For example, modulo 11 there are four residues less than 6 (namely 1, 3, 4, and 5), but only one nonresidue (2).
An intriguing fact about these two theorems is that all known proofs rely on analysis; no-one has ever published a simple or direct proof of either statement.
See main article: quadratic reciprocity.
If p and q are odd primes, then:
((p is a quadratic residue mod q) if and only if (q is a quadratic residue mod p)) if and only if (at least one of p and q is congruent to 1 mod 4).
That is:
| \left( | p |
| q |
\right)\left(
| q | |
| p |
\right)=
| ||||||||
| (-1) |
where
| \left( | p |
| q |
\right)
Thus, for numbers a and odd primes p that don't divide a:
| a | a is a quadratic residue mod p if and only if | a | a is a quadratic residue mod p if and only if | |
|---|---|---|---|---|
| 1 | (every prime p) | −1 | p ≡ 1 (mod 4) | |
| 2 | p ≡ 1, 7 (mod 8) | −2 | p ≡ 1, 3 (mod 8) | |
| 3 | p ≡ 1, 11 (mod 12) | −3 | p ≡ 1 (mod 3) | |
| 4 | (every prime p) | −4 | p ≡ 1 (mod 4) | |
| 5 | p ≡ 1, 4 (mod 5) | −5 | p ≡ 1, 3, 7, 9 (mod 20) | |
| 6 | p ≡ 1, 5, 19, 23 (mod 24) | −6 | p ≡ 1, 5, 7, 11 (mod 24) | |
| 7 | p ≡ 1, 3, 9, 19, 25, 27 (mod 28) | −7 | p ≡ 1, 2, 4 (mod 7) | |
| 8 | p ≡ 1, 7 (mod 8) | −8 | p ≡ 1, 3 (mod 8) | |
| 9 | (every prime p) | −9 | p ≡ 1 (mod 4) | |
| 10 | p ≡ 1, 3, 9, 13, 27, 31, 37, 39 (mod 40) | −10 | p ≡ 1, 7, 9, 11, 13, 19, 23, 37 (mod 40) | |
| 11 | p ≡ 1, 5, 7, 9, 19, 25, 35, 37, 39, 43 (mod 44) | −11 | p ≡ 1, 3, 4, 5, 9 (mod 11) | |
| 12 | p ≡ 1, 11 (mod 12) | −12 | p ≡ 1 (mod 3) |
Modulo a prime p, the number of pairs n, n + 1 where n R p and n + 1 R p, or n N p and n + 1 R p, etc., are almost equal. More precisely,[19] [20] let p be an odd prime. For i, j = 0, 1 define the sets
Aij=\left\{k\in\{1,2,...,p-2\}:\left(
| k | |
| p |
| ||||
| \right)=(-1) |
\right)=(-1)j\right\},
\alphaij=|Aij|.
That is,
α00 is the number of residues that are followed by a residue,
α01 is the number of residues that are followed by a nonresidue,
α10 is the number of nonresidues that are followed by a residue, and
α11 is the number of nonresidues that are followed by a nonresidue.
Then if p ≡ 1 (mod 4)
\alpha00=
| p-5 | |
| 4 |
, \alpha01=\alpha10=\alpha11=
| p-1 | |
| 4 |
and if p ≡ 3 (mod 4)
\alpha01=
| p+1 | |
| 4 |
, \alpha00=\alpha10=\alpha11=
| p-3 | |
| 4 |
.
For example: (residues in bold)Modulo 17
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
A00 =,
A01 =,
A10 =,
A11 = .
Modulo 19
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18
A00 =,
A01 =,
A10 =,
A11 = .
Gauss (1828)[21] introduced this sort of counting when he proved that if p ≡ 1 (mod 4) then x4 ≡ 2 (mod p) can be solved if and only if p = a2 + 64 b2.
The values of
(\tfrac{a}{p})
| M+N | |
| \left|\sum | |
| n=M+1 |
\chi(n)\right|=O\left(\sqrtqlogq\right),
in big O notation. Setting
\chi(n)=\left(
| n | |
| q |
\right),
this shows that the number of quadratic residues modulo q in any interval of length N is
| 1 | |
| 2 |
N+O(\sqrtqlogq).
It is easy[24] to prove that
\left|
| M+N | |
| \sum | |
| n=M+1 |
\left(
| n | |
| q |
\right)\right|<\sqrtqlogq.
In fact,[25]
\left|
| M+N | |
| \sum | |
| n=M+1 |
\left(
| n | |
| q |
\right)\right|<
| 4 | |
| \pi2 |
\sqrtqlogq+0.41\sqrtq+0.61.
Montgomery and Vaughan improved this in 1977, showing that, if the generalized Riemann hypothesis is true then
| M+N | |
| \left|\sum | |
| n=M+1 |
\chi(n)\right|=O\left(\sqrtqloglogq\right).
This result cannot be substantially improved, for Schur had proved in 1918 that
maxN
| N | ||
| \left|\sum | \left( | |
| n=1 |
| n | \right)\right|> | |
| q |
| 1 | |
| 2\pi |
\sqrtq
and Paley had proved in 1932 that
maxN
| N | ||
| \left|\sum | \left( | |
| n=1 |
| d | \right)\right|> | |
| n |
| 1 | |
| 7 |
\sqrtdloglogd
for infinitely many d > 0.
The least quadratic residue mod p is clearly 1. 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.
The Pólya–Vinogradov inequality above gives O(log p).
The best unconditional estimate is n(p) ≪ pθ for any θ>1/4, obtained by estimates of Burgess on character sums.
Assuming the Generalised Riemann hypothesis, Ankeny obtained n(p) ≪ (log p)2.[26]
Linnik showed that the number of p less than X such that n(p) > Xε is bounded by a constant depending on ε.[27]
The least quadratic non-residues mod p for odd primes p are:
2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, ...
Let p be an odd prime. The quadratic excess E(p) is the number of quadratic residues on the range (0,p/2) minus the number in the range (p/2,p) . For p congruent to 1 mod 4, the excess is zero, since −1 is a quadratic residue and the residues are symmetric under r ↔ p−r. For p congruent to 3 mod 4, the excess E is always positive.[28]
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. Modulo a prime p, a quadratic residue a has 1 + (a|p) roots (i.e. zero if a N p, one if a ≡ 0 (mod p), or two if a R p and gcd(a,p) = 1.)
In general if a composite modulus n is written as a product of powers of distinct primes, and there are n1 roots modulo the first one, n2 mod the second, ..., there will be n1n2... roots modulo n.
The theoretical way solutions modulo the prime powers are combined to make solutions modulo n is called the Chinese remainder theorem; it can be implemented with an efficient algorithm.[29]
For example:Solve x2 ≡ 6 (mod 15).
x2 ≡ 6 (mod 3) has one solution, 0; x2 ≡ 6 (mod 5) has two, 1 and 4.
and there are two solutions modulo 15, namely 6 and 9.
Solve x2 ≡ 4 (mod 15).
x2 ≡ 4 (mod 3) has two solutions, 1 and 2; x2 ≡ 4 (mod 5) has two, 2 and 3.
and there are four solutions modulo 15, namely 2, 7, 8, and 13.
Solve x2 ≡ 7 (mod 15).
x2 ≡ 7 (mod 3) has two solutions, 1 and 2; x2 ≡ 7 (mod 5) has no solutions.
and there are no solutions modulo 15.
| \left( | a |
| n |
\right)
| \left( | a |
| n |
\right)=1
x\equiv\pm a(n+1)/4\pmod{n},
x\equiv\begin{cases}\pm a(n+3)/8\pmod{n}&ifaisaquarticresiduemodulon\\ \pm a(n+3)/82(n-1)/4\pmod{n}&ifaisaquarticnon-residuemodulon\end{cases}
For prime n ≡ 1 (mod 8), however, there is no known formula. Tonelli[32] (in 1891) and Cipolla[33] found efficient algorithms that work for all prime moduli. Both algorithms require finding a quadratic nonresidue modulo n, and there is no efficient deterministic algorithm known for doing that. But since half the numbers between 1 and n are nonresidues, picking numbers x at random and calculating the Legendre symbol
| \left( | x |
| n |
\right)
If the modulus n is a prime power n = pe, a solution may be found modulo p and "lifted" to a solution modulo n using Hensel's lemma or an algorithm of Gauss.[8]
If the modulus n has been factored into prime powers the solution was discussed above.
\left(\tfrac{a}{n}\right)=-1
\left(\tfrac{a}{n/2}\right)=-1
\left(\tfrac{a}{n}\right)=1
\left(\tfrac{a}{n/2}\right)=1
If the complete factorization of n is not known, and
\left(\tfrac{a}{n}\right)=1
\left(\tfrac{a}{n/2}\right)=1
The above discussion indicates how knowing the factors of n allows us to find the roots efficiently. 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 and suffices to factorize n efficiently. Generate a random number, square it modulo n, and have the efficient square root algorithm find a root. Repeat until it returns a number not equal to the one we originally squared (or its negative modulo n), then follow the algorithm described in congruence of squares. The efficiency of the factoring algorithm depends on the exact characteristics of the root-finder (e.g. does it return all roots? just the smallest one? a random one?), but it will be efficient.[34]
Determining whether a is a quadratic residue or nonresidue modulo n (denoted or) can be done efficiently for prime n by computing the Legendre symbol. However, for composite n, this forms the quadratic residuosity problem, which is not known to be as hard as factorization, but is assumed to be quite hard.
On the other hand, if we want to know if there is a solution for x less than some given limit c, this problem is NP-complete; however, this is a fixed-parameter tractable problem, where c is the parameter.
In general, to determine if a is a quadratic residue modulo composite n, one can use the following theorem:[35]
Let, and . Then is solvable if and only if:
\left(\tfrac{a}{p}\right)=1
Note: This theorem essentially requires that the factorization of n is known. Also notice that if, then the congruence can be reduced to, but then this takes the problem away from quadratic residues (unless m is a square).
The list of the number of quadratic residues modulo n, for n = 1, 2, 3 ..., looks like:
1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, ...
A formula to count the number of squares modulo n is given by Stangl.
Sound diffusers have been based on number-theoretic concepts such as primitive roots and quadratic residues.[36]
Paley graphs are dense undirected graphs, one for each prime p ≡ 1 (mod 4), that form an infinite family of conference graphs, which yield an infinite family of symmetric conference matrices.
Paley digraphs are directed analogs of Paley graphs, one for each p ≡ 3 (mod 4), that yield antisymmetric conference matrices.
The construction of these graphs uses 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 quadratic residuosity problem is the basis for the Goldwasser-Micali cryptosystem.
The discrete logarithm is a similar problem that is also used in cryptography.
Euler's criterion is a formula for the Legendre symbol (a|p) where p is prime. If p is composite the formula may or may not compute (a|p) correctly. 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, and also using Euler's criterion.[37] If the results disagree, n is composite; if they agree, n may be composite or prime. For a composite n at least 1/2 the values of a in the range 2, 3, ..., n - 1 will return "n is composite"; for prime n none will. If, after using many different values of a, n has not been proved composite it is called a "probable prime".
The Miller–Rabin primality test is based on the same principles. 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.
In § VI of the Disquisitiones Arithmeticae[38] Gauss discusses two factoring algorithms that use quadratic residues and the law of quadratic reciprocity.
Several modern factorization algorithms (including Dixon's algorithm, the continued fraction method, the quadratic sieve, and the number field sieve) generate small quadratic residues (modulo the number being factorized) in an attempt to find a congruence of squares which will yield a factorization. The number field sieve is the fastest general-purpose factorization algorithm known.
The following table lists the quadratic residues mod 1 to 75 (a means it is not coprime to n). (For the quadratic residues coprime to n, see, and for nonzero quadratic residues, see .)
| n | quadratic residues mod n | n | quadratic residues mod n | n | quadratic residues mod n | |
|---|---|---|---|---|---|---|
| 1 | 0 | 26 | , 1, 3,, 9,,,,,, 17,, 23, 25 | 51 | , 1, 4,, 13,, 16,, 19,, 25,,,,,, 43, 49 | |
| 2 | , 1 | 27 | , 1, 4, 7,, 10, 13, 16, 19, 22, 25 | 52 | , 1,, 9,,,, 17, 25, 29,,,, 49 | |
| 3 | , 1 | 28 | , 1,,, 9,,, 25 | 53 | , 1, 4, 6, 7, 9, 10, 11, 13, 15, 16, 17, 24, 25, 28, 29, 36, 37, 38, 40, 42, 43, 44, 46, 47, 49, 52 | |
| 4 | , 1 | 29 | , 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28 | 54 | , 1,, 7,,, 13,, 19,, 25,,, 31,,, 37,, 43,, 49, | |
| 5 | , 1, 4 | 30 | , 1,,,,,,, 19,,, | 55 | , 1, 4,, 9,, 14,, 16,,, 26, 31, 34, 36,,, 49 | |
| 6 | , 1,, | 31 | , 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28 | 56 | , 1,,, 9,, 25,,,,, | |
| 7 | , 1, 2, 4 | 32 | , 1,, 9,, 17, 25 | 57 | , 1, 4,, 7,, 16,,, 25, 28,,,,, 43,, 49,, 55 | |
| 8 | , 1, | 33 | , 1,, 4,,,, 16,, 25,, 31 | 58 | , 1,, 5,, 7, 9, 13,,,, 23,, 25,,,, 33,, 35,,,, 45, 49, 51,, 53,, 57 | |
| 9 | , 1, 4, 7 | 34 | , 1,,,, 9, 13, 15,,,, 19, 21, 25,,,, 33 | 59 | , 1, 3, 4, 5, 7, 9, 12, 15, 16, 17, 19, 20, 21, 22, 25, 26, 27, 28, 29, 35, 36, 41, 45, 46, 48, 49, 51, 53, 57 | |
| 10 | , 1,,,, 9 | 35 | , 1, 4, 9, 11,,, 16,,, 29, | 60 | , 1,,,,,,,,,, 49 | |
| 11 | , 1, 3, 4, 5, 9 | 36 | , 1,,, 13,, 25, | 61 | , 1, 3, 4, 5, 9, 12, 13, 14, 15, 16, 19, 20, 22, 25, 27, 34, 36, 39, 41, 42, 45, 46, 47, 48, 49, 52, 56, 57, 58, 60 | |
| 12 | , 1,, | 37 | , 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36 | 62 | , 1,,, 5, 7,, 9,,,,, 19,, 25,,,, 33, 35,,, 39,, 41, 45, 47, 49,, 51,, 59 | |
| 13 | , 1, 3, 4, 9, 10, 12 | 38 | , 1,, 5,, 7, 9, 11,, 17,,, 23,, 25,,,, 35, | 63 | , 1, 4,,, 16,, 22, 25,,, 37, 43, 46,, 58 | |
| 14 | , 1,,,,, 9, 11 | 39 | , 1,, 4,, 10,,, 16, 22, 25,,, | 64 | , 1,, 9,, 17, 25, 33,, 41, 49, 57 | |
| 15 | , 1, 4,,, | 40 | , 1,, 9,,,,, | 65 | , 1, 4, 9,, 14, 16,,, 29,,, 36,,, 49, 51,, 56, 61, 64 | |
| 16 | , 1,, 9 | 41 | , 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40 | 66 | , 1,,,,,,,, 25,, 31,,,, 37,,,, 49,,,, | |
| 17 | , 1, 2, 4, 8, 9, 13, 15, 16 | 42 | , 1,,,,,,,,, 25,,,, 37, | 67 | , 1, 4, 6, 9, 10, 14, 15, 16, 17, 19, 21, 22, 23, 24, 25, 26, 29, 33, 35, 36, 37, 39, 40, 47, 49, 54, 55, 56, 59, 60, 62, 64, 65 | |
| 18 | , 1,, 7,,, 13, | 43 | , 1, 4, 6, 9, 10, 11, 13, 14, 15, 16, 17, 21, 23, 24, 25, 31, 35, 36, 38, 40, 41 | 68 | , 1,,, 9, 13,,, 21, 25,, 33,, 49,, 53,, | |
| 19 | , 1, 4, 5, 6, 7, 9, 11, 16, 17 | 44 | , 1,, 5, 9,,,, 25,,, 37 | 69 | , 1,, 4,,,, 13, 16,,, 25,, 31,,,,, 49, 52,, 55, 58, 64 | |
| 20 | , 1,,, 9, | 45 | , 1, 4,,, 16, 19,, 31, 34,, | 70 | , 1,, 9, 11,,,,,, 29,,,, 39,,,,, 51,,,, | |
| 21 | , 1, 4,,,, 16, | 46 | , 1,, 3,,,, 9,, 13,,,,, 25,, 27, 29, 31,, 35,, 39, 41 | 71 | , 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 19, 20, 24, 25, 27, 29, 30, 32, 36, 37, 38, 40, 43, 45, 48, 49, 50, 54, 57, 58, 60, 64 | |
| 22 | , 1, 3,, 5, 9,,,, 15,, | 47 | , 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 17, 18, 21, 24, 25, 27, 28, 32, 34, 36, 37, 42 | 72 | , 1,,,, 25,,,, 49,, | |
| 23 | , 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 | 48 | , 1,,,, 25,, | 73 | , 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 19, 23, 24, 25, 27, 32, 35, 36, 37, 38, 41, 46, 48, 49, 50, 54, 55, 57, 61, 64, 65, 67, 69, 70, 71, 72 | |
| 24 | , 1,,,, | 49 | , 1, 2, 4, 8, 9, 11, 15, 16, 18, 22, 23, 25, 29, 30, 32, 36, 37, 39, 43, 44, 46 | 74 | , 1, 3,, 7, 9,, 11,,, 21, 25,, 27,,, 33,,,,,, 41,,, 47,, 49, 53,,, 63,, 65, 67,, 71, 73 | |
| 25 | , 1, 4, 6, 9, 11, 14, 16, 19, 21, 24 | 50 | , 1,,, 9, 11,,, 19, 21,,,, 29, 31,,, 39, 41,,, 49 | 75 | , 1, 4,,, 16, 19,,,, 31, 34,,, 46, 49,,, 61, 64,, |
| x | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| x2 | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 | 100 | 121 | 144 | 169 | 196 | 225 | 256 | 289 | 324 | 361 | 400 | 441 | 484 | 529 | 576 | 625 | |
| mod 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| mod 2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | |
| mod 3 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | |
| mod 4 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | |
| mod 5 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 | |
| mod 6 | 1 | 4 | 3 | 4 | 1 | 0 | 1 | 4 | 3 | 4 | 1 | 0 | 1 | 4 | 3 | 4 | 1 | 0 | 1 | 4 | 3 | 4 | 1 | 0 | 1 | |
| mod 7 | 1 | 4 | 2 | 2 | 4 | 1 | 0 | 1 | 4 | 2 | 2 | 4 | 1 | 0 | 1 | 4 | 2 | 2 | 4 | 1 | 0 | 1 | 4 | 2 | 2 | |
| mod 8 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 | |
| mod 9 | 1 | 4 | 0 | 7 | 7 | 0 | 4 | 1 | 0 | 1 | 4 | 0 | 7 | 7 | 0 | 4 | 1 | 0 | 1 | 4 | 0 | 7 | 7 | 0 | 4 | |
| mod 10 | 1 | 4 | 9 | 6 | 5 | 6 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 6 | 5 | 6 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 6 | 5 | |
| mod 11 | 1 | 4 | 9 | 5 | 3 | 3 | 5 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 5 | 3 | 3 | 5 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | |
| mod 12 | 1 | 4 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 4 | 1 | 0 | 1 | |
| mod 13 | 1 | 4 | 9 | 3 | 12 | 10 | 10 | 12 | 3 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 3 | 12 | 10 | 10 | 12 | 3 | 9 | 4 | 1 | |
| mod 14 | 1 | 4 | 9 | 2 | 11 | 8 | 7 | 8 | 11 | 2 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 2 | 11 | 8 | 7 | 8 | 11 | 2 | 9 | |
| mod 15 | 1 | 4 | 9 | 1 | 10 | 6 | 4 | 4 | 6 | 10 | 1 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 1 | 10 | 6 | 4 | 4 | 6 | 10 | |
| mod 16 | 1 | 4 | 9 | 0 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 0 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 0 | 9 | 4 | 1 | 0 | 1 | |
| mod 17 | 1 | 4 | 9 | 16 | 8 | 2 | 15 | 13 | 13 | 15 | 2 | 8 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 8 | 2 | 15 | 13 | |
| mod 18 | 1 | 4 | 9 | 16 | 7 | 0 | 13 | 10 | 9 | 10 | 13 | 0 | 7 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 7 | 0 | 13 | |
| mod 19 | 1 | 4 | 9 | 16 | 6 | 17 | 11 | 7 | 5 | 5 | 7 | 11 | 17 | 6 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 6 | 17 | |
| mod 20 | 1 | 4 | 9 | 16 | 5 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 5 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 5 | |
| mod 21 | 1 | 4 | 9 | 16 | 4 | 15 | 7 | 1 | 18 | 16 | 16 | 18 | 1 | 7 | 15 | 4 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | |
| mod 22 | 1 | 4 | 9 | 16 | 3 | 14 | 5 | 20 | 15 | 12 | 11 | 12 | 15 | 20 | 5 | 14 | 3 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | |
| mod 23 | 1 | 4 | 9 | 16 | 2 | 13 | 3 | 18 | 12 | 8 | 6 | 6 | 8 | 12 | 18 | 3 | 13 | 2 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | |
| mod 24 | 1 | 4 | 9 | 16 | 1 | 12 | 1 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 1 | 12 | 1 | 16 | 9 | 4 | 1 | 0 | 1 | |
| mod 25 | 1 | 4 | 9 | 16 | 0 | 11 | 24 | 14 | 6 | 0 | 21 | 19 | 19 | 21 | 0 | 6 | 14 | 24 | 11 | 0 | 16 | 9 | 4 | 1 | 0 |
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.
| \left( | a |
| n |
\right)