Math 2.0

Number theory Definition

Jacobi symbol

Builds on Legendre symbolPrime factorization

Definition

Let nn be a positive odd integer with prime factorization n=p1e1⋯pkekn = p_1^{e_1} \cdots p_k^{e_k}, and let aa be an integer. The Jacobi symbol is (an)=(ap1)e1⋯(apk)ek,\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{e_1} \cdots \left(\frac{a}{p_k}\right)^{e_k}, where each factor on the right is a Legendre symbol. For n=1n = 1, the empty product gives (a1)=1\left(\frac{a}{1}\right) = 1.

Remarks

For a prime nn, the Jacobi symbol equals the Legendre symbol. If (an)=−1\left(\frac{a}{n}\right) = -1, then aa is not a quadratic residue modulo nn. The converse fails: (215)=(23)(25)=1\left(\frac{2}{15}\right) = \left(\frac{2}{3}\right) \left(\frac{2}{5}\right) = 1, but 22 is not a square modulo 1515. The symbol is 00 exactly when gcd⁡(a,n)>1\gcd(a, n) > 1.

Reading path

To understand this page from the ground up, read these 7 pages in order. The foundations come first.

Show the path as a graph
Divisibility, definition, no evidence levelDivisibilitydefinitionCongruence modulo n, definition, no evidence levelCongruence modulo ndefinitionPrime number, definition, no evidence levelPrime numberdefinitionQuadratic residue, definition, no evidence levelQuadratic residuedefinitionPrime factorization, definition, no evidence levelPrime factorizationdefinitionLegendre symbol, definition, no evidence levelLegendre symboldefinitionJacobi symbol, definition, no evidence levelJacobi symboldefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Divisibility definition
  2. Congruence modulo n definition
  3. Prime number definition
  4. Quadratic residue definition
  5. Prime factorization definition
  6. Legendre symbol definition
  7. Jacobi symbol definition

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Jacobi_symbol, Definition
About this page
Tag0XDB5AW7M1
URIm2://0XDB5AW7M1
Kinddefinition
WritingW1 stated
MSC11A15
DefinesJacobi symbol
UsesLegendre symbol, Prime factorization

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge instance_of in: one example (0 of 1)
  • edge not_instance_of in: one non-example that fails one clause (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by