11.7 Jacobi

Jacobi( n, m )

Jacobi returns the value of the Jacobi symbol of the integer n modulo the integer m.

Suppose that m = p_1 p_2 .. p_k as a product of primes, not necessarily distinct. Then for n relatively prime to m the Jacobi symbol is defined by J(n/m) = L(n/p_1) L(n/p_2) .. L(n/p_k), where L(n/p) is the Legendre symbol (see Legendre). By convention J(n/1) = 1. If the gcd of n and m is larger than 1 we define J(n/m) = 0.

If n is an quadratic residue modulo m, i.e., if there exists an r such that r^2 = n mod m then J(n/m) = 1. However J(n/m) = 1 implies the existence of such an r only if m is a prime.

Jacobi is very efficient, even for large values of n and m, it is about as fast as the Euclidean algorithm (see Gcd).

    gap> Jacobi( 11, 35 );
    1         # $9^2 = 11$ mod $35$
    gap> Jacobi( 6, 35 );
    -1        # thus there is no $r$ such that $r^2 = 6$ mod $35$
    gap> Jacobi( 3, 35 );
    1         # even though there is no $r$ with $r^2 = 3$ mod $35$ 

Previous Up Top Next
Index