Jacobi Symbol

Let \( n \) be a positive odd composite integer with the prime factorization \[n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}\] where \( p_1, p_2, \ldots, p_k \) are distinct prime numbers and \( e_1, e_2, \ldots, e_k \) are their respective exponents. The Jacobi symbol \(\left(\frac{a}{n}\right)\) is defined as: \[ \left(\frac{a}{n}\right) = \prod_{i=1}^k \left(\frac{a}{p_i}\right)^{e_i}\] where \(\left(\frac{a}{p_i}\right)\) is the Legendre symbol for each prime factor \( p_i \) of \( n \).

The Jacobi symbol generalizes the Legendre symbol.

While the Legendre symbol is only defined when \( n \) is prime, the Jacobi symbol extends this concept to composite values of \( n \).

What is it used for?

The Jacobi symbol helps determine whether an integer \( a \) is a quadratic residue modulo \( n \) when \( n \) is composite.

Note.  The Jacobi symbol plays a key role in primality testing and cryptography, particularly in the Solovay-Strassen primality test, which assesses whether a number is likely prime. It is also used to identify Euler pseudoprimes.

However, it's important to note that the Jacobi symbol \(\left(\frac{a}{n}\right)\) does not necessarily indicate whether \( a \) is a quadratic residue modulo \( n \).

• If \( \left(\frac{a}{n}\right) = -1 \), then \( a \) is definitely not a quadratic residue modulo \( n \).
• If \( \left(\frac{a}{n}\right) = 1 \), no definitive conclusion can be drawn—\( a \) might be a quadratic residue modulo \( n \), but it could also be a non-residue.
  

  Note. To determine this, we need to check whether the congruence \( x^2 \equiv a \pmod{n} \) holds for some integer \( x \) between 0 and \( n-1 \). A more efficient approach is to examine the Legendre symbols of the prime factors. If at least one of them is -1, we can immediately conclude that \( a \) is not a quadratic residue.

In contrast, the Legendre symbol provides a definitive answer about \( a \), but only when \( n \) is prime.

A Practical Example

Let's compute \(\left(\frac{2}{15}\right)\), where \( n = 15 = 3 \cdot 5\).

We calculate the Legendre symbol for each prime factor and then multiply them together:

\[ \left(\frac{2}{15}\right) = \left(\frac{2}{3}\right) \cdot \left(\frac{2}{5}\right) \]

Next, we evaluate each Legendre symbol and replace it with 1, -1, or 0, depending on whether the numerator is a quadratic residue modulo the denominator.

Step 1: First Factor

For \(\left(\frac{2}{3}\right)\), the number \( 2 \) is not a quadratic residue modulo 3, since no integer \( x \) satisfies \( x^2 \equiv 2 \pmod{3} \).

The quadratic residues modulo 3 are simply the squares of \( x \in \{0,1,2\} \), reduced modulo 3:

• \(0^2 = 0 \equiv 0 \pmod{3}\)
• \(1^2 = 1 \equiv 1 \pmod{3}\)
• \(2^2 = 4 \equiv 1 \pmod{3}\)

Since 2 is not on this list, it is not a quadratic residue modulo 3.

Thus, \(\left(\frac{2}{3}\right) = -1\).

\[ \left(\frac{2}{15}\right) = -1 \cdot \left(\frac{2}{5}\right) \]

Note. At this point, we already know that 2 is not a quadratic residue modulo 15. If 2 is not a quadratic residue modulo one of the prime factors (in this case, modulo 3), then it cannot be a quadratic residue modulo 15 either. However, for completeness, let's go through the full calculation.

Step 2: Second Factor

For \(\left(\frac{2}{5}\right)\), the number \( 2 \) is not a quadratic residue modulo 5, because no integer \( x \) satisfies \( x^2 \equiv 2 \pmod{5} \).

The quadratic residues modulo 5 are the squares of \( x \in \{0,1,2,3,4\} \), reduced modulo 5:

• \(0^2 = 0 \equiv 0 \pmod{5}\)
• \(1^2 = 1 \equiv 1 \pmod{5}\)
• \(2^2 = 4 \equiv 4 \pmod{5}\)
• \(3^2 = 9 \equiv 4 \pmod{5}\)
• \(4^2 = 16 \equiv 1 \pmod{5}\)

Since 2 does not appear in this list, it is not a quadratic residue modulo 5.

Therefore, \(\left(\frac{2}{5}\right) = -1\).

Now, we substitute our results into the Jacobi symbol calculation:

\[ \left(\frac{2}{15}\right) = \left(\frac{2}{3}\right) \cdot \left(\frac{2}{5}\right) \]

\[ \left(\frac{2}{15}\right) = (-1) \cdot (-1) = 1 \]

\[ \left(\frac{2}{15}\right) = 1 \]

This means that the Jacobi symbol \(\left(\frac{2}{15}\right)\) evaluates to \( 1 \).

How should we interpret this result?

The fact that the Jacobi symbol equals \( 1 \) does not necessarily mean that \( 2 \) is a quadratic residue modulo 15.

However, analyzing the individual Legendre symbols allows us to reach a definitive conclusion:

\[ \left(\frac{2}{15}\right) = \left(\frac{2}{3}\right) \cdot \left(\frac{2}{5}\right) = (-1) \cdot (-1) = 1 \]

Since at least one of these values is \( -1 \) (specifically, \( \left(\frac{2}{3}\right) = -1 \)), we can conclude that 2 is not a quadratic residue modulo 15.

Explanation. If a number is not a quadratic residue modulo at least one of the prime factors of 15, then it cannot be a quadratic residue modulo 15, regardless of the final value of the Jacobi symbol.

Verification

To verify our result, we compute all the perfect squares from 0 to 14 modulo 15 and check if \( a = 2 \) appears among them.

• \(0^2 = 0 \equiv 0 \pmod{15}\)
• \(1^2 = 1 \equiv 1 \pmod{15}\)
• \(2^2 = 4 \equiv 4 \pmod{15}\)
• \(3^2 = 9 \equiv 9 \pmod{15}\)
• \(4^2 = 16 \equiv 1 \pmod{15}\)
• \(5^2 = 25 \equiv 10 \pmod{15}\)
• \(6^2 = 36 \equiv 6 \pmod{15}\)
• \(7^2 = 49 \equiv 4 \pmod{15}\)
• \(8^2 = 64 \equiv 4 \pmod{15}\)
• \(9^2 = 81 \equiv 6 \pmod{15}\)
• \(10^2 = 100 \equiv 10 \pmod{15}\)
• \(11^2 = 121 \equiv 1 \pmod{15}\)
• \(12^2 = 144 \equiv 9 \pmod{15}\)
• \(13^2 = 169 \equiv 4 \pmod{15}\)
• \(14^2 = 196 \equiv 1 \pmod{15}\)

Since none of these squares are congruent to \( 2 \pmod{15} \), the equation \( x^2 \equiv 2 \pmod{15} \) has no solutions.

Thus, our verification confirms that 2 is not a quadratic residue modulo 15.

General Case and Key Properties

The Jacobi symbol \( \left( \frac{a}{n} \right) \) is defined only when the denominator \( n \) is a positive odd integer. However, the numerator \( a \) can be any integer.

There are two main cases to consider:

• If \( a \) is even, a special rule applies for \( \left( \frac{2}{n} \right) \).
• If \( a \) is odd, we can apply the quadratic reciprocity law directly.

In the specific case where \( a=2 \), the following formula holds: \[ \left( \frac{2}{n} \right) = (-1)^{\frac{n^2 - 1}{8}} \]

1] Case where \( a \) is even

If \( a \) is even, it can be factored as \( a = 2^k \cdot m \), where \( m \) is odd.

\[ \left( \frac{a}{n} \right) = \left( \frac{2^k \cdot m}{n} \right) = \left( \frac{2^k}{n} \right) \cdot \left( \frac{m}{n} \right) \]

The Jacobi symbol for \( 2^k \) can be determined using the special rule for \( a=2 \), applying it repeatedly if \( k > 1 \).

\[ \left( \frac{2}{n} \right) = (-1)^{\frac{n^2 - 1}{8}} \]

The remaining Jacobi symbol involves two odd numbers, which can be evaluated using standard methods, such as the reciprocity law.

Example

Let's compute:

\[ \left( \frac{22}{91} \right) \]

Since \( a \) is even, we can rewrite the Jacobi symbol as:

\[ \left( \frac{22}{91} \right) = \left( \frac{2 \cdot 11}{91} \right) = \left( \frac{2}{91} \right) \cdot \left( \frac{11}{91} \right) \]

This breaks the calculation into simpler parts. First, we evaluate \( \left( \frac{2}{91} \right) \) using the special formula for \( a=2 \):

\[ \left( \frac{2}{91} \right) = (-1)^{\frac{91^2 - 1}{8}} = (-1)^{1035} = -1 \]

Substituting \( \left( \frac{2}{91} \right) = -1 \), we get:

\[ \left( \frac{22}{91} \right) = -1 \cdot \left( \frac{11}{91} \right) \]

To compute \( \left( \frac{11}{91} \right) \), we apply the quadratic reciprocity law:

\[ \left( \frac{11}{91} \right) = (-1)^{\frac{(11-1)(91-1)}{4}} \left( \frac{91}{11} \right) \]

\[ = (-1)^{225} \left( \frac{91}{11} \right) \]

\[ = - \left( \frac{91}{11} \right) \]

Since \( 91 \equiv 3 \pmod{11} \), we substitute:

\[ \left( \frac{11}{91} \right) = - \left( \frac{3}{11} \right) \]

Using Euler’s criterion:

\[ \left(\frac{3}{11}\right) \equiv 3^5 \pmod{11} \]

\[ \equiv 1 \pmod{11} \]

Since \( \left( \frac{3}{11} \right) = 1 \), we conclude:

\[ \left( \frac{11}{91} \right) = -1 \]

Substituting back into our original equation:

\[ \left( \frac{22}{91} \right) = (-1) \cdot (-1) = 1 \]

Thus, the final result is:

\[ \left( \frac{22}{91} \right) = 1 \]

2] Case where \( a \) is odd: Quadratic Reciprocity

When \( a \) is odd, we can use the quadratic reciprocity law:

\[ \left( \frac{a}{n} \right) = (-1)^{\frac{(a-1)(n-1)}{4}} \left( \frac{n}{a} \right) \]

This allows us to swap the numerator and denominator, often simplifying the computation.

Example

Let's compute:

\[ \left( \frac{3}{11} \right) \]

Applying the reciprocity law:

\[ \left( \frac{3}{11} \right) = (-1)^{\frac{(3-1)(11-1)}{4}} \left( \frac{11}{3} \right) \]

\[ = (-1)^5 \left( \frac{11}{3} \right) \]

Since 5 is odd, the sign flips:

\[ \left( \frac{3}{11} \right) = - \left( \frac{11}{3} \right) \]

Since \( 11 \equiv 2 \mod 3 \), we substitute:

\[ \left( \frac{3}{11} \right) = - \left( \frac{2}{3} \right) \]

Using the rule for \( \left( \frac{2}{3} \right) \):

\[ \left( \frac{2}{3} \right) = (-1)^1 = -1 \]

Thus:

\[ \left( \frac{3}{11} \right) = -(-1) = 1 \]

So, the final result is:

\[ \left( \frac{3}{11} \right) = 1 \]

Additional Properties

The Jacobi symbol shares several key properties with the Legendre symbol but also has some important differences:

• Multiplicative Properties
  The Jacobi symbol satisfies the following key multiplicative rules:
  • Multiplicativity in the numerator (always holds):
    \[ \left(\frac{a_1 \cdot a_2}{n}\right) = \left(\frac{a_1}{n}\right) \cdot \left(\frac{a_2}{n}\right) \] for any integers \( a_1, a_2 \), as long as \( n \) is a positive odd integer.
  • Multiplicativity in the denominator (valid only when \( n \) is factored into primes):
    If \( n \) has a prime factorization given by \( n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \), then: \[ \left(\frac{a}{n}\right) = \left(\frac{a}{p_1^{e_1}}\right) \cdot \left(\frac{a}{p_2^{e_2}}\right) \cdots \left(\frac{a}{p_k^{e_k}}\right). \] Moreover, for any prime \( p \), we have: \[ \left(\frac{a}{p^e}\right) = \left(\frac{a}{p}\right)^e. \]
• Quadratic Reciprocity
  If \( a \) and \( n \) are both odd, then:
  \[ \left(\frac{a}{n}\right) = (-1)^{\frac{(a-1)(n-1)}{4}} \cdot \left(\frac{n}{a}\right) \]
• Notable Values of the Jacobi Symbol
  The Jacobi symbol can take on the values \(-1\), \(0\), or \(1\): $$ \left(\frac{a}{n}\right) = 0 \quad \text{if} \quad \gcd(a, n) \neq 1 $$ $$ \left( \frac{a}{2} \right) = \begin{cases} 0 \quad \text{if } a \text{ is even} \\ \\ 1 \quad \text{if } a \text{ is odd} \end{cases} $$ $$ \left( \frac{a}{1} \right) = 1  $$
• Does Not Imply the Existence of a Quadratic Solution
  Unlike the Legendre symbol, the fact that \(\left(\frac{a}{n}\right) = 1\) does not guarantee that there exists an integer \( x \) such that \( x^2 \equiv a \pmod{n} \) when \( n \) is composite.

And so on.