Euler’s Criterion for Quadratic Residues

400px-Stamp_Leonhard_Euler
Leonhard Euler (source: Prolineserver)

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

An integer a is a quadratic residue with respect to prime p if a \equiv x^2 \mod{p} for some integer x.

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

Statement

Given a prime p and an integer a,

  • (First Part) If \displaystyle a^\frac{p-1}{2} \equiv 1 \mod{p}, it means a is a quadratic residue module p.
  • (Second Part) If a^\frac{p-1}{2} \equiv -1 \mod{p}, it means a is a not a quadratic residue module p.

One  might wonder: what about other possible values of   a^\frac{p-1}{2} modulo p? As it turns out, a^\frac{p-1}{2} modulo p can have only two possible values \pm 1, as shown in the proof of the second part below.

Proof of the First Part

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

a^{p-1}\equiv 1\mod{p}\ \ \ \ (1),

or equivalently

a^{p-1} - 1\equiv 0\mod{p} .\ \ \ \ (2)

Now, observe that just like a^2-b^2=(a+b)(a-b), we can write Equation (2) as

a^{p-1}-1 = (a^\frac{p-1}{2}-1)(a^\frac{p-1}{2}+1) = 0 \bmod p .\ \ \ \ (3)

Now, since p is prime, if the product of two numbers modulo p is zero modulo p, at least one of them must be zero modulo p. Hence at least one of the factors on the left hand side of Equation (3) (that is, either a^\frac{p-1}{2}-1 or a^\frac{p-1}{2}+1) must be congruent to 0\bmod{p}.

Note: If p were composite, then there must be two non-zero integers 0<x,y < p such that xy = p = 0 \bmod p  and the above argument would not hold. Moreover, since p is prime, the 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; hence at least one of s,t must be zero.

Now suppose a\equiv x^2\mod{p} for some integer 0\leq x\leq p-1. That is, we are assuming that a is a quadratic residue modulo p. Then, it follows that

\begin{array}{rcl}a^\frac{p-1}{2}-1&=&(x^2)^\frac{p-1}{2}-1\\ &=&x^{p-1}-1\\ &\equiv&1-1\mod{p}\ \ \ \ \text{using Fermat's Little Theorem}\\ \implies a^\frac{p-1}{2}&\equiv&1\mod{p}\ \ \ \ (4)\\\end{array}

Hence, if a is a quadratic residue modulo p, 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 a is not a quadratic residue modulo p, we can observe that

\begin{array}{rcl}a^\frac{p-1}{2}&\equiv&\left(a^{p-1}\right)^\frac{1}{2}\mod{p}\\ &\equiv&(1)^\frac{1}{2}\mod{p}\ \ \ \ \text{using Fermat's Little Theorem}\\ &\equiv&q\mod{p}\\\end{array}

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

\square

Advertisements

2 thoughts on “Euler’s Criterion for Quadratic Residues

  1. “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.

    1. Mike, you are right: 1 \leq s,t \leq p-1 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 1 \leq s,t \leq p-1 must be revised to allow s,t 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s