 If "g" is the GCD of "a" and "b", then "a" = "mg" and "b" = "ng" for two coprime numbers "m" and "n".Then

as may be seen by dividing all the steps in the Euclidean algorithm by "g".By the same argument, the number of steps remains the same if "a" and "b" are multiplied by a common factor "w"