Thus a quadratic residue gives one and a quadratic nonresidue gives minus one, represented by if a nonnegative remainder is used. The formula also holds when , because and both sides are zero modulo .[ref]
Quadratic Residues by Ben Lynn. Ben Lynn, Quadratic Residues, Euler's Criterion and The Legendre Symbol: exponent test and the zero value
For example, modulo seven the exponent is three: confirms that two is a quadratic residue, while confirms that three is a quadratic nonresidue. Modulo eleven the exponent is five, and confirms that two is a quadratic nonresidue. The test answers whether a square root exists; it does not itself return the roots of .
A short proof needs only Fermat's little theorem and the root bound for a polynomial. Put . If in the prime field, then . There are already such quadratic residues. The nonzero polynomial has polynomial degree , so it has no other polynomial roots. Finally, for every nonzero , Fermat's little theorem gives . Factoring in the field shows ; every quadratic nonresidue must take the remaining value . This proves the criterion without first finding a primitive root.
For a larger original example, decide whether seven is a quadratic residue modulo the prime number . Exponentiation by squaring computes the required power without listing fifty squares:Therefore and has no solution. Each intermediate product is reduced modulo , as in modular exponentiation. The advantage is that exponentiation by squaring uses a number of multiplications proportional to the binary digit length of the exponent rather than testing every potential square root.
The odd prime hypothesis is essential. For the composite modulus nine, , which is neither one nor minus one. Although four is a nonzero square modulo nine, , so even the square-to-one implication fails. The Jacobi symbol and Euler pseudoprime discuss different questions for odd composite moduli; they do not make this a universal square test.
There are infinitely many prime numbers congruent to five modulo eight. Suppose instead that they form a finite list , and put , with if the list is empty. Then is an odd number andFor every prime factor of , the integer is nonzero modulo and . Thus a square root of minus one modulo a prime exists for , which forces . All prime factors are therefore one or five modulo eight. Their product is five modulo eight, so at least one prime factor is five modulo eight. Yet none of the divides , since . This contradicts completeness of the list.
Articles by others on the same topic
Euler's criterion is a result in number theory that provides a way to determine whether a given integer is a quadratic residue modulo a prime number.