# Do we need to apply the Euclidean Algorithm before applying the Extended Euclidean Algorithm?

As the title says, do we need to apply the Euclidean Algorithm before applying the Extended Euclidean Algorithm?

For example, we have $\gcd(24,17)$, so we can find $x,y$ such that $24x+17y=1$. Applying the Euclidean algorithm:

$$\gcd(24,17)=\gcd(7,17)=\gcd(7,3)=\gcd(1,3)=1$$

Applying the Extended Euclidean algorithm:

\begin{align*} 1 &= 7-2\cdot3 \\ &= 7-2\cdot(17-2\cdot7) \\ &= 5\cdot7-2\cdot17 \\ &=5\cdot(24-17)-2\cdot17 \\ &=5\cdot24-7\cdot17 \end{align*}

Is there a way to do this without first applying the Euclidean algorithm?

• It is spelt "Euclidean". And the answer is no. – user21820 Jun 23 '15 at 8:29
• @user21820 Okay, thank you. – wythagoras Jun 23 '15 at 8:32
• As said by @user21820 the answer is no. The extended algorithm is obtained by enhancing the standard one with computation of the Bezout coefficients as you go. en.wikipedia.org/wiki/Extended_Euclidean_algorithm – Yves Daoust Jun 23 '15 at 8:35
• I always thought of them as executed simultaneously, not one after the other... – Arthur Jun 23 '15 at 8:37