1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ It is spelt "Euclidean". And the answer is no. $\endgroup$ – user21820 Jun 23 '15 at 8:29
  • $\begingroup$ @user21820 Okay, thank you. $\endgroup$ – wythagoras Jun 23 '15 at 8:32
  • 1
    $\begingroup$ 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 $\endgroup$ – Yves Daoust Jun 23 '15 at 8:35
  • 2
    $\begingroup$ I always thought of them as executed simultaneously, not one after the other... $\endgroup$ – Arthur Jun 23 '15 at 8:37
2
$\begingroup$

As the name suggests the extended Euclidean algorithm is an extension of the classical algorithm, which means the normal Euclidean algorithm is part of the extended Euclidean algorithm. normal: Provides gcd extended provides gcd + the 2 numbers x,y such that gcd= nx + my whereas n,m are the input numbers

So to answer your original question, yes you don't have to compute the classic Euclidean since you get the gcd at the end.

Look at this simple example from Wikipedia.

I hope this is useful for you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.