📂Number Theory

Proof of the Multiplicative Property of the Legendre Symbol

Definition

QR and NR stand for quadratic residue and non-quadratic residue, respectively. The Legendre symbol is defined, for a natural number $a$ smaller than $p$, as $$ \left( { a \over p } \right) = \begin{cases} 1 & a \text{: QR} \\ -1 & a \text{: NR} \end{cases} $$ In number theory, $\displaystyle \left( {{x} \over {y}} \right)$ is not a fraction but is called the Legendre symbol, and when generalized to natural numbers that are not prime, the notation is written the same way but is called the Jacobi symbol.

Theorem ¹

For a prime $p$ greater than $2$, $$ \left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right) $$

Explanation

For example, for $p=7$, since $1,2,4$ are QR and $3,5,6$ are NR, $$ \left( { 1 \over 7 } \right) = \left( { 2 \over 7 } \right) = \left( { 4 \over 7 } \right) = 1 $$ and $$ \left( { 3 \over 7 } \right) = \left( { 5 \over 7 } \right) = \left( { 6 \over 7 } \right) = -1 $$ This symbol has a multiplicative property that makes computations involving quadratic residues extremely convenient. The multiplicative property refers to the property of preserving multiplication inside and outside a function, as in $f(ab) = f(a)f(b)$. It means that large numbers do not need to be computed as they are, but can instead be factored into smaller numbers for computation.

Before the proof, stating the facts first, QR and NR have the following properties:

• QR x QR = QR
• QR x NR = NR
• NR x NR = QR

Looking at the example of $p=7$ given above, try verifying for yourself whether these computations are true. It looks just like multiplication of $1$ and $-1$, and indeed that is the core idea of the Legendre symbol.

Proof

Part 1. QR x QR = QR

This is the case in $\displaystyle \left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right) $ where $\displaystyle \left( { ab \over p } \right) = \left( { a \over p } \right)$ and $\displaystyle \left( { b \over p } \right) = 1$. If we consider $q_{1} = a$ and $q_{2} = b$ to be QR, then there exist ${m_{1}}$ and ${m_{2}}$ satisfying $q_{1} \equiv {m_{1}}^2 \pmod{p}$ and $q_{2} \equiv {m_{2}}^2 \pmod{p}$. Therefore, letting $q_{3} = q_{1} q_{2}$, $$ q_{3} \equiv q_{1} q_{2} \equiv {m_{1}}^2 {m_{2}}^2 \equiv (m_{1} m_{2})^2 \pmod{p} $$ That is, $q_{3}$ is QR.

---

Part 2. QR x NR = NR

This is the case in $\displaystyle \left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right)$ where $\displaystyle \left( { ab \over p } \right) = -1$, and one of $\displaystyle \left( { a \over p } \right)$ and $\displaystyle \left( { b \over p } \right)$ is $1$ while the other is $-1$.

If $q = a$ is QR and $n = b$ is NR, then there exists $m$ satisfying $q \equiv m^2 \pmod{p}$. Assume that their product $r=qn$ is QR.

Then there exists $k$ satisfying $r \equiv k^2 \pmod{p}$, and since $$ qn \equiv r \pmod{p} $$ we have $(m)^2 n \equiv (k)^2 \pmod{p}$.

Multiplicative inverse in congruences: The ring of integers $\mathbb{Z}_{p}$ is an integer field if $p$ is a prime. In other words, if $\gcd(p,a) = 1$, the equation $a x \equiv 1 \pmod{p}$ has exactly one solution in $0<x<p$.

Multiplying both sides by $(m^{-1})^2$, $$ n \equiv (m^{-1}k)^2 \pmod{p} $$ However, since $n$ is NR, there cannot exist an $m^{-1} k$ satisfying such a congruence. This is a contradiction, so $r=qn$ is NR.

---

Part 3. NR x NR = QR

This is the case in $\displaystyle \left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right)$ where $\displaystyle \left( { ab \over p } \right) = 1$ and $\displaystyle \left( { a \over p } \right) = \left( { b \over p } \right) = -1$.

Let $n = a$ be NR. For a prime $p$, among $1,2, \cdots (p-1)$, exactly half are QR and exactly half are NR. Similarly to when proving Fermat’s little theorem, if we consider $n, 2n, \cdots (p-1)n$, then likewise exactly half of $n, 2n, \cdots (p-1)n$ will be QR and exactly half will be NR.

Since we showed in Part 2 that QR x NR = NR, the product of $n$ and some QR will be NR. That means whatever was a QR in $1,2, \cdots (p-1)$ is an NR in $n, 2n, \cdots (p-1)n$. The number of such NRs is exactly $\displaystyle {{p-1} \over 2}$, and the QRs must also number exactly $\displaystyle {{p-1} \over 2}$. For this to be possible, we cannot but conclude that NR x NR = QR.

Summarizing Parts 1–3 above in terms of the Legendre symbol, we obtain the following. $$ \left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right) $$

■

Meanwhile, using the multiplicative property of the Legendre symbol and Gauss’s law of quadratic reciprocity, we obtain the following corollary. This means that the multiplicative property of the Legendre symbol also works with respect to the so-called ‘denominator’.

Corollary

For a prime $a$ greater than $2$, $$ \left( { a \over pq } \right) = \left( { a \over p } \right) \left( { a \over q } \right) $$

Proof of the Corollary

Gauss’s law of quadratic reciprocity: $$\left( {{ q } \over { p }} \right) = \begin{cases} \left( {{ p } \over { q }} \right) & p \equiv 1 \pmod{4} \lor q \equiv 1 \pmod{4} \\ - \left( {{ p } \over { q }} \right) & p \equiv 3 \pmod{4} \land q \equiv 3 \pmod{4} \end{cases}$$

---

Case 1. $a \equiv 1 \pmod{4} \lor pq \equiv 1 \pmod{4}$

$$ \left( {{ a } \over { pq }} \right) = \left( {{ pq } \over { a }} \right) = \left( {{ p } \over { a }} \right) \left( {{ q } \over { a }} \right) $$ Since $a \equiv 1 \pmod{4}$, $$ \left( {{ p } \over { a }} \right) \left( {{ q } \over { a }} \right) = \left( {{ a } \over { p }} \right) \left( {{ a } \over { q }} \right) $$

---

Case 2. $a \equiv 3 \pmod{4} \land pq \equiv 3 \pmod{4}$

$$ \left( {{ a } \over { pq }} \right) = - \left( {{ pq } \over { a }} \right) = - \left( {{ p } \over { a }} \right) \left( {{ q } \over { a }} \right) $$ Since $pq \equiv 3 \pmod{4}$, we have $p \equiv \pm 1 \equiv - q \pmod{4}$, and $$ - \left( {{ p } \over { a }} \right) \left( {{ q } \over { a }} \right) = \left( {{ a } \over { p }} \right) \left( {{ a } \over { q }} \right) $$

---

Summarizing the cases above, the following holds in any case. $$ \left( { a \over pq } \right) = \left( { a \over p } \right) \left( { a \over q } \right) $$

■