Quadratic Residues-Legendre and Jacobi Symbols

Quadratic Congruence

 

There is a general question whether an integer $a$ has a square root $\pmod{n}$ and if so, how many are there and how one can find them.

We know that the solution of the quadratic equation can be found by 

$$x=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$$

If we want to apply this to the case where $a,b,c \in Z_n$, then $2a$ to be unit in $\pmod{n}$, so that we can divide by $2a$.

We can write the equation in the form

$$(2ax+b)^2=b^2-4ac$$

If we can find all the square roots $s$ of $b^2-4ac$ in $\mathbb{Z}_n$, we can then find all the solutions $x \in \mathbb{Z}_n$ of the quadratic equation of the form $2ax+b=s$, or equivalently $x=(s-b)/2a$.

If we look at the square roots at $\mathbb{Z}_{15}$, then  1 and 4 have four square roots each($\pm 1 ,\pm 4$ and $\pm 2,\pm 7$ respectively, while the other units have none.

Example:

Find all the solutions of $x^2-3x+2 \equiv 0 \pmod{15}$

given $a=1, b=−3$ and $c=2,$ we have:
$b^2−4ac=(−3)^2−4(1)(2)=9−8=1$

So, $b^2−4ac=1.$

Now, we need to find the square roots of 1 modulo 15. The solutions to $x^2 \equiv 1(mod15)$ are $x \equiv \pm 1(mod15)$.

Using the quadratic formula:

For $x1​$:

$$x1=(−(−3)+\sqrt{1})/2=(3+1)/2=2$$

For $x2​$:

$$x2=(−(−3)−\sqrt{1})/2=(3−1)/2=1$$

So, the solutions modulo 15 are $x≡1(mod15) $and $x≡2(mod15)$

Example:Solve the quadratic congruence $3x^2-4x+7 \equiv 0 \pmod{13}$ 

Lets apply $(2ax+b)^2=b^2-4ac$

$(6x-4)^2 \equiv 10 \pmod{13}$

let $y=6x-4$.then $y^2 \equiv 10 \pmod{13}$. This congruence has exactly two solutions $y \equiv 6,7 \pmod{13}$

Therefore the solutions of the congruence are given by those of linear congruences $6x-4 \equiv 6 \pmod{13}$ and $6x-4 \equiv 7 \pmod{13}$ namely $x \equiv 6,4 \pmod{13}$

Note that the quadratic congruence in this example has exactly two solutions.But the next example shows that not every quadratic congruence has a solution.

Example: Solve $3x^2+7x+5 \equiv 0 \pmod{13}$.This congruence yields $(6x+7)^2 \equiv 2 \pmod{13}$.But square of none of the least residues modulo 13 yields 2.So this is not solvable.

Now the question arise when the congruence $x^2 \equiv a \pmod{p}$ is solvable? when solvable how many solutions does it have.

if $p |a$ then $x^2 \equiv 0 \pmod{p}$, so $x \equiv 0 \pmod{p}$ is the only solution. Now assume $p \nmid a$. The congruence has exactly two solutions.

lemma: Let $p$ be an odd prime and $a$ an integer such that $p \nmid a$. Then the congruence $ x^2 \equiv a \pmod{p}$ has either no solutions or exactly two incongruent solutions.

Quadratic Residue and  The Group of Quadratic Residue

An element $a \in U_n$ is a quadratic residue $\pmod{n}$ if $a=s^2$ for some $s \in U_n$.The set of such quadratic residues is denoted by $Q_n$.For small $n$ one can determine $Q_n$ by squaring all elements $s \in U_n$

Example:

Consider the positive integers less than 10. We'll calculate their squares modulo 10 to identify quadratic residues.

$0^2=0(mod10)$-0 is a quadratic residue modulo 10.

$1^2≡1(mod10)$- 1 is a quadratic residue 

$2^2≡4(mod10)$ - 4 is a quadratic residue.

$3^2≡9(mod10)$ - 9 is a quadratic residue.

$4^2≡6(mod10)$ - 6 is a quadratic residue.

$5^2≡5(mod10)$ - 5 is a quadratic residue.

$6^2≡6(mod10)$ - 6 is a quadratic residue.

$7^2≡9(mod10)$ - 9 is a quadratic residue.

$8^2≡4(mod10)$- 4 is a quadratic residue.

$9^2≡1(mod10)$ - 1 is a quadratic residue.

So, the quadratic residues modulo 10 are 1, 4, 5, 6, and 9.If we consider units $Q_{10}=\{1,9\} \subset U_{10}$

$Q_7=\{1,2,4\} \subset U_7$

$Q_8=\{1\} \subset U_8$

Python Code

list all quadratic residues

from sympy.ntheory import quadratic_residues

print(quadratic_residues(10))

[0,1,4,5,6,9]

check whether an element is a quadratic residue

from sympy.ntheory import is_quad_residue

print(is_quad_residue(4,10))

True

print(is_quad_residue(7,10))

False

Example:Find the quadratic residue and  nonresidues of $p=13$

$1^2 \equiv 1 \equiv 12^2 \pmod{13} \quad 2^2 \equiv 4 \equiv 11^2 \pmod{13}$

$3^2 \equiv 9 \equiv 10^2 \pmod{13} \quad 4^2 \equiv 3 \equiv 9^2 \pmod{13}$

$5^2 \equiv 12 \equiv 8^2 \pmod{13} \quad 6^2 \equiv 10 \equiv 7^2 \pmod{13}$

Accordingly 13 has exactly six quadratic residues namely 1,3,4,9,10 and 12, and it has six quadratic non residues also, namely 2,5,6,7,8 and 11.

This example provides us with two interesting bonuses

• The prime 13 has the same number of quadratic residues and non residues(6 each)
• They form the partitioning of the set of positive residues of 13.

Theorem: every odd prime $p$ has exactly $(p-1)/2$ quadratic residues and $(p-1)/2$ quadratic non residues.

We can determine how many square roots an element $a \in Q_n$ can have

Note : $Q_n$ is a subgroup of $U_n$

 

Lemma: Let $n>2$ and suppose that there is a primitive root $g \pmod{n}$, then $Q_n$ is a cyclic group of order $\phi(n)/2$, generated by $g^2$ consisting of the even powers of $g$.

Example: If $n=7$ then we can take $g=3$ as primitive root. The powers of $g$ in $U_7$ are $g=3,g^2=2,g^3=6,g^4=4,g^5=5 $ and $g^6=1;$ of these the quadratic residues $a=1,2$ and 4 corresponds to the even powers of $g$. Thus $Q_7$ is the cyclic group of order 3 generated by $g^2=2$

Legendre Symbol ( Adrein-marie Legendre 1978)

 

The Legendre symbol is a mathematical concept used in number theory to determine whether a given integer is a quadratic residue modulo a prime number. It is denoted as $\left(\frac{a}{p}\right)$, where $a$ is an integer and $p$ is an odd prime number. 

 

The Legendre symbol is defined as follows:

This shows that $x^2 \equiv a \pmod{p}$ is solvable if and only if $\left(\frac{a}{p}=1\right)$

Python Code

from sympy.ntheory import legendre_symbol

ls=[legendre_symbol(i, 7) for i in range(7)]

print(ls)

[0, 1, 1, -1, 1, -1, -1]

 

The following theorem shows three fundamental properties of the symbol

Theorem: Let $p$ be an odd prime and $a$ and $b$ be any integers with $p \nmid ab$. Then

• if $a \equiv b \pmod{p}$ then $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$
• $ \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right) \left(\frac{b}{p}\right)$
• $\left(\frac{a^2}{p}\right)=1$

 

Corollary:If $p$ is an odd prime and $g$ is a primitive root $\pmod{p}$ then

$$ \left(\frac{g^i}{p}\right)   =(-1)^i$$

\mlegendre{x}{y}

Reference: https://www.physicsforums.com/threads/latex-frustration-defining-commands-with-arguments.277730/

$x \overwithdelims () y$

Reference: https://www.physicsforums.com/threads/latex-frustration-defining-commands-with-arguments.277730/

Note: when $i$ is even $g^i$ generates a quadratic residue.

 

Corollary: If $p$ be an odd prime, $q$ a prime such that $p \nmid q$, and $i$ is a positive integer. Then $\left(\frac{q^i}{p}\right)=\left(\frac{q}{p}\right)^i$

Example:Using the fact that $\left(\frac{5}{17}\right)=-1$, compute $\left(\frac{125}{17}\right)$

 

$\left(\frac{125}{17}\right)=\left(\frac{5^3}{17}\right)$

$\quad \quad =\left(\frac{5}{17}\right)^3$

$\quad \quad =(-1)^3=-1$

 

Multiplicativity

if $p$ is an odd prime, then

$$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right) \left(\frac{b}{p}\right)$$

for all integers $a$ and $b$.

 

Example:

The set $Q_{13}=\{1,3,4,9,10,12\}$.So $\left(\frac{6}{13}\right)=-1$. This can be verified $\left(\frac{2}{13}\right) \left(\frac{3}{13}\right)=-1 \times 1=-1$

$For\; all\; integers\; \$a\_1,a\_2,\backslash ldots,a\_k\$\; we\; have$

$$\left( \frac{a_1,\ldots,a_k}{p}\right)=\left(\frac{a_1}{p}\right) \cdots

\left(\frac{a_k}{p}\right)$$

Example: Using the fact that $\left(\frac{2}{23}\right)=1$ and $\left(\frac{5}{23}\right)=-1$ , compute $\left(\frac{5000}{23}\right)$

Notice that $5000=2^3.5^4$. So

$\left(\frac{5000}{23}\right)=\left(\frac{2}{23}\right)^3 \left(\frac{5}{23}\right)^4$

 $\left(\frac{5000}{23}\right)=(1)^3.(-1)^4=1$

So 5000 is a quadratic residue in $\pmod{23}$

Theorem:Euler's Criterion

Let $p$ be an odd prime. then a positive integer $a$ with $p \nmid a$ is a quadratic residue of $p$ if and only if $a^{(p-1)/2} \equiv 1 \pmod{p}$

if $p$ is an odd prime, then for all integers $a$ we have

$$a^{(p-1)/2}=\left(\frac{a}{p}\right)$$

Example:

Consider $a=5$ and $p=13$. We want to determine whether $5$ is a quadratic residue modulo 13, that is, we want to find $\left(\frac{5}{13}\right)$

According to Euler's criteria

$5^6=5^2.5^2.5^2=-1.-1.-1=-1 \pmod{13}$. So 5 is not a quadratic residue in $Z_{13}$

Example:

Determine if 10 and 7 are quadratic residues of 13.

 

notice that $10^{(13-1)/2} = 10^6 \equiv (-3)^6 \equiv 1 \pmod{13}$. So by Euler's criterion 10 is a quadratic residue of 13.

$7^{(13-1)/2} \equiv 7^6 \equiv (7^3)^2 \equiv 562 \equiv -1 \pmod{13}$. Since $7^6 \not \equiv 1 \pmod{13}$, by Euler's criterion 7 is a quadratic non residue of 13.

Note:If $p$ is an odd prime. Then a positive integer $a$, where $p \nmid a$ is a quadratic nonresidue if and only if $a^{(p-1)/2} \equiv -1 \pmod{p}$

corollary: If $p$ is an odd prime. Then $-1 \in Q_p$ if and only if $p \equiv 1 \pmod{4}$

$$\left(\frac{-1}{p}\right) \equiv 1 \quad \text{if}\: p \equiv 1 \pmod{4}$$

$$\left(\frac{-1}{p}\right) \equiv -1 \quad \text{if}\: p \equiv -1 \pmod{4}$$

 

Proof: if we take $a=-1$ in Euler's criteria

$$\left(\frac{-1}{p}\right) \equiv (-1)^{(p-1)/2}\pmod{p}$$

 

So $-1 \in Q_p$ only if  $(p-1)/2$ is even that is $p \equiv 1 \pmod{4}$

 

Example:

We have $-1 =2^2 \pmod{5}$ and $-1=5^2 \pmod{13}$ .But -1 is not a quadratic residue in $\mathbb{Z_7}$ or $\mathbb{Z_3}$.

Example:

Let $p=17$ , then $-1 \equiv 4^2$. So $(\frac{-1}{17})=1$.This shows that $(\frac{a}{17})=(\frac{-a}{17})$  for all $a \in U_{17}$. That is $a \in Q_{17}$ if and only if $-a \in Q_{17}$. For instance $13 \in Q_{17}$ since $-13 \equiv 2^2 \in Q_{17}$

 

This can be used to evaluate the Legendre Equations

Example: evaluate $\left(\frac{-4}{41}\right)$ 

 

$\left(\frac{-4}{41}\right)=\left(\frac{4}{41}\right)\left(\frac{-1}{41}\right)$

$\left(\frac{-4}{41}\right)=1.1=1$

So -4 is a quadratic residue in $\pmod{41}$ 

Note:There are infinitely many primes of the form $4n+1$

Gauss' Lemma

Let $p$ be an odd prime.We can partition the set $U_p$ into two sets
$P=\{1,2,\ldots,(p-1)/2\} \subset U_p \quad \text{and} \quad N=\{-1,-2,\ldots,-(p-1)/2\} \subset U_p$

 

represented  as shown by positive and  negative integers.For each $a \in U_p$, we define 

$$aP=\{a,2a,\ldots,a(p-1)/2\} \subset U_p$$

Gauss Lemma says that

If $p$ is an odd prime and $a \in U_p$, then $\left(\frac{a}{p}\right)=(-1)^\mu$, where $\mu=|aP \cap N|$

Example:

Let $p=19$.So $P=\{1,2,3,4,5,6,7,8,9\}$.If we multiply each element of $P$ by 11 and represent it by an element of $P \cup N$, we get

$$aP=11P=\{-8,3,-5,6,-2,9,1,-7,4\}$$

This contains four elements of $N$, (terms with minus sign).So $\mu=4$, which is even.Thus $\frac{11}{9}=1$, So $11 \in Q_{19}$. In fact $11 \equiv 7^2 \pmod{19}$

Example:

Evaluate $\left(\frac{10}{13}\right)$ using Gauss lemma 

Here $P=\{1,2,3,4,5,6\}$ and $N=\{-1,-2,-3,-4,-5,-6\}$ 

$10P=\{-3,-6,4,1,-2,-5\}$

here $\mu=4$

So $\left(\frac{10}{13}\right)=(-1)^4=1$

 

Example:

Evaluate $\left(\frac{2}{13}\right)$ using Gauss lemma 

Here $P=\{1,2,3,4,5,6\}$ and $N=\{-1,-2,-3,-4,-5,-6\}$ 

$2P=\{2,4,6,-5,-3,-1\}$

here $\mu=3$

So $\left(\frac{2}{13}\right)=(-1)^3=-1$

Corollary:

If $p$ is an odd prime. Then

$$\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}$$

thus $2 \in Q_p$ if and only if $p \equiv \pm 1 \pmod{8}$

 $2 \not \in Q_p$ if and only if $p \equiv \pm 3 \pmod{8}$

 

Example:

2 is a  quadratic residue $\pmod{p}$ for $p=7,17,23,31,\ldots$ with square roots $\pm3,\pm 6,\pm 5 ,\pm 8,\ldots$,however, 2 is not a quadratic residue $\pmod{p}$ for $p=3,5,11,13,\ldots$

Example: solve $\left(\frac{13}{31}\right)$

 $\left(\frac{13}{31}\right)=\left(\frac{-18}{31}\right)$

$\quad \quad =\left(\frac{9}{31}\right).\left(\frac{2}{31}\right).\left(\frac{-1}{31}\right)$

Note:$31 \equiv -1 \pmod{8}$ and also $31 \equiv -1 \pmod{4}$

$\quad \quad =1.1.-1=-1$

So $13 \not \in Q_{31}$

Quadratic Reciprocity

To determine whether or not an integer $a$ is a quadratic residue $\pmod{p}$,we need to evaluate $\left(\frac{a}{p}\right)$.For the prime factorization of $a$, we can evaluate $\left(\frac{q}{p}\right)$ for the $q's$ dividing $a$.The following table shows the evaluation of  $\left(\frac{q}{p}\right)$ for small values of $p$ and $q$.

Theorem:

If $p$ and $q$ are distinct odd primes, then

$$\left(\frac{q}{p}\right)=\left(\frac{p}{q}\right)$$

except when $p \equiv q \equiv 3 \pmod{4}$ , in which case

$$\left(\frac{q}{p}\right)=-\left(\frac{p}{q}\right)$$

 

Note:An equivalent  form of this is the elegant result by Legendre is that

$$\left(\frac{q}{p}\right).\left(\frac{p}{q}\right)=(-1)^{(p-1)(q-1)/4}$$

 

for all distinct odd primes $p$ and $q$. This is the generalized Law of Quadratic Reciprocity.

Proof: if $p \equiv 1 \pmod{4}$ then $(p-1)/2$ is even, so $(p-1)(q-1)/4$ is even. Therefore by the law of quadratic reciprocity $(p/q)(q/p)=1$.But $(p/q) \pm 1 = (q/p)$, so $(q/p)=(p/q)$.

On the other hand assume that $p \equiv q \equiv 3 \pmod{4}$.Then $(p-1)/2, (q-1)/2$ and hence $(p-1)(q-1)/4$ are odd.Therefore , again by the law of quadratic reciprocity $(p/q).(q/p)=-1$.Thus $(p/q)=-(q/p)$

Example:Since $17 \equiv 1 \pmod{4}, \left(\frac{17}{29}\right)= \left(\frac{29}{17}\right)$ and since $23 \equiv 3 \pmod{4}$ and $47 \equiv 3 \pmod{4}$,$\left(\frac{23}{47}\right)= -\left(\frac{47}{23}\right)$

Example:

Compute $\left(\frac{152}{43}\right)$

 

 $\left(\frac{152}{43}\right)=\left(\frac{23}{43}\right)$

Note that 23 and 43 are primes of form $4n+3$ so

$\left(\frac{23}{43}\right)=-\left(\frac{43}{23}\right)$

$\quad \quad = -\left(\frac{20}{23}\right)$

$\quad \quad = -\left(\frac{4}{23}\right).\left(\frac{5}{23}\right)$

$\quad \quad = - 1.\left(\frac{5}{23}\right)$ 

$\quad \quad = - 1.\left(\frac{23}{5}\right)$ 

$\quad \quad = - 1.\left(\frac{3}{5}\right)$  

$\quad \quad = - 1.-1=1$

Consequently the congruence   $x^2 \equiv 152 \pmod{53}$ is solvable.

Example:

Compute $\left(\frac{3797}{7297}\right)$

$\left(\frac{3797}{7297}\right)=\left(\frac{7297}{3797}\right)$

$\quad \quad =\left(\frac{3500}{3797}\right)$

$\quad \quad =\left(\frac{2^2.5^3.7}{3797}\right)$

 

Note  $\left(\frac{2}{3797}\right)^2=1$

$\left(\frac{5}{3797}\right)^3=\left(\frac{2}{5}\right)=(-1)^3=-1$

$\left(\frac{7}{3797}\right)=\left(\frac{3}{7}\right)=-1$

therefore

 $\quad \quad =\left(\frac{2^2.5^3.7}{3797}\right)$

$\quad \quad =1.-1.-1=1$

thus the congruence $x^2 \equiv 3797 \pmod{7297} $ is solvable

Jacobi Symbol

 

Jacobi symbol is the generalization of the Legendre Symbol, which was introduced in 1846 by the German Mathematician Karl G J Jacobi.In the Jacobi symbol $\left(\frac{a}{m}\right)$, the modulus $m$ need not be prime, but must be odd and relatively prime to $a$.

Let $m$ be an odd positive integer with the canonical decomposition $m =\prod_{i=1}^k P_i^{e_i}$ and $a$ any integer with $gcd(a,m)=1$. Then the Jacobi symbol $\left(\frac{a}{m}\right)$ is defined by

$$\left(\frac{a}{m}\right)=\left(\frac{a}{\prod_{i=1}^k P_i^{e_i}}\right)=\prod_{i=1}^k \left(\frac{a}{P_i^{e_i}}\right)$$

 

where $\left(\frac{a}{P_i}\right)$ denotes the familiar Legendre symbol.Although we use the same notation, bear in mind that the symbol $\left(\frac{a}{m}\right)$ is the Legendre symbol if and only if $m$ is prime.

Thus if $x^2 \equiv a \pmod{m}$ is solvable , then the Jacobi symbol $\left(\frac{a}{p}\right)=1$.How ever this does not imply that $x^2 \equiv a \pmod{m}$ is solvable when $\left(\frac{a}{m}\right)=1$.For example $\left(\frac{2}{33}\right)=\left(\frac{2}{3.11}\right)=\left(\frac{2}{3}\right)\left(\frac{2}{11}\right)=-1.-1=1$.but $x^2 \equiv 2 \pmod{33}$ has no solutions.

Example: evaluate the jacobi Symbol $\left(\frac{55}{273} \right)$

Note $273=3.7.13$, So by the definition of the Jacobi symbol

$\left(\frac{55}{273}\right)= \left(\frac{55}{3}\right) .\left(\frac{55}{7}\right). \left(\frac{55}{13}\right)$
$\quad \quad = \left(\frac{1}{3}\right) \left(\frac{-1}{7}\right).\left(\frac{3}{13}\right)$
$\quad \quad =1.-1. \left(\frac{13}{3}\right)$
$\quad \quad =- \left(\frac{1}{3}\right)= -1$

Python Code

from sympy.ntheory import jacobi_symbol

from sympy import S

print(S(273).factors())

print(jacobi_symbol(55,273))

{3: 1, 7: 1, 13: 1}
-1

Theorem:

let $m$ be an odd positive integer, and $a$ and $b$ be any integers with $gcd(a,m,)=1=gcd(b,m)$. then

• if $a \equiv b \pmod{m}$,, then $\left(\frac{a}{m}\right)=\left(\frac{b}{m}\right)$
• $\left(\frac{ab}{m}\right)=\left(\frac{a}{m}\right)\left(\frac{b}{m}\right)$
• $ \left(\frac{a^2}{m}\right)=1$

Theorem:

Let $m$ be an odd positive integer.Then

 

• $\left(\frac{-1}{m}\right)=(-1)^{(m-1)/2}$
• $\left(\frac{2}{m}\right)=(-1)^{(m^2-1)/8}$

 Theorem:

The generalized law of Quadratic Reciprocity 

let $m$ and $n$ be relatively prime odd positive integers. Then

 $\left(\frac{m}{n}\right)\left(\frac{n}{m}\right)=(-1)^{(m-1)/2.(n-1)/2}$

Example:Compute the jacobi Symbol $(221/399)$

$(221/399)=(-1)^{(221-1)/2.(399-1)/2}(399/221)$

$\quad \quad= (178/221)=(2/221)(89/221)$

 

$(2/221)=(-1)^{(221^2-1)/8}=-1$

$(89/221)=(-1)^{(89-1)/2.(221-1)/2}(221/89)$

$\quad \quad = (221/89)=(43/89)$

$\quad \quad =(-1)^{(43-1)/2.(89-1)/2}(89/43)$

$ \quad \quad =(89/43)=(3/43)$

$ \quad \quad =(-1)^{(43-1)/2.(3-1)/2}(43/3)$

$ \quad \quad=-(43/3)=-(1/3)$

$ \quad \quad=-1$

 

So $(221/399)=(-1)(-1)=1$

Example:Solve the congruence $x^2 \equiv 15 \pmod{187}$

First notice that $187=11.17$ and $(15/11)=(15/17)=1$. So the congruences $x^2 \equiv 15 \pmod{11}$ and $x^2 \equiv 15 \pmod{17}$ are solvable.Thus $x^2 \equiv 15 \pmod{187}$ is also solvable.

You may note that the two incongruent solutions of $x^2 \equiv 15 \pmod{11}$ are $x \equiv \pm 2 \pmod{11}$ and those of $x^2 \equiv 15 \pmod{17}$ are $x \equiv \pm 7 \pmod{17}$. Therefore by CRT(Chinese Remainder Theorem), the given congruence has four incongruent solutions.So the solutions are $x \equiv \pm 24, \pm 75 \pmod{187}$ ie; $x=24,75,112,163 \pmod{187}$.

\mlegendre{x}{y}

Reference: https://www.physicsforums.com/threads/latex-frustration-defining-commands-with-arguments.277730/