TheoremStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passjudge pass (deepseek-v4-pro + claude-sonnet-5)audited 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 Euclidean algorithm computes the Jacobi symbol without factoring the denominator

Statement

Let $a \in Z$ and let $n \geq 1$ be odd. Starting from $(ε, A, N) = (1, a, n)$ , repeat the following deterministic procedure:

if $N = 1$ , return $ε$ ;
otherwise let $r$ be the least nonnegative remainder of $A$ modulo $N$ , and return $0$ if $r = 0$ ;
write $r = 2^{s} b$ with $b$ odd, replace $ε$ by $ε (- 1)^{s (N^{2} - 1) / 8}$ , then replace it by $ε (- 1)^{(b - 1) (N - 1) / 4}$ and replace $(A, N)$ by $(N, b)$ .

The Euclidean Jacobi algorithm terminates and returns $(\frac{a}{n})$ without factoring the odd denominator $n$ .

Facts & Assumptions

Given: An integer $a$ , an odd positive integer $n$ , and the algorithmic state described in the Statement.

[L1]

The Jacobi symbol satisfies $(\frac{a}{1}) = 1$ and is zero exactly when $\gcd (a, n) > 1$ (The Jacobi symbol, with its zero value and empty-product convention).

[L2]

The Jacobi symbol depends only on its numerator modulo the odd positive denominator (The Jacobi symbol is well defined on numerator residue classes).

[L3]

For odd positive $N$ , $(\frac{u v}{N}) = (\frac{u}{N}) (\frac{v}{N})$ (The Jacobi symbol is multiplicative in numerator and denominator).

[L4]

For odd positive $N$ , $(\frac{2}{N}) = (- 1)^{(N^{2} - 1) / 8}$ (The two supplementary laws for the Jacobi symbol).

[L5]

For coprime odd positive $b, N$ , $(\frac{b}{N}) (\frac{N}{b}) = (- 1)^{(b - 1) (N - 1) / 4}$ (Quadratic reciprocity for coprime odd Jacobi denominators).

[L6]

Division by a positive integer has a unique remainder $r$ with $0 \leq r < N$ (Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ ).

[L7]

Every nonzero integer $r$ has a uniquely determined maximal power $2^{s}$ dividing it and can be written $r = 2^{s} b$ with $b$ odd (For a prime $p$ and a nonzero integer $a$ : $p^{v_{p} (a)} ∣ a$ and $p^{v_{p} (a) + 1} ∤ a$ ; $p^{k} ∣ a$ holds exactly for $k \leq v_{p} (a)$ ; $v_{p} (a) \geq 1$ exactly when $p ∣ a$ ; $v_{p} (1) = v_{p} (- 1) = 0$ ; and $v_{p} (p) = 1$ ).

Proof

technique · direct

1.1

Maintain the invariant $(\frac{a}{n}) = ε (\frac{A}{N})$ . By [L2] and [L6], replacing $A$ by $r$ preserves the current symbol. If $r = 2^{s} b$ , then [L3] and [L4] give $(\frac{r}{N}) = (- 1)^{s (N^{2} - 1) / 8} (\frac{b}{N})$ . When $\gcd (b, N) = 1$ , [L5] gives $(\frac{b}{N}) = (- 1)^{(b - 1) (N - 1) / 4} (\frac{N}{b})$ ; when the gcd exceeds $1$ , [L1] makes both Jacobi symbols zero, so the same signed equality remains true. Thus every nonterminal update preserves the invariant.

L1L2L3L4L5L6L7algebra

2.1

At a nonterminal update, $0 < r < N$ and the new denominator is the positive odd part $b \leq r$ , so it is strictly smaller than $N$ . A strictly decreasing chain of positive integers cannot have more terms than its initial value, so the procedure reaches a terminal state.

step 1.1L6algebra

3.1

If $N = 1$ , [L1] and the invariant give $(\frac{a}{n}) = ε$ . If $r = 0$ while $N > 1$ , then $N$ divides $A$ , so [L1] gives $(\frac{A}{N}) = 0$ and the invariant gives the returned value $0$ . These are all terminal states, proving correctness and termination; only division, extraction of powers of $2$ , and sign updates were used, not a factorisation of $n$ .

step 1.1step 2.1L1L6∎

Depends on

Used by

Computing (1111/8093) by the Euclidean Jacobi algorithm Example

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 97 results over 28 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

V. Shoup, A Computational Introduction to Number Theory and Algebra, 2nd ed., §12.3 (standard reference, not scraped)
P. Hackman, Elementary Number Theory, §D.II (standard reference, not scraped)
A. Gorodnik, Number Theory, Lecture 10, §1 (standard reference, not scraped)