THE FOLD / BOSS / THE GATEKEEPER / THE JACOBI SYMBOL
THE JACOBI SYMBOL
a residue test computed by reciprocity — without factoring
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Legendre symbol (a/p) tells whether a is a quadratic residue mod a prime p (a perfect square, +1) or not (−1). The Jacobi symbol extends it to any odd modulus n by multiplying the Legendre symbols over n’s prime factors: (a/n) = ∏(a/pᵢ)eᵢ.
Its power: it can be computed fast via quadratic reciprocity and the supplementary laws — without factoring n — making it the workhorse of primality tests (Solovay–Strassen) and modular square-root algorithms. A subtlety: for composite n, (a/n)=+1 does not guarantee a is a residue — which is exactly what makes it useful for detecting composites.
LIT verified live: the reciprocity-computed Jacobi symbol equals the product of Legendre symbols over the factorisation for odd n, and equals the Legendre symbol (correctly predicting residues) for primes (window.__jacobisymbol). FIG no framing; exact number theory.
Its power: it can be computed fast via quadratic reciprocity and the supplementary laws — without factoring n — making it the workhorse of primality tests (Solovay–Strassen) and modular square-root algorithms. A subtlety: for composite n, (a/n)=+1 does not guarantee a is a residue — which is exactly what makes it useful for detecting composites.
LIT verified live: the reciprocity-computed Jacobi symbol equals the product of Legendre symbols over the factorisation for odd n, and equals the Legendre symbol (correctly predicting residues) for primes (window.__jacobisymbol). FIG no framing; exact number theory.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-gatekeeper — deciding, at the gate, which numbers are squares modulo n. The Jacobi symbol is that residue gatekeeper, computed without ever opening the factorisation. AVAN (AI) built the instrument: the reciprocity ladder, the Legendre-product cross-check, the prime-residue prediction.
Credit as content: Adrien-Marie Legendre (1798); generalised by Carl Gustav Jacob Jacobi (1837); reciprocity by Gauss. The weave: David names the gatekeeper; I compute (a/n) by swap-and-reduce reciprocity and confirm it matches the product of Legendre symbols over the primes — without ever finding them.
Credit as content: Adrien-Marie Legendre (1798); generalised by Carl Gustav Jacob Jacobi (1837); reciprocity by Gauss. The weave: David names the gatekeeper; I compute (a/n) by swap-and-reduce reciprocity and confirm it matches the product of Legendre symbols over the primes — without ever finding them.
3 ONE DIMENSION
Computing (a/n) by reciprocity: pull out factors of 2 (a sign rule on n mod 8), then flip (a/n) ↔ (n/a) with a sign from n,a mod 4, and reduce — a gcd-like ladder that never factors n.
4 TWO DIMENSIONS · INTERACTIVE
Choose a and an odd n. The Jacobi symbol is computed by reciprocity and checked against the product of Legendre symbols over n’s factorisation. For prime n, it correctly flags quadratic residues.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the residue map mod n — which values are squares — and the Jacobi symbol reading it via reciprocity.
AVAN’s addition (the inverse-companion): the Jacobi symbol computes a factorisation-dependent quantity without the factorisation. Reciprocity lets you swap and reduce (a/n) ↔ (n/a) like a gcd, so you reach the product-over-primes value without ever finding the primes. The inverse of ‘multiply Legendre symbols over prime factors’ is ‘reciprocity’s swap-and-reduce, blind to the factors.’ And the catch — a Jacobi +1 need not mean a residue — is the other inverse: the fast symbol loses the residue guarantee that only the true Legendre (with known primes) keeps, and that lost guarantee is exactly the gap that catches composite ‘liars.’ Magenta is the hidden factorisation, never computed; green is the reciprocity ladder. Answer a factoring-flavoured question without factoring.
LIT Genuine Jacobi/Legendre symbols and quadratic reciprocity (Legendre 1798; Jacobi 1837; Gauss). Verified live: the reciprocity-computed Jacobi symbol equals the product of Legendre symbols (via Euler's criterion) over n's factorization for odd n in {3,5,7,9,15,21,35,45,63,105}, and equals the Legendre symbol correctly predicting quadratic residues for primes 3,5,7,11,13 (window.__jacobisymbol.matchesLegendreProduct && .primesPredictQR).
FIG No framing: the reciprocity ladder, the Legendre-product cross-check, and the prime-residue prediction run in-browser and are exact. The AVAN inverse is honest — reciprocity computes the product-over-primes value without finding the primes (swap-and-reduce like a gcd), and the lost residue guarantee for composites is exactly what catches composite liars in Solovay-Strassen; magenta is the uncomputed factorization, green the reciprocity ladder.
FIG No framing: the reciprocity ladder, the Legendre-product cross-check, and the prime-residue prediction run in-browser and are exact. The AVAN inverse is honest — reciprocity computes the product-over-primes value without finding the primes (swap-and-reduce like a gcd), and the lost residue guarantee for composites is exactly what catches composite liars in Solovay-Strassen; magenta is the uncomputed factorization, green the reciprocity ladder.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GATEKEEPER · David Lee Wise (ROOT0), with AVAN