# jacobiSymbol

## Syntax

``J = jacobiSymbol(a,n)``

## Description

example

````J = jacobiSymbol(a,n)` returns the value of the Jacobi symbol for integer `a` and positive odd integer `n`.```

## Examples

collapse all

Find the Jacobi symbol for $a=1,2,\dots ,9$ and $n=3$.

```a = 1:9; n = 3; J = jacobiSymbol(a,n)```
```J = 1×9 1 -1 0 1 -1 0 1 -1 0 ```

The Jacobi symbol is periodic with respect to its first argument, where $\left(\frac{a}{n}\right)=\left(\frac{b}{n}\right)$ if $a\equiv b\phantom{\rule{0.2222222222222222em}{0ex}}\left(mod\phantom{\rule{0.2222222222222222em}{0ex}}n\right)$.

Find the Jacobi symbol for $a=28$ and $n=9$.

`J = jacobiSymbol(28,9)`
```J = 1 ```

The Jacobi symbol is a completely multiplicative function, where the Jacobi symbol satisfies the relation $\left(\frac{a}{n}\right)=\left(\frac{{a}_{1}}{n}\right)×\left(\frac{{a}_{2}}{n}\right)×\dots \left(\frac{{a}_{r}}{n}\right)$ for $a={a}_{1}×{a}_{2}×\dots {a}_{r}$. Show that the Jacobi symbol follows this relation for $a=28=2×2×7$.

`Ja = jacobiSymbol(2,9)*jacobiSymbol(2,9)*jacobiSymbol(7,9)`
```Ja = 1 ```

The Jacobi symbol also satisfies the relation $\left(\frac{a}{n}\right)=\left(\frac{a}{{n}_{1}}\right)×\left(\frac{a}{{n}_{2}}\right)×\dots \left(\frac{a}{{n}_{r}}\right)$ for $n={n}_{1}×{n}_{2}×\dots {n}_{r}$. Show that the Jacobi symbol follows this relation for $n=9=3×3$.

`Jb = jacobiSymbol(28,3)*jacobiSymbol(28,3)`
```Jb = 1 ```

You can use the Jacobi symbol $\left(\frac{a}{n}\right)$ for the Solovay–Strassen primality test. If an odd integer $n>1$ is prime, then the congruence

`$\left(\frac{a}{n}\right)\equiv {a}^{\left(n-1\right)/2}\phantom{\rule{0.2777777777777778em}{0ex}}\left(mod\phantom{\rule{0.2777777777777778em}{0ex}}n\right)$`

must hold for all integers $a$. If there is an integer $a$ in $\left\{1,2,\dots ,n-1\right\}$ such that the congruence relation is not satisfied, then $n$ is not prime.

Check if $n=561$ is prime or not. Choose $a=19$ and perform the primality test. Compare the two values in the congruence relation.

First calculate the left side of the congruence relation using the Jacobi symbol.

```n = 561; a = 14; J = jacobiSymbol(a,n)```
```J = 1 ```

Calculate the right side of the congruence relation.

`m = powermod(a,(n-1)/2,n)`
```m = 67 ```

The integer $n=561$ is not prime since it does not satisfy the congruence relation for $a=19$.

`checkPrime = mod(J,n) == m`
```checkPrime = logical 0 ```

Next, check if $n=557$ is prime or not. Choose $a=19$ and perform the primality test.

```n = 557; a = 19; J = jacobiSymbol(a,n); m = powermod(a,(n-1)/2,n);```

The integer $n=557$ is probably prime since it satisfies the congruence relation for $a=19$.

`checkPrime = mod(J,n) == m`
```checkPrime = logical 1 ```

Perform the primality test for all $a$ in $\left\{1,2,\dots ,556\right\}$ to confirm that the integer $n=557$ is indeed prime.

```a = 1:n-1; J = jacobiSymbol(a,n); m = powermod(a,(n-1)/2,n); checkPrime = all(mod(J,n) == m)```
```checkPrime = logical 1 ```

Verify the result with `isprime`.

`isprime(n)`
```ans = logical 1 ```

## Input Arguments

collapse all

Input, specified as a number, vector, matrix, array, symbolic number, or symbolic array. The elements of `a` must be integers. `a` and `n` must be the same size, or else one of them must be a scalar.

Data Types: `single` | `double` | `sym`

Input, specified as a number, vector, matrix, array, symbolic number, or symbolic array. The elements of `n` must be positive odd integers. `a` and `n` must be the same size, or else one of them must be a scalar.

Data Types: `single` | `double` | `sym`

## Output Arguments

collapse all

Output value, returned as `–1`, `0`, or `1`.

Data Types: `single` | `double` | `sym`

collapse all

### Jacobi Symbol

The Jacobi symbol $\left(\frac{a}{n}\right)$ is defined as the product of the Legendre symbols

`$\left(\frac{a}{n}\right)={\left(\frac{a}{{p}_{1}}\right)}^{{k}_{1}}{\left(\frac{a}{{p}_{2}}\right)}^{{k}_{2}}\dots {\left(\frac{a}{{p}_{r}}\right)}^{{k}_{r}}$`

for an integer a and a positive odd integer n with prime factorization

`$n={p}_{1}^{{k}_{1}}{p}_{2}^{{k}_{2}}\dots {p}_{r}^{{k}_{r}}.$`

The Legendre symbol $\left(\frac{a}{p}\right)$ for an integer a and an odd prime p is defined as

When n is an odd prime, the Jacobi symbol is equal to the Legendre symbol.

## References

[1] Dietzfelbinger, M. Primality Testing in Polynomial Time: From Randomized Algorithms to "PRIMES Is in P". Springer, 2004.