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=240, b=46a = 240,\ b = 46

gcd⁡(240,46)=2=240×(−9)+46×47\displaystyle \gcd(240, 46) = 2 = 240 \times \left(-9\right) + 46 \times 47

Bézout coefficients

x=−9, y=47\displaystyle x = -9,\ y = 47

Least common multiple

5520\displaystyle 5520

Number of divisions

5\displaystyle 5
Show the work
  1. Euclidean algorithm

    Divide the larger number by the smaller, then the smaller by the remainder, and so on. The last non-zero remainder is gcd⁡(240,46)=2\gcd(240, 46) = 2.

    240=46×5+1046=10×4+610=6×1+46=4×1+24=2×2+0\begin{array}{rcrcrcr} 240 & = & 46 & \times & 5 & + & 10 \\ 46 & = & 10 & \times & 4 & + & 6 \\ 10 & = & 6 & \times & 1 & + & 4 \\ 6 & = & 4 & \times & 1 & + & 2 \\ 4 & = & 2 & \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.

    2=1×6+(−1)×42=(−1)×10+2×62=2×46+(−9)×102=(−9)×240+47×46\begin{array}{rcl} 2 & = & 1 \times 6 + \left(-1\right) \times 4 \\ 2 & = & \left(-1\right) \times 10 + 2 \times 6 \\ 2 & = & 2 \times 46 + \left(-9\right) \times 10 \\ 2 & = & \left(-9\right) \times 240 + 47 \times 46 \end{array}
  3. Bézout's identity

    So there are whole numbers x=−9x = -9 and y=47y = 47 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

    240×(−9)+46×47=−2160+2162=2\begin{aligned} 240 \times \left(-9\right) + 46 \times 47 &= -2160 + 2162 \\ &= 2 \end{aligned}
  4. Result

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

Worked examples