• About
• Statistics
• Number Theory
• Java
• Data Structures
• Cornerstones
• Calculus

Power Residues and Legendre's Symbol

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

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

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"

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:

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:

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)}$$

Consequently,

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,

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

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

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

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

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

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

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

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}}$