Prove the following for any integers a b and c For each of t

Prove the following, for any integers a, b, and c. For each of these problems, you will need only the definition of the gcd. 1 If a >0 and a|b, then gcd(a, b) = a.

Solution

we need to prove that if a > 0 and a|b , then gcd(a,b) = a

we will use one property of gcd to prove the above statement

we know that from the properties of the gcd

1) gcd(ka,kb) = k* gcd(a,b)

2) gcd(1 , k) for k > 0 is 1

now as given a|b means a divide b so we can say that if a divides b then there exists k such that a = bk where k is not equal to 0

hence we can say that gcd(a,b) = gcd(a,ak)

from property 1) we know that gcd(a,ak) = a * gcd(1,k) so,

gcd(a,b) = a * gcd(1,k)

from property 2) we know that gcd(1,k) = 1 so

gcd(a,b) = a * 1 = a

hence we have proved that if a > 0 and a|b then gcd(a,b) = a