Extended Euclidean Algorithm Calculator screenshot

Extended Euclidean Algorithm Calculator

Return gcd(a, b) together with the integers s and t that satisfy a·s + b·t = gcd, exactly.

Privacy First
0 Runs
Updated 2026-11-22
Runs in your browser
No sign-up, no upload
Exact where arithmetic allows

Extended Euclidean Algorithm Calculator

Return gcd(a, b) together with the integers s and t that satisfy a·s + b·t = gcd, exactly.

What the page prints, and what it refuses

Every figure is printed with the rule or formula that produced it, and any numerical tolerance is stated on the result rather than implied. The page refuses an input the formula does not define and names the value it read; it prints no answer it cannot support.

The calculation runs entirely in this browser tab; nothing is uploaded.

The page runs the extended Euclidean algorithm on two integers. For 240 and 46 it returns a gcd of 2 with s = −9 and t = 47, because 240 × (−9) + 46 × 47 = 2.

The identity is printed with the actual values substituted, so the coefficients can be checked by arithmetic rather than trusted. Negative inputs are handled, and the returned gcd is always non-negative.

What the coefficients prove

Each Euclidean step replaces a remainder by an earlier one, and carrying the quotients along expresses the final non-zero remainder as a whole-number combination of the original pair. That combination is the Bézout identity.

It matters because a·s + b·t = 1 is exactly the statement that a and b are coprime, and the same coefficients give the modular inverse. The page prints the lcm as well, which is ab ÷ gcd.

How to use Extended Euclidean Algorithm Calculator

Enter the two integers, positive or negative, then press Run.

The first line is the gcd, the next two are s and t, and the identity line substitutes all four values.

What to Expect

Best for

  • Finding Bézout coefficients exactly
  • Checking a modular inverse by hand
  • Seeing the identity that proves coprimality

Not ideal for

  • A single integer on its own
  • Floating-point coefficients, which this page does not produce
  • gcd(0, 0), which has no Bézout pair

What this tool keeps

  • Both integers and their signs

What may need cleanup

  • Nothing: the coefficients are exact integers

Common errors

  • gcd(0, 0) is refused as having no pair
  • A decimal input is refused by name

Example use cases

  • Find s and t for 240 and 46
  • Prove that 35 and 64 are coprime
  • Check a modular inverse

Sample input

a = 240, b = 46

Sample output

gcd = 2, s = −9, t = 47, and 240×(−9) + 46×47 = 2

Who this is for

  • Number theory students
  • Programmers implementing a modular inverse

Frequently asked questions

Are the coefficients unique?

No. Adding b/g to s and subtracting a/g from t gives another valid pair. The page prints the pair the algorithm returns, which is the one with the smallest coefficients.

Why is the gcd always non-negative?

The greatest common divisor is a positive count, so the page normalises the sign at the end. A negative result would be a different object.

What is this used for?

The same coefficients give a modular inverse when the gcd is 1. The page prints the identity so the link to that calculation is visible.

Developer program

Build custom tools for your store

Join the SDK program to create useful ecommerce utilities for your store.