For an odd positive integer , the Jacobi symbol is the product of Legendre symbols
The fundamental theorem of arithmetic makes this definition unambiguous. Its value is zero exactly when and have a common prime factor; otherwise it is or . For , the empty product convention gives .
If is a quadratic residue modulo and is coprime to , its Jacobi symbol is one. The converse can fail for a composite number: , but two is not a square modulo fifteen because it is not a square modulo three.
Computing the Jacobi symbol does not require first finding the prime factorization. Repeatedly remove factors of two, swap odd numerator and denominator using Jacobi reciprocity, and reduce the numerator modulo the denominator, as in the Euclidean algorithm. This makes it useful in the Solovay-Strassen primality test.
For coprime positive odd integers , the Jacobi symbol satisfies . It follows by factoring and into primes and multiplying the quadratic reciprocity for each prime pair; the parity of the sums of prime half-differences agrees with and . A Jacobi symbol equal to one does not imply that its numerator is a quadratic residue for a composite denominator.
For an odd positive nonsquare integer , there are infinitely many primes with Legendre symbol . Choose a residue modulo with Jacobi symbol by making it a quadratic nonresidue at one prime occurring to odd multiplicity and a square at every other prime. The Chinese remainder theorem also imposes and at any finite list of previously found primes. Then Jacobi reciprocity gives , so a prime factor of has and is outside that list.
For odd positive , the Jacobi symbol is multiplicative in its numerator:
It is also multiplicative in an odd denominator: .

Ancestors (4)

  1. Number theory
  2. Area of mathematics
  3. Mathematics
  4. Home

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (1)