1
$\begingroup$

Here is what I am trying to prove:

Let $a,b,c,d \in ℤ_+$ with gcd$(a,b)=1$. If $a|c$ and $b|c$, prove that $ab|c$. Does the result hold if gcd $(a,b)\neq 1$ ?

I know that gcd $(a,b)=1$ can be written $ax+by=1$ where $x,y$ are integers. And $a|c$ can be written $c=al$ where $l$ is an integer, b|c can be written $c=bk$ where $k$ is an integer, and $ab|c$ can be written $c=ab(m)$ where $m$ is an integer.

What do I do?

$\endgroup$
1
  • $\begingroup$ You can prove in general: if $a\mid c$ and $b\mid c$, then $\operatorname{lcm}(a,b)\mid c$. You can approach this problem symbolically using prime factors if you want. $\endgroup$
    – Ian Coley
    Mar 19 '14 at 20:02
1
$\begingroup$

Since $ax+by=1$ hence $acx+bcy=c$. Divide throughout by $ab$ to get $cx/b$ + $cy/a$ = $c/ab$. But $b|c$ and $a|c$ hence LHS is an integer and so is RHS $\Rightarrow$ $ab|c$. The result is false if gcd$(a,b)\neq 1$. Take $a=4,b=2$ and $c=12$.

$\endgroup$
0
$\begingroup$

If a divides c, then there exists a positive integer m say, such that

$c = ma$ (1)

Likewise, b|c => that there exists $n$, such that

$c = nb$ (2)

Multiplying both sides of (1) by $b$ and both sides of (2) by $a$ gives :

$bc = mab$ (3)

$ac = nab$(4)

Subtracting both sides of (4) from those of (3):

$$(b - a)c = (m - n)ab$$

So either $ab|(b-a)$ or $ab|c$

$ab|(b-a) <=> a = b $

But $gcd(a, b) = 1$ , so this is not possible .

So therefore $ab|c$

$\endgroup$
0
$\begingroup$

Hint $\,\ a,b\mid c \iff ab\mid ac,bc\iff ab\mid \gcd(ac,bc) = \gcd(a,b)c$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.