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 $\left({\frac {a}{n}}\right)$ equals the product of the Legendre symbols $\left({\frac {a}{p_{i}}}\right)^{k_{i}}$, where $n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{i}^{k_{i}}$ is the prime factorization of $n$ and the Legendre symbol $\left({\frac {a}{p}}\right)$ denotes the value of $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 $\left({\frac {a}{n}}\right)$ equals the Legendre symbol $\left({\frac {a}{n}}\right)$.

Task

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