Jacobi

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

an=ap1α1ap2α2apkαk

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

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

ap={leftleft-1  if  a0 (mod p) and there is no integer x: ax2italic (mod p),  0   if  a0 (mod p),  1   if  a0 (mod p) and for some integer x: ax2 (mod p).

Syntax

jacobi(Integer, Integer)

Description

Given two integers aLaTeXa and nLaTeXn, returns the Jacobi symbol ap.

arithmetic.jacobi.calc.png