JacobDem

Jacobi Symbol Demonstration

Calculate the Jacobi symbol step by step

Enter $a$:

Enter number $n$:

Use only positive numbers

How the Jacobi Symbol Works

The Jacobi symbol is a generalization of the Legendre symbol and is used in number theory:

1. The Jacobi symbol $(\frac{a}{n})$ is defined for odd positive integers $n$
2. It equals $1$, $-1$, or $0$ depending on the quadratic residue properties
3. The algorithm uses reduction modulo $n$ and the following properties:
4. Multiplicativity: The symbol is multiplicative in both numerator and denominator: $(\frac{ab}{n}) = (\frac{a}{n})(\frac{b}{n})$ and $(\frac{a}{mn}) = (\frac{a}{m})(\frac{a}{n})$
5. Special values: $(\frac{-1}{n}) = (-1)^{\frac{n-1}{2}}$ and $(\frac{2}{n}) = (-1)^{\frac{n^2-1}{8}}$ for odd $n$
6. Quadratic reciprocity: For odd coprime numbers $n$ and $m$: $(\frac{m}{n})(\frac{n}{m}) = (-1)^{\frac{(n-1)(m-1)}{4}}$
7. These properties allow efficient computation through reduction and avoid direct factorization
8. If $\left(\frac{a}{n}\right) = -1$ then $a$ is not a quadratic residue modulo $n$.
9. If $n$ is prime and $\left(\frac{a}{n}\right) = 1$ then $a$ is quadratic residue modulo $n$.