Euclid's Algorithm:

Abstract

Classroom narratives about Euclid’s algorithm routinely assert that Euclid discovered it circa 300 BCE and that it is “the oldest nontrivial algorithm.” These claims are transmitted as fact, yet the underlying historiography is contested: attribution likely traces to Theaetetus via Eudoxus and the Pythagorean school, the phrase “algorithm” is a modern anachronism, and Knuth’s famous phrasing is frequently misquoted. Moreover, pedagogical literature treats the algorithm as a vehicle for computational thinking (CT) without isolating historical framing as a variable, while measures often conflate disposition and ability.

To make such a literature map checkable, we built a self-verifying corpus (44 sources, 51 atomic claims, 12 research opportunities) with an executable verification framework and a 13-rule prose linter. Every quantitative claim is recomputed (647 differential samples), source credibility and claim grades (A–E) are machine-computed from retrieval depth and independence, and register documents (claim/source registers, research agenda) are generated from JSON so they cannot drift. The linter catches anachronism, quote drift, numeric corruption, design weakness, and AI contamination; it also applies to the source text itself (revealing defects deliberately recorded in the corpus). The whole system is dependency-free, runs end-to-end, and is enforced by 69 tests with zero lint errors in the prose corpus. We present code examples, representative tests, and a complete APA-style reference list.

1. The Problem: Transmission Errors

A canonical sentence typifies the issue:

Euclid discovered the Euclidean algorithm in c. 300 BCE when compiling the Elements, and it is the oldest nontrivial algorithm in history.

When linted, three distinct defects appear:

[ERROR] ATR1 (attribution)  Unqualified discovery attribution to Euclid
        why:   The procedure is transmitted in Elements (c. 300 BCE) but
               priority is contested (Theaetetus; Eudoxus; Pythagorean school).
        fix:   Attribute transmission, not discovery; record counter-positions.

[ERROR] DRF1 (quote-drift)   Misquote of Knuth
        why:   Attested form: "the oldest nontrivial algorithm that has
               survived to the present day" (not "in history").
        fix:   Quote verbatim with locator.

[ERROR] DRF2 (date-as-discovery)
        why:   c. 300 BCE is the date of compilation/transmission, not invention.
        fix:   Say transmitted in Elements c. 300 BCE at Book VII Props. 1–2,
               Book X Props. 2–3; treat priority separately.

The errors propagate by transmission across textbooks, teacher guides, and aggregator summaries (including machine-generated ones). A machine-generated summary for Shallit (1994) on one aggregator asserted Diophantine/Gaussian developments not present in the paper—a case of contamination caught by rule CON1. A peer-reviewed abstract contained “666%” where the body read “66%” (OCR corruption, NUM1). These are exactly the kinds of defects the corpus deliberately records and grades.

2. Corpus and Strata

We assembled 44 sources across three strata (Table 1), tracked retrieval depth separately from existence (Table 2), and decomposed into 51 atomic, falsifiable claims with disconfirming conditions.

Table 1. Strata of the corpus

Stratum	Focus	Role
H — Historiography	Fowler (1999), Høyrup, Chemla, Negrepontis, Pengelley	Priority, terminology (anthyphairesis), ratio theory
T — Algorithmics	Lamé (1844), Knuth (1997), Shallit (1994), Bernstein and Yang (2019), van der Hoeven (2011)	Complexity, worst/average case, bounds, modern analyses
P — Pedagogy	Wing (2006), Grover and Pea (2013), Weintrop et al. (2016), Yadav et al. (2017), Chacón-Rivadeneira et al. (2026)	CT definitions/measures, interventions, assessments

Table 2. Retrieval depth (44 sources)

Depth	Count	Meaning
full-text	12	Read in full
abstract	6	Abstract/record only
snippet	22	Search-engine snippet only (not a reading)
metadata	2	Bibliographic record only
none	2	Not obtained (deliberate gaps: S03 primary Elements, S39 Aho & Lam 1979)

No source reached tier A; highest credibility 0.782. Two works duplicated others and were not counted as independent corroboration.

3. Verification Framework (V0–V5)

The framework enforces checkability at every stage:

• V0 — Fix the referent. Procedure for GCD of two integers, transmitted in Elements (c. 300 BCE), Book VII Props. 1–2 and Book X Props. 2–3.
• V1 — Retrieve with depth. Record retrieval_depth per source; snippets are never treated as readings.
• V2 — Atomic, falsifiable claims. 51 claims, each with a disconfirming condition.
• V3 — Grade sources and claims. Weighted rubric; independence counted by work (via same_work_as), retrieval_depth: none forced to tier E. Declared vs. computed disagreements reported (exactly one annotated as intentional: P12).
• V4 — Reproduce quantitatively. All technical claims re-derived by tools/gcd_reference.py (647 differential samples).
• V5 — Lint prose against framework. 13 rules, scoped suppressions with reasons, generated registers exempt in marked regions but linted separately.

3.1 Claim grades and source tiers (summary)

• Claims: A=15, B=9, C=15, D=11, E=1
• Sources: B=32, C=4, D=5, E=3
• Disagreements: 1 unannotated none (1 annotated intentional)

4. Executable Reference: tools/gcd_reference.py

The technical reference implements subtractive, division (Euclidean), binary (Stein), and Lehmer forms, continued fractions/anthyphairesis, Fibonacci worst case, Lamé’s bound, and the average-step constant. It self-tests against math.gcd over 647 differential pairs.

4.1 Key functions (excerpt)

# tools/gcd_reference.py (excerpt)
import math
from dataclasses import dataclass
from typing import List, Tuple

@dataclass
class GcdResult:
    gcd: int
    steps: int
    trace: List[Tuple[int,int]]

def gcd_division(a: int, b: int) -> GcdResult:
    """Euclidean algorithm by division (the form in modern pedagogy)."""
    ...

def gcd_subtractive(a: int, b: int) -> GcdResult:
    """Subtractive form (the form in Elements Book VII)."""
    ...

def gcd_binary(a: int, b: int) -> GcdResult:
    """Binary GCD (Stein)."""
    ...

def anthyphairesis(a: int, b: int) -> List[int]:
    """Repeated subtraction counts / division quotients (Fowler's reading)."""
    ...

def continued_fraction(a: int, b: int) -> List[int]:
    """Continued fraction of a/b."""
    r = anthyphairesis(a,b)
    # same sequence
    return r

4.2 Reproduced values

average-step constant 12 ln 2 / π² = 0.842766
anthyphairesis(22, 6) = [3, 1, 2]
continued_fraction(22, 6) = [3, 1, 2]
lame_step_bound(90) expects Fibonacci index (not value)

4.3 Cost comparison (by bit length)

Bits	Subtractions	Divisions	Binary steps
20	1,048,576	1	20
30	1,073,741,824	1	30
40	1,099,511,627,776	1	40
50	1,125,899,906,842,624	1	50

This quantifies the 2,400-year technical gap: historical form is exponential in bit length; division/binary are logarithmic/linear.

5. Prose Linter: tools/anachronism_linter.py

13 rules across 10 functions. Each finding includes rule, category, severity, line, excerpt, message (why), remediation (fix). Suppressions are line-scoped and must state a reason.

5.1 Rule catalog

Rule	Category	Severity	Description
ATR1	attribution	error	Unqualified discovery attribution to Euclid
ANC1	anachronism	error	Modern computational vocabulary projected onto ancient actors
ANC3	anachronism	warning	'Algorithm' used as a period term for Greek practice
ANC4	anachronism	error	Fibonacci / golden ratio attributed to Greek mathematics
DRF1	quote-drift	error	Quote drift in the Knuth sentence about the algorithm's age
DRF2	quote-drift	error	The c. 300 BCE date used as a discovery date
CIT1	citation-drift	error	Shallit (1994) pagination drift
CIT2	citation-drift	warning	Lamé (1844) volume/page drift
NUM1	numeric	error	Percentage above 100 (OCR corruption)
NUM3	numeric	info	Percentage not obtainable from stated denominator
DES1	design	warning	Study design cannot support the effect claim it carries
DES2	design	info	Attitudinal measure carrying a performance claim
CON1	contamination	error	Machine-generated summary posing as a source

5.2 Design rules for the linter

1. Gap between claim and design, not weakness alone. DES1 fires only when an effect claim depends on missing control/randomization; it stays silent if the text already remediates (“so its effect claims are associational”).
2. Negated weakness is remediated. If the line negates adequacy (“cannot”, “must not”, “is insufficient”), the design rule stays silent.
3. Institutional context is not anachronism. Usage context (“as used in computer science education”) is not projected agency.
4. Marker must be diagnostic. CON1 dropped TL;DR (human convention) after a regression test; only diagnostic markers remain (e.g., “Key takeaways AI”, disclosed LLM authorship, generated preambles).

5.3 Scoped suppressions (example)

The guide dates it to c. 300 BCE. <!-- lint-allow: DRF2 reason: quoting the defect under analysis -->
Of 30 teachers, 666%... <!-- lint-allow: NUM1 reason: reporting the published OCR artifact under analysis, not asserting it -->

A suppression without a reason is reported by self-audit. Generated register regions (<!-- register: begin --> / <!-- register: end -->) are exempt from content rules but bounded by render_registers.py --check.

6. Linting the Source Text Itself: tools/lint_corpus.py

The generated registers exempt quoted defects, but lint_corpus.py applies the same rules to the raw register text (51 claim statements + 44 source records).

$ python lint_corpus.py
==============================================================================
CORPUS LINT  (tools/lint_corpus.py)
==============================================================================
findings on register text : 6
distinct rule ids triggered: 4

  ANC3  2 finding(s)  [warning]   'Algorithm' used as a period term for Greek practice.
  CON1  1 finding(s)  [error]     Machine-generated summary posing as a source.
  DRF2  2 finding(s)  [error]     The c. 300 BCE date used as a discovery date.
  NUM1  1 finding(s)  [error]     Percentage above 100 (OCR corruption).

These are defects in the *sources the corpus records*, not in the corpus prose.
The register grades them; the prose quotes them with a scoped suppression stating why.

The register holds these deliberately (graded, with notes), rather than silently correcting them.

7. Tests: tools/test_toolkit.py (69 tests)

The test suite covers technical reproduction, linter behavior (including negation guards and false-positive prevention), credibility/grading, dependency acyclicity, bibliography consistency, and register rendering.

7.1 Representative tests

# tools/test_toolkit.py (excerpt)
class TestGcdReference(unittest.TestCase):
    def test_anthyphairesis_matches_fowler(self):
        self.assertEqual(gcd_reference.anthyphairesis(22, 6), [3, 1, 2])
        self.assertEqual(gcd_reference.continued_fraction(22, 6), [3, 1, 2])

    def test_average_step_constant(self):
        self.assertAlmostEqual(
            gcd_reference.mean_division_steps_constant(), 12*math.log(2)/math.pi**2, places=12
        )

class TestLinter(unittest.TestCase):
    def test_detects_ai_contamination(self):
        text = ("Key takeaways AI: the paper traces the lineage back to "
                "Diophantus in the 3rd century and a shift in the 18th century.")
        rules = {f.rule for f in anachronism_linter.lint_document(text)}
        self.assertIn("CON1", rules)

    def test_tldr_is_not_a_contamination_marker(self):
        text = ("> **TL;DR** -- I collected 44 sources and checked them against "
                "a retrieval-depth rubric. 66% were read in full.\n")
        rules = {f.rule for f in anachronism_linter.lint_document(text)}
        self.assertNotIn("CON1", rules)

    def test_detects_unreconciled_percentage(self):
        text = ("Of 30 teachers, 43% did so unassisted and 83% applied it "
                "correctly without direct instruction.")
        rules = {f.rule for f in anachronism_linter.lint_document(text)}
        self.assertIn("NUM3", rules)

    def test_institutional_context_is_not_an_anachronism(self):
        text = "Euclid's algorithm as it is used in computer-science education has become a standard example."
        self.assertEqual(anachronism_linter.lint_document(text), [])

class TestNegationGuard(unittest.TestCase):
    def test_des2_silent_when_text_warns_against_self_report(self):
        text = ("A framing study that measures only self-reported computational "
                "thinking would reproduce the central problem of the field.\n")
        rules = {f.rule for f in anachronism_linter.lint_document(text)}
        self.assertNotIn("DES2", rules)

class TestLintCorpus(unittest.TestCase):
    def test_lint_corpus_finds_the_known_defects(self):
        findings = lint_corpus.collect()
        by_rule = {f.rule for _, f in findings}
        for rule in ("NUM1", "CON1", "DRF2", "ANC3"):
            self.assertIn(rule, by_rule)
        self.assertGreaterEqual(len(findings), 6)

class TestDependencyGraph(unittest.TestCase):
    def test_dependency_graph_is_acyclic_and_consistent(self):
        # checks depends_on references exist and graph acyclic
        ...

7.2 Run tests

cd tools
python test_toolkit.py         # 69 tests, all OK
python gcd_reference.py        # 647 differential samples, 0 failures
python run_all.py              # end-to-end verification

Last reported run:

technical self-test            : PASS
register documents current     : YES
deliverables present           : 9/9
lint errors in prose corpus    : 0
unannotated grade disagreements: 0
run status                     : PASS

8. Research Agenda (top opportunities)

Twelve opportunities ranked by weighted score (evidence_gap 0.30, impact 0.25, feasibility 0.20, novelty 0.15, risk 0.10 cost-inverted). Ranking is by value; sequencing is a separate dependency graph (acyclic, tested).

Rank	ID	Score	Opportunity	Notes
1	O1	0.815	Historical framing as a causal treatment in a GCD-based CT intervention	Three-arm RCT: algorithm-only vs algorithm+history vs algorithm+complexity. Needs O7.
2	O2	0.800	Design/validate “Greek algorithm” lab (subtraction counts = continued fractions = quotients)	Performance-based tasks, not only self-report.
3	O3	0.760	Teach GCD at bit complexity (close 2,400-year gap)	Include binary/Lehmer, complexity intuition.
4	O7	0.710	Retrieve/verify three unretrieved anchors (primary Elements etc.)	Prerequisite for several; tie.
5	O6	0.710	Audit history in secondary textbooks	Tie.
6	O8	0.710	Citation-provenance audit of CT-in-mathematics literature	Tie.
7	O5	0.695	Performance-based CT instrument specialized to algorithmic reasoning	Addresses disposition/ability conflation.
8	O4	0.690	Preregistered replication/extension of 2026 intervention	Causal leverage with control.
9	O12	0.638	Ancient procedure as bridge to complexity classes	Exploratory.
10	O9	0.630	PD for teachers’ historical/algorithmic knowledge	Scalable.
11	O11	0.585	Terminological study of “Euclid’s algorithm”	Historiographic.
12	O10	0.562	Adjudicate Theaetetus/Eudoxus on primary texts	Hard without O7.

Dependencies (examples): O1→[O3,O4,O5,O7], O3→[O7], O5→[O2], O6→[O8], etc. Four have no prerequisites (O2,O7,O8,O11).

9. Practical Usage

9.1 Directory layout (relevant files)

articles/
├── README.md
├── ARTICLE.md (narrative)
├── 01-landscape-map.md
├── 02-gap-analysis.md
├── 03-verification-framework.md
├── 04-claim-register.md        # generated
├── 05-source-register.md      # generated
├── 06-research-agenda.md      # generated
├── refs.bib
├── tools/
│   ├── gcd_reference.py
│   ├── anachronism_linter.py
│   ├── lint_corpus.py
│   ├── credibility.py
│   ├── prioritize.py
│   ├── render_registers.py
│   ├── claims.json
│   ├── sources.json
│   ├── gaps.json
│   ├── run_all.py
│   └── test_toolkit.py
└── outputs/
    ├── verification-report.json
    ├── source-scores.csv
    ├── claim-grades.csv
    └── research-agenda.json

9.2 Commands

cd tools
# tests
python test_toolkit.py         # 69 tests
# end-to-end
python run_all.py              # verify everything, write outputs
# technical
python gcd_reference.py        # 647 differential samples
# linting
python anachronism_linter.py --demo
python anachronism_linter.py --self-audit
python lint_corpus.py          # defects in source text
# registers
python render_registers.py     # regenerate 04-06
python render_registers.py --check

10. Limitations and Honesty

• Primary Elements never retrieved (S03). Proposition locations rest on secondary works; registered as O7.
• Aho and Lam (1979) not located (S39). Three searches returned GCD-of-polynomials literature; registered as deliberate gap, must not be cited.
• Argument from absence (P14, grade C). “No retrieved study isolates historical framing as a variable” is over 44 sources, not proof of universal absence.
• Measure conflation. Widely used CT scales are self-report (disposition) vs performance instruments; the corpus documents this gap.
• Attribution unsettled. No tie-break procedure; framework records contradictions and penalties rather than averaging.

11. Conclusion

Treating a literature review as a codebase changes the cost of being careful. Types (retrieval depth), tests (recomputation), linting (prose rules), generated artifacts, explicit budgets (snippets), and dependency graphs make errors visible and fixable. The framework doesn’t claim the historical framing improves learning—it makes it testable. The defects found (quote drift, date confusion, OCR corruption, AI contamination) are common, but here they are counted, graded, suppressed with reasons when quoted, and enforced by tests. If a sentence cannot be checked against sources or code, the system requires it to become checkable or be removed.

References (APA 7)

Aho, A. V., & Lam, M. S. (1979). The complexity of computing the greatest common divisor [Unretrieved; registered as S39]. (Not located after three searches.)

Bernstein, D. J., & Yang, B.-Y. (2019). Fast constant-time gcd computation and modular inversion. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019(3), 340–398. https://doi.org/10.13154/tches.v2019.i3.340-398

Chacón-Rivadeneira, L., Ruiz-Aguilar, L. A., & Paredes, F. G. (2026). Developing computational thinking through Euclid’s algorithm: An action research with prospective lower-secondary mathematics teachers in Panama. Journal of Mathematics Teacher Education. [As reported in corpus; abstract contained OCR artifact “666%”.]

Chemla, K. (Ed.). (2004). History of science, history of text. Springer. https://doi.org/10.1007/1-4020-2321-9

Euclid. (n.d.). The Elements. (Primary edition S03 unretrieved; propositions cited via secondary sources: Book VII Props. 1–2, Book X Props. 2–3.)

Fowler, D. H. (1999). The mathematics of Plato’s Academy: A new reconstruction (2nd ed.). Clarendon Press.

Grover, S., & Pea, R. (2013). Computational thinking in K–12: A review of the state of the field. Educational Researcher, 42(1), 38–43. https://doi.org/10.3102/0013189X12463051

Høyrup, J. (1994). In measure, number, and weight: Studies in mathematics and culture. State University of New York Press.

Knuth, D. E. (1997). The art of computer programming: Vol. 2. Seminumerical algorithms (3rd ed.). Addison-Wesley.

Lamé, G. (1844). Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences, 19, 867–870.

Negrepontis, S. (2001). The anthyphairesis and the origins of the theory of proportions. In C. Sasaki, M. Saito, & J. Dauben (Eds.), The intersection of history and mathematics (pp. 79–118). Birkhäuser. https://doi.org/10.1007/978-3-0348-7521-9_5

Pengelley, D. (2002). The bridge between continuous and discrete via original sources. In D. M. Bressoud et al. (Eds.), Study the masters: The Abel-Fauvel conference (pp. 169–196). National Center for Mathematics Education.

Shallit, J. (1994). Origins of the analysis of the Euclidean algorithm. Historia Mathematica, 21(4), 401–419. https://doi.org/10.1006/hmat.1994.1031

van der Hoeven, J. (2011). Faster algorithms for gcds. In Proceedings of the 2011 International Symposium on Symbolic and Algebraic Computation (pp. 225–232). ACM. https://doi.org/10.1145/1993886.1993920

van der Waerden, B. L. (1949). Science awakening. Noordhoff.

Weintrop, D., Beheshti, E., Horn, M., Orton, K., Jona, K., Trouille, L., & Wilensky, U. (2016). Defining computational thinking for mathematics and science classrooms. Journal of Science Education and Technology, 25(1), 127–147. https://doi.org/10.1007/s10956-015-9581-5

Wing, J. M. (2006). Computational thinking. Communications of the ACM, 49(3), 33–35. https://doi.org/10.1145/1118178.1118215

Yadav, A., Good, J., Voogt, J., & Fisser, P. (2017). Computational thinking as an emerging competence domain. In M. Mulder (Ed.), Competence-based vocational and professional education (pp. 1051–1067). Springer. https://doi.org/10.1007/978-3-319-41713-4_49