﻿ JacobiSymbol – Algosim documentation
Algosim documentation: JacobiSymbol

# JacobiSymbol

The Jacobi symbol.

## Syntax

• `JacobiSymbol(a, n)`

• `a` is an integer

• `n` is 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`