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â ...
, Euler's criterion is a formula for determining whether 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 ...
is a
quadratic residue modulo a
prime
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 ...
. Precisely,
Let ''p'' be an
odd
Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric.
Odd may also refer to:
Acronym
* ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...
prime and ''a'' be an integer
coprime
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 ''p''. Then
:
Euler's criterion can be concisely reformulated using the
Legendre symbol:
:
The criterion first appeared in a 1748 paper by
Leonhard 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 ...
.
[L Euler, Novi commentarii Academiae Scientiarum Imperialis Petropolitanae, 8, 1760-1, 74; Opusc Anal. 1, 1772, 121; Comm. Arith, 1, 274, 487]
Proof
The proof uses the fact that the residue classes modulo a prime number are a
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 ...
. See the article
prime field
In mathematics, the characteristic of a ring , often denoted , is defined to be the smallest number of times one must use the ring's multiplicative identity (1) in a sum to get the additive identity (0). If this sum never reaches the additive ide ...
for more details.
Because the modulus is prime,
Lagrange's theorem applies: a polynomial of degree can only have at most roots. In particular, has at most 2 solutions for each . This immediately implies that besides 0 there are at least distinct quadratic residues modulo : each of the possible values of can only be accompanied by one other to give the same residue.
In fact,
This is because
So, the
distinct quadratic residues are:
As is coprime to ,
Fermat's little theorem says that
:
which can be written as
:
Since the integers mod form a field, for each , one or the other of these factors must be zero.
Now if is a quadratic residue, ,
:
So every quadratic residue (mod ) makes the first factor zero.
Applying Lagrange's theorem again, we note that there can be no more than values of that make the first factor zero. But as we noted at the beginning, there are at least distinct quadratic residues (mod ) (besides 0). Therefore, they are precisely the residue classes that make the first factor zero. The other residue classes, the nonresidues, must make the second factor zero, or they would not satisfy Fermat's little theorem. This is Euler's criterion.
Alternative proof
This proof only uses the fact that any congruence
has a unique (modulo
) solution
provided
does not divide
. (This is true because as
runs through all nonzero remainders modulo
without repetitions, so does
- if we have
, then
, hence
, but
and
aren't congruent modulo
.) It follows from this fact that all nonzero remainders modulo
the square of which isn't congruent to
can be grouped into unordered pairs
according to the rule that the product of the members of each pair is congruent to
modulo
(since by this fact for every
we can find such an
, uniquely, and vice versa, and they will differ from each other if
is not congruent to
). If
is a quadratic nonresidue, this is simply a regrouping of all
nonzero residues into
pairs, hence we conclude that
. If
is a quadratic residue, exactly two remainders were not among those paired,
and
such that
. If we pair those two absent remainders together, their product will be
rather than
, whence in this case
. In summary, considering these two cases we have demonstrated that for
we have
. It remains to substitute
(which is obviously a square) into this formula to obtain at once
Wilson's theorem
In algebra and number theory, Wilson's theorem states that a natural number ''n'' > 1 is a prime number if and only if the product of all the positive integers less than ''n'' is one less than a multiple of ''n''. That is (using the notations of m ...
, Euler's criterion, and (by squaring both sides of Euler's criterion)
Fermat's little theorem.
Examples
Example 1: Finding primes for which ''a'' is a residue
Let ''a'' = 17. For which primes ''p'' is 17 a quadratic residue?
We can test prime ''ps manually given the formula above.
In one case, testing ''p'' = 3, we have 17
(3 − 1)/2 = 17
1 ≡ 2 ≡ −1 (mod 3), therefore 17 is not a quadratic residue modulo 3.
In another case, testing ''p'' = 13, we have 17
(13 − 1)/2 = 17
6 ≡ 1 (mod 13), therefore 17 is a quadratic residue modulo 13. As confirmation, note that 17 ≡ 4 (mod 13), and 2
2 = 4.
We can do these calculations faster by using various modular arithmetic and Legendre symbol properties.
If we keep calculating the values, we find:
:(17/''p'') = +1 for ''p'' = (17 is a quadratic residue modulo these values)
:(17/''p'') = −1 for ''p'' = (17 is not a quadratic residue modulo these values).
Example 2: Finding residues given a prime modulus ''p''
Which numbers are squares modulo 17 (quadratic residues modulo 17)?
We can manually calculate it as:
: 1
2 = 1
: 2
2 = 4
: 3
2 = 9
: 4
2 = 16
: 5
2 = 25 ≡ 8 (mod 17)
: 6
2 = 36 ≡ 2 (mod 17)
: 7
2 = 49 ≡ 15 (mod 17)
: 8
2 = 64 ≡ 13 (mod 17).
So the set of the quadratic residues modulo 17 is . Note that we did not need to calculate squares for the values 9 through 16, as they are all negatives of the previously squared values (e.g. 9 ≡ −8 (mod 17), so 9
2 ≡ (−8)
2 = 64 ≡ 13 (mod 17)).
We can find quadratic residues or verify them using the above formula. To test if 2 is a quadratic residue modulo 17, we calculate 2
(17 − 1)/2 = 2
8 ≡ 1 (mod 17), so it is a quadratic residue. To test if 3 is a quadratic residue modulo 17, we calculate 3
(17 − 1)/2 = 3
8 ≡ 16 ≡ −1 (mod 17), so it is not a quadratic residue.
Euler's criterion is related 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 ...
.
Applications
In practice, it is more efficient to use an extended variant 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 ef ...
to calculate 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 ...
. If
is an odd prime, this is equal to the Legendre symbol, and decides whether
is a quadratic residue modulo
.
On the other hand, since the equivalence of
to the Jacobi symbol holds for all odd primes, but not necessarily for composite numbers, calculating both and comparing them can be used as a primality test, specifically 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 196 ...
. Composite numbers for which the congruence holds for a given
are called
Euler–Jacobi pseudoprime In number theory, an odd integer ''n'' is called an Euler–Jacobi probable prime (or, more commonly, an Euler probable prime) to base ''a'', if ''a'' and ''n'' are coprime, and
:a^ \equiv \left(\frac\right)\pmod
where \left(\frac\right) is the J ...
s to base
.
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
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 ...
, 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, and unpublished notes.
*
*
*
*
External links
The Euler Archive
{{DEFAULTSORT:Euler's Criterion
Articles containing proofs
Modular arithmetic
Quadratic residue
Squares in number theory
Theorems about prime numbers