# 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. Jun 23, 2015 at 8:29
• @user21820 Okay, thank you. Jun 23, 2015 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
– user65203
Jun 23, 2015 at 8:35
• I always thought of them as executed simultaneously, not one after the other... Jun 23, 2015 at 8:37