# Extended Euclidean Algorithm (EEA)

The extended Euclidean Algorithm allows us to calculate $g(a,b)$, and solve the Linear Diophantine Equation for $g(a,b)$ in terms of $a$ and $b$, where $ax+by=g(a,b)$

We know that an answer always exists from Bezout’s Lemma.

LCM and GCD

Recursive

Iterative (i think the way we learned in class)??

There is something very important to observe about the table. If we are computing $g(a,b)$, then for each row of the table we have $ax_{i}+by_{i}=r_{i}$

**Input**: Integers $a$, $b$ with $a≥b>0$
**Initialize**: Construct the table with four columns so that

- the columns are labeled $x,y,randq$,
- the first row in the table is $(1,0,a,0)$,
- the second row in the table is $(0,1,b,0)$.

**Repeat**: For $i≥3$,

- $q_{i}←⌊r_{i−1}r_{i−2} ⌋$
- $Row_{i}←Row_{i−2}−q_{i}Row_{i−1}$

**Stop**: When $r_{i}=0$
**Output**: Set $n=i−1$. Then $g(a,b)=r_{n}$, and $s=x_{n}$ and $t=y_{n}$ are a certificate of correctness.