Here we would show a beautiful application of Fermat’s Little Theorem.

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**

Recall that according to Fermat’s Little Theorem, if integers and are coprime (that is, and do not have any common divisor except 1), 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 module is zero modulo , at least one of them must be zero modulo . (If were not prime, the product of the factors of would be , and hence the above argument would not hold. Moreover, if is prime, product of two non-zero integers cannot be a multiple of since is coprime to .) Hence, according to this argument, at least one of the factors on the left hand side of Equation (3) (that is, either or ) must be congruent to .

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.

### Like this:

Like Loading...

*Related*

## Leave a comment

Comments feed for this article