Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
That's not true. Try $a=4, b=4$ and $c=24$. – N. S. Nov 1 '11 at 4:01
Is there a condition that $(a,b)=1$? – yunone Nov 1 '11 at 4:02
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. – user17366 Nov 1 '11 at 4:11
Ok, without that condition it's false. And yes, $(a,b)$ is another way to write $\gcd(a,b)$, both are pretty standard. – yunone Nov 1 '11 at 4:23
up vote 4 down vote accepted

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.

share|cite|improve this answer
A smaller example is $a=b=2$, $c=6$. – Gerry Myerson Nov 1 '11 at 4:43
@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$. – Arturo Magidin Nov 1 '11 at 4:51
Even with $a=6$, $b=15$, one could take $c=120$. – Gerry Myerson Nov 1 '11 at 5:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.