# galois.jacobi_symbol¶

galois.jacobi_symbol(a, n)

Computes the Jacobi symbol $$(\frac{a}{n})$$.

Parameters
• a (int) – An integer.

• n (int) – An odd integer $$n \ge 3$$.

Returns

The Jacobi symbol $$(\frac{a}{n})$$ with value in $$\{0, 1, -1\}$$.

Return type

int

Notes

The Jacobi symbol extends the Legendre symbol for odd $$n \ge 3$$. Unlike the Legendre symbol, $$(\frac{a}{n}) = 1$$ does not imply $$a$$ is a quadratic residue modulo $$n$$. However, all $$a \in Q_n$$ have $$(\frac{a}{n}) = 1$$.

References

Examples

The quadratic residues modulo $$9$$ are $$Q_9 = \{1, 4, 7\}$$ and these all satisfy $$(\frac{a}{9}) = 1$$. The quadratic non-residues modulo $$9$$ are $$\overline{Q}_9 = \{2, 3, 5, 6, 8\}$$, but notice $$\{2, 5, 8\}$$ also satisfy $$(\frac{a}{9}) = 1$$. The set of integers $$\{3, 6\}$$ not coprime to $$9$$ satisfies $$(\frac{a}{9}) = 0$$.

In [1]: [pow(x, 2, 9) for x in range(9)]
Out[1]: [0, 1, 4, 0, 7, 7, 0, 4, 1]

In [2]: for a in range(9):
...:     print(f"({a} / 9) = {galois.jacobi_symbol(a, 9)}")
...:
(0 / 9) = 0
(1 / 9) = 1
(2 / 9) = 1
(3 / 9) = 0
(4 / 9) = 1
(5 / 9) = 1
(6 / 9) = 0
(7 / 9) = 1
(8 / 9) = 1