close
Jump to content

Euler's criterion

From Wikipedia, the free encyclopedia

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[1][2][3] ap−12≡{1(modp) if there is an integer x such that x2≡a(modp),−1(modp) if there is no such integer.

Euler's criterion can be concisely reformulated using the Legendre symbol:[4] (ap)≡ap−12(modp).

The criterion dates from a 1748 paper by Leonhard Euler.[5][6]

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, x2 ≡ a (mod p) has at most 2 solutions for each a. This immediately implies that besides 0 there are at least ⁠p − 1/2⁠ distinct quadratic residues modulo p: each of the p − 1 possible values of x can only be accompanied by one other to give the same residue.

In fact, (p−x)2≡x2(modp). This is because (p−x)2≡p2−2xp+x2≡x2(modp). So, the p−12 distinct quadratic residues are: 12,22,...,(p−12)2(modp).

As a is coprime to p, Fermat's little theorem says that ap−1≡1(modp), which can be written as (ap−12−1)(ap−12+1)≡0(modp). Since the integers mod p form a field, for each a, one or the other of these factors must be zero. Therefore, ap−12≡1(modp) or ap−12≡−1(modp).

Now if a is a quadratic residue, a ≡ x2, ap−12≡(x2)p−12≡xp−1≡1(modp). 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.

Alternative proof

[edit]

This proof only uses the fact that any congruence kx≡l(modp) has a unique (modulo p) solution x provided p does not divide k. (This is true because as x runs through all nonzero remainders modulo p without repetitions, so does kx: if we have kx1≡kx2(modp), then p∣k(x1−x2), hence p∣(x1−x2), but x1 and x2 aren't congruent modulo p.) It follows from this fact that all nonzero remainders modulo p the square of which isn't congruent to a can be grouped into unordered pairs (x,y) according to the rule that the product of the members of each pair is congruent to a modulo p (since by this fact for every y we can find such an x, uniquely, and vice versa, and they will differ from each other if y2 is not congruent to a). If a is not a quadratic residue, this is simply a regrouping of all p−1 nonzero residues into (p−1)/2 pairs, hence we conclude that 1⋅2⋅...⋅(p−1)≡ap−12(modp). If a is a quadratic residue, exactly two remainders were not among those paired, r and −r such that r2≡a(modp). If we pair those two absent remainders together, their product will be −a rather than a, whence in this case 1⋅2⋅...⋅(p−1)≡−ap−12(modp). In summary, considering these two cases we have demonstrated that for a≢0(modp) we have 1⋅2⋅...⋅(p−1)≡−(ap)ap−12(modp). It remains to substitute a=1 (which is obviously a square) into this formula to obtain at once Wilson's theorem, Euler's criterion, and (by squaring both sides of Euler's criterion) Fermat's little theorem.

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.

Applications

[edit]

In practice, it is more efficient to use an extended variant of Euclid's algorithm to calculate the Jacobi symbol (an). If n is an odd prime, this is equal to the Legendre symbol, and decides whether a is a quadratic residue modulo n.

On the other hand, since the equivalence of an−12 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. Composite numbers for which the congruence holds for a given a are called Euler–Jacobi pseudoprimes to base a.

Notes

[edit]
  1. ↑ Gauss, DA, Art. 106
  2. ↑ Dense, Joseph B.; Dence, Thomas P. (1999). "Theorem 6.4, Chap 6. Residues". Elements of the Theory of Numbers. Harcourt Academic Press. p. 197. ISBN 9780122091308.
  3. ↑ Leonard Eugene Dickson, "History Of The Theory Of Numbers", vol 1, p 205, Chelsea Publishing 1952
  4. ↑ Hardy & Wright, thm. 83
  5. ↑ Lemmermeyer, p. 4 cites two papers, E134 and E262 in the Euler Archive
  6. ↑ L Euler, Novi commentarii Academiae Scientiarum Imperialis Petropolitanae, 8, 1760-1, 74; Opusc Anal. 1, 1772, 121; Comm. Arith, 1, 274, 487

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 (1986), Disquisitiones Arithemeticae (Second, corrected edition), translated by Clarke, Arthur A. (English), New York: Springer, ISBN 0-387-96254-9
  • Gauss, Carl Friedrich (1965), Untersuchungen über höhere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), translated by Maser, H. (German), New York: Chelsea, ISBN 0-8284-0191-8
[edit]