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)$
[Math] What’s the difference between the euclidean algorithm and the extended euclidean algorithm
number theory
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$:
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)$.