Euler's criterion

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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 an integer coprime to p. Then[1]

Euler's criterion can be concisely reformulated using the Legendre symbol:[2]

The criterion first appeared in a 1748 paper by Euler.[3]

Proof[edit]

The proof uses the fact that the residue classes modulo a prime number are a field. See the article prime field for more details.

Because the modulus is prime, Lagrange's theorem applies: a polynomial of degree k can only have at most k roots. In particular, has at most 2 roots for each a. This immediately implies that besides 0 there are at least (p - 1)/2 distinct quadratic residues (mod p): each of the p - 1 possible x can only be accompanied by one other to give the same residue.

As a is coprime to p, Fermat's little theorem says that

which can be written as

Since the integers mod p form a field, for each a one or the other of these factors must be zero.

Now if a is a quadratic residue, ax2,

So every quadratic residue (mod p) makes the first factor zero.

Applying Lagrange's theorem again, we note that there can be no more than (p - 1)/2 values of a that make the first factor zero. But as we noted at the beginning, there are at least (p - 1)/2 distinct quadratic residues (mod p) (besides 0). Therefore they are precisely the residue classes that make the first factor zero. The other (p - 1)/2 residue classes, the nonresidues, must make the second factor zero, or they would not satisfy Fermat's little theorem. This is Euler's criterion.

Examples[edit]

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 p's manually given the formula above.

In one case, testing p = 3, we have 17(3 − 1)/2 = 171 ≡ 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 = 176 ≡ 1 (mod 13), therefore 17 is a quadratic residue modulo 13. As confirmation, note that 17 ≡ 4 (mod 13), and 22 = 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 = {13, 19, ...} (17 is a quadratic residue modulo these values)
(17/p) = −1 for p = {3, 5, 7, 11, 23, ...} (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:

12 = 1
22 = 4
32 = 9
42 = 16
52 = 25 ≡ 8 (mod 17)
62 = 36 ≡ 2 (mod 17)
72 = 49 ≡ 15 (mod 17)
82 = 64 ≡ 13 (mod 17).

So the set of the quadratic residues modulo 17 is {1,2,4,8,9,13,15,16}. 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 92 ≡ (−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 = 28 ≡ 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 = 38 ≡ 16 ≡ −1 (mod 17), so it is not a quadratic residue.

Euler's criterion is related to the Law of quadratic reciprocity and is used in a definition of Euler–Jacobi pseudoprimes.

Notes[edit]

  1. ^ Gauss, DA, Art. 106
  2. ^ Hardy & Wright, thm. 83
  3. ^ Lemmermeyer, p. 4 cites two papers, E134 and E262 in the Euler Archive

References[edit]

The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

  • Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 0-387-96254-9 
  • Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8 

External links[edit]