3
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – samerivertwice Mar 11 '17 at 14:27
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.