Euclid steps

GCD, LCM and Bézout, one line at a time.

For checking your work after you’ve tried it yourself.

Step 1:
Type two numbers

Whole numbers, not both zero.

Each division appears as a line.

gcd, lcm and the Bezout pair, then Do it by hand.

What it does.

Runs the Euclidean algorithm line by line to find the greatest common divisor, the lowest common multiple, and whole numbers

x, y

with

ax + by = \gcd(a, b)

When it helps.

Checking a gcd, an lcm or a Bezout pair you found by hand.

What it won’t do.

Two numbers at a time, up to

10^{18}

in size.

Example.

\gcd(240, 46) = 2

, and

240 \cdot (-9) + 46 \cdot 47 = 2

Two whole numbers, not both 0

a

b

Up to $10^{18}$ either way. Negative numbers are fine.

Try