📂Number Theory

Proof of the Multiplicative Property of the Legendre Symbol

Definition

QR and NR respectively stand for quadratic residues and non-quadratic residues. The Legendre Symbol for a natural number $a$ less than $p$ is defined 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 referred to as the Legendre Symbol, and when generalized for non-prime natural numbers, the notation remains the same but is called the Jacobi Symbol.

Theorem ¹

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

Description

For example, for $p=7$, $1,2,4$ is a QR and $3,5,6$ is an NR, therefore $$ \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 greatly facilitates operations on quadratic residues, having a multiplicative property. The multiplicative property means maintaining multiplication inside and outside the function as in $f(ab) = f(a)f(b)$. It means that instead of calculating large numbers as they are, they can be factored into smaller numbers for computation.

Before proving, let’s first discuss a fact that QR and NR have the following properties:

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

Let’s look at the example given in $p=7$ to check if this calculation is indeed true. It seems like watching the multiplication of $1$ and $-1$, and actually, that’s the core idea of the Legendre Symbol.

Proof

Part 1. QR x QR = QR

In the case of $\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)$, $\displaystyle \left( { b \over p } \right) = 1$. If we assume $q_{1} = a$ and $q_{2} = b$ are 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, if we say $$ q_{3} \equiv q_{1} q_{2} \equiv {m_{1}}^2 {m_{2}}^2 \equiv (m_{1} m_{2})^2 \pmod{p} $$ then, $q_{3}$ is a QR.

---

Part 2. QR x NR = NR

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$, one of $\displaystyle \left( { a \over p } \right)$ and $\displaystyle \left( { b \over p } \right)$ is $1$, and the other is $-1$.

If we assume $q = a$ is QR and $n = b$ is NR satisfying $q \equiv m^2 \pmod{p}$, and if we assume that the product $r=qn$ is QR.

Then there exists $k$ satisfying $$ qn \equiv r \pmod{p} $$ hence $(m)^2 n \equiv (k)^2 \pmod{p}$ is true.

The Multiplicative Inverse in Modular Arithmetic: For a prime number $p$, 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, a $m^{-1} k$ satisfying such a modular equation cannot exist. This contradiction means that $r=qn$ is NR.

---

Part 3. NR x NR = QR

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’s assume $n = a$ is NR. For a prime number $p$, exactly half of $1,2, \cdots (p-1)$ are QR, and exactly half are NR. Similar to proving Fermat’s Little Theorem, thinking of $n, 2n, \cdots (p-1)n$ will also result in exactly half being QR, and exactly half being NR.

Since we have shown in Part 2 that QR x NR = NR, the product of $n$ and any QR would be NR. That means if it was QR in $1,2, \cdots (p-1)$, it would be NR in $n, 2n, \cdots (p-1)n$. The count of such NRs must precisely be $\displaystyle {{p-1} \over 2}$, and so must QRs to be possible. Therefore, we can only conclude that NR x NR = QR.

The summary of Parts 1~3 represented by the Legendre Symbol is as follows. $$ \left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right) $$

■

Using the multiplicative properties of the Legendre Symbol and Gauss’s Law of Quadratic Reciprocity, the following Corollary can be obtained. This implies that the multiplicative property of the Legendre Symbol also holds for the ‘denominator’.

Corollary

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

Proof of 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}$, and assuming $p \equiv \pm 1 \equiv - q \pmod{4}$, $$ - \left( {{ p } \over { a }} \right) \left( {{ q } \over { a }} \right) = \left( {{ a } \over { p }} \right) \left( {{ a } \over { q }} \right) $$

---

In any case, the following holds true. $$ \left( { a \over pq } \right) = \left( { a \over p } \right) \left( { a \over q } \right) $$

■