Euclidean algorithm Proof

hilly1

Prove that the number of steps of the euclidean algorithm needed to find gcd(km,kn) is exactly the same as the number of steps needed to find gcd(m,n).

any help on this would be appreciated. I'm really lost.

JSuarez

This a consequence of gcd(ka,kb) = |k|gcd(a,b); after applying the euclidean algorithm to gcd(a,b), multiply each of the lines by |k|, and check that this is a valid sequence of divisions (that is, |k|ri is a valid remainder for each of the divisions). The result follows immediately.

Similar Threads for: Euclidean algorithm Proof
Thread	Forum	Replies
Euclidean algorithm	Calculus & Beyond Homework	3
Euclidean algorithm	Set Theory, Logic, Probability, Statistics	2
euclidean algorithm	Calculus & Beyond Homework	4
Dijkstra's algorithm proof?	Engineering, Comp Sci, & Technology Homework	2
Euclidean algorithm	Linear & Abstract Algebra	1

hilly1	Euclidean algorithm Proof Tweet Prove that the number of steps of the euclidean algorithm needed to find gcd(km,kn) is exactly the same as the number of steps needed to find gcd(m,n). any help on this would be appreciated. I'm really lost.

JSuarez	This a consequence of gcd(ka,kb) = \|k\|gcd(a,b); after applying the euclidean algorithm to gcd(a,b), multiply each of the lines by \|k\|, and check that this is a valid sequence of divisions (that is, \|k\|ri is a valid remainder for each of the divisions). The result follows immediately.