Skip to main content

Jacobi

Returns the Jacobi symbol. The Jacobi symbol is a generalization of the Legendre symbol. For any integer aa and any positive odd integer nn, the Jacobi symbol an is defined as the product of the Legendre symbols corresponding to the prime factors of nn:

an=ap1α1ap2α2apkαk

where n=p1α1p2α2pkαk is the prime factorization of nn.

The Legendre symbol ap is defined for all integers aa and all odd primes p by

ap=-1ifa0(modp)andthereisnointegerx:ax2(modp),0ifa0(modp),1ifa0(modp)andforsomeintegerx:ax2(modp).

Syntax

jacobi(Integer, Integer)

Description

Given two integers aa and nn, returns the Jacobi symbol ap.

arithmetic.jacobi.calc.png