Core Algorithm

Quick Calculator

Fast Euclid Output for Trustworthy Spot Checks

Verified Verified

12082 = 5280 * 2 + 1522

5280 = 1522 * 3 + 714

1522 = 714 * 2 + 94

714 = 94 * 7 + 56

94 = 56 * 1 + 38

56 = 38 * 1 + 18

38 = 18 * 2 + 2

18 = 2 * 9 + 0

GCD

Steps

Bezout

12082 * (281) + 5280 * (-643) = 2

Inverse mod b

none

Claim Status

Rigour stays visible

Verified Verified

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).

Fun Fact

c. 300 BCE

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

Related Labs

Sources