Powers Modulo p: Legendre Symbol and Application to Mod p^k

Let's try to solve the simplest case. Let's try to determine when $k$ is a quadratic residue modulo $p$, where $p$ is an odd prime. Again, we say $p$ is odd for simplicity. If it were $2$, then everything is a quadratic residue.

For the remainder of this explanation, I will abbreviate quadratic residue as QR and quadratic non-residue as QNR.

Let's make some definitions in order to make our lives easier

Legendre symbol

Let's define a function $(a|p):=\begin{cases} 1&\text{if }a\text{ is a nonzero QR modulo }p\\ 0&\text{if }a\equiv 0\pmod{p}\\ -1&\text{if }a\text{ is a QNR modulo }p \end{cases}$

Also, $(a|p)=a^{(\frac{p-1}{2})}$

These two definitions are equivalent. We will not be proving it, but it is a nice exercise. It is known as Euler's Criterion.

This is called the Legendre symbol, and other ways to express it are $(a/p)$ and $\left(\dfrac{a}{p}\right)$.

In general we will be looking at nonzero elements modulo $p$, so we will rarely use the $0$ case.

Let's find out some interesting properties about $(a|p)$.

We get a QR. This is because if $(a|p)=1$ and $(b|p)=1$, then $a=k^2$ and $b=\ell^2$ for some $k,l$. Then, $ab=k^2\ell^2=(k\ell)^2$, so $(ab|p)=1$.

We get a QR. This is because if $(a|p)=a^{(\frac{p-1}{2})}=-1$ and $(b|p)=b^{(\frac{p-1}{2})}=-1$, then $(ab|p)=ab^{(\frac{p-1}{2})}=a^{(\frac{p-1}{2})}b^{(\frac{p-1}{2})}=1$.

This motivates the property that $\left(\dfrac{a}{p}\right)\left(\dfrac{b}{p}\right)=\left(\dfrac{ab}{p}\right)$.

This is true because $ab^{(\frac{p-1}{2})}=a^{(\frac{p-1}{2})}b^{(\frac{p-1}{2})}$.

Quadratic Reciprocity

How are quadratic residues related? Well, let's try to solve the congruence $$x^2\equiv q\pmod{p}.$$ It would be a huge surprise if this was somehow related to the following congruence: $$x^2\equiv p\pmod{q}.$$

Right, the congruences are under different moduli, and it would be quite challenging to get to modulo $q$ if you were working on an equation in modulo $p$.

Well, quadratic reciprocity states something that does just that! Specifically, it states $$\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{p-1}{2}}.$$

That's quite confusing, so here's an equivalent statement:

Suppose that $p,q$ are odd primes. Then, if both of $p$ and $q$ are congruent to $3\pmod4$, then either $x^2\equiv p\pmod{q}$ has a solution or $x^2\equiv q\pmod{p}$ has a solution.

Otherwise, at least one of $p,q$ are congruent to $1\pmod{4}$. Then, $x^2\equiv p\pmod{q}$ has a solution if and only if $x^2\equiv q\pmod{p}$ has a solution.

The proof is fairly long. Here's a sketch:

Lemma 1: Given integers $a,p$ there exists $q,r,\epsilon$ such that $a=pq+\epsilon r$, where $0\leq \frac{p}{2}$ and $\epsilon=\pm1$. More specifically, $\epsilon=(-1)^{\lfloor 2a/p\rfloor}$.

Sketch of Proof: Use the division algorithm and perform casework based on which hald of the interval $a$ is in between $bq$ and $b(q+1)$. Then, since we have both an upper and lower bound on the remainder from the division algorithm, we can find the floor of $2a/p$.

Lemma 2: $a^{\frac{p-1}{2}}\equiv (-1)^S\pmod{p}$, where $S=\sum\limits^{\frac{p-1}{2}}_{k=1}\left\lfloor\dfrac{2ak}{p}\right\rfloor$.

Sketch of Proof: Take Lemma 1 for $a\mapsto ak$ for $k$ from $1$ to $\frac{p-1}{2}$ and take the product of the results. All the remainders are a permutation of $\{1,2,\cdots,\frac{p-1}{2}\}$, so many things cancel to yield the result.

Lemma 3: $\left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$.

Sketch of Proof: Apply the second definition of the Legendre symbol. Note that this is modulo $p$. Show that it is an equality.

Lemma 4: Given an odd $a$ with $p\nmid a$, $\left(\dfrac{2a}{p}\right)=\left(\dfrac{\frac{p+a}{2}}{p}\right)$.

Sketch of Proof: Just some algebraic manipulation. Use the definition of the Legendre Symbol.

Lemma 5: $(2|p)=(-1)^{\frac{p^2-1}{8}}$

Sketch of Proof: Use Lemma 4.

Lemma 6: $\sum\limits^{\frac{p-1}{2}}_{\ell=1}\left\lfloor\frac{2ql}{p}\right\rfloor=\sum\limits^{\frac{p-1}{2}}_{\ell=1}\left\lfloor\frac{ql}{p}\right\rfloor\pmod{2}.$

Sketch of Proof: Consider the lattice points with even $x$ coordinates under the line $y=qx/p$ inside the rectangle.

Consider the total number of lattice points on the right side, and then note the number of lattice points with even $x$ coordinate above the diagonal on the right side is the same number of lattice points with odd $x$ coordinates under the diagonal on the left side.

Lemma 7: $\displaystyle\sum^{\frac{Q-1}{2}}_{n=1}\left\lfloor\dfrac{P}{Q}n\right\rfloor+\sum^{\frac{P-1}{2}}_{n=1}\left\lfloor\dfrac{Q}{P}n\right\rfloor=\dfrac{P-1}{2}\cdot\dfrac{Q-1}{2}$

Sketch of Proof: Considert the number of lattice points in the bottom right rectangle . Count it in two different ways.

Now it's time to actually prove quadratic reciprocity!

PROOF: By Lemma 2 and the definition of the Legendre symbol, $$\left(\dfrac{p}{q}\right)=(-1)^{\sum\limits^{\frac{p-1}{2}}_{\ell=1}\left\lfloor\frac{2ql}{p}\right\rfloor}.$$ By Lemma 6, $$\left(\dfrac{p}{q}\right)=(-1)^{\sum\limits^{\frac{p-1}{2}}_{\ell=1}\left\lfloor\frac{ql}{p}\right\rfloor}.$$ Similarly, $$\left(\dfrac{q}{p}\right)=(-1)^{\sum\limits^{\frac{pq-1}{2}}_{\ell=1}\left\lfloor\frac{pl}{q}\right\rfloor}.$$ Multiplying, we have $$\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right)=(-1)^{\sum\limits^{\frac{p-1}{2}}_{\ell=1}\left\lfloor\frac{ql}{p}\right\rfloor+\sum\limits^{\frac{pq-1}{2}}_{\ell=1}\left\lfloor\frac{pl}{q}\right\rfloor}.$$ By Lemma 7, $$\left(\dfrac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.$$ $\Box$

The Legendre Symbol is denoted as (x/p) and is the same value as x to the power p-1/2, which takes the value of 0 iff x is 0 mod p, 1 iff x is a qudratic residue mod p, and -1 iff x is not a quadratic residue mod p.