The magic of mathematics and theoretical computer science is all the unexpected connections. You start looking for general principles and then mysterious connections emerge. Nobody can say why this is. — Robert Endre Tarjan

An integer is a quadratic residue with respect to prime if for some integer .

Given a prime and an integer , how fast can we decide whether is a quadratic residue modulo ? As it turns out (courtesy to Euler), pretty fast.

Statement

Given a prime and an integer ,

(First Part) If , it means is a quadratic residue module .

(Second Part) If , it means is a not a quadratic residue module .

One might wonder: what about other possible values of modulo ? As it turns out, modulo can have only two possible values , as shown in the proof of the second part below.

Proof of the First Part

Two integers are coprime if and do not have any common divisor except 1. Recall that according to Fermat’s Little Theorem, if integers and are coprime the following is true:

,

or equivalently

Now, observe that just like , we can write Equation (2) as

Now, since is prime, if the product of two numbers modulo is zero modulo , at least one of them must be zero modulo . Hence at least one of the factors on the left hand side of Equation (3) (that is, either or ) must be congruent to .

Note: If were composite, then there must be two non-zero integers such that and the above argument would not hold. Moreover, since is prime, the product of two non-zero integers cannot be a multiple of since is coprime to ; hence at least one of must be zero.

Now suppose for some integer . That is, we are assuming that is a quadratic residue modulo . Then, it follows that

Hence, if is a quadratic residue modulo , the first factor of Equation (3) becomes zero, and thus Equation (3) is satisfied. Equation (4) is the proof of the first part of the statement.

Proof of the Second Part

Now, when is not a quadratic residue modulo , we can observe that

where is an integer such that . The two candidate values for are therefore $\latex \pm 1$. However, cannot be , since it would imply which is identical to Equation (4) which , in turn, would imply is a quadratic residue modulo , contradicting our assumption that is not a quadratic residue modulo . Therefore, , which completes the proof of the second part of the statement.

2 thoughts on “Euler’s Criterion for Quadratic Residues”

“Moreover, if p is prime, product st of two non-zero integers 1\leq s,t\leq p-1 cannot be a multiple of p since p is coprime to s,t.”, By this argument if 1<=s,t<=(p-1), then s and t can't be congruent to 0 modulo p either.

Mike, you are right: cannot be congruent to 0 mod p if p is prime. Since p is prime and we are assuming Equation (3), it follows that the condition must be revised to allow to equal zero.

My language was indeed confusing, thanks for pointing it out. I cleaned it up a little. Let me know if it is still confusing.

“Moreover, if p is prime, product st of two non-zero integers 1\leq s,t\leq p-1 cannot be a multiple of p since p is coprime to s,t.”, By this argument if 1<=s,t<=(p-1), then s and t can't be congruent to 0 modulo p either.

Mike, you are right: cannot be congruent to 0 mod p if p is prime. Since p is prime and we are assuming Equation (3), it follows that the condition must be revised to allow to equal zero.

My language was indeed confusing, thanks for pointing it out. I cleaned it up a little. Let me know if it is still confusing.