[Math] What’s the difference between the euclidean algorithm and the extended euclidean algorithm

number theory

What does the euclidean algorithm compute, and what problems is the extended euclidean algorithm used for? Can someone please show how they each differ on the pair $(210,65)$

Best Answer

Well, there are lots of pages written about that, yet I'll try explain it in the simplest way. Given two integers $a$ and $b$:

  • the Euclidean Algorithm computes $GCD(a,b)$
  • the Extended Euclidean Algorithm gives out 2 integers $x$ and $y$ such that $ax+by=GCD(a,b)$; mainly used when $GCD(a,b) = 1$

There is a page giving a clear example of the differences between the Algorithms. In your case $(a=210,b=65)$ aplying the Euclidean Algorithm: \begin{cases} 210 = 65\cdot 3+15\\ 65 = 15\cdot 4 +5\\ 15 = 5\cdot 3 \Rightarrow GCD(210,65) = 5 \end{cases}

Instead, if we wish to find 2 integers $x$ and $y$ such that $210x+65y=GCD(210,65)=5$, we use the Extended Euclidean Algorithm:

\begin{cases} 5 = 65-15\cdot4\\ 5 = 65-(210-65\cdot 3)\cdot4\\ 5= 210\cdot -4 + 65\cdot 13 \Rightarrow (x,y) = (-4,13) \end{cases} The couple $(x,y)$ is also called pair of Bézout coefficients, and as you can imagine a pair can be found by using the Extended Euclidean Algorithm, but there are infinite couples $(x,y)$ which satisfy the equation $ax+by=GCD(a,b)$.

Related Question