Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euclidean algorithm Proof

  1. Dec 21, 2009 #1
    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.
  2. jcsd
  3. Dec 21, 2009 #2
    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Euclidean algorithm Proof Date
Euclidean Algorithm Gaussian Integers Aug 6, 2014
Extended Euclidean Algorithm May 17, 2011
Efficiency and the Euclidean Algorithm Feb 10, 2011
Euclidean algorithm congruences May 7, 2009