Marcelo Mullins

Answered

2022-07-26

If $gcd(a,c)=1$ and $gcd(b,c)=1$, prove that $gcd(ab,c)=1$

Answer & Explanation

lelapem

Expert

2022-07-27Added 12 answers

to prove that gcd(ab, c) = 1, we need to show that there exists integers x and y such that abx+cy=1 ( using property of relatively prime)

given that gcd(a, c) = 1

so there exists some integers k and l such that

ak+cl=1 ( using property of relatively prime)

given that gcd(b, c) = 1

so there exists some integers m and n such that

bm+cn=1 ( using property of relatively prime)

multiply both equations we get:

$(ak+cl)\cdot (bm+cn)=1\cdot 1\phantom{\rule{0ex}{0ex}}abkm+ackn+cblm+ccln=1$

or

$ab(km)+c(akn+blm+cln)=1$

or abx+cy=1 where x=km and y=akn+blm+cln

because product and sum of integers also give integer.

as we have proved that abx+cy=1, Hence gcd(ab, c) = 1

given that gcd(a, c) = 1

so there exists some integers k and l such that

ak+cl=1 ( using property of relatively prime)

given that gcd(b, c) = 1

so there exists some integers m and n such that

bm+cn=1 ( using property of relatively prime)

multiply both equations we get:

$(ak+cl)\cdot (bm+cn)=1\cdot 1\phantom{\rule{0ex}{0ex}}abkm+ackn+cblm+ccln=1$

or

$ab(km)+c(akn+blm+cln)=1$

or abx+cy=1 where x=km and y=akn+blm+cln

because product and sum of integers also give integer.

as we have proved that abx+cy=1, Hence gcd(ab, c) = 1

Most Popular Questions