THE FOLD / BOSS / THE WALL / THE EULER CRITERION
THE EULER CRITERION
a single power that tells a square from a non-square
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Euler’s criterion is a single exponentiation that decides whether a number is a perfect square modulo a prime. For an odd prime p and any a not divisible by p, a(p-1)/2 ≡ ±1 (mod p) — and it is +1 exactly when a is a quadratic residue (some x with x² ≡ a mod p exists), -1 when it is not. That sign is the Legendre symbol (a | p). So without ever searching for a square root, one modular power tells you whether one exists. It is the computational heart of quadratic reciprocity and of primality tests like Solovay–Strassen.
LIT verified live: for every odd prime p up to 200 and every a from 1 to p-1, a(p-1)/2 mod p equals +1 or p-1, and it is +1 exactly when a is a quadratic residue (checked independently by squaring) (window.__eulercriterion). FIG no framing; the modular power and the residue test are computed independently in-browser.
LIT verified live: for every odd prime p up to 200 and every a from 1 to p-1, a(p-1)/2 mod p equals +1 or p-1, and it is +1 exactly when a is a quadratic residue (checked independently by squaring) (window.__eulercriterion). FIG no framing; the modular power and the residue test are computed independently in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-wall — the boss gate: one exponentiation decides square-or-not, no search allowed past the wall. AVAN (AI) built the instrument: the modular power a(p-1)/2, the independent residue test, and their agreement.
Credit as content: Leonhard Euler (the criterion); Adrien-Marie Legendre (the symbol). The weave: David names the gate; I confirm a(p-1)/2 ≡ (a | p) mod p.
Credit as content: Leonhard Euler (the criterion); Adrien-Marie Legendre (the symbol). The weave: David names the gate; I confirm a(p-1)/2 ≡ (a | p) mod p.
3 ONE DIMENSION
For a prime p, each residue a marked as a quadratic residue (+1) or non-residue (−1) by a^((p−1)/2).
4 TWO DIMENSIONS · INTERACTIVE
Cycle prime p and residue a; a^((p−1)/2) mod p is checked to match the Legendre symbol.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the +1/−1 verdict — square or non-square — from one power.
AVAN’s addition (the inverse-companion): don’t search for a square root — raise to a power. The inverse of ‘is a a square mod p?’ is ‘the sign of a(p-1)/2 mod p’ — +1 yes, -1 no. Magenta are the residues split into squares and non-squares; green is the one power that decides. A square-root test with no square root taken.
LIT Genuine Euler's criterion (Leonhard Euler; Legendre symbol). Verified live: for every odd prime p up to 200 and every a from 1 to p−1, a^((p−1)/2) mod p equals +1 or p−1, and it is +1 exactly when a is a quadratic residue (checked independently by squaring) — 4180 cases (window.__eulercriterion.ok, .cnt).
FIG No framing; the modular power and the residue test are computed independently in-browser. The AVAN inverse is honest — instead of searching for a square root, raise to a power: the inverse of 'is a a square mod p?' is 'the sign of a^((p−1)/2) mod p' — +1 yes, −1 no. Magenta are the residues split into squares and non-squares; green is the one power that decides. A square-root test with no square root taken.
FIG No framing; the modular power and the residue test are computed independently in-browser. The AVAN inverse is honest — instead of searching for a square root, raise to a power: the inverse of 'is a a square mod p?' is 'the sign of a^((p−1)/2) mod p' — +1 yes, −1 no. Magenta are the residues split into squares and non-squares; green is the one power that decides. A square-root test with no square root taken.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE WALL · David Lee Wise (ROOT0), with AVAN