BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Saturday , July 22 2017
Home / Elementary Number Theory / If k > 0 then gcd(ka, kb) = kgcd(a, b).

If k > 0 then gcd(ka, kb) = kgcd(a, b).

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

ak = q1(bk) + r1k; 0 <r1k <bk

bk = q2(r1k) + r2k; 0 < r2k < r1k

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

rn-2k = qn(rn-1k) + rnk; 0 < rnk <rn-1k

rn-1k = qn+1(rnk) + 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 rnk; that is

gcd(ka, kb) = rnk = kgcd(a, b)

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

Check Also

Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...

Leave a Reply

Your email address will not be published. Required fields are marked *