Compute square roots with a shrinking order invariant

Try

A square root exists modulo an odd prime, but how can we find it without testing every residue? For p congruent to three modulo four, a nonzero square a has the root a^((p+1)/4). For example, modulo seven a=2 gives 2²=4, whose square is two modulo seven. Euler’s criterion proves the formula because the square of that candidate is a times a^((p−1)/2), and the latter factor is one. Primes congruent to one modulo four require more work.

Predict

Predict what structure remains after removing the odd part of p−1. Write p−1=Q·2^S with Q odd. Choose a nonsquare z, detectable by Euler’s criterion. Set c=z^Q, t=a^Q, x=a^((Q+1)/2), and M=S. Then x²=at, c has exact order 2^M, and t has order dividing 2^(M−1), because a is a square. The algorithm repeatedly shrinks the exponent controlling t until t=1, at which point x is a square root.

Experiment

Work the fixed example p=13, a=10, z=2. Here Q=3, S=2, c=8, t=12, x=9. The least i with t^(2^i)=1 is i=1. Set b=c^(2^(M−i−1))=8, then update x to xb=7, t to tb²=1, c to b²=12, and M to 1.

State	x	t	c	M
Initial	9	12	8	2
Updated	7	1	12	1

Check both 9²=10·12 and 7²=10 modulo 13. The other root is six.

Understand

Here is the full loop invariant over the field modulo p: x²=at; c has exact order 2^M; t has order dividing 2^(M−1). If t≠1, let i be the least positive index with t^(2^i)=1. Then 1≤i< M. Choose b=c^(2^(M−i−1)). The element b² has exact order 2^i. Both t and b², raised to 2^(i−1), equal the unique element of order two, namely−1. Their product therefore has order dividing 2^(i−1). The updates x←xb, t←tb², c←b², M←i preserve all three invariants. Since M strictly decreases through positive integers whenever the loop runs, termination is proved. At exit t=1 gives x²=a.

Execute the proof with an explicit stopping contract

Predict the default trace before running. First set the correction budget to zero: this particular input needs an update, so the correct result is an incomplete computation, not a proof that a root does not exist. Then restore the budget, reveal the next state and compare all three invariants with your prediction. The full completed trace is already in the report; manual revelation is a display aid, not an untouched assessment.

Predict, execute and audit a bounded procedure

Record a predicted status or root before running. This reference executes exact small-integer arithmetic; a supplied trace is not your own implementation. Controls and the at-most-12 action records are temporary. Save a report in your lesson argument before leaving.

Modulus p (2–257) Input a (−10000–10000) Maximum corrections012345678

Run bounded root procedure Reset controls, retain records

Independently check your submitted root

Candidate root (0–256, also less than p) Square candidate against current inputs

This check uses the current p and a, not an earlier trace. Direct squaring can verify a root for an even or composite modulus even though the odd-prime procedure refuses that modulus. Root validity and algorithm eligibility are different questions.

Changed hypotheses: lift one branch by one prime-power digit

Input p is an odd prime at most 31; k is 1 or 2; root r is canonical modulo p^k. This checker tries at most p digits and verifies the resulting roots directly. It handles one supplied branch; it does not claim that branch contains every root of the full congruence.

Lift prime35711131719232931Starting exponent12Lift input aStarting root r

Audit one lifting digit

Combine two supplied residues by coprime CRT

Each modulus is 2–1000, product at most 1,000,000; each residue must be canonical. CRT checks these congruences, not whether either supplied residue is a square root. Independently square the final candidate in your report.

First modulusFirst residueSecond modulusSecond residue

Audit CRT combination

0 of 12 records used.

Download procedure report

Copyable exact report

Procedure JSON{ "version": "modular-root-investigation-v1", "scope": "Public bounded teaching procedure; no learner mastery or cryptographic suitability claim.", "records": [] }

Record filenames and model/input identities in your saved investigation response. Reload clears this temporary record; it does not clear already saved lesson arguments. Public traces are development/practice evidence, not an untouched test or secure cryptographic implementation.

The executor validates an odd prime by trial division through its square-root bound before interpreting Euler’s criterion. Modulus 9 with input 1 illustrates why a residue passing a power test is not itself primality evidence. Zero is handled separately after the procedure’s modulus check; direct squaring can still recognize a zero root for a modulus the odd-prime algorithm refuses. Normalizing a negative input changes its representative, not its congruence class.

For primes at most 257, the initial exponent S is at most 8. Every actual correction strictly decreases positive M, so at most seven are required. A cap of zero can still succeed if a is zero or the initialized t is already one. A cap does not require unnecessary work, and an exhausted cap must retain the preceding complete invariant state. The search for a nonsquare and the invariant checks have separate work counts; ignoring them would misdescribe the algorithm’s cost. Products stay exact within the documented small-integer ranges. This is teaching arithmetic, not secure cryptographic software or a bit-complexity theorem.

Apply

Initialization also deserves proof. A nonsquare z has z^((p−1)/2)=−1, so c=z^Q has order exactly 2^S. For a square a, Euler’s criterion gives t^(2^(S−1))=1. Finally x²=a^(Q+1)=at. This verifies the starting hypotheses and explains why a composite modulus or nonsquare input breaks the reasoning. Handle a=0 separately. For nonzero a, first use Euler’s criterion to reject nonsquares; then find z by testing candidates. A nonsquare exists because exactly half the nonzero residues are squares.

Retain one reproducible procedure investigation

Use the new written investigation task below for one dossier with an input manifest, predictions, your own code or a fully independent hand audit, complete traces, adversarial cases, exact output checks and a review revision. Preserve both failed and successful records. The workbench’s report is temporary: download or copy it before leaving, keep the actual file externally, and identify its filename and version in the saved argument. A provided trace is not evidence that you independently implemented its algorithm. If no person has reviewed your proof or code, say so.

Change a or p after obtaining a root and run the separate direct-square check. Its displayed input identity must match the claim you are making. A previously correct root need not remain correct after an input change; neither a remembered green result nor a plot is a substitute for that check.

For the prime-power transfer, start with both roots of 2 modulo 7, namely 3 and 4. The Hensel lifting proof gives the digit equation (r²−a)/p^k + 2r d ≡ 0 modulo p. It uses the signed exact quotient. A nonzero derivative gives one digit; a zero derivative gives all p digits or none, depending on that quotient. The reference digit checker tests at most p possibilities and squares its outputs; it does not claim the arithmetic cost of an inverse-based Hensel implementation. Lift each branch, rather than treating one branch as every root.

Next pair each root modulo 49 with each root modulo 17 and use CRT. The coprime CRT checker verifies the supplied residue pair, not whether those inputs were square roots. Independently square every combined value and explain why prime-field root counts, uniqueness of simple lifts and CRT bijectivity make the list exhaustive. This new modulus is outside the prime-only procedure: applying its field proof directly to 833 would be invalid.

The singular starting root zero modulo 7 separates two important cases. For a=0 the quotient and derivative both vanish, giving seven roots from that branch modulo 49. For a=7 the quotient is −1 and derivative zero, so no digit works. Likewise, a coprime-only CRT refusal need not mean incompatibility: residues 1 modulo 6 and 4 modulo 9 are compatible modulo their gcd. A general solver would use modulus 18, not 54. These are changes of mathematical hypotheses, not numerical precision problems.

Continue

Implement the loop on paper using repeated squaring, keeping the old c and M until all update quantities are computed. Test the shortcut case, an input with t initially one, and the worked two-adic correction. Verify the returned root by squaring it independently. This is Tonelli–Shanks for odd prime moduli; composite moduli require factorization, prime-power lifting and CRT, and powers of two need separate treatment. The invariant proves correctness, while practical performance depends on modular arithmetic and the search for a nonsquare.

Return to the number theory unit to choose a targeted retry. Continue with connect polynomial factors with multiplicative orders.

The changed-protocol mixed task asks for a different target and composite modulus. Source scope: MIT 18.781 Spring 2012 calendar and lecture notes, consulted 28 October 2026, explicitly connect CRT algorithms, Hensel lifting and Tonelli’s algorithm. The bounded procedure, investigation and transfer here are original.