Euclidyne

Instrument-Lab Explorations into Euclid, Ratios, and Rhythm

Core Algorithm

Algorithm Explorer

Scrub Euclid Steps, Bézout Rows, and the One-Step Phase Analogy

Verified Verified Verified Analogy Only
One full driver turn yields 5 full follower turns and a residual phase of 10/46.

GCD

2

Steps

5

CF

[5; 4, 1, 1, 2]

Division Steps

step A B q r
1 240 46 5 10
2 46 10 4 6
3 10 6 1 4
4 6 4 1 2
5 4 2 2 0

Extended Euclid Rows

i q r r recurrence s t identity
0 240 1 0 240 * (1) + 46 * (0) = 240
1 46 0 1 240 * (0) + 46 * (1) = 46
2 5 10 240 - 5 * 46 1 -5 240 * (1) + 46 * (-5) = 10
3 4 6 46 - 4 * 10 -4 21 240 * (-4) + 46 * (21) = 6
4 1 4 10 - 1 * 6 5 -26 240 * (5) + 46 * (-26) = 4
5 1 2 6 - 1 * 4 -9 47 240 * (-9) + 46 * (47) = 2
6 2 0 4 - 2 * 2 23 -120 240 * (23) + 46 * (-120) = 0

Claim Status

Rigour stays visible

Verified Verified Verified Analogy Only
  • Running the Euclidean algorithm on positive integers yields the finite continued fraction of a/b.
  • Extended Euclid produces coefficients x and y with a*x + b*y = gcd(a, b).
  • If gcd(a, b) = 1, the x coefficient from extended Euclid gives the inverse of a modulo b.
  • A single division step can be visualized as q full turns plus a residual phase r/b, but that is an analogy rather than a full autonomous machine.

Fun Fact

c. 300 BCE

Ancient, Still Useful

Euclid's algorithm is one of the oldest named algorithms that is still used directly in modern software.