Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
3  
That's not true. Try $a=4, b=4$ and $c=24$. –  N. S. Nov 1 '11 at 4:01
1  
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

1 Answer 1

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|improve this answer
2  
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

 
discard

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