# jacobiSymbol

## 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.

## Version History

Introduced in R2020a