In
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 ...
, an
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 ...
''q'' is called a quadratic residue
modulo ''n'' if it is
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 ...
to a
perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that:
:
Otherwise, ''q'' is called a quadratic nonresidue modulo ''n''.
Originally an abstract
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 ...
concept from the branch of number theory known as
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 ...
, quadratic residues are now used in applications ranging from
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 ...
to
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 ...
and the
factoring of large numbers.
History, conventions, and elementary facts
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,
Legendre, 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''
2 ≡ (''n'' − ''a'')
2 (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.
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
:12 ≡ 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 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 ide ...
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''
2 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
:
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
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
then , and if then
but if
we do not know whether or . For example:
and
, 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 12 ≡ 1, 10462 ≡ 2, 1232 ≡ 3, 22 ≡ 4, 6432 ≡ 5, 872 ≡ 6, 6682 ≡ 7, 4292 ≡ 8, 32 ≡ 9, and 5292 ≡ 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
:
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.
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
.
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.
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:
:
where
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
:
and let
:
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)
:
and if ''p'' ≡ 3 (mod 4)
:
For example: (residues in bold)
Modulo 17
:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
::''A''00 = ,
::''A''01 = ,
::''A''10 = ,
::''A''11 = .
Modulo 19
:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18
::''A''00 = ,
::''A''01 = ,
::''A''10 = ,
::''A''11 = .
Gauss (1828) introduced this sort of counting when he proved that if ''p'' ≡ 1 (mod 4) then ''x''
4 ≡ 2 (mod ''p'') can be solved if and only if ''p'' = ''a''
2 + 64 ''b''
2.
The Pólya–Vinogradov inequality
The values of
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 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'',
:
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
:
this shows that the number of quadratic residues modulo ''q'' in any interval of length ''N'' is
:
It is easy to prove that
:
In fact,
:
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
:
This result cannot be substantially improved, for
Schur had proved in 1918 that
:
and
Paley had proved in 1932 that
:
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'')2.
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''2 ≡ ''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''1 roots modulo the first one, ''n''2 mod the second, ..., there will be ''n''1''n''2... 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 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.
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 ...
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 , if ''n'' ≡ 3 (mod 4), Lagrange found that the solutions are given by
:
and Legendre found a similar solution if ''n'' ≡ 5 (mod 8):
:
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 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 ...
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 ...
then there is no solution; if ''n'' is congruent to 2 modulo 4 and , then there is also no solution. If ''n'' is not congruent to 2 modulo 4 and , or ''n'' is congruent to 2 modulo 4 and , there may or may not be one.
If the complete factorization of ''n'' is not known, and and ''n'' is not congruent to 2 modulo 4, or ''n'' is congruent to 2 modulo 4 and , 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 ...
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, ...
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 .)
See also
*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 ...
* Gauss's lemma
*Zolotarev's lemma
In number theory, Zolotarev's lemma states that the Legendre symbol
:\left(\frac\right)
for an integer ''a'' modulo an odd prime number ''p'', where ''p'' does not divide ''a'', can be computed as the sign of a permutation:
:\left(\frac\right) ...
*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 ...
*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 ...
*Quadratic residue code
A quadratic residue code is a type of cyclic code.
Examples
Examples of quadratic
residue codes include the (7,4) Hamming code
over GF(2), the (23,12) binary Golay code
over GF(2) and the (11,6) ternary Golay code
over GF(3).
Constructions
There ...
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
**Ge ...
. 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