# Why is a number that is divisible by $2$ and $3$, also divisible by $6$?

Why is it that a number such as $108$, that is divisible by $2$ and $3$, is also divisible by $6$?

Is this true that all numbers divisible by two integers are divisible by their product?

• Think about the factorization of a number that's divisible by 2 and 3. – Ben Longo Mar 11 '17 at 14:20
• Every number can be expressed as the product of primes. $2$ & $3$ are coprime ... Can you get it from there Jason ? – Donald Splutterwit Mar 11 '17 at 14:21
• Provided the numbers are mutually prime. – SchrodingersCat Mar 11 '17 at 14:22
• note $108 = 2^2 \cdot 3^3 = 3 \cdot (2\cdot 3) \cdot (2 \cdot 3) = 3 \cdot (6) \cdot (6)$ – Dando18 Mar 11 '17 at 14:23
• What about 30, that's divisible by 10 and 15? – Ethan Bolker Mar 11 '17 at 14:23

It is certainly not true that if $x$ is divisible by both $y$ and $z$, then $x$ is divisible by $yz$. For example, $2$ is divisible by $2$ and $2$, but is not divisible by $2\cdot 2$. As a less silly example, $120$ is divisible by both $15$ and $6$, but is not divisible by $90$.

But if you think about the examples above, you'll notice that the factors involved in each overlap: e.g. both $2$ and $2$ are even, and both $15$ and $6$ are divisible by $3$. Meanwhile, $2$ and $3$ don't overlap - they share no factors in common.

It turns out that this is the crucial property:

If $x$ is divisible by $y$ and $z$, and $y$ and $z$ have no factors in common besides $1$, then $x$ is divisible by $yz$.

Proving this is a good challenge. HINT: think about factorization into primes . . .

• There is perhaps something to add here, since there are divisors that fulfil these rules and DO have factors in common, but still divide some number, e.g. in the case $2$ divides $y$ and $z$, and $4$ divides $x$ – samerivertwice Mar 11 '17 at 14:27

It is not true that for any two integers $m$, $n$, if $x$ is divisible by $m$ and $n$, it is divisible by $mn$. For example $4$ is divisible by $4$ and $2$, but it is not divisible by $8$.

However, this is true if $m$ and $n$ are relatively prime, i.e. the greatest common divisor of $m$ and $n$ is $1$. Thus, since $2$ and $3$ are relatively prime, any number divisible by $2$ and $3$ will also be divisible by $6$.

More generally, if $x$ is divisible by $m$ and $n$, then it must be divisible by $\operatorname{lcm}(m,n)$ (least common multiple). Case of $m$ and $n$ being relatively prime is a special case of this, since $$\operatorname{lcm}(m,n) = \frac{mn}{\operatorname{gcd}(m,n)}$$

where $\operatorname{gcd}$ stands for the greatest common divisor and thus $\operatorname{lcm}(m,n) = mn$, when $m$ and $n$ are relatively prime.

Let $a$ be divisible by $2$ and $3$. So $$a=2^{r_{0}}\cdot p^{r_{1}}_{1}\cdot p^{r_{2}}_{2}\cdot\ldots=3^{s_{0}}\cdot q^{s_{1}}_{1}\cdot q^{s_{2}}_{2}\cdot\ldots$$ where $p_{i}$ and $q_{j}$ are distinct prime numbers, $r_{i}$ and $s_{j}$ are possibly $0$ for $1\leqslant i,j<\infty$ and $r_{0},s_{0}\geqslant 1$. We know from the fundamental theorem that these two must be unique factorisations (up to re-ordering). Hence there must be some $p_{k}^{r_{k}}=3^{s_{0}}$ and some $q_{\ell}^{s_{\ell}}=2^{r_{0}}$. Therefore $a$ has a factor of $6$: \begin{align*} a&=2^{r_{0}}\cdot p_{1}^{r_{1}}\ldots\cdot p_{k}^{r_{k}}\cdot\ldots\\ &=2^{r_{0}}\cdot p_{1}^{r_{1}}\ldots\cdot3^{s_{0}}\cdot\ldots\\ &=6\cdot(2^{r_{0}-1}\cdot3^{s_{0}-1}\cdot p_{1}^{r_{1}}\cdot\ldots). \end{align*} (The argument works on the other side as well). This might be a little explicit but I hope it helps.

As the comments point out, and as you may suspect, it is not true in general that if a number is divisible by two integers, then it is divisible by their product. What we can say is the following:

If $x,y,z$ are integers such that $z$ is divisible by both $x$ and $y,$ then $z$ is divisible by the least common multiple of $x$ and $y.$

This isn't actually much of a surprise, given the way that least common multiple is often defined:

Given two integers $x$ and $y,$ the least common multiple of $x$ and $y$ is the nonnegative integer $z$ such that (i) $z$ is divisible by both $x$ and $y,$ and (ii) every common multiple of $x$ and $y$ is divisible by $z.$

Proving that such a multiple exists isn't exactly straightforward, though. It is slightly easier to prove the existence of another integer:

Given two integers $x$ and $y,$ the greatest common factor of $x$ and $y$ is the positive integer $z$ such that (i) both $x$ and $y$ are divisible by $z,$ and (ii) $z$ is divisible by every common factor of $x$ and $y.$

One can, for example, use the Euclidean algorithm to prove that $\operatorname{gcf}(x,y)$ exists, regardless of $x,y.$ At that point, one can show that $\frac{|xy|}{\operatorname{gcf}(x,y)}$ turns out to be the least common multiple of $x$ and $y.$ As an immediate consequence of the identity $$\operatorname{lcm}(x,y)=\frac{|xy|}{\operatorname{gcf}(x,y)},$$ together with the result mentioned at the beginning, we find the following:

If $x,y,z$ are integers such that $z$ is divisible by both $x$ and $y,$ and if $\operatorname{gcf}(x,y)=1,$ then $z$ is divisible by $xy.$

Since $\operatorname{gcf}(2,3)=1,$ then any number divisible by both $2$ and $3$ is necessarily divisible by $6.$

The general result is this:

If a number $n$ is divisible by $a$ and $b$, then it is divisible by $\DeclareMathOperator{\lcm}{lcm}\lcm(a,b)$.

Indeed, let $\;d=\gcd(a,b)$, $\;m=\lcm(a,b)$, $\;a'=\dfrac ad$, $\;b'=\dfrac bd$. These numbers satisfy the relation $$md=ab, \enspace\text{so}\quad m=\frac{ab}d=a'b=ab'.$$ By hypothesis, we can write $$n=qa=qda', \qquad n=rb=rb'd$$ We deduce that $\;qa'=rb'$. So $a'$ divides $rb'$. As $a'$ and $b'$ are coprime, Gauß' lemma ensures $a'$ divides $r$, i.e. we have $r=r'a'$, and $$n=(r'a')b'd=r'(a'b)=r'm.$$