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=17, b=5a = 17,\ b = 5

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

Bézout coefficients

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

Least common multiple

85\displaystyle 85

Number of divisions

3\displaystyle 3
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⁡(17,5)=1\gcd(17, 5) = 1.

    17=5×3+25=2×2+12=1×2+0\begin{array}{rcrcrcr} 17 & = & 5 & \times & 3 & + & 2 \\ 5 & = & 2 & \times & 2 & + & 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×5+(−2)×21=(−2)×17+7×5\begin{array}{rcl} 1 & = & 1 \times 5 + \left(-2\right) \times 2 \\ 1 & = & \left(-2\right) \times 17 + 7 \times 5 \end{array}
  3. Bézout's identity

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

    17×(−2)+5×7=−34+35=1\begin{aligned} 17 \times \left(-2\right) + 5 \times 7 &= -34 + 35 \\ &= 1 \end{aligned}
  4. Result

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

Worked examples