# The Jacobi symbol

The Jacobi symbol is a generalization of the Legendre symbol. In this post, we define the Jacobi symbol and discuss some of its important properties. The Legendre symbol (coupled with the law of reciprocity) is a useful tool in determining whether a number is a quadratic residue modulo an odd prime. However, the Legendre symbol is also restrictive since the bottom argument must be a prime. The Jacobi symbol generalizes the Legendre symbol and in many cases is easier to evaluate than the Legendre symbol. This is demonstrated in several examples.

____________________________________________________________________________

Defining The Jacobi Symbol

The Legendre symbol is $\displaystyle \biggl(\frac{a}{p}\biggr)$ where the bottom argument is always an odd prime and the top argument can be any integer. When $a$ is an integer that is relatively prime to the odd prime $p$, the Legendre symbol $\displaystyle \biggl(\frac{a}{p}\biggr)$ carries information on whether the integer $a$ is quadratic residue modulo $p$. The following gives the definition of the Legendre symbol.

$\displaystyle \biggl(\frac{a}{p}\biggr) = \left\{ \begin{array}{rl} 0 &\ \text{if } a \equiv 0 \ (\text{mod} \ p) \\ 1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a \text{ is a quadratic residue modulo }p\\ -1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a \text{ is a quadratic nonresidue modulo }p \end{array} \right.$

The Jacobi symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$ has the same look as the Legendre symbol. The top argument can be any integer. The bottom argument is an odd positive integer. If the odd positive integer $n>1$ has the prime factorization $n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_t^{e_t}$, the Jacobi symbol is defined as follows:

$\displaystyle \biggl(\frac{a}{n}\biggr)=\biggl(\frac{a}{p_1}\biggr)^{e_1} \times \biggl(\frac{a}{p_2}\biggr)^{e_2} \times \cdots \times \biggl(\frac{a}{p_t}\biggr)^{e_t}$

For convenience, we define $\displaystyle \biggl(\frac{a}{1}\biggr)=1$. A slightly different, but equivalent, definition is that whenever the odd integer $n>1$ has the prime factorization $n=q_1 \times q_2 \times \cdots \times q_k$ (the prime numbers $q_j$ are not necessarily distinct), the symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$ is defined as follows:

$\displaystyle \biggl(\frac{a}{n}\biggr)=\biggl(\frac{a}{q_1}\biggr) \times \biggl(\frac{a}{q_2}\biggr) \times \cdots \times \biggl(\frac{a}{q_k}\biggr)$

The Jacobi symbol is defined using the Legendre symbol according to the prime factorization of the bottom argument.

____________________________________________________________________________

Properties of The Jacobi Symbol

Now that the Jacobi symbol has been defined based on the Legendre symbol, there are two natural questions.

• Does the value of $\displaystyle \biggl(\frac{a}{n}\biggr)= \pm 1$ indicates that $a$ is a quadratic residue or nonresidue modulo $n$?
• The Legendre symbol follows a set of rules (e.g. the law of quadratic reciprocity) that make the Legendre symbol a versatile tool. Does the Jacobi symbol follow these rules? Conceptually, evaluating the Jacobi symbol requires factoring the bottom argument of the symbol. On the surface, this appears to be a limitation. However, if the Jacobi symbol follows the rules for the Legendre symbol including the law of quadratic reciprocity, it will be just as easy to evaluate the Jacobi symbol.

For the first question, the following is true: If $a$ is a quadratic residue modulo $n$, then $\displaystyle \biggl(\frac{a}{n}\biggr)=1$. The contrapositive of this statement is that if $\displaystyle \biggl(\frac{a}{n}\biggr)=-1$, then the number $a$ is a quadratic nonresidue modulo the odd integer $n$, i.e. the equation $x^2 \equiv a \ (\text{mod} \ n)$ has no solutions. However, the value of $\displaystyle \biggl(\frac{a}{n}\biggr)=1$ does not imply that $a$ is a quadratic residue modulo $n$. For example, $\displaystyle \biggl(\frac{2}{15}\biggr)=1$ but the equation $x^2 \equiv 2 \ (\text{mod} \ 15)$ has no solutions. Note that both equations $x^2 \equiv 2 \ (\text{mod} \ 3)$ and $x^2 \equiv 2 \ (\text{mod} \ 5)$ have no solutions. This means that the value of $\displaystyle \biggl(\frac{2}{15}\biggr)=1$ is the product of two Legendre symbols of -1.

Theorem 1
Let $n$ be an odd positive integer. Let $a$ be such that $\text{GCD}(a,n)=1$. Then If $a$ is a quadratic residue modulo $n$, then $\displaystyle \biggl(\frac{a}{n}\biggr)=1$. The converse does not hold if $n$ is not a prime.

Proof
Suppose that $a$ is a quadratic residue modulo $n$, i.e. the equation $x^2 \equiv a \ (\text{mod} \ n)$ has a solution. Let $n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_t^{e_t}$ be the prime factorization of $n$. Let $m_i=p_i^{e_i}$ for each $i$. By the Chinese remainder theorem, the equation $x^2 \equiv a \ (\text{mod} \ m_i)$ has a solution for each $i=1,2,\cdots,t$. it then follows that the equation $x^2 \equiv a \ (\text{mod} \ p_i)$ has a solution too for each $i=1,2,\cdots,t$. Hence the Legendre symbol $\displaystyle \biggl(\frac{a}{p_i}\biggr)=1$ for each $i$. It follows that the Jacobi symbol $\displaystyle \biggl(\frac{a}{n}\biggr)=1$. $\square$

For the second question, the rules that are obeyed by the Legendre symbol are also obeyed by the Jacobi symbol. Some of the rules are easily seen to carry over to the Jacobi symbol. The fact that the law of quadratic reciprocity and the two supplements are obeyed by the Jacobi symbol is not entirely obvious from the definition. However the proof is not difficult. We give a complete proof here.

Lemma 2
Let $a$ and $b$ be odd positive integers. The following two conditions hold.

$\displaystyle \frac{a-1}{2} \times \frac{b-1}{2} \equiv \frac{ab-1}{2} \ (\text{mod} \ 2)$

$\displaystyle \frac{a^2-1}{8} \times \frac{b^2-1}{8} \equiv \frac{(ab)^2-1}{8} \ (\text{mod} \ 2)$

Proof
The lemma is established by the following derivation:

$\displaystyle \frac{ab-1}{2}-\biggl[\frac{a-1}{2}+\frac{b-1}{2} \biggr]=\frac{ab-a-b+1}{2}=\frac{(a-1)(b-1)}{2}$

$\displaystyle \frac{(ab)^2-1}{8}-\biggl[\frac{a^2-1}{8}+\frac{b^2-1}{8} \biggr]=\frac{(ab)^2-a^2-b^2+1}{8}=\frac{(a^2-1)(b^2-1)}{8}$

Because both $a$ and $b$ are odd integers, the right-hand-side of both equations are even integers and thus $\equiv 0 \ (\text{mod} \ 2)$. $\square$

Theorem 3 (Properties of Jacobi Symbol)

1. $\displaystyle \biggl(\frac{a}{n}\biggr) = \left\{ \begin{array}{rl} 0 &\ \text{if } \text{GCD}(a,n) >1 \\ \pm 1 &\ \text{if } \text{GCD}(a,n)=1 \end{array} \right.$
2. $\text{ }$

3. If $n$ is a prime, then the Jacobi symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$ coincides with the Legendre symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$.
4. $\text{ }$

5. If $a \equiv b \ (\text{mod} \ n)$, then $\displaystyle \biggl(\frac{a}{n}\biggr)=\biggl(\frac{b}{n}\biggr)$.
6. $\text{ }$

7. The Jacobi symbol is multiplicative when the bottom argument is fixed, i.e. $\displaystyle \biggl(\frac{ab}{n}\biggr)=\biggl(\frac{a}{n}\biggr) \biggl(\frac{b}{n}\biggr)$.
8. $\text{ }$

9. The Jacobi symbol is multiplicative when the upper argument is fixed, i.e. $\displaystyle \biggl(\frac{a}{mn}\biggr)=\biggl(\frac{a}{m}\biggr) \biggl(\frac{a}{n}\biggr)$.
10. $\text{ }$

11. (The law of quadratic reciprocity)
Let $a$ and $b$ be relatively prime odd positive integers. Then

$\displaystyle \biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr)=(-1)^{(a-1)/2 \times (b-1)/2}$

Equivalently, $\displaystyle \biggl(\frac{a}{b}\biggr) = \left\{ \begin{array}{rl} \displaystyle \biggl(\frac{b}{a}\biggr) &\ \text{if } a \equiv 1 \ (\text{mod} \ 4) \text{ or } b \equiv 1 \ (\text{mod} \ 4) \\ \displaystyle -\biggl(\frac{b}{a}\biggr) &\ \text{if } a \equiv b \equiv 3 \ (\text{mod} \ 4) \end{array} \right.$

12. (First supplement to the law of quadratic reciprocity)
Let $n$ be an odd positive integer. Then

$\displaystyle \biggl(\frac{-1}{n}\biggr)=(-1)^{(n-1)/2}$.

Equivalently, $\displaystyle \biggl(\frac{-1}{n}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } n \equiv 1 \ (\text{mod} \ 4) \\ -1 &\ \text{if } n \equiv 3 \ (\text{mod} \ 4) \end{array} \right.$

13. (Second supplement to the law of quadratic reciprocity)
Let $n$ be an odd positive integer. Then

$\displaystyle \biggl(\frac{2}{n}\biggr)=(-1)^{(n^2-1)/8}$.

Equivalently, $\displaystyle \biggl(\frac{2}{n}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } n \equiv 1 \ (\text{mod} \ 8) \text{ or } n \equiv 7 \ (\text{mod} \ 8) \\ -1 &\ \text{if } n \equiv 3 \ (\text{mod} \ 8) \text{ or } n \equiv 5 \ (\text{mod} \ 8) \end{array} \right.$

Proof
For the first bullet point, if the top argument and the bottom argument have a prime factor in common, then one of the Legendre symbols that make up the Jacobi symbol is zero. If the top argument and the bottom argument have no prime factor in common, then all the Legendre symbols that make up the Jacobi symbol is either 1 or -1.

The second point is clear. If the bottom argument is an odd prime, the definition of Jacobi symbol leads to the Legendre symbol.

For bullet points 3, 4 and 5, simply write out the Jacobi symbol and then use the corresponding properties of the Legendre symbol.

Now the proof of bullet point 6 (the law of quadratic reciprocity). Let $a$ and $b$ be relatively prime. Let $a=p_1 \times p_2 \times \cdots \times p_w$ and $b=q_1 \times q_2 \times \cdots \times q_t$ be their prime factorizations. Note that the primes $p_i$ are not necessarily distinct and the primes $q_i$ are not necessarily distinct. However, $p_i \ne q_j$ since $a$ and $b$ are relatively prime. Consider the following derivation of the product $\displaystyle \biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr)$.

\displaystyle \begin{aligned}\biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr)&=\prod \limits_{i=1}^t \biggl(\frac{a}{q_i}\biggr) \ \prod \limits_{j=1}^w \biggl(\frac{b}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \ \prod \limits_{j=1}^w \prod \limits_{i=1}^t \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \ \prod \limits_{i=1}^t \prod \limits_{j=1}^w \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w (-1)^{(p_j-1)/2 \times (q_i-1)/2} \\&=(-1)^E \end{aligned}

where

$\displaystyle E=\sum \limits_{i,j} \biggl[\frac{p_j-1}{2} \times \frac{q_i-1}{2} \biggr]$

The bullet point 6 is established after the quantity $E$ is simplified as follows:

\displaystyle \begin{aligned} \sum \limits_{i,j} \biggl[\frac{p_j-1}{2} \times \frac{q_i-1}{2} \biggr]&=\sum_j \biggl[\sum_i \frac{q_i-1}{2}\biggr] \frac{p_j-1}{2} \\&\equiv \sum_j \biggl[ \frac{b-1}{2}\biggr] \frac{p_j-1}{2} \ \ \ \text{ Use Lemma 2}\\&\equiv \frac{b-1}{2} \sum_j \frac{p_j-1}{2} \\&\equiv \frac{b-1}{2} \frac{a-1}{2} \ (\text{mod} \ 2) \ \ \ \text{ Use Lemma 2} \end{aligned}

Now consider the bullet point #7 (the first supplement to the law of quadratic reciprocity). The proof is an induction proof on the number of prime factors of $n$. If $n$ is a prime, then it is done. So we assume $n=p_1 \times p_2$ (not necessarily distinct). Consider the following derivation:

\displaystyle \begin{aligned} \biggl(\frac{-1}{n}\biggr)&=\biggl(\frac{-1}{p_1}\biggr) \biggl(\frac{-1}{p_2}\biggr) \\&=(-1)^{(p_1-1)/2} \ (-1)^{(p_2-1)/2} \\&=(-1)^{(p_1-1)/2+(p_2-1)/2} \\&\equiv (-1)^{(p_1 \times p_2 -1)/2} \ \ \ \ \ \text{Use Lemma 2} \\&\equiv (-1)^{(n -1)/2} \ (\text{mod} \ 2) \end{aligned}

It is a straightforward argument that whenever the property is true for $n$ being a product of $k$ primes, the property is true for $n$ being a product of $k+1$ primes. Thus bullet 7 is established.

The proof of bullet point 8 (the second supplement to the law of quadratic reciprocity) is also an induction proof on the number of prime factors of $n$. The most important case is the of two prime factors.

\displaystyle \begin{aligned} \biggl(\frac{2}{n}\biggr)&=\biggl(\frac{2}{p_1}\biggr) \biggl(\frac{2}{p_2}\biggr) \\&=(-1)^{(p_1^2-1)/8} \ (-1)^{(p_2^2-1)/8} \\&=(-1)^{(p_1^2-1)/8+(p_2^2-1)/8} \\&\equiv (-1)^{((p_1 \times p_2)^2 -1)/8} \ \ \ \ \ \text{Use Lemma 2} \\&\equiv (-1)^{(n^2 -1)/8} \ (\text{mod} \ 2) \end{aligned}

With the 2-case established, it is straightforward to carry out the remainder of the induction proof of bullet 8. $\square$

____________________________________________________________________________

Examples

Example 1
Evaluate $\displaystyle \biggl(\frac{1783}{7523}\biggr)$, an example where both the upper and lower arguments are primes. In the previous post, the example is calculated using only Legendre symbol. Here we work it in Jacobi symbol. As much as possible, we flip the symbol without factoring.

\displaystyle \begin{aligned} \biggl(\frac{1783}{7523}\biggr)&=-\biggl(\frac{7523}{1783}\biggr) \\&=-\biggl(\frac{391}{1783}\biggr) \ \ *\\&=\biggl(\frac{1783}{391}\biggr) \\&=\biggl(\frac{219}{391}\biggr) \ \ *\\&=-\biggl(\frac{391}{219}\biggr) \\&=-\biggl(\frac{172}{219}\biggr) \\&=-\biggl(\frac{2}{219}\biggr)^2 \biggl(\frac{43}{219}\biggr) \\&=-\biggl(-1\biggr)^2 (-1) \biggl(\frac{219}{43}\biggr) \\&=\biggl(\frac{4}{43}\biggr) \\&=1 \end{aligned}

One advantage of using Jacobi symbol is that when the upper argument is an odd integer that is not prime, we can still flip it (the steps with *). Then reduce and then flip again until we reach a point with small numbers. Thinking in Legendre symbol only, the steps with * cannot be flipped. As Jacobi symbols, they can be flipped freely as long as the arguments are odd integers. The advantage may not be apparent in this example. When the composite integers are large to the point that their factorizations are in effect not obtainable, this advantage is huge. $\square$

Example 2
Evaluate $\displaystyle \biggl(\frac{a}{p}\biggr)$ where $p=$ 1298351, an odd prime and $a=$ 756479. This is Example 2 in this previous post. The number $a$ is not a prime. Here we use Jacobi symbol to demonstrate that factoring is not needed. We can start by flipping. We have the following derivation.

\displaystyle \begin{aligned} \biggl(\frac{756479}{1298351}\biggr)&=-\biggl(\frac{1298351}{756479}\biggr) \\&=-\biggl(\frac{541872}{756479}\biggr) \\&=-\biggl(\frac{2}{756479}\biggr)^4 \times \biggl(\frac{33867}{756479}\biggr) \\&=-\biggl(1\biggr)^4 \times (-1) \biggl(\frac{756479}{33867}\biggr) \\&=\biggl(\frac{11405}{33867}\biggr) \\&=\biggl(\frac{33867}{11405}\biggr) \\&=\biggl(\frac{11057}{11405}\biggr) \\&=\biggl(\frac{11405}{11057}\biggr) \\&=\biggl(\frac{348}{11057}\biggr) \\&=\biggl(\frac{2}{11057}\biggr)^2 \biggl(\frac{87}{11057} \biggr) \\&=\biggl(1\biggr)^2 \biggl(\frac{11057}{87} \biggr) \\&=\biggl(\frac{8}{87}\biggr) \\&=\biggl(\frac{2}{87} \biggr)^3 \\&=1 \end{aligned}

Note that the original symbol to evaluate is a Legendre symbol. The interim steps are done with Jacobi symbol as much as possible. With the Jacobi way, the symbol is flipped, reduced and flipped again multiple times. The derivation seems long. However, the flip-reduce-flip is much faster than factoring when the numbers involved are large. $\square$

Example 3
Evaluate $\displaystyle \biggl(\frac{a}{n}\biggr)$ where $n=$ 12408107 and $a=$ 4852777. Both numbers are not prime. The symbol has to be evaluated as a Jacobi symbol.

\displaystyle \begin{aligned} \biggl(\frac{4852777}{12408107}\biggr)&=\biggl(\frac{12408107}{4852777}\biggr) \\&= \biggl(\frac{2702553}{4852777}\biggr) \\&= \biggl(\frac{4852777}{2702553}\biggr) \\&= \biggl(\frac{2150224}{2702553}\biggr) \\&= \biggl(\frac{2}{2702553}\biggr)^4 \biggl(\frac{134389}{2702553}\biggr) \\&= \biggl(1\biggr)^4 \biggl(\frac{2702553}{134389}\biggr) \\&= \biggl(\frac{14773}{134389}\biggr) \\&= \biggl(\frac{134389}{14773}\biggr) \\&= \biggl(\frac{1432}{14773}\biggr) \\&= \biggl(\frac{2}{14773}\biggr)^3 \biggl(\frac{179}{14773}\biggr) \\&= \biggl(-1\biggr)^3 \biggl(\frac{14773}{179}\biggr) \\&= - \biggl(\frac{95}{179}\biggr) \\&= - (-1) \biggl(\frac{179}{95}\biggr) \\&=\biggl(\frac{84}{95}\biggr) \\&=\biggl(\frac{2}{95}\biggr)^2 \biggl(\frac{21}{95}\biggr) \\&=\biggl(1\biggr)^2 \biggl(\frac{95}{21}\biggr) \\&=\biggl(\frac{11}{21}\biggr) \\&=\biggl(\frac{21}{11}\biggr) \\&=\biggl(\frac{10}{11}\biggr) \\&=\biggl(\frac{2}{11}\biggr) \biggl(\frac{5}{11}\biggr) \\&=\biggl(-1\biggr) \biggl(\frac{11}{5}\biggr) \\&=-\biggl(\frac{6}{5}\biggr) \\&=-\biggl(\frac{2}{5}\biggr) \biggl(\frac{3}{5}\biggr) \\&=-\biggl(-1\biggr) \biggl(\frac{5}{3}\biggr) \\&=\biggl(\frac{2}{3}\biggr) \\&=-1 \end{aligned}

The above derivation seems long in that there are quite a few steps. But many of the steps are flip-reduce-flip-reduce that are easy to do. The steps are all done without factoring, except when the top argument is an even number. The Jacobi symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$ is -1. In this case, it gives definite information about the status of quadratic nonresidues. We know for sure that $a$ is a quadratic nonresidue modulo the odd integer $n$, i.e. the equation $x^2 \equiv a \ (\text{mod} \ n)$ has no solutions. $\square$

Example 4
Evaluate $\displaystyle \biggl(\frac{a}{n}\biggr)$ where $n=$ 48746413 and $a=$ 17327467. Both numbers are not prime. As in Example 3, the symbol is evaluated using Jacobi symbol.

\displaystyle \begin{aligned} \biggl(\frac{17327467}{48746413}\biggr) &=\biggl(\frac{48746413}{17327467}\biggr) \\&=\biggl(\frac{14091479}{17327467}\biggr) \\&=-\biggl(\frac{17327467}{14091479}\biggr) \\&=-\biggl(\frac{3236168}{14091479}\biggr) \\&=-\biggl(\frac{2}{14091479}\biggr)^3 \biggl(\frac{404521}{14091479}\biggr) \\&=-\biggl(1\biggr)^3 \biggl(\frac{14091479}{404521}\biggr) \\&=- \biggl(\frac{337765}{404521}\biggr) \\&=- \biggl(\frac{404521}{337765}\biggr) \\&=- \biggl(\frac{66756}{337765}\biggr) \\&=- \biggl(\frac{2}{337765}\biggr)^2 \biggl(\frac{16689}{337765}\biggr) \\&=- \biggl(-1\biggr)^2 \biggl(\frac{337765}{16689}\biggr) \\&=-\biggl(\frac{3985}{16689}\biggr) \\&=-\biggl(\frac{16689}{3985}\biggr) \\&=-\biggl(\frac{749}{3985}\biggr) \\&=-\biggl(\frac{3985}{749}\biggr) \\&=-\biggl(\frac{240}{749}\biggr) \\&=-\biggl(\frac{2}{749}\biggr)^4 \biggl(\frac{15}{749}\biggr) \\&=-\biggl(-1\biggr)^4 \biggl(\frac{749}{15}\biggr) \\&=-\biggl(\frac{14}{15}\biggr) \\&=-\biggl(\frac{-1}{15}\biggr)\\&=-(-1)\\&=1 \end{aligned}

The result of $\displaystyle \biggl(\frac{a}{n}\biggr)=1$ gives ambiguous information about the status of $a=$ 17327467 being a quadratic residue or nonresidue modulo $n=$ 48746413. In this case, the Jacobi symbol cannot tell us whether the equation $x^2 \equiv a \ (\text{mod} \ n)$ has a solution. In such a case, the only way to know the status of quadratic residue is to know some additional information, namely the factoring of the numbers. This example is small enough that $a=$ 3049 x 5683 and $n=$ 7109 x 6857. With this information, the Jacobi symbol can be set up as follows:

\displaystyle \begin{aligned} \biggl(\frac{17327467}{48746413}\biggr) &=\biggl(\frac{17327467}{7109}\biggr) \biggl(\frac{17327467}{6857}\biggr)=(-1) (-1)=1 \end{aligned}

By knowing the factoring of $n$, the original Jacobi symbol is a product of two Legendre symbols. It can be shown that both of these Legendre symbols are -1. These two Legendre symbols corresponds to these two equations: $x^2 \equiv a \ (\text{mod} \ 7109)$ and $x^2 \equiv a \ (\text{mod} \ 6857)$. The Legendre values of -1 indicate that these two equations have no solutions. By the Chinese remainder theorem, the equation $x^2 \equiv a \ (\text{mod} \ 7109 \times 6857)$ has no solutions. Hence $a=$ 17327467 is a quadratic nonresidue modulo $n=$ 48746413=7109 x 6857. $\square$

____________________________________________________________________________

One versatile feature of the Jacobi symbol is that it can be used in evaluating the Legendre symbol, as shown in Example 1 and Example 2. The original Legendre symbol in Example 1 have arguments that are both odd prime and thus can be flipped right away. However, there are numbers in the interim steps that are odd and not prime. With the use of the Jacobi symbol, these interim numbers do have to be factored. The original Legendre symbol in Example 2 has a top argument that is odd and not prime. Treating it as a Jacobi symbol, it can be flipped right away. When numbers involved in Legendre symbol evaluation are large such that the factoring is not obtainable, the Jacobi symbol can be flipped and reduced and flipped again to obtain the answer of the Legendre symbol. The Jacobi symbol plays an outsize role in the evaluation of the Legendre symbol and thus is a pivotal tool in determining whether a number is a quadratic residue modulo an odd prime $p$ or the solvability of the equation $x^2 \equiv a \ (\text{mod} \ p)$.
Example 3 shows that when the Jacobi symbol produces the value of -1, the top argument $a$ is a quadratic nonresidue modulo the lower argument $n$. Example 4 shows that when the Jacobi symbol produces the value of 1, the picture is murky. In such a case, settling the question of whether the top argument $a$ is a quadratic nonresidue modulo the lower argument $n$ requires additional information. Example 4 shows that if we can factor the lower argument $n$, then evaluating the individual Legendre symbols (based on the prime factors) will help answer the original question. This points to the possibility that solving the equation $x^2 \equiv a \ (\text{mod} \ n)$ is not feasible when the factorization of a large composite modulus $n$ is not obtainable.
$\copyright \ 2015 \text{ by Dan Ma}$