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

Question

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?

Answer 1

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.

Answer 2

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$.

Answer 3

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

Answer 4

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\ $

Answer 5

If $a$ and $b$ are relatively prime, then $x a + y b = 1$ for some integers $x, y$ (Bezout's identity). Then $$ n = k_1 a \overset{\times yb}{\Leftrightarrow} (yb)n = (yk_1) ab\\ n = k_2 b \overset{\times xa}{\Leftrightarrow} (xa)n = (xk_2) ab $$ Adding the two equations together we get $(xa + yb)n = (yk_1 + x k_2)ab \Leftrightarrow n = k (ab)$, where $k = yk_1 + xk_2$ is an integer. This proves that $ab \mid n$.