NationMaster - Encyclopedia: Jacobi symbol

The Jacobi symbol generalises the Legendre symbol. It is used by mathematicians in the area of number theory and is named after the German mathematician Carl Gustav Jakob Jacobi. The Legendre symbol is a number theory concept. ... Leonhard Euler is considered by many to be one of the greatest mathematicians of all time A mathematician is the person whose primary area of study and research is the field of mathematics. ... Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study. ... Karl Gustav Jacob Jacobi Carl Gustav Jacob Jacobi (December 10, 1804 - February 18, 1851), was not only a great German mathematician but also considered by many as the most inspiring teacher of his time (Bell, p. ...

1 Definition
2 Properties of the Jacobi symbol
3 Residue
4 External links

Definition

The Jacobi symbol $left(frac{a}{n}right)$ uses the prime factorization of the bottom number. It is defined as follows: In mathematics, the integer prime-factorization (also known as prime decomposition) problem is this: given a positive integer, write it as a product of prime numbers. ...

Let n > 0 be odd and let $p_1^{alpha_1}p_2^{alpha_2}cdots p_k^{alpha_k}$ be the prime factorization of n.

For any integer a, the Jacobi symbol $left(frac{a}{n}right) = left(frac{a}{p_1}right)^{alpha_1}left(frac{a}{p_2}right)^{alpha_2}cdots left(frac{a}{p_k}right)^{alpha_k}$ where the symbols on the right are all Legendre symbols (given that the bottom numbers $p i$ are all prime). The Legendre symbol is a number theory concept. ... In mathematics, a prime number, or prime for short, is a natural number greater than one and whose only distinct positive divisors are 1 and itself. ...

Properties of the Jacobi symbol

There are a number of useful properties of the Jacobi symbol which can be used to speed up calculations. They include:

If n is prime, the Jacobi symbol is the Legendre symbol.
$left(frac{a}{n}right)in {0,1,-1}$
$left(frac{a}{n}right) = 0$ if $gcd (a,n) neq 1$
$left(frac{ab}{n}right) = Bigg(frac{a}{n}Bigg)left(frac{b}{n}right)$
$left(frac{a}{mn}right)=left(frac{a}{m}right)left(frac{a}{n}right)$ Note that this means that $left(frac{a}{n^2}right)$ is 0 or 1 for any a and any n.
If a ≡ b (mod n), then $Bigg(frac{a}{n}Bigg) = left(frac{b}{n}right)$
$left(frac{1}{n}right) = 1$
$left(frac{-1}{n}right) = (-1)^{(n-1)/2} = left{begin{array}{cl} 1 & textrm{if};n equiv 1 mod 4 -1 &textrm{if};n equiv 3 mod 4end{array}right.$
${left(frac{2}{n}right) = (-1)^{(n^2-1)/8} = left{begin{array}{cl} 1 & textrm{if};n equiv 1;textrm{ or };7 mod 8 -1 &textrm{if};n equiv 3;textrm{ or };5mod 8end{array}right.}$
$left(frac{m}{n}right) = left(frac{n}{m}right)(-1)^{(m-1)(n-1)/4}$ if m and n are odd integers.

The last property is known as reciprocity, similar to the law of quadratic reciprocity for Legendre symbols. In number theory, the law of quadratic reciprocity connects the solvability of two related quadratic equations in modular arithmetic. ...

Residue

There are two statements about quadratic residues with respect to the Legendre symbol which cannot be made with the Jacobi symbol.

First, if $left(frac{a}{n}right) = -1$ then a is not a quadratic residue of n because a was not a quadratic residue of some p_k that divides n. However, in the case where $left(frac{a}{n}right) = 1$ we are unable to say that a is a quadratic residue of n. Since the Jacobi symbol is a product of Legendre symbols, there are cases where two Legendre symbols evaluate to −1 and the Jacobi symbol evaluates to 1.

There is a second noticeable missing property from the list above, namely an analogue of Euler's congruence $left(frac{a}{n}right) equiv a^{(n-1)/2}$ mod n. In fact, that congruence is false at least half the time for Jacobi symbols with a composite denominator, and this is the basis for the Solovay-Strassen probabilistic primality test. The Solovay-Strassen primality test is a probabilistic test to determine if a number is composite or probably prime. ...

External links

Calculate Jacobi symbol

Category: Modular arithmetic

Results from FactBites:

PlanetMath: Jacobi symbol (89 words)
	The Jacobi symbol is a generalization of the Legendre symbol to all odd positive integers.
	A further generalization of the Legendre symbol, due to Kronecker, is the Kronecker symbol.
	This is version 6 of Jacobi symbol, born on 2002-04-22, modified 2004-08-24.

PlanetMath: Legendre symbol (100 words)
	The Legendre symbol can be computed by means of Euler's criterion or Gauss' lemma.
	A generalization of this symbol is the Jacobi Symbol.
	This is version 7 of Legendre symbol, born on 2001-10-08, modified 2006-11-01.

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.

Contents

Definition GA_googleFillSlot("encyclopedia_square");

Properties of the Jacobi symbol

Residue

External links

Definition