jacobiSymbol

Jacobi symbol (a/n), a generalization of the Legendre symbol.

Category: Mathematics > Number Theory

Syntax

J = jacobiSymbol(a, n)

Description

The Jacobi symbol is the product of Legendre symbols over the prime factors of n. For a prime n it tells whether a is a quadratic residue: 1 if it is, -1 if it is not, 0 if n divides a. For composite n a value of 1 does not guarantee that a is a square modulo n, but -1 does prove it is not.

The symbol follows quadratic reciprocity, which allows a fast computation without factoring. An even n raises an error.

Input arguments

a

Integer scalar or array.

n

Odd positive integer.

Output arguments

J

0 if a and n share a factor; otherwise 1 or -1.

Example

Residues modulo 7 and 15

jacobiSymbol(1:6, 7)
jacobiSymbol(7, 7)
jacobiSymbol(2, 15)

ans = 1×6

     1     1    -1     1    -1    -1
ans = 0
ans = 1

See also

isPrimitiveRoot eulerPhi mod isprime