# How to prove that if a number is divisible by two other numbers, then it is divisible by their product

I would like to prove if $a \mid n$ and $b \mid n$ then $a \cdot b \mid n$ for $\forall n \ge a \cdot b$ where $a, b, n \in \mathbb{Z}$

I'm stuck.
$n = a \cdot k_1$
$n = b \cdot k_2$
$\therefore a \cdot k_1 = b \cdot k_2$

EDIT: so for fizzbuzz it wouldn't make sense to check to see if a number is divisible by 15 to see if it's divisible by both 3 and 5?

• You are possibly thinking of the following: if $a\mid n$ and $b\mid n$ and $a,b$ are relatively prime, then $ab\mid n$. – David May 2 '14 at 0:13
• Re: edit, yes it would make sense because $3$ and $5$ are relatively prime (have no common factor except $1$). See my previous comment. – David May 2 '14 at 0:16
• @David ya that's what I was thinking of. so it needs to be a condition a and b are relatively prime? – Celeritas May 2 '14 at 2:43
• It is a sufficient condition that $a,b$ are relatively prime. – David May 2 '14 at 3:00

## 4 Answers

You are possibly thinking of the following: if $a\mid n$ and $b\mid n$ and $a,b$ are relatively prime (have no common factor except 1), then $ab\mid n$.

Proof. We have $n=ak$ and $n=bl$ for some integers $k,l$. Therefore $b\mid ak$; since $a,b$ are relatively prime this implies $b\mid k$, so $k=bm$, so $n=abm$; therefore $ab\mid n$.

Re: edit, yes this would make sense because $3$ and $5$ are relatively prime.

• how do you know b | ak ? – Celeritas May 2 '14 at 2:45
• Because $n=ak$, see the first equation in the proof. – David May 2 '14 at 2:56
• How to formally prove that: b∣ak; since a,b are relatively prime this implies b∣k? – user394691 Oct 10 '17 at 21:43
• @user394691 Since $a,b$ are relatively prime we have $ax+by=1$ for some integers $x,y$. Hence $akx+bky=k$; and $b\mid akx$ (because $b\mid ak$) and $b\mid bky$ (obviously); so $b\mid akx+bky$, that is, $b\mid k$. – David Nov 5 '17 at 23:30

This is false. For example, 3 | 30 and 6 | 30, but their product, 18, does not divide 30 even though $3 \times 6 < 30$.

Updated: The edited version is still not true. At least two counterexamples in the comments below.

Prior counterexample: This is not true. $12|36$ and $9|36$, but $12\cdot9 = 108 \not | 36$.

• We misread the question this isn't a counter example. – Git Gud May 2 '14 at 0:07
• @GitGud . . . however, replacing $36$ by $36+12\times9$, that is, $144$, does give a counterexample. – David May 2 '14 at 0:10
• Or $(a,b,n)=(4,6,36)$. It's hard to believe someone up voted this when my comment says this isn't a counter example. – Git Gud May 2 '14 at 0:13
• @GitGud: So, ..., I reread and reread the problem. (1) it has not changed and (2) it still claims a falsehood. – Eric Towers May 2 '14 at 1:30
• @EricTowers Yes and your answer still isn't a counter example to statement in the OP's question. – Git Gud May 2 '14 at 1:32

Hint $\,\ a,b\mid n\iff {\rm lcm}(a,b)\mid n\!\!\!\overset{\ \ \ \large \times\, (a,b)}\iff ab\mid n(a,b),\,$ which is not equivalent to $\,ab\mid n\$