# Two independent routes for Euler's criterion

[← Guide index](https://ocme.evemisslab.com/en/derivations/) · [Original MKO](https://ocme.evemisslab.com/en/mko/mko-euler-criterion-quadratic-residue/)

This is an owner-adopted natural-language teaching guide. Finite/arithmetic checks are not universal proofs; no Lean was run, and review scope is recorded per revision. Original source status labels are retained as historical data. Formulas retain exact TeX; no new semantic AST is invented.

derivation-mko-euler-criterion-quadratic-residue-01 · ocme-new142-reader-adoption-20261021



## Goal and scope

For p=7,a=-4 the Legendre value is -1 and a^3=6=-1 mod 7; 2 gives +1.

A complete square table and independent repeated-squaring route, certifying p=7 instances only.





## Givens and symbols


- calc


- G1 — p=7,a=-4; normalize to 3 modulo 7, then independently compute the Legendre value and a^((p-1)/2).


- Q_7 — complete nonzero squares
- (a/7) — signed Legendre value





## Rules and sources

Some rule statements have reader clarifications in this revision: they are paraphrases, not verbatim quotations. Referenced original source bytes and hashes are unchanged.


- calc · prerequisite — Assume exact integer arithmetic, division with remainder, and definitions of divisibility and gcd; every congruence has an explicit modulus. Assume the square-root trial-division primality criterion; define Legendre values by zero and the complete nonzero square table.
- mko_definition · cited — Require odd primality and a normalized nonzero class first. Compute the Legendre value independently from the complete nonzero square table, and the modular half power by repeated squaring; interpret p−1 as signed−1. Residues give +1 and nonresidues−1. A finite table checks its specific p,a, not the theorem for every odd prime. Modulus2, composite moduli and the zero class are outside this node domain. Do not circularly define Legendre by this criterion or infer a general composite-modulus converse. · mko-euler-criterion-quadratic-residue





## Main derivation

S01 · impliesBefore

p=7,\quad a=-4

After

7\text{ odd prime},\quad a\equiv3\ne0\pmod7,\quad(p-1)/2=3

Conditions: none

Rule: calc · Uses: G1

Leaf basis: calc

2 does not divide 7 and 3^2>7, qualifying the odd-prime domain; the exponent is integer 3.



S02 · impliesBefore

x=1,2,3,4,5,6

After

\begin{array}{c|rrrrrr}x&1&2&3&4&5&6\\\hline x^2\bmod7&1&4&2&2&4&1\end{array}

Conditions: none

Rule: calc · Uses: G1, S01

Leaf basis: calc

All nonzero squares are obtained directly from six multiplications, without any half-power formula.



S03 · impliesBefore

\begin{array}{c|rrrrrr}x&1&2&3&4&5&6\\\hline x^2\bmod7&1&4&2&2&4&1\end{array}

After

Q_7=\{1,2,4\},\quad(3/7)=-1,\quad(2/7)=1

Conditions: none

Rule: calc · Uses: G1, S02

Leaf basis: calc

3 is absent from the full square values while 2 has root 3, independently defining both symbols.



S04 · impliesBefore

a\equiv3\pmod7

After

3^2=9\equiv2\pmod7

Conditions: none

Rule: calc · Uses: G1, S01

Leaf basis: calc

The power route first squares the base using exact integer remainders only.



S05 · impliesBefore

3^2\equiv2\pmod7

After

3^3\equiv2\cdot3=6\equiv-1\pmod7

Conditions: none

Rule: calc · Uses: G1, S04

Leaf basis: calc

One further multiplication gives half-power residue 6, interpreted as signed -1.



S06 · impliesBefore

(a/7)=-1,\quad a^3\equiv6\pmod7

After

a^{(7-1)/2}\equiv(a/7)\pmod7

Conditions: none

Rule: mko_definition · Uses: G1, S01, S03, S05

Leaf basis: mko_definition

The independent certificates agree for the same a,p, verifying this nonsquare instance.



S07 · impliesBefore

b=2,\quad(2/7)=1

After

2^2\equiv4,\quad2^3\equiv4\cdot2\equiv1\pmod7

Conditions: none

Rule: calc · Uses: G1, S03

Leaf basis: calc

Independent powers also check the residue branch +1 rather than only one sign.



S08 · impliesBefore

a=1,2,3,4,5,6

After

a^3\bmod7=1,1,6,1,6,6;\quad(a/7)=1,1,-1,1,-1,-1

Conditions: none

Rule: calc · Uses: G1, S02, S03, S04, S05, S07

Leaf basis: calc

Squaring then multiplying each base gives the complete six-entry comparison, checking all nonzero classes for prime 7.



S09 · impliesBefore

a\equiv0\pmod7\text{ or }p=2\text{ or }p\text{ composite}

After

\text{outside this criterion's qualified domain}

Conditions: none

Rule: calc · Uses: G1, S01, S06, S08

Leaf basis: calc

Keep all three boundaries outside this criterion; the zero half-power is 0, not +1 or -1.







## Substeps and lemmas

No substeps in this guide.





## Reverse audits


- S09 · premise_audit · G1, S01, S06, S08 — No Jacobi symbol, reciprocity or composite square-root algorithm is inferred.
- S08 · premise_audit · G1, S02, S03, S04, S05, S07 — Even a complete table covers p=7 only, not the theorem for every odd prime.
- S07 · premise_audit · G1, S03 — The root witness 3^2=2 comes from S02, not inferred from this power result.
- S06 · premise_audit · G1, S01, S03, S05 — Retain modulo 7: integers 6 and -1 are unequal but congruent.
- S05 · premise_audit · G1, S04 — Residue 6 is not a fourth Legendre value; the signed value remains -1.
- S04 · premise_audit · G1, S01 — This calculation does not use Q7 membership and has a different role from the root table.
- S03 · premise_audit · G1, S02 — The symbol is not defined backward from the a^3 result.
- S02 · premise_audit · G1, S01 — This route independently establishes the Legendre classification.
- S01 · premise_audit · G1 — The zero class is outside the theorem domain; primality alone is insufficient.





## Error controls and negative controls

Two routesDefine Legendre from all squares, then compute the half-power independently.

Sign and residueResidue 6 modulo 7 corresponds to signed -1, not integer equality.


- The zero class modulo 7 should give +1. → reject — 0^3=0 and this criterion requires nonzero input.
- The Legendre value is integer 6. → reject — 6 represents -1 modulo 7; the symbol value is -1.
- This finite table proves the theorem for all odd primes. → reject — The table contains only p=7 and does not cover all primes.





## Result and limitations

For p=7,a=-4 the Legendre value is -1 and a^3=6=-1 mod 7; 2 gives +1.







## Verification and source binding

3 declared checks for this guide; only the listed expressions are covered.


- source commit: b1b2f1dcf8c50d67a93fe52d95f8eef7b3abba9f
- adopted source SHA-256: bfc2a00296ec4845bb2bac52d8d35b1658baa23430ee96f708f9268d434e17b8
- original source SHA-256: 2f805577c16cb2f7cbc2ff07f2140cb59c25f78198341aa58674efdb3cd73780
- Lean: NOT_RUN · independent AI: SCOPED_LEAD_AND_BILINGUAL_CONTEXT_REVIEW

[Same-source full JSON (formulas, ASTs, controls and revision log)](https://ocme.evemisslab.com/data/derivations/coverage-20261021/guides/derivation-mko-euler-criterion-quadratic-residue-01.json)