Talk:Jacobi symbol

Promote to Task

This task is well defined and has many implementation. Any objection to promoting this draft task to a task?

--DavidFashion (talk) 22:55, 5 February 2020 (UTC)

Lead rewrite

I rewrote the lead to use LaTeX, but Mathoid wasn't working when I tried to preview it, so I'm dumping it here so that I don't lose it. Disregard the errors if it doesn't re-render by the time you see this. -happy5214 06:22, 6 February 2020 (UTC)

---

The Jacobi symbol is a multiplicative function that generalizes the Legendre symbol. Specifically, the Jacobi symbol ${\displaystyle \left({\frac {a}{n}}\right)}$ equals the product of the Legendre symbols ${\displaystyle \left({\frac {a}{p_{i}}}\right)^{k_{i}}}$, where ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{i}^{k_{i}}}$ is the prime factorization of ${\displaystyle n}$ and the Legendre symbol ${\displaystyle \left({\frac {a}{p}}\right)}$ denotes the value of ${\displaystyle a^{(p-1)/2}{\pmod {p}}={\begin{cases}1&{\text{if a is a square}}{\pmod {p}}\\-1&{\text{if a is not a square}}{\pmod {p}}\\0&{\text{if }}a\equiv 0{\pmod {p}}\end{cases}}}$

If n is prime, then the Jacobi symbol ${\displaystyle \left({\frac {a}{n}}\right)}$ equals the Legendre symbol ${\displaystyle \left({\frac {a}{n}}\right)}$.

Task

Calculate the Jacobi symbol ${\displaystyle \left({\frac {a}{n}}\right)}$.