Jacobi Symbols

Subjects: Elementary Number Theory
Links: Legendre Symbols, Quadratic Congruences

Let $a$ and $b$ are relatively prime, $b$ is odd and $b = \prod_{i = 1}^{r} p_{i}^{k_{i}}$ , then we define the Jacobi symbol as

(a / b) = \prod_{i = 1}^{r} (a / p_{i})^{k_{i}}

Th: If $a$ is a quadratic residue of $b$ , then $(a / b) = 1$ . But the converse is not true, meaning we have a test for quadratic nonresidue of $b$

Let $b$ and $b^{'}$ be positive odd integers, and $gcd (a a^{'}, b b^{'}) = 1$ , then

$a \equiv a^{'} (\mod b)$ , then $(a / b) = (a^{'} / b)$
$(a a^{'} / b) = (a / b) (a^{'} / b)$
$(a / b b^{'}) = (a / b) (a / b^{'})$
$(a^{2} / b) = (a / b^{2}) = 1$
$(1 / b) = 1$
$(- 1 / b) = (- 1)^{(b - 1) / 2}$
$(2 / b) = (- 1)^{(b^{2} - 1) / 8}$

Generalized Quadratic Reciprocity Law

If $a$ and $b$ are relatively prime positive odd integers, each greater than $1$ , then

(a / b) (b / a) = (- 1)^{\frac{a - 1}{2} \frac{b - 1}{2}}

Quadratic Congruences with Composite Moduli

Th: If $p$ is an odd prime and $gcd (a, p) = 1$ , then the congruence

x^{2} \equiv a (\mod p^{n}) n \geq 1

has a solution iff $(a / p) = 1$

Th: Let $a$ be an odd integer. Then

$x^{2} \equiv a (\mod 2)$ always has solution
$x^{2} \equiv a (\mod 4)$ has a solution iff $a \equiv 1 (\mod 4)$
$x^{2} \equiv a (\mod 2^{n})$ , for $n \geq 3$ , has a solution iff $a \equiv 1 (\mod 8)$

Th: Let $n = 2^{k_{0}} p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}$ be the prime factorization of $n > 1$ and let $gcd (a, n) = 1$ . Then $x^{2} \equiv a (\mod n)$ is solvable iff

$(a / p_{i}) = 1$ for all $i = 1, 2, \dots, r$
$a \equiv 1 (\mod 4)$ , if $4 ∥ n$ ; $a \equiv 1 (\mod 8)$ if $8 ∣ n$