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^[1]^[2]^[3]

a^{\tfrac {p-1}{2}}\equiv {\begin{cases}\;\;\,1{\pmod {p}}&{\text{ if there is an integer }}x{\text{ such that }}a\equiv x^{2}{\pmod {p}},\\-1{\pmod {p}}&{\text{ if there is no such integer.}}\end{cases}}

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

\left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}.

The criterion first appeared in 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, $x 2 \equiv 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}\equiv x^{2}{\pmod {p}}.$ This is because $(p-x)^{2}\equiv p^{2}-{2}{x}{p}+x^{2}\equiv x^{2}{\pmod {p}}.$ So, the ${\tfrac {p-1}{2}}$ distinct quadratic residues are: $1^{2},2^{2},...,({\tfrac {p-1}{2}})^{2}{\pmod {p}}.$

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

a^{p-1}\equiv 1{\pmod {p}},

which can be written as

\left(a^{\tfrac {p-1}{2}}-1\right)\left(a^{\tfrac {p-1}{2}}+1\right)\equiv 0{\pmod {p}}.

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, $a \equiv x 2$ ,

a^{\tfrac {p-1}{2}}\equiv {(x^{2})}^{\tfrac {p-1}{2}}\equiv x^{p-1}\equiv 1{\pmod {p}}.

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\equiv l\!\!\!{\pmod {p}}$ 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 $kx_{1}\equiv kx_{2}{\pmod {p}}$ , then $p|k(x_{1}-x_{2})$ , hence $p|(x_{1}-x_{2})$ , but $x_{1}$ and $x_{2}$ 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 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 $y^{2}$ is not congruent to $a$ ). If $a$ is a quadratic nonresidue, this is simply a regrouping of all $p-1$ nonzero residues into $(p-1)/2$ pairs, hence we conclude that $1\cdot 2\cdot ...\cdot (p-1)\equiv a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}$ . If $a$ is a quadratic residue, exactly two remainders were not among those paired, $r$ and $-r$ such that $r^{2}\equiv a\!\!\!{\pmod {p}}$ . If we pair those two absent remainders together, their product will be $-a$ rather than $a$ , whence in this case $1\cdot 2\cdot ...\cdot (p-1)\equiv -a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}$ . In summary, considering these two cases we have demonstrated that for $a\not \equiv 0\!\!\!{\pmod {p}}$ we have $1\cdot 2\cdot ...\cdot (p-1)\equiv -\left({\frac {a}{p}}\right)a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}$ , 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} = 17¹ ≡ 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⁶ ≡ 1 (mod 13), therefore 17 is a quadratic residue modulo 13. As confirmation, note that 17 ≡ 4 (mod 13), and 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 = {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:

1² = 1

2² = 4

3² = 9

4² = 16

5² = 25 ≡ 8 (mod 17)

6² = 36 ≡ 2 (mod 17)

7² = 49 ≡ 15 (mod 17)

8² = 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 9² ≡ (−8)² = 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⁸ ≡ 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⁸ ≡ 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 $\left({\frac {a}{n}}\right)$ . 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 $a^{\frac {n-1}{2}}$ 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]

^ Gauss, DA, Art. 106
^ Dense, Joseph B.; Dence, Thomas P. (1999). "Theorem 6.4, Chap 6. Residues". Elements of the Theory of Numbers. Harcourt Academic Press. p. 197.
^ Leonard Eugene Dickson, "History Of The Theory Of Numbers", vol 1, p 205, Chelsea Publishing 1952
^ Hardy & Wright, thm. 83
^ Lemmermeyer, p. 4 cites two papers, E134 and E262 in the Euler Archive
^ 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; 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 über höhere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8

Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0-19-853171-5

Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, ISBN 3-540-66957-4

External links[edit]

The Euler Archive

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

[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

[1]

[2]

[3]

[4]

[5]

[6]

ANHDUC - WIKI 2

Saturday, August 1, 2020