Skip to content
OneKitly
Sign up · Sign in

Extended Euclidean algorithm calculator

Run the extended Euclidean algorithm on two integers a and b: it returns their greatest common divisor together with Bézout coefficients x and y satisfying a·x + b·y = gcd(a, b). Beyond the gcd, those coefficients are exactly what you need to build modular inverses and solve linear Diophantine equations. The full division step table is shown so you can follow every reduction.

Related tools

All Numbers & arithmetic tools →
LCM calculatorFind the least common multiple (and GCD) of two numbers.Modular multiplicative inverse calculatorFind a⁻¹ mod m — the number x with a·x ≡ 1 (mod m) — using the extended Euclidean algorithm. An inverse exists exactly when gcd(a, m) = 1; otherwise the tool reports that none exists. The modular inverse is what lets you 'divide' in modular arithmetic and is the step that produces the RSA private exponent d from the public exponent e.Amicable Number CheckerCheck whether two numbers are amicable — or give just one and get its candidate partner plus the verified loop, with perfect and sociable numbers identified.Arctan2 Calculator (atan2 of y and x)atan2(y, x) is not atan(y/x): it reads the signs of both arguments to place the angle in the right quadrant over the full −180°…180° turn, and it stays defined when x = 0. Enter x and y, read the angle in degrees or radians, see the quadrant and the point plotted. For a single ratio with no quadrant information, use the arctan calculator instead.Carry and borrow visualizerAdds or subtracts two whole numbers the way it is taught in school — set up in columns, digit by digit — and highlights every carry (addition) or borrow (subtraction) as it happens. A clear way to see the mechanic behind column arithmetic.Ceiling and floor function calculatorThe ceiling ⌈x⌉ rounds up to the next integer, the floor ⌊x⌋ rounds down. Enter any number to get both, plus the ordinary round, the truncation toward zero and the fractional part left over.Common Factor CalculatorFind every common factor of 2 to 10 numbers, with the greatest common factor highlighted and coprime pairs flagged.Comparing fractions calculatorWhich fraction is bigger? Enter two and it cross-multiplies to compare them exactly — no rounding — and shows both as decimals so you can see how close they are.

The Extended Euclidean algorithm calculator turns a, b into gcd(a, b), Bézout x, Bézout y, Bézout identity, instantly and for free. For instance, with a = 252 and b = 105 it returns gcd(a, b) = 21, Bézout x = -2 and Bézout y = 5.

How to use it

  1. Enter your values: a, b.
  2. Read the result instantly: gcd(a, b), Bézout x, Bézout y, Bézout identity.

Frequently asked questions

What does the Extended Euclidean algorithm calculator actually compute?

It takes a and b and derives gcd(a, b), Bézout x, Bézout y and Bézout identity from them. The calculation is live as you type, so the result updates on every change.

What information do I need to provide?

2 values: a and b. Nothing else is required — no account, no file upload.

Can you show a worked example?

With a = 252 and b = 105, the calculator returns gcd(a, b) = 21, Bézout x = -2 and Bézout y = 5. Those figures come from running this exact tool, so you can reproduce them by entering the same values.

When would I actually use this?

Reading a number written another way: a Roman numeral on a monument, a hexadecimal colour, a binary byte, or a fraction that needs reducing.

What is the most common mistake?

Assuming a decimal fraction survives a change of base. A tenth is exact in decimal and infinitely repeating in binary, which is why 0.1 + 0.2 is not 0.3 in most programming languages.

Where do the figures come from, and how current are they?

Base conversion and number-theory results are exact. Roman numerals follow the standard subtractive form used since the Middle Ages, which is not the only one the Romans themselves used.

Further reading

All guides →
How-toLCM and GCD ExplainedThe GCD is the biggest shared divisor; the LCM is the smallest shared multiple. Here's what each means, how to find them with prime factors, and the shortcut linking them.How-toHow to Simplify a RatioDivide both sides by their greatest common divisor. Here's what a ratio is, how to reduce it, why units must match first, and how to compare ratios.How-toHow to Round Numbers: Round Half Up, Round Half to Even, and MoreRound to any decimal place or number of significant figures, and learn when to use round half up versus round half to even to avoid bias.ExplainerSignificant Figures Explained: Counting, Rounding, and Why They MatterLearn what counts as a significant figure, the rules for leading, trailing, and captive zeros, and how sig figs keep your calculated answers honest.How-toHow to Find Prime Factors: Factor Trees and the Division MethodBreak any whole number into its prime building blocks with a factor tree or repeated division — and write the result as a clean prime factorization with exponents.How-toHow to Multiply and Divide Fractions: Multiply Across, Flip to DivideMultiplying fractions needs no common denominator — just multiply across. Dividing means multiplying by the reciprocal. Learn both with worked examples and how to simplify.