Topic : Greatest Common DivisorQuestion : Prove that gcd(a,c)=gcd(b,c)=1 if and only if gcd(ab,c)= 1, where a,b and c are integers..
Hint:If gcd(a,c)=1, then there exists real numbers x and y such that ax+by=1.
Answer : Suppose first that (a,c)=1 and (b,c)=1
hence there exist integers x1 and y1 such that a.x1 + c.y1 = 1
also there exist integers x2 and y2 such that b.x2 + c.y2 = 1
hence a.x1 = 1 - c.y1 and
b.x2 = 1 - c.y2
hence (a.x1)(b.x2) = (1 - c.y1) (1 - c.y2 ) = 1 - c.y1 - c.y2 + c^2 . y1 .y2
hence ab(x1.x2) + c ( y1 + y2 - c . y1 . y2 ) = 1
hence (ab,c)=1
conversly
suppose that (ab,c)=1
we need to show that (a,c)=1 and (b,c)=1
Let
(a,c)= d
hence d divides a and d divides c
hence d divides ab and d divides c
hence d divides (ab,c) , but (ab,c)=1
hence d divides 1
hence d=1
hence (a,c)= 1
similarly we can show that (b,c) =1
Hope the proof did the needful.
Hint:If gcd(a,c)=1, then there exists real numbers x and y such that ax+by=1.
Answer : Suppose first that (a,c)=1 and (b,c)=1
hence there exist integers x1 and y1 such that a.x1 + c.y1 = 1
also there exist integers x2 and y2 such that b.x2 + c.y2 = 1
hence a.x1 = 1 - c.y1 and
b.x2 = 1 - c.y2
hence (a.x1)(b.x2) = (1 - c.y1) (1 - c.y2 ) = 1 - c.y1 - c.y2 + c^2 . y1 .y2
hence ab(x1.x2) + c ( y1 + y2 - c . y1 . y2 ) = 1
hence (ab,c)=1
conversly
suppose that (ab,c)=1
we need to show that (a,c)=1 and (b,c)=1
Let
(a,c)= d
hence d divides a and d divides c
hence d divides ab and d divides c
hence d divides (ab,c) , but (ab,c)=1
hence d divides 1
hence d=1
hence (a,c)= 1
similarly we can show that (b,c) =1
Hope the proof did the needful.
No comments:
Post a Comment