Thursday, May 23, 2019

elementary number theory - 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?


Answer



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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...