Proof: If each of the equations appearing in the Euclidean Algorithm for a and b is multiplied by k, we obtain,

ak = q_{1}(bk) + r_{1}k; 0 <r_{1}k <bk

bk = q_{2}(r_{1}k) + r_{2}k; 0 < r_{2}k < r_{1}k

……………………………….

r_{n-2}k = q_{n}(r_{n-1}k) + r_{n}k; 0 < r_{nk} <r_{n-1}k

r_{n-1}k = q_{n+1}(r_{n}k) + 0

But this is clearly the Euclidean algorithm applied to the integers ak and bk. So that their greatest common divisor is the last non zero *remainder r _{n}k; that is*

gcd(ka, kb) = r_{n}k = kgcd(a, b)

∴ gcd (ka, kb) = kgcd(a, b) **(Proved).**