jacobiSymbol

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(modn)$$.

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)\times \left(\frac{a_2}{n}\right)\times \dots \left(\frac{a_r}{n}\right)$$ for $$a=a_1\times a_2\times \dots a_r$$. Show that the Jacobi symbol follows this relation for $$a=28=2\times 2\times 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)\times \left(\frac{a}{n_2}\right)\times \dots \left(\frac{a}{n_r}\right)$$ for $$n=n_1\times n_2\times \dots n_r$$. Show that the Jacobi symbol follows this relation for $$n=9=3\times 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

must hold for all integers $$a$$. If there is an integer $$a$$ in $$\{1,2,\dots ,n-1\}$$ 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 $$\{1,2,\dots ,556\}$$ 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