Power Residues and Legendre's Symbol

Suppose we wish to know if there are any solutions to a congruence of the form

$$x^k \equiv a \pmod{m}$$

When such solutions exist, we say that $a$ is a $k^{th}$ power residue of $m$. We have solved specific instances of this problem before (for example, here), and can start by following a similar line of attack. We would like to use indices to deal with the exponent $k$, but this requires knowledge of some primitive root that we can use as the base for our indices.

As such, let us assume that $r$ is a primitive root for $m$. Then, we can "take indices of both sides" to obtain

$$\textrm{ind}_r x^k \equiv \textrm{ind}_r a \pmod{\varphi(m)}$$

Note, we can only do this if $\gcd(a,m)=1$ (otherwise, $\textrm{ind}_r a$ fails to exist), so let us assume this is the case.

Now, as desired, we can use one of the properties of indices to "bring the exponent down"

$$k \cdot \textrm{ind}_r x \equiv \textrm{ind}_r a \pmod{\varphi(m)}$$

What we do next depends upon the nature of $k$ and $\varphi(m)$, or more specifically -- on the the value of their greatest common divisor $d$.

If $d \, | \, \textrm{ind}_r a$, then we can proceed by dividing both sides by $d$ -- which, remembering the consequent effect on the modulus, yields the following:

$$\frac{k}{d} \cdot \textrm{ind}_r x \equiv \frac{\textrm{ind}_r a}{d} \pmod{\frac{\varphi(m)}{d}}$$

We can then find $\textrm{ind}_r x$ in the normal way (i.e., find $(k/d)^{-1}$ modulo $\varphi(m)$ using the Euclidean Algorithm as necessary, and then multiply both sides by this value).

Finally, we arrive at our solution by computing $x = r^{\textrm{ind}_r x}$ for any such index values found.

If $d \not|\, \textrm{ind}_r a$, the resulting congruence can't have any solutions, which then tells us that $a$ is not a $k^{th}$ power residue for modulus $m$.

So, the question of whether or not $x^k \equiv a \pmod{m}$ has solutions is identical to the question of whether or not $d = \gcd(k,\varphi(m))$ divides $\textrm{ind}_r a$ for some primitive root $r$.

However, we would much prefer to have a condition related to the existence of a power residue that didn't depend on identifying a primitive root, or on finding the value of an index -- which in general can be difficult. With this in mind, consider the following:

First, note that both expressions below are products of two integers if and only if $d \, | \, \textrm{ind}_r a$. $$\textrm{ind}_r a \cdot \frac{\varphi(m)}{d} = \frac{\textrm{ind}_r a}{d} \cdot \varphi(m)$$

The one on the right is clearly a multiple of $\varphi(m)$, so $$\textrm{ind}_r a \cdot \frac{\varphi(m)}{d} \equiv 0\pmod{\varphi(m)}$$


$$r^{\textrm{ind}_r a \cdot \frac{\varphi(m)}{d}} \equiv r^0\pmod{m}$$

Note, we can simplify the right side -- and on the left, the index appearing in the exponent gives us the opportunity to remove $r$ from the congruence. Hence,

$$(r^{\textrm{ind}_r a})^{\frac{\varphi(m)}{d}} \equiv r^0\pmod{m}$$ $$a^{\frac{\varphi(m)}{d}} \equiv 1\pmod{m}$$

Recalling that $d$ is the greatest common divisor of $k$ and $\varphi(m)$, we arrive at our result: We are assured that $a$ can only be a $k^{th}$ power residue for modulus $m$ when

$$a^{\frac{\varphi(m)}{\gcd(k,\varphi(m))}} \equiv 1\pmod{m}$$

Implications for Squares and Prime Moduli

Under certain conditions, we have seen how to borrow from the techniques used in RSA encryption to find the $k^{th}$ root of a given value $a$ in some given modulus $m$. However, this fails to be a fruitful when $\gcd(k,\varphi(m)) \ne 1$.

If we seek a square root of some $a$ in a prime (and odd) modulus $p$, then we seek some $x$ so that

$$x^2 \equiv a \pmod{p}$$

In this case, $\gcd(k,\varphi(m)) = \gcd(2,p-1) = 2 \ne 1$. So the previously mentioned RSA-related technique doesn't get us anywhere. We have seen methods to solve for square roots when $p$ is congruent to $3\pmod{4}$ -- but that doesn't say anything about the odd primes congruent to $1\pmod{4}$.

However, the result in the above section will guarantee that if $x^2 \equiv a\pmod{m}$ has a solution, then

$$a^{\frac{p-1}{2}} \equiv 1 \pmod{m}$$

Consider the following powers of $a$ under an odd prime modulus of $p=11$:

$$\begin{array}{c|c} a & a^{\frac{p-1}{2}} = a^5 \pmod{11}\\\hline 1 & +1\\ 2 & -1\\ 3 & +1\\ 4 & +1\\ 5 & +1\\ 6 & -1\\ 7 & -1\\ 8 & -1\\ 9 & +1\\ 10 & -1\\ \end{array}$$

The immediate conclusion is of course, that $x^2 \equiv a\pmod{11}$ could only have solutions when $a = 1,3,4,5,\textrm{ and } 9$.

You may have wondered why all of these values are either $+1$ or $-1$, and if this happens in general. Indeed, it does! Note, by Fermat's Little Theorem, we have $$a^{\frac{p-1}{2}} \cdot a^{\frac{p-1}{2}} = a^{p-1} \equiv 1\pmod{p}$$

Thus, $a^{\frac{p-1}{2}}$ is its own multiplicative inverse modulo $p$. However, recall in the proof of Wilson's Theorem we saw that the only values in a prime modulus that were their own inverses were congruent to either $+1$ or $-1 \pmod{p}$.

The Legendre Symbol

The above discussion motivates the following definitions:

First, we say that if the below congruence has a solution, then $a$ is called a quadratic residue of $m$, and a quadratic non-residue of $m$ otherwise

$$x^2 \equiv a\pmod{m}$$

Second, we define for an odd prime $p$ the Legendre Symbol, $(a/p)$ by the following:

$$\left( \frac{a}{p} \right) = \left\{ \begin{array}{rl} 0 & \textrm{if } p \textrm{ divides } a\\ +1 & \textrm{if $a$ is a quadratic residue of $p$}\\ -1 & \textrm{if $a$ is a quadratic non-residue of $p$, and $p \not\mid a$} \end{array} \right.$$

We know from above that if $(a/p) = 1$ then it must be the case that $a^{\frac{p-1}{2}} \equiv 1 \pmod{p}$.

Now suppose $(a/p) = -1$. This means that $x^2 \equiv a\pmod{p}$ has no solutions.

Recall, for each $i$ in $1,2,3,\ldots (p-1)$, we know there is a unique $j$ such that $ij \equiv a\pmod{p}$, as we know how to solve for this $j$ (i.e., calculate and use the multiplicative inverse).

Further, since $x^2 \equiv a\pmod{p}$ has no solutions, it is never the case that $ i\equiv j$.

Consequently, we can group the integers $1,2,3,\ldots (p-1)$ into $(p-1)/2$ pairs, each with product congruent to $a$. Multiplying these pairs together, we have

$$a^{\frac{p-1}{2}} \equiv (p-1)! \pmod{p} $$ Which by Wilson's theorem, tells us that $$a^{\frac{p-1}{2}} \equiv -1 \pmod{p}$$

Thus for $p \not\mid a$, $(a/p) = 1$ precisely when $a^{\frac{p-1}{2}} \equiv 1 \pmod{p}$, and equals $-1$ otherwise.

The above suggests Euler's Criterion:

When $p$ is an odd prime and $p \not\mid a$,   $\displaystyle{\left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}}\pmod{p}}$