1
$\begingroup$

Does someone know the proof of why the Jacobi symbol is the product of the Legendre symbols of its prime factorization? i.e. why does:

$$\left(\frac{z}{pq}\right) = \left(\frac{z}{p}\right)\left(\frac{z}{q}\right)$$

when p and q are primes (I know there is a more general one, but the one above suffices for my application. Also, leaving the full generalization as an exercise might be fun after I get some ideas how to proceed)?

I tried using the definition of the Legendre symbol:

$\left(\dfrac{z}{p}\right) = z^{\frac{p-1}{2}} \pmod p$

$\left(\dfrac{z}{p}\right) = z^{\frac{q-1}{2}} \pmod q$

$\left(\dfrac{z}{pq}\right) = z^{\frac{pq-1}{2}} \pmod {pq}$

However, I was not sure how to keep going because I realized that the Jacobi symbol is a remainder mod pq and the other two are in mod p and q, which got me stuck. However, I thought of then apply maybe the Chinese remainder theorem but it didn't seem right because the Legendre symbols for p and q were not the same. I also tried multiplying the two legendre symbols to see what I get but it doesn't seem to match at all with $\left(\frac{z}{pq}\right) = z^{\frac{pq-1}{2}} \pmod {pq}$.

Thanks for the help in advance!

$\endgroup$
2
$\begingroup$

The formula $\left(\frac{z}{p}\right) = z^{(p-1)/2}$ only holds for Legendre symbols, where $p$ is an odd prime, and $(z,p)=1$. The definition of the Jacobi symbol is the multiplicative extension of the Legendre symbol, i.e., $$\left(\frac{z}{p_1 p_2 \ldots p_n}\right) = \left(\frac{z}{p_1}\right)\left(\frac{z}{p_2}\right)\ldots\left(\frac{z}{p_n}\right)$$ where $p_i$'s are (not necessarily distinct) odd primes, relatively prime to $z$.

An alternative definition of the Jacobi symbol is that $\left(\frac{a}{n}\right)$ is the sign of the permutation of the multiplication by $a$ map on $(\mathbb{Z}/n\mathbb{Z})^{\times}$.

$\endgroup$
  • $\begingroup$ So is the Jacobi symbol, actually defined differently from the legendre symbol but use the same notation? I.e. is the following just not true: $$(\frac{z}{pq}) \neq z^{\frac{pq-1}{2}} \pmod {pq}$$? $\endgroup$ – Pinocchio Jan 23 '14 at 4:57
  • 1
    $\begingroup$ @Pinocchio That's correct, it's defined differently but uses the same notation. $\endgroup$ – Ted Jan 23 '14 at 4:58
  • $\begingroup$ Oh, no wonder it was confusing. Well, I guess that fixes my question. The proof is that they are equal by definition? $\endgroup$ – Pinocchio Jan 23 '14 at 4:59
  • 1
    $\begingroup$ @Pinocchio Yes. There is also a different definition (see my edit), but most people define use the definition where it's multiplicative. $\endgroup$ – Ted Jan 23 '14 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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