Extended Euclidean Algorithm Calculator

Enter two integers to find their gcd and the numbers x and y.

A whole number.

A whole number.

Try

Result

You entereda=3, b=5a = 3,\ b = 5

gcd⁡(3,5)=1=3×2+5×(−1)\displaystyle \gcd(3, 5) = 1 = 3 \times 2 + 5 \times \left(-1\right)

Bézout coefficients

x=2, y=−1\displaystyle x = 2,\ y = -1

Least common multiple

15\displaystyle 15

Number of divisions

4\displaystyle 4
Show the work
  1. Euclidean algorithm

    Divide the first number by the second, then the second by the remainder, and so on; because 33 is smaller than 55, the first division has quotient 00 and only swaps them. The last non-zero remainder is gcd⁡(3,5)=1\gcd(3, 5) = 1.

    3=5×0+35=3×1+23=2×1+12=1×2+0\begin{array}{rcrcrcr} 3 & = & 5 & \times & 0 & + & 3 \\ 5 & = & 3 & \times & 1 & + & 2 \\ 3 & = & 2 & \times & 1 & + & 1 \\ 2 & = & 1 & \times & 2 & + & 0 \end{array}
  2. Back-substitution

    Each division says that a remainder is the number before the previous one minus a multiple of the previous one. Substituting upwards from the last step writes the gcd as a combination of the two starting numbers.

    1=1×3+(−1)×21=(−1)×5+2×31=2×3+(−1)×5\begin{array}{rcl} 1 & = & 1 \times 3 + \left(-1\right) \times 2 \\ 1 & = & \left(-1\right) \times 5 + 2 \times 3 \\ 1 & = & 2 \times 3 + \left(-1\right) \times 5 \end{array}
  3. Bézout's identity

    So there are whole numbers x=2x = 2 and y=−1y = -1 with ax+by=gcd⁡(a,b)ax + by = \gcd(a, b). Checking by multiplying out confirms it.

    Using gcd⁡(a,b)=ax+by\gcd(a, b) = a x + b y

    3×2+5×(−1)=6+(−5)=1\begin{aligned} 3 \times 2 + 5 \times \left(-1\right) &= 6 + \left(-5\right) \\ &= 1 \end{aligned}
  4. Result

    So gcd⁡=1\gcd = 1, with x=2x = 2 and y=−1y = -1.

Worked examples