# proof if gcd(a,b)=1 and a|c b|c then ab|c

• Feb 7th 2013, 01:23 PM
dave52
proof if gcd(a,b)=1 and a|c b|c then ab|c
.
• Feb 7th 2013, 01:35 PM
HallsofIvy
Re: proof if gcd(a,b)=1 and a|c b|c then ab|c
That follows pretty quickly from the definition of "greatest common dominator", doesn't it? If gcd(a, b)= 1, then a and b have no common factors. You might try, for one thing, consider the prime factorization of c.
• Feb 7th 2013, 08:10 PM
earthboy
Re: proof if gcd(a,b)=1 and a|c b|c then ab|c
Quote:

Originally Posted by dave52
.

little rigorous proof:

if \$\displaystyle a|c\$ and \$\displaystyle b|c\$ there exists some integers \$\displaystyle r\$ and \$\displaystyle s\$ such that \$\displaystyle c=ar=bs\$
now as \$\displaystyle gcd(a,b)=1\$, we can write: \$\displaystyle 1=ax+by \implies\$ (after multiplying both sides by \$\displaystyle c\$) \$\displaystyle c=acx+bcy\$
after substituting the right expressions for \$\displaystyle c \$ we get \$\displaystyle c=a(bs)x+b(ar)y=(ab)(sx)+(ab)(ry)=ab(sx+ry)\$, which in other words mean \$\displaystyle ab|c\$