[Math] The meaning of the Jacobi Symbol and its efficient evaluation

elementary-number-theorymodular arithmeticquadratic-reciprocity

Are the following jacobi symbol evaluations correct?:

  1. $(\frac{35}{53}) = -1$
  2. $(\frac{68}{233}) = -1$
  3. $(\frac{126}{509}) = 1$
  4. $(\frac{672}{1297}) = 1$
  5. $(\frac{1235}{3499}) = -1$

Also what is the meaning of the jacobi symbol? I am confused as to why I would want to compute the jacobi symbol since the legendre symbol $(\frac{n}{m})$ when evaluated tells me whether or not $n$ is a quadratic residue $\mod m$.

Here is a justification for 2:

$(\frac{68}{233}) = (\frac{233}{68})$ since $233 \equiv 1\mod 4$

$=(\frac{29}{68})$ since $29 \equiv 233 \mod 68$

$=(\frac{68}{29})$ since $29 \equiv 1 \mod 4$

$=(\frac{10}{29})$ since $68 \equiv 10 \mod 29$

$=(\frac{2}{29}) \cdot (\frac{5}{29})$ what is the justification here

$=-(\frac{5}{29})$ since $29 \equiv -3 \mod 8$

$=-(\frac{29}{5})$ since $5 \equiv 1 \mod 4$

$=-(\frac{4}{5})$ since $29 \equiv 4 \mod 5$

$=-1$ since $\gcd(2, 5) = 1$

Can I do this in significantly less steps?

Best Answer

Suppose that we want to evaluate the Legendre symbol $(a/p)$. If we are going to use Reciprocity, a first step is to factor $a$.

For huge $a$, factorization seems to be computationally very difficult. By doing a Jacobi symbol calculation, we can, apart from trivial divisions by $2$, bypass factorization. The Jacobi symbol calculation gives us an algorithm that works roughly as fast as the Euclidean Algorithm. This makes the calculation feasible for the kinds of numbers involved in current applications.

Remark: The usual version of the Jacobi symbol $(a/m)$ is for odd $m$ only. So your sample calculation is not what I would do. Indeed, one can do similar-flavoured computations and get the wrong answer.

The first step, since $68=2^2\cdot 17$, is to say that $(68/233)=(17/233)$. This is (invert) $(233/17)$, which is $(12/17)$, which is $(3/17)$, which is $(2/3)$, which is $-1$.

I have done quick calculations of the Jacobi symbols in your list. The answers you give are all correct, or at least the same as mine.

Related Question