PropositionStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-17

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The Jacobi symbol is well defined on numerator residue classes

Statement

For every integer $a$ and odd positive integer $n$ , the product in The Jacobi symbol, with its zero value and empty-product convention is independent of the ordering used to list the canonical prime factors and belongs to ${- 1, 0, 1}$ . The Jacobi symbol depends only on $a (m o d n)$ , and it is zero exactly when $\gcd (a, n) > 1$ . At $n = 1$ it has the value $1$ .

Facts & Assumptions

Given: An integer $a$ and an odd positive integer $n$ .

[L1]

For odd $n \geq 1$ with canonical prime factorisation $n = \prod_{i < r} p_{i}^{e_{i}}$ , define $(\frac{a}{n}) : = \prod_{i < r} {(\frac{a}{p_{i}})}^{e_{i}}$ (The Jacobi symbol, with its zero value and empty-product convention).

[L2]

In a prime factorisation of a positive integer, the exponents are determined by the integer; primes outside the factor list have exponent zero (For $n \geq 1$ and any injective list $p : r \to Z$ of primes containing every prime divisor of $n$ , one has $n = \prod_{i < r} p_{i}^{v_{p_{i}} (n)}$ ; the exponents are determined by $n$ , and $v_{q} (n) = 0$ for every prime $q$ outside the list).

[L3]

For every odd prime $p$ , the Legendre symbol belongs to ${- 1, 0, 1}$ , depends only on the numerator modulo $p$ , and equals zero exactly when $p$ divides the numerator (The Legendre symbol is well defined on residue classes).

[L4]

Every integer greater than $1$ has a prime divisor (Every integer $n > 1$ has a prime divisor; indeed the least divisor of $n$ that exceeds $1$ is prime).

Proof

technique · direct

1.1L1L2L3algebra

The uniqueness in [L2] fixes the set of prime factors and every exponent in [L1]; changing their order does not change a finite product of integers. Each factor belongs to ${- 1, 0, 1}$ by [L3], so their product does too, and at $n = 1$ the empty product is $1$ .

2.1step 1.1L1L3L4algebra∎

If $a \equiv b (m o d n)$ , then $a \equiv b (m o d p)$ for every prime factor $p$ of $n$ , so [L3] makes every corresponding factor in [L1] equal. The product is zero exactly when some prime factor $p$ of $n$ divides $a$ , which gives $\gcd (a, n) > 1$ ; conversely, if $\gcd (a, n) > 1$ , [L4] supplies a prime divisor of the gcd, hence a prime factor of $n$ dividing $a$ , and [L3] makes that Legendre factor zero.

Depends on

Used by

Cited to discharge well-definedness by The Jacobi symbol, with its zero value and empty-product convention.

Dependency tree · two levels

38 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

A. Gorodnik, Number Theory, Lecture 10, §1 (standard reference, not scraped)
V. Shoup, A Computational Introduction to Number Theory and Algebra, 2nd ed., §12.2 (standard reference, not scraped)