7.1.26  Jacobi symbol

The Jacobi symbol is a generalization of the Legendre symbol (a/n) when n is not prime. Let

be the prime factorization of n. The Jacobi symbol of a is defined by:

Where the left hand side is the Jacobi symbol and the right hand side contains Legendre symbols. The jacobi_symbol command computes the Jacobi symbol.

• jacobi_symbol takes two arguments: a and n, integers.
• jacobi_symbol(a,n) returns the Jacobi symbol (a/n).

Examples