Are the following jacobi symbol evaluations correct?:
- $(\frac{35}{53}) = -1$
- $(\frac{68}{233}) = -1$
- $(\frac{126}{509}) = 1$
- $(\frac{672}{1297}) = 1$
- $(\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?