Prove: If $c \ge ab$ and $a|c$ and $b|c$ then $ab|c$.

If $a|c$ and $b|c$ then there are integers $p$ and $q$ such that

$ap=c$ and $bq=c$

All of my work has boiled down to substitutions, a lot of them. My intuition has been pointing towards the inequality, but I'm not sure how to implement it.

I've attempted manipulating a diophantine equation, but I'm not sure if I have enough prior results available to use anything like ax+cy=1.

I've found this question which was somewhat similar.

  • 3
    $\begingroup$ That's not true. Try $a=4, b=4$ and $c=24$. $\endgroup$ – N. S. Nov 1 '11 at 4:01
  • 1
    $\begingroup$ Is there a condition that $(a,b)=1$? $\endgroup$ – yunone Nov 1 '11 at 4:02
  • $\begingroup$ No there is no specification such as (a,b)=1. Also, a quick question about notation. Is (a,b)=1 the same as gcd(a,b)=1? That's slightly flustering. I attempted this problem for a long time before asking for help. If there's anything that I've learned it's that I need to attempt more examples like @arturomagidin. $\endgroup$ – user17366 Nov 1 '11 at 4:11
  • $\begingroup$ Ok, without that condition it's false. And yes, $(a,b)$ is another way to write $\gcd(a,b)$, both are pretty standard. $\endgroup$ – yunone Nov 1 '11 at 4:23

The statement you want to prove is false in general.

Take $c=330$, $a=6$, $b=15$. Then $a|c$, $b|c$, $ab = 90\leq c$, but $ab=90$ does not divide $c=330$.

Essentially, the problem is that if $\gcd(a,b)\gt 1$, then you could have prime factors show up to "too large" a power in $ab$; you can ensure $ab\leq c$ easily enough by adding large prime factors that don't involve $a$ and $b$. Above, I took $a=2\times 3$, $b=3\times 5$, and then started with $2\times 3\times 5$, and then multiplied by $11$ to ensure it was large enough.

  • 2
    $\begingroup$ A smaller example is $a=b=2$, $c=6$. $\endgroup$ – Gerry Myerson Nov 1 '11 at 4:43
  • $\begingroup$ @Gerry: Sure. For some reason, I was stuck on $a\neq b$, neither a multiple of the other; even then, of course, a smaller example would have $b=10$ instead of $15$. $\endgroup$ – Arturo Magidin Nov 1 '11 at 4:51
  • $\begingroup$ Even with $a=6$, $b=15$, one could take $c=120$. $\endgroup$ – Gerry Myerson Nov 1 '11 at 5:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy