number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777� ...

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...

modulo In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation). Given two positive numbers and , modulo (often abbreviated as ) is t ...

congruent Congruence may refer to: Mathematics * Congruence (geometry), being the same size and shape * Congruence or congruence relation, in abstract algebra, an equivalence relation on an algebraic structure that is compatible with the structure * In mod ...

perfect square ''Perfect Square'' is a 2004 concert film of the alternative rock Musical ensemble, band R.E.M. (band), R.E.M., filmed on July 19, 2003, at the bowling green, Bowling Green in Wiesbaden, Germany. It was released by Warner Reprise Video on March 9, ...

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

modular arithmetic In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book ...

acoustical engineering Acoustical engineering (also known as acoustic engineering) is the branch of engineering dealing with sound and vibration. It includes the application of acoustics, the science of sound and vibration, in technology. Acoustical engineers are typical ...

cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

Fermat Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he i ...

Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...

Lagrange Joseph-Louis Lagrange (born Giuseppe Luigi LagrangiaLegendre, and other number theorists of the 17th and 18th centuries established theorems and formed conjectures about quadratic residues, but the first systematic treatment is § IV of

Gauss Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...

's ''

Disquisitiones Arithmeticae The (Latin for "Arithmetical Investigations") is a textbook of number theory written in Latin by Carl Friedrich Gauss in 1798 when Gauss was 21 and first published in 1801 when he was 24. It is notable for having had a revolutionary impact on th ...

'' (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 the numbers 0, 1, ..., . Because ''a''² ≡ (''n'' − ''a'')² (mod ''n''), the list of squares modulo ''n'' is symmetric around ''n''/2, and the list only needs to go that high. This can be seen in the table

below Below may refer to: *Earth *Ground (disambiguation) *Soil *Floor *Bottom (disambiguation) Bottom may refer to: Anatomy and sex * Bottom (BDSM), the partner in a BDSM who takes the passive, receiving, or obedient role, to that of the top or ...

. Thus, the number of quadratic residues modulo ''n'' cannot exceed ''n''/2 + 1 (''n'' even) or (''n'' + 1)/2 (''n'' odd). The product of two residues is always a residue.

Prime modulus

Modulo 2, every integer is a quadratic residue. Modulo an odd

prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

''p'' there are (''p'' + 1)/2 residues (including 0) and (''p'' − 1)/2 nonresidues, by

Euler's criterion In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely, Let ''p'' be an odd prime and ''a'' be an integer coprime to ''p''. Then : a^ \equiv \begin \;\;\,1\pmod& \text ...

. In this case, it is customary to consider 0 as a special case and work within the multiplicative group of nonzero elements of the

field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...

Z/''p''Z. (In other words, every congruence class except zero modulo ''p'' has a multiplicative inverse. This is not true for composite moduli.)Gauss, DA, art. 96 Following this convention, the multiplicative inverse of a residue is a residue, and the inverse of a nonresidue is a nonresidue.Gauss, DA, art. 98 Following this convention, modulo an odd prime number there are an equal number of residues and nonresidues. Modulo a prime, the product of two nonresidues is a residue and the product of a nonresidue and a (nonzero) residue is a nonresidue. The first supplement to the

law of quadratic reciprocity In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard st ...

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.

Prime power modulus

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).

For example, mod (32) the odd squares are :1² ≡ 15² ≡ 1 :3² ≡ 13² ≡ 9 :5² ≡ 11² ≡ 25 :7² ≡ 9² ≡ 49 ≡ 17 and the even ones are :0² ≡ 8² ≡ 16² ≡ 0 :2² ≡ 6²≡ 10² ≡ 14²≡ 4 :4² ≡ 12² ≡ 16.

So a nonzero number is a residue mod 8, 16, etc., if and only if it is of the form 4^''k''(8''n'' + 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''.Gauss, DA, art. 101 If the modulus is ''p''^''n'', :then ''p''^''k''''a'' ::is a residue modulo ''p''^''n'' if ''k'' ≥ ''n'' ::is a nonresidue modulo ''p''^''n'' if ''k'' < ''n'' is odd ::is a residue modulo ''p''^''n'' if ''k'' < ''n'' is even and ''a'' is a residue ::is a nonresidue modulo ''p''^''n'' if ''k'' < ''n'' is even and ''a'' is a nonresidue. Notice that the rules are different for powers of two and powers of odd primes. Modulo an odd prime power ''n'' = ''p''^''k'', 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 In mathematics, the Klein four-group is a Group (mathematics), group with four elements, in which each element is Involution (mathematics), self-inverse (composing it with itself produces the identity) and in which composing any two of the three ...

.

Composite modulus not a prime power

The basic fact in this case is :if ''a'' is a residue modulo ''n'', then ''a'' is a residue modulo ''p''^''k'' for ''every'' prime power dividing ''n''. :if ''a'' is a nonresidue modulo ''n'', then ''a'' is a nonresidue modulo ''p''^''k'' 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.

This phenomenon can best be described using the vocabulary of abstract algebra. The congruence classes relatively prime to the modulus are a

group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic iden ...

under multiplication, called the

group of units In algebra, a unit of a ring is an invertible element for the multiplication of the ring. That is, an element of a ring is a unit if there exists in such that vu = uv = 1, where is the multiplicative identity; the element is unique for this ...

of the

ring Ring may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...

Z/''n''Z, and the squares are a

subgroup In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgroup ...

of it. Different nonresidues may belong to different

coset In mathematics, specifically group theory, a subgroup of a group may be used to decompose the underlying set of into disjoint, equal-size subsets called cosets. There are ''left cosets'' and ''right cosets''. Cosets (both left and right) ...

s, and there is no simple rule that predicts which one their product will be in. Modulo a prime, there is only the subgroup of squares and a single coset. 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/''n''Z, which has

zero divisor In abstract algebra, an element of a ring is called a left zero divisor if there exists a nonzero in such that , or equivalently if the map from to that sends to is not injective. Similarly, an element of a ring is called a right zero ...

s for composite ''n''. For this reason some authors add to the definition that a quadratic residue ''a'' must not only be a square but must also be

relatively prime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...

to the modulus ''n''. (''a'' is coprime to ''n'' if and only if ''a''² is coprime to ''n''.) Although it makes things tidier, this article does not insist that residues must be coprime to the modulus.

Notations

Gauss used and to denote residuosity and non-residuosity, respectively; :for example, and , or and . Although this notation is compact and convenient for some purposes, a more useful notation is the

Legendre symbol In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo an odd prime number ''p'': its value at a (nonzero) quadratic residue mod ''p'' is 1 and at a non-quadratic residu ...

, also called the quadratic character, which is defined for all integers and positive odd

prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

s as :

\left(\frac\right) = \begin\;\;\,0&\textp \text  a\\+1&\text a \operatorname p \textp \text  a\\-1&\texta \operatorname p \textp \text a\end

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 In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...

from the multiplicative group of nonzero congruence classes modulo to the

complex numbers In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form a ...

under multiplication. Setting

(\tfrac) = 0

allows its

domain Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined **Domain of definition of a partial function **Natural domain of a partial function **Domain of holomorphy of a function * Do ...

to be extended to the multiplicative

semigroup In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...

of all the integers. One advantage of this notation over Gauss's is that the Legendre symbol is a function that can be used in formulas. It can also easily be generalized to cubic, quartic and higher power residues. There is a generalization of the Legendre symbol for composite values of , the

Jacobi symbol Jacobi symbol for various ''k'' (along top) and ''n'' (along left side). Only are shown, since due to rule (2) below any other ''k'' can be reduced modulo ''n''. Quadratic residues are highlighted in yellow — note that no entry with a ...

, but its properties are not as simple: if is composite and the Jacobi symbol

(\tfrac) = -1,

then , and if then

(\tfrac) = 1,

but if

(\tfrac) = 1

we do not know whether or . For example:

(\tfrac) = 1

and

(\tfrac) = 1

, but and . If is prime, the Jacobi and Legendre symbols agree.

Distribution of quadratic residues

Although quadratic residues appear to occur in a rather random pattern modulo ''n'', and this has been exploited in such

applications Application may refer to: Mathematics and computing * Application software, computer software designed to help the user to perform specific tasks ** Application layer, an abstraction layer that specifies protocols and interface methods used in a c ...

as

acoustics Acoustics is a branch of physics that deals with the study of mechanical waves in gases, liquids, and solids including topics such as vibration, sound, ultrasound and infrasound. A scientist who works in the field of acoustics is an acoustician ...

and

cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

, their distribution also exhibits some striking regularities. Using Dirichlet's theorem on primes in

arithmetic progression An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...

s, the

law of quadratic reciprocity In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard st ...

, and the

Chinese remainder theorem In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...

(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 1² ≡ 1, 1046² ≡ 2, 123² ≡ 3, 2² ≡ 4, 643² ≡ 5, 87² ≡ 6, 668² ≡ 7, 429² ≡ 8, 3² ≡ 9, and 529² ≡ 10 (mod 2521).

Dirichlet's formulas

The first of these regularities stems from

Peter Gustav Lejeune Dirichlet Johann Peter Gustav Lejeune Dirichlet (; 13 February 1805 – 5 May 1859) was a German mathematician who made deep contributions to number theory (including creating the field of analytic number theory), and to the theory of Fourier series and ...

's work (in the 1830s) on the analytic formula for the class number of binary

quadratic form In mathematics, a quadratic form is a polynomial with terms all of degree two ("form" is another name for a homogeneous polynomial). For example, :4x^2 + 2xy - 3y^2 is a quadratic form in the variables and . The coefficients usually belong to a ...

s. Let ''q'' be a prime number, ''s'' a complex variable, and define a

Dirichlet L-function In mathematics, a Dirichlet ''L''-series is a function of the form :L(s,\chi) = \sum_^\infty \frac. where \chi is a Dirichlet character and ''s'' a complex variable with real part greater than 1. It is a special case of a Dirichlet series. By a ...

as :

L(s) = \sum_^\infty\left(\frac\right)n^.

Dirichlet showed that if ''q'' ≡ 3 (mod 4), then :

L(1) = -\frac\sum_^ \frac \left(\frac\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. 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

\frac

. Dirichlet also proved that for prime ''q'' ≡ 3 (mod 4), :

L(1) = \frac\sum_^\frac\left(\frac\right) > 0.

This implies that there are more quadratic residues than nonresidues among the numbers 1, 2, ..., (''q'' − 1)/2.

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.

Law of 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(\frac\right) \left(\frac\right) = (-1)^

where

\left(\frac\right)

is the

Legendre symbol In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo an odd prime number ''p'': its value at a (nonzero) quadratic residue mod ''p'' is 1 and at a non-quadratic residu ...

. Thus, for numbers ''a'' and odd primes ''p'' that don't divide ''a'':

Pairs of residues and nonresidues

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, let ''p'' be an odd prime. For ''i'', ''j'' = 0, 1 define the sets :

A_=\left\,

and let :

\alpha_ = , A_, .

That is, :α₀₀ is the number of residues that are followed by a residue, :α₀₁ is the number of residues that are followed by a nonresidue, :α₁₀ is the number of nonresidues that are followed by a residue, and :α₁₁ is the number of nonresidues that are followed by a nonresidue. Then if ''p'' ≡ 1 (mod 4) :

\alpha_ = \frac,\;\alpha_ =\alpha_ =\alpha_ = \frac

and if ''p'' ≡ 3 (mod 4) :

\alpha_ = \frac,\;\alpha_ =\alpha_ =\alpha_ = \frac.

For example: (residues in bold) Modulo 17 :1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ::''A''₀₀ = , ::''A''₀₁ = , ::''A''₁₀ = , ::''A''₁₁ = . Modulo 19 :1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 ::''A''₀₀ = , ::''A''₀₁ = , ::''A''₁₀ = , ::''A''₁₁ = .

Gauss (1828) introduced this sort of counting when he proved that if ''p'' ≡ 1 (mod 4) then ''x''⁴ ≡ 2 (mod ''p'') can be solved if and only if ''p'' = ''a''² + 64 ''b''².

The Pólya–Vinogradov inequality

The values of

(\tfrac)

for consecutive values of ''a'' mimic a random variable like a

coin flip Coin flipping, coin tossing, or heads or tails is the practice of throwing a coin in the air and checking which side is showing when it lands, in order to choose between two alternatives, heads or tails, sometimes used to resolve a dispute betwe ...

. Specifically, Pólya and

Vinogradov Vinogradov or Vinogradoff (russian: Виногра́дов) is a common Russian last name derived from the Russian word виноград (''vinograd'', meaning "grape" and виноградник ''vinogradnik'', meaning "vineyard"). Vinogradova (ru ...

proved (independently) in 1918 that for any nonprincipal

Dirichlet character In analytic number theory and related branches of mathematics, a complex-valued arithmetic function \chi:\mathbb\rightarrow\mathbb is a Dirichlet character of modulus m (where m is a positive integer) if for all integers a and b: :1) \chi ...

χ(''n'') modulo ''q'' and any integers ''M'' and ''N'', :

\left, \sum_^\chi(n)\ =O\left( \sqrt q \log q\right),

in

big O notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...

. Setting :

\chi(n) = \left(\frac\right),

this shows that the number of quadratic residues modulo ''q'' in any interval of length ''N'' is :

\fracN + O(\sqrt q\log q).

It is easy to prove that :

\left,  \sum_^ \left( \frac \right) \ < \sqrt q \log q.

In fact, :

\left,  \sum_^ \left( \frac \right) \ < \frac \sqrt q \log q+0.41\sqrt q +0.61.

Montgomery and

Vaughan Vaughan () (2021 population 323,103) is a city in Ontario, Canada. It is located in the Regional Municipality of York, just north of Toronto. Vaughan was the fastest-growing municipality in Canada between 1996 and 2006 with its population increas ...

improved this in 1977, showing that, if the

generalized Riemann hypothesis The Riemann hypothesis is one of the most important conjectures in mathematics. It is a statement about the zeros of the Riemann zeta function. Various geometrical and arithmetical objects can be described by so-called global ''L''-functions, whic ...

is true then :

\left, \sum_^\chi(n)\=O\left(\sqrt q \log  \log q\right).

This result cannot be substantially improved, for Schur had proved in 1918 that :

\max_N \left, \sum_^\left(\frac\right)\>\frac\sqrt q

and Paley had proved in 1932 that :

\max_N \left, \sum_^\left(\frac\right)\>\frac\sqrt d \log \log d

for infinitely many ''d'' > 0.

Least quadratic non-residue

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 sum In mathematics, a character sum is a sum \sum \chi(n) of values of a Dirichlet character χ '' modulo'' ''N'', taken over a given range of values of ''n''. Such sums are basic in a number of questions, for example in the distribution of quadratic ...

s. Assuming the

Generalised Riemann hypothesis The Riemann hypothesis is one of the most important conjectures in mathematics. It is a statement about the zeros of the Riemann zeta function. Various geometrical and arithmetical objects can be described by so-called global ''L''-functions, ...

, Ankeny obtained ''n''(''p'') ≪ (log ''p'')². Linnik showed that the number of ''p'' less than ''X'' such that ''n''(''p'') > X^ε is bounded by a constant depending on ε. The least quadratic non-residues mod ''p'' for odd primes ''p'' are: :2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, ...

Quadratic excess

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.

Complexity of finding square roots

That is, given a number ''a'' and a modulus ''n'', how hard is it # to tell whether an ''x'' solving ''x''² ≡ ''a'' (mod ''n'') exists # assuming one does exist, to calculate 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 ''n''₁ roots modulo the first one, ''n''₂ mod the second, ..., there will be ''n''₁''n''₂... roots modulo ''n''. The theoretical way solutions modulo the prime powers are combined to make solutions modulo ''n'' is called the

Chinese remainder theorem In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...

; it can be implemented with an efficient algorithm.

For example: :Solve x² ≡ 6 (mod 15). ::x² ≡ 6 (mod 3) has one solution, 0; x² ≡ 6 (mod 5) has two, 1 and 4. :: and there are two solutions modulo 15, namely 6 and 9. :Solve x² ≡ 4 (mod 15). ::x² ≡ 4 (mod 3) has two solutions, 1 and 2; x² ≡ 4 (mod 5) has two, 2 and 3. :: and there are four solutions modulo 15, namely 2, 7, 8, and 13. :Solve x² ≡ 7 (mod 15). ::x² ≡ 7 (mod 3) has two solutions, 1 and 2; x² ≡ 7 (mod 5) has no solutions. :: and there are no solutions modulo 15.

Prime or prime power modulus

First off, if the modulus ''n'' is prime the

Legendre symbol In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo an odd prime number ''p'': its value at a (nonzero) quadratic residue mod ''p'' is 1 and at a non-quadratic residu ...

\left(\frac\right)

can be quickly computed using a variation of

Euclid's algorithm In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an eff ...

or the

Euler's criterion In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely, Let ''p'' be an odd prime and ''a'' be an integer coprime to ''p''. Then : a^ \equiv \begin \;\;\,1\pmod& \text ...

. If it is −1 there is no solution. Secondly, assuming that

\left(\frac\right)=1

, if ''n'' ≡ 3 (mod 4),

Lagrange Joseph-Louis Lagrange (born Giuseppe Luigi LagrangiaLegendre found a similar solution if ''n'' ≡ 5 (mod 8): :

x \equiv  \begin  
\pm\; a^            \pmod& \text a \text n \\
\pm\; a^2^ \pmod& \text a \text n \end

For prime ''n'' ≡ 1 (mod 8), however, there is no known formula. Tonelli (in 1891) and Cipolla 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(\frac\right)

until a nonresidue is found will quickly produce one. A slight variant of this algorithm is the

Tonelli–Shanks algorithm The Tonelli–Shanks algorithm (referred to by Shanks as the RESSOL algorithm) is used in modular arithmetic to solve for ''r'' in a congruence of the form ''r''2 ≡ ''n'' (mod ''p''), where ''p'' is a prime: that is, to find a square root of ''n'' ...

. If the modulus ''n'' is a

prime power In mathematics, a prime power is a positive integer which is a positive integer power of a single prime number. For example: , and are prime powers, while , and are not. The sequence of prime powers begins: 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17 ...

''n'' = ''p''^''e'', a solution may be found modulo ''p'' and "lifted" to a solution modulo ''n'' using

Hensel's lemma In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a prime number , then this root can be ''lifted'' to a ...

or an algorithm of Gauss.

Composite modulus

If the modulus ''n'' has been factored into prime powers the solution was discussed above. If ''n'' is not congruent to 2 modulo 4 and the

Kronecker symbol In number theory, the Kronecker symbol, written as \left(\frac an\right) or (a, n), is a generalization of the Jacobi symbol to all integers n. It was introduced by . Definition Let n be a non-zero integer, with prime factorization :n=u \cdot ...

\left(\tfrac\right)=-1

then there is no solution; if ''n'' is congruent to 2 modulo 4 and

\left(\tfrac\right)=-1

, then there is also no solution. If ''n'' is not congruent to 2 modulo 4 and

\left(\tfrac\right)=1

, or ''n'' is congruent to 2 modulo 4 and

\left(\tfrac\right)=1

, there may or may not be one. If the complete factorization of ''n'' is not known, and

\left(\tfrac\right)=1

and ''n'' is not congruent to 2 modulo 4, or ''n'' is congruent to 2 modulo 4 and

\left(\tfrac\right)=1

, the problem is known to be equivalent to

integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...

of ''n'' (i.e. an efficient solution to either problem could be used to solve the other efficiently).

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 In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms. Derivation Given a positive integer ''n'', Fermat's factorization method relies on finding numbers ''x'' and ''y'' satisfying the equali ...
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.

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 The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not. Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which are ...

, which is not known to be as

hard Hard may refer to: * Hardness, resistance of physical materials to deformation or fracture * Hard water, water with high mineral content Arts and entertainment * ''Hard'' (TV series), a French TV series * Hard (band), a Hungarian hard rock supe ...

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 In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

; however, this is a

fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...

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: Let , and . Then is solvable if and only if: * The

Legendre symbol In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo an odd prime number ''p'': its value at a (nonzero) quadratic residue mod ''p'' is 1 and at a non-quadratic residu ...

\left(\tfrac\right)=1

for all odd prime divisors ''p'' of ''n''. * if ''n'' is divisible by 4 but not 8; or if ''n'' is divisible by 8. 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 number of quadratic residues

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.

Applications of quadratic residues

Acoustics

Sound diffusers have been based on number-theoretic concepts such as primitive roots and quadratic residues.

Graph theory

Paley graph In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, whic ...

s are dense undirected graphs, one for each prime ''p'' ≡ 1 (mod 4), that form an infinite family of

conference graph In the mathematics, mathematical area of graph theory, a conference graph is a strongly regular graph with parameters ''v'', and It is the graph associated with a symmetric conference matrix, and consequently its order ''v'' must be 1 (modular a ...

s, which yield an infinite family of

symmetric Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...

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.

Cryptography

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 The hard problem of consciousness is the problem of explaining why and how humans have qualia or phenomenal experiences. This is in contrast to the "easy problems" of explaining the physical systems that give us and other animals the ability to d ...

) has been used for constructing cryptographic schemes such as the

Rabin cryptosystem The Rabin cryptosystem is a family of public-key encryption schemes based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization. The Rabin trapdoor function has the advantage that invertin ...

and the oblivious transfer. The

quadratic residuosity problem The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not. Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which are ...

is the basis for the Goldwasser-Micali cryptosystem. The

discrete logarithm In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...

is a similar problem that is also used in cryptography.

Primality testing

Euler's criterion In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely, Let ''p'' be an odd prime and ''a'' be an integer coprime to ''p''. Then : a^ \equiv \begin \;\;\,1\pmod& \text ...

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 The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic test to determine if a number is composite or probably prime. The idea behind the test was discovered by M. M. Artjuhov in 1967 ...

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. 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 In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific con ...

". The

Miller–Rabin primality test The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen prima ...

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 Riemann hypothesis is one of the most important conjectures in mathematics. It is a statement about the zeros of the Riemann zeta function. Various geometrical and arithmetical objects can be described by so-called global ''L''-functions, whic ...

; 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.

Integer factorization

In § VI of the ''Disquisitiones Arithmeticae''Gauss, DA, arts 329–334 Gauss discusses two factoring algorithms that use quadratic residues and the

law of quadratic reciprocity In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard st ...

. Several modern factorization algorithms (including

Dixon's algorithm In number theory, Dixon's factorization method (also Dixon's random squares method or Dixon's algorithm) is a general-purpose integer factorization algorithm; it is the prototypical factor base method. Unlike for other factor base methods, its run- ...

, the continued fraction method, the

quadratic sieve The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considerab ...

, and the

number field sieve In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form :\exp\left( ...

) generate small quadratic residues (modulo the number being factorized) in an attempt to find a

congruence of squares In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms. Derivation Given a positive integer ''n'', Fermat's factorization method relies on finding numbers ''x'' and ''y'' satisfying the equali ...

which will yield a factorization. The number field sieve is the fastest general-purpose factorization algorithm known.

Table of quadratic residues

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 .)

Notes

References

The ''

Disquisitiones Arithmeticae The (Latin for "Arithmetical Investigations") is a textbook of number theory written in Latin by Carl Friedrich Gauss in 1798 when Gauss was 21 and first published in 1801 when he was 24. It is notable for having had a revolutionary impact on th ...

'' has been translated from Gauss's Ciceronian Latin into

English English usually refers to: * English language * English people English may also refer to: Peoples, culture, and language * ''English'', an adjective for something of, from, or related to England ** English national ide ...

and

German German(s) may refer to: * Germany (of or related to) **Germania (historical use) * Germans, citizens of Germany, people of German ancestry, or native speakers of the German language ** For citizens of Germany, see also German nationality law **Ger ...

. 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 In algebraic number theory, a Gauss sum or Gaussian sum is a particular kind of finite sum of roots of unity, typically :G(\chi) := G(\chi, \psi)= \sum \chi(r)\cdot \psi(r) where the sum is over elements of some finite commutative ring , is a ...

, the investigations into

biquadratic reciprocity Quartic or biquadratic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence ''x''4 ≡ ''p'' (mod ''q'') is solvable; the word "reciprocity" comes from the form o ...

, and unpublished notes. * * * * * * A7.1: AN1, pg.249. * * * *

External links

* * {{DEFAULTSORT:Quadratic Residue Modular arithmetic NP-complete problems

History, conventions, and elementary facts

Prime modulus

Prime power modulus

Composite modulus not a prime power

Notations

Distribution of quadratic residues

Dirichlet's formulas

Law of quadratic reciprocity

Pairs of residues and nonresidues

The Pólya–Vinogradov inequality

Least quadratic non-residue

Quadratic excess

Complexity of finding square roots

Prime or prime power modulus

Composite modulus

The number of quadratic residues

Applications of quadratic residues

Acoustics

Graph theory

Cryptography

Primality testing

Integer factorization

Table of quadratic residues

See also

Notes

References

External links