Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

3.10 Legendre and Jacobi Symbols

Suppose we want to determine whether or not $x^{2} \equiv a (mod p)$ $x^{2} \equiv a (mod p)$ has a solution, where $p$ $p$ is prime. If $p$ $p$ is small, we could square all of the numbers mod $p$ $p$ and see if $a$ $a$ is on the list. When $p$ $p$ is large, this is impractical. If $p \equiv 3 (mod 4),$ $p \equiv 3 (mod 4),$ we can use the technique of the previous section and compute $s \equiv a^{(p + 1) / 4} (mod p) .$ $s \equiv a^{(p + 1) / 4} (mod p) .$ If $a$ $a$ has a square root, then $s$ $s$ is one of them, so we simply have to square $s$ $s$ and see if we get $a .$ $a .$ If not, then $a$ $a$ has no square root mod $p .$ $p .$ The following proposition gives a method for deciding whether $a$ $a$ is a square mod $p$ $p$ that works for arbitrary odd $p .$ $p .$

Proposition

Let $p$ $p$ be an odd prime and let $a$ $a$ be an integer with $a \equiv 0 (mod p) .$ $a \equiv 0 (mod p) .$ Then $a^{(p - 1) / 2} \equiv \pm 1 (mod p) .$ $a^{(p - 1) / 2} \equiv \pm 1 (mod p) .$ The congruence $x^{2} \equiv a (mod p)$ $x^{2} \equiv a (mod p)$ has a solution if and only if $a^{(p - 1) / 2} \equiv 1 (mod p) .$ $a^{(p - 1) / 2} \equiv 1 (mod p) .$

Proof. Let $y \equiv a^{(p - 1) / 2} (mod p) .$ $y \equiv a^{(p - 1) / 2} (mod p) .$ Then $y^{2} \equiv a^{p - 1} \equiv 1 (mod p),$ $y^{2} \equiv a^{p - 1} \equiv 1 (mod p),$ by Fermat’s theorem. Therefore (Exercise 15), $y \equiv \pm 1 (mod p) .$ $y \equiv \pm 1 (mod p) .$

If $a \equiv x^{2},$ $a \equiv x^{2},$ then $a^{(p - 1) / 2} \equiv x^{p - 1} \equiv 1 (mod p) .$ $a^{(p - 1) / 2} \equiv x^{p - 1} \equiv 1 (mod p) .$ The hard part is showing the converse. Let $α$ $α$ be a primitive root mod $p .$ $p .$ Then $a \equiv α^{j}$ $a \equiv α^{j}$ for some $j .$ $j .$ If $a^{(p - 1) / 2} \equiv 1 (mod p),$ $a^{(p - 1) / 2} \equiv 1 (mod p),$ then

\begin{matrix} α^{j (p - 1) / 2} \equiv a^{(p - 1) / 2} \equiv 1 & (mod p) . \end{matrix}

$\begin{matrix} α^{j (p - 1) / 2} \equiv a^{(p - 1) / 2} \equiv 1 & (mod p) . \end{matrix}$

By the Proposition of Section 3.7, $j (p - 1) / 2 \equiv 0 (mod p - 1) .$ $j (p - 1) / 2 \equiv 0 (mod p - 1) .$ This implies that $j$ $j$ must be even: $j = 2 k .$ $j = 2 k .$ Therefore, $a \equiv g^{j} \equiv (α^{k})^{2} (mod p),$ $a \equiv g^{j} \equiv (α^{k})^{2} (mod p),$ so $a$ $a$ is a square mod $p .$ $p .$

The criterion is very easy to implement on a computer, but it can be rather difficult to use by hand. In the following, we introduce the Legendre and Jacobi symbols, which give us an easy way to determine whether or not a number is a square mod $p .$ $p .$ They also are useful in primality testing (see Section 9.3).

Let $p$ $p$ be an odd prime and let $a \equiv 0 (mod p) .$ $a \equiv 0 (mod p) .$ Define the Legendre symbol

(\frac{a}{p}) = {\begin{array}{l} + 1 if x^{2} \equiv a ​ ​ (mod p) has a solution . \\ - 1 if x^{2} \equiv a ​ ​ (mod p) has no solution . \end{array}

$(\frac{a}{p}) = {\begin{array}{l} + 1 if x^{2} \equiv a (mod p) has a solution . \\ - 1 if x^{2} \equiv a (mod p) has no solution . \end{array}$

Some important properties of the Legendre symbol are given in the following.

Proposition

Let $p$ $p$ be an odd prime.

If $a \equiv b \equiv 0 (mod p),$ $a \equiv b \equiv 0 (mod p),$ then

$(\frac{a}{p}) = (\frac{b}{p}) .$ $(\frac{a}{p}) = (\frac{b}{p}) .$
If $a \equiv 0 (mod p),$ $a \equiv 0 (mod p),$ then

$\begin{matrix} (\frac{a}{p}) \equiv a^{(p - 1) / 2} & (mod p) . \end{matrix}$ $\begin{matrix} (\frac{a}{p}) \equiv a^{(p - 1) / 2} & (mod p) . \end{matrix}$
If $a b \equiv 0 (mod p),$ $a b \equiv 0 (mod p),$ then

$(\frac{a b}{p}) = (\frac{a}{p}) (\frac{b}{p}) .$ $(\frac{a b}{p}) = (\frac{a}{p}) (\frac{b}{p}) .$
$(\frac{- 1}{p}) = (- 1)^{(p - 1) / 2} .$ $(\frac{- 1}{p}) = (- 1)^{(p - 1) / 2} .$

Proof. Part (1) is true because the solutions to $X^{2} \equiv a$ $X^{2} \equiv a$ are the same as those to $X^{2} \equiv b$ $X^{2} \equiv b$ when $a \equiv b (mod p) .$ $a \equiv b (mod p) .$

Part (2) is the definition of the Legendre symbol combined with the previous proposition.

To prove part (3), we use part (2):

\begin{matrix} (\frac{a b}{p}) \equiv {(a b)}^{(p - 1) / 2} \equiv a^{(p - 1) / 2} b^{(p - 1) / 2} \equiv (\frac{a}{p}) (\frac{b}{p}) & (mod p) . \end{matrix}

$\begin{matrix} (\frac{a b}{p}) \equiv {(a b)}^{(p - 1) / 2} \equiv a^{(p - 1) / 2} b^{(p - 1) / 2} \equiv (\frac{a}{p}) (\frac{b}{p}) & (mod p) . \end{matrix}$

Since the left and right ends of this congruence are $\pm 1$ $\pm 1$ and they are congruent mod the odd prime $p,$ $p,$ they must be equal. This proves (3).

For part (4), use part (2) with $a = - 1 :$ $a = - 1 :$

\begin{matrix} (\frac{- 1}{p}) \equiv {(- 1)}^{(p - 1) / 2} & (mod p) . \end{matrix}

$\begin{matrix} (\frac{- 1}{p}) \equiv {(- 1)}^{(p - 1) / 2} & (mod p) . \end{matrix}$

Again, since the left and right sides of this congruence are $\pm 1$ $\pm 1$ and they are congruent mod the odd prime $p,$ $p,$ they must be equal. This proves (4).

Example

Let $p = 11 .$ $p = 11 .$ The nonzero squares mod 11 are $1, 3, 4, 5, 9 .$ $1, 3, 4, 5, 9 .$ We have

(\frac{6}{11}) (\frac{7}{11}) = (- 1) (- 1) = + 1

$(\frac{6}{11}) (\frac{7}{11}) = (- 1) (- 1) = + 1$

and (use property (1))

(\frac{42}{11}) = (\frac{9}{11}) = + 1.

$(\frac{42}{11}) = (\frac{9}{11}) = + 1.$

Therefore,

(\frac{6}{11}) (\frac{7}{11}) = (\frac{42}{11}) .

$(\frac{6}{11}) (\frac{7}{11}) = (\frac{42}{11}) .$

The Jacobi symbol extends the Legendre symbol from primes $p$ $p$ to composite odd integers $n .$ $n .$ One might be tempted to define the symbol to be $+ 1$ $+ 1$ if $a$ $a$ is a square mod $n$ $n$ and $- 1$ $- 1$ if not. However, this would cause the important property (3) to fail. For example, $2$ $2$ is not a square mod 35, and $3$ $3$ is not a square mod 35 (since they are not squares mod 5), but also the product $6$ $6$ is not a square mod 35 (since it is not a square mod 7). If Property (3) held, then we would have $(- 1) (- 1) = - 1,$ $(- 1) (- 1) = - 1,$ which is false.

In order to preserve property (3), we define the Jacobi symbol as follows. Let $n$ $n$ be an odd positive integer and let $a$ $a$ be a nonzero integer with $gcd (a, n) = 1 .$ $gcd (a, n) = 1 .$ Let

n = p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{r}^{b_{r}}

$n = p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{r}^{b_{r}}$

be the prime factorization of $n .$ $n .$ Then

(\frac{a}{n}) = {(\frac{a}{p_{1}})}^{b_{1}} {(\frac{a}{p_{2}})}^{b_{2}} \dots {(\frac{a}{p_{r}})}^{b_{r}} .

$(\frac{a}{n}) = {(\frac{a}{p_{1}})}^{b_{1}} {(\frac{a}{p_{2}})}^{b_{2}} \dots {(\frac{a}{p_{r}})}^{b_{r}} .$

The symbols on the right side are the Legendre symbols introduced earlier. Note that if $n = p,$ $n = p,$ the right side is simply one Legendre symbol, so the Jacobi symbol reduces to the Legendre symbol.

Example

Let $n = 135 = 3^{3} \cdot 5 .$ $n = 135 = 3^{3} \cdot 5 .$ Then

(\frac{2}{135}) = {(\frac{2}{3})}^{3} (\frac{2}{5}) = (- 1)^{3} (- 1) = + 1.

$(\frac{2}{135}) = {(\frac{2}{3})}^{3} (\frac{2}{5}) = (- 1)^{3} (- 1) = + 1.$

Note that 2 is not a square mod 5, hence is not a square mod 135. Therefore, the fact that the Jacobi symbol has the value $+ 1$ $+ 1$ does not imply that 2 is a square mod 135.

The main properties of the Jacobi symbol are given in the following theorem. Parts (1), (2), and (3) can be deduced from those of the Legendre symbol. Parts (4) and (5) are much deeper.

Theorem

Let $n$ $n$ be odd.

If $a \equiv b (mod n)$ $a \equiv b (mod n)$ and $gcd (a, n) = 1,$ $gcd (a, n) = 1,$ then

$( \frac{a}{n}) = (\frac{b}{n}) .$ $( \frac{a}{n}) = (\frac{b}{n}) .$
If $gcd (a b, n) = 1,$ $gcd (a b, n) = 1,$ then

$(\frac{a b}{n}) = ( \frac{a}{n}) (\frac{b}{n}) .$ $(\frac{a b}{n}) = ( \frac{a}{n}) (\frac{b}{n}) .$
$(\frac{- 1}{n}) = (- 1)^{(n - 1) / 2} .$ $(\frac{- 1}{n}) = (- 1)^{(n - 1) / 2} .$
$(\frac{2}{n}) = {\begin{array}{l} + 1 i f n \equiv 1 or 7 (mod 8) \\ - 1 i f n \equiv 3 or 5 (mod 8) . \end{array}$ $(\frac{2}{n}) = {\begin{array}{l} + 1 i f n \equiv 1 or 7 (mod 8) \\ - 1 i f n \equiv 3 or 5 (mod 8) . \end{array}$
Let $m$ $m$ be odd with $gcd (m, n) = 1 .$ $gcd (m, n) = 1 .$ Then

$(\frac{m}{n}) = {\begin{array}{l} - (\frac{n}{m}) i f m \equiv n \equiv 3 (mod 4) \\ + (\frac{n}{m}) o t h e r w i s e . \end{array}$ $(\frac{m}{n}) = {\begin{array}{l} - (\frac{n}{m}) i f m \equiv n \equiv 3 (mod 4) \\ + (\frac{n}{m}) o t h e r w i s e . \end{array}$

Note that we did not include a statement that $(\frac{a}{n}) \equiv a^{(n - 1) / 2} .$ $(\frac{a}{n}) \equiv a^{(n - 1) / 2} .$ This is usually not true for composite $n$ $n$ (see Exercise 45). In fact, the Solovay-Strassen primality test (see Section 9.3) is based on this fact.

Part (5) is the famous law of quadratic reciprocity, proved by Gauss in 1796. When $m$ $m$ and $n$ $n$ are primes, it relates the question of whether $m$ $m$ is a square mod $n$ $n$ to the question of whether $n$ $n$ is a square mod $m .$ $m .$

A proof of the theorem when $m$ $m$ and $n$ $n$ are primes can be found in most elementary number theory texts. The extension to composite $m$ $m$ and $n$ $n$ can be deduced fairly easily from this case. See [Niven et al.], [Rosen], or [KraftW], for example.

When quadratic reciprocity is combined with the other properties of the Jacobi symbol, we obtain a fast way to evaluate the symbol. Here are two examples.

Example

Let’s calculate $(\frac{4567}{12345}) :$ $(\frac{4567}{12345}) :$

\begin{array}{rcl} (\frac{4567}{12345}) & = & + (\frac{12345}{4567}) (by (5), since 12345 \equiv 1   (mod 4)) \\ = & + (\frac{3211}{4567}) (by (1), since 12345 \equiv 3211 (mod 4567)) \\ = & - (\frac{4567}{3211}) (by (5)) = - (\frac{1356}{3211}) (by (1)) \\ = & - {(\frac{2}{3211})}^{2} (\frac{339}{3211}) (by (2), since 1356 = 2^{2} \cdot 339) \\ = & - (\frac{339}{3211}) (since {(\pm 1)}^{2} = 1) \\ = & + (\frac{3211}{339}) (by (5)) = + (\frac{160}{339}) (by (1)) \\ = & + {(\frac{2}{339})}^{5} (\frac{5}{339}) (by (2), since 160 = 2^{5} \cdot 5) \\ = & + (- 1)^{5} (\frac{5}{339}) (by (4)) = - (\frac{339}{5}) (by (5)) \\ = & - (\frac{4}{5}) (by (1)) = - {(\frac{2}{5})}^{2} = - 1 . \end{array}

$\begin{array}{rcl} (\frac{4567}{12345}) & = & + (\frac{12345}{4567}) (by (5), since 12345 \equiv 1 (mod 4)) \\ = & + (\frac{3211}{4567}) (by (1), since 12345 \equiv 3211 (mod 4567)) \\ = & - (\frac{4567}{3211}) (by (5)) = - (\frac{1356}{3211}) (by (1)) \\ = & - {(\frac{2}{3211})}^{2} (\frac{339}{3211}) (by (2), since 1356 = 2^{2} \cdot 339) \\ = & - (\frac{339}{3211}) (since {(\pm 1)}^{2} = 1) \\ = & + (\frac{3211}{339}) (by (5)) = + (\frac{160}{339}) (by (1)) \\ = & + {(\frac{2}{339})}^{5} (\frac{5}{339}) (by (2), since 160 = 2^{5} \cdot 5) \\ = & + (- 1)^{5} (\frac{5}{339}) (by (4)) = - (\frac{339}{5}) (by (5)) \\ = & - (\frac{4}{5}) (by (1)) = - {(\frac{2}{5})}^{2} = - 1 . \end{array}$

The only factorization needed in the calculation was removing powers of 2, which is easy to do. The fact that the calculations can be done without factoring odd numbers is important in the applications. The fact that the answer is $- 1$ $- 1$ implies that 4567 is not a square mod 12345. However, if the answer had been $+ 1,$ $+ 1,$ we could not have deduced whether 4567 is a square or is not a square mod 12345. See Exercise 44.

Example

Let’s calculate $(\frac{107}{137}) :$ $(\frac{107}{137}) :$

\begin{array}{rcl} (\frac{107}{137}) & = & + (\frac{137}{107}) (by (5)) \\ = & + (\frac{30}{107}) (by (1)) \end{array}

$\begin{array}{rcl} (\frac{107}{137}) & = & + (\frac{137}{107}) (by (5)) \\ = & + (\frac{30}{107}) (by (1)) \end{array}$

\begin{array}{l} = & + (\frac{2}{107}) (\frac{15}{107}) (by (2)) \\ = & + (- 1) (\frac{15}{107}) (by (4)) \\ = & + (\frac{107}{15}) (by (5)) \\ = & + (\frac{2}{15}) (by (1)) \\ = & + 1 (by (5)) . \end{array}

$\begin{array}{l} = & + (\frac{2}{107}) (\frac{15}{107}) (by (2)) \\ = & + (- 1) (\frac{15}{107}) (by (4)) \\ = & + (\frac{107}{15}) (by (5)) \\ = & + (\frac{2}{15}) (by (1)) \\ = & + 1 (by (5)) . \end{array}$

Since 137 is a prime, this says that 107 is a square mod 137. In contrast, during the calculation, we used the fact that $(\frac{2}{15}) = + 1 .$ $(\frac{2}{15}) = + 1 .$ This does not mean that 2 is a square mod 15. In fact, 2 is not a square mod 5, so it cannot be a square mod 15. Therefore, although we can interpret the final answer as saying that 107 is a square mod the prime 137, we should not interpret intermediate steps involving composite numbers as saying that a number is a square.

Suppose $n = p q$ $n = p q$ is the product of two large primes. If $(\frac{a}{n}) = - 1,$ $(\frac{a}{n}) = - 1,$ then we can conclude that $a$ $a$ is not a square mod $n .$ $n .$ What can we conclude if $(\frac{a}{n}) = + 1$ $(\frac{a}{n}) = + 1$ ? Since

(​ ​ ​ ​ \frac{a}{n}) = (\frac{a}{p}) (\frac{a}{q}),

$( \frac{a}{n}) = (\frac{a}{p}) (\frac{a}{q}),$

there are two possibilities:

(\frac{a}{p}) = (\frac{a}{q}) = - 1 or (\frac{a}{p}) = (\frac{a}{q}) = + 1.

$(\frac{a}{p}) = (\frac{a}{q}) = - 1 or (\frac{a}{p}) = (\frac{a}{q}) = + 1.$

In the first case, $a$ $a$ is not a square mod $p,$ $p,$ therefore cannot be a square mod $p q .$ $p q .$

In the second case, $a$ $a$ is a square mod $p$ $p$ and mod $q .$ $q .$ The Chinese remainder theorem can be used to combine a square root mod $p$ $p$ and a square root mod $q$ $q$ to get a square root of $a$ $a$ mod $n .$ $n .$ Therefore, $a$ $a$ is a square mod $n .$ $n .$

Therefore, if $(\frac{a}{n}) = + 1,$ $(\frac{a}{n}) = + 1,$ then $a$ $a$ can be either a square or a nonsquare mod $n .$ $n .$ Deciding which case holds is called the quadratic residuosity problem. No fast algorithm is known for solving it. Of course, if we can factor $n,$ $n,$ then the problem can easily be solved by computing $(\frac{a}{p}) .$ $(\frac{a}{p}) .$

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 3.10 Legendre and Jacobi Symbols

Create new playlist

Sign In

Sign Up

Table of Contents for
3.10 Legendre and Jacobi Symbols