JacobiSymbol
The Jacobi symbol.
Syntax
-
JacobiSymbol(a, n)-
ais an integer -
nis a positive odd integer
-
Description
The Jacobi symbol is an extension of the Legendre symbol to all positive odd integers n.
If a is an integer and n a positive odd integer with prime factorisation
n = p1^α1 ⋅ p2^α2 ⋅ ⋯ ⋅ pk^αk
where p1, p2, ..., pk are distinct primes and α1, α2, ... αk positive integers, then
JacobiSymbol(a, n) = ∏(LegendreSymbol(a, pi)^αi, i, 1, k).
Examples
matrix(compute(JacobiSymbol(a, 2⋅n + 1), n, 0, 19, a, 1, 20))
⎛ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1⎞ ⎜ 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1⎟ ⎜ 1 −1 −1 1 0 1 −1 −1 1 0 1 −1 −1 1 0 1 −1 −1 1 0⎟ ⎜ 1 1 −1 1 −1 −1 0 1 1 −1 1 −1 −1 0 1 1 −1 1 −1 −1⎟ ⎜ 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1⎟ ⎜ 1 −1 1 1 1 −1 −1 −1 1 −1 0 1 −1 1 1 1 −1 −1 −1 1⎟ ⎜ 1 −1 1 1 −1 −1 −1 −1 1 1 −1 1 0 1 −1 1 1 −1 −1 −1⎟ ⎜ 1 1 0 1 0 0 −1 1 0 0 −1 0 −1 −1 0 1 1 0 1 0⎟ ⎜ 1 1 −1 1 −1 −1 −1 1 1 −1 −1 −1 1 −1 1 1 0 1 1 −1⎟ ⎜ 1 −1 −1 1 1 1 1 −1 1 −1 1 −1 −1 −1 −1 1 1 −1 0 1⎟ ⎜ 1 −1 0 1 1 0 0 −1 0 −1 −1 0 −1 0 0 1 1 0 −1 1⎟ ⎜ 1 1 1 1 −1 1 −1 1 1 −1 −1 1 1 −1 −1 1 −1 1 −1 −1⎟ ⎜ 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0⎟ ⎜ 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1 0 1 −1⎟ ⎜ 1 −1 −1 1 1 1 1 −1 1 −1 −1 −1 1 −1 −1 1 −1 −1 −1 1⎟ ⎜ 1 1 −1 1 1 −1 1 1 1 1 −1 −1 −1 1 −1 1 −1 1 1 1⎟ ⎜ 1 1 0 1 −1 0 −1 1 0 −1 0 0 −1 −1 0 1 1 0 −1 −1⎟ ⎜ 1 −1 1 1 0 −1 0 −1 1 0 1 1 1 0 0 1 1 −1 −1 0⎟ ⎜ 1 −1 1 1 −1 −1 1 −1 1 1 1 1 −1 −1 −1 1 −1 −1 −1 −1⎟ ⎝ 1 1 0 1 1 0 −1 1 0 1 1 0 0 −1 0 1 −1 0 −1 1⎠
∑(ans)
67