Extended Euclidean Algorithm

Revisiting An Old Friend

The steps for deriving gcd(1180, 482) = 2, and its linear combination of a*x + b*y = gcd, where it presents itself as (1180*-29) + (482*71) = 2.

The left hand side is the Euclidean Algorithm, and the right hand side (where the linear combination is derived) is the Extended Euclidean Algorithm.

The steps are as follows:

latex below

\begin{align*}
1180 &= (482 \times 2) + 216 \\
482 &= (216 \times 2) + 50 \\
216 &= (50 \times 4) + 16 \\
50 &= (16 \times 3) + 2 \quad \text{-----------------}| \\
16 &= (2 \times 8) + 0 \quad \quad \quad \quad \quad \quad \quad | \\
   & \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad | \\
   & \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad | \text{--------------->} \text{ } 2 = 50 + (16 \times -3) \\

   & \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad 
      \quad \quad \quad \quad \quad \quad \quad \text{} = 50 + (216 + (50 \times -4)) (-3) 
\\
   & \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad 
      \quad \quad \quad \quad \quad \quad \quad \text{} = (216 \times (-3))…