Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
The Legendre symbol is only defined when $m$ is prime. –  Gerry Myerson Oct 25 '12 at 5:37

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
What is the formal rule for factoring out powers of 2? I recalculated the jacobi symbols for 1-5 and got different answers. –  CodeKingPlusPlus Oct 25 '12 at 5:52
    
Even powers of $2$ disappear. So the only issue is $(2/m)$. This is $1$ if $m\equiv \pm 1\pmod{8}$, and $-1$ if $m\equiv \pm 3\pmod{8}$. Exactly like Legendre symbol calculation. –  André Nicolas Oct 25 '12 at 6:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.