Well I'm working on some mathematics aptitude problem on divisibility. There are certain divisibility rules for numbers 6, 12, 15 etc. which are

  1. If n is divisible by 2 and 3, it is divisible by 6
  2. If n is divisible by 3 and 4, it is divisible by 12
  3. If n is divisible by 3 and 5, it is divisible by 15

So, I applied the above rule on 8 and thought

  1. If n is divisible by 2 and 4, it is divisible by 8

but I found a counterexample 576484 to my intuition and it bust the bubble of my figment. It is divisible by 2 and as well by 4, but not by 8.

Why then it is not divisible by 8? If it is simultaneously divisible by 2 and 4.

Doesn't the rule applies in this case as well? Just like they are applied in the cases of 6, 12, & 15. That is, if factors 'a' and 'b' of number 'n' divides a given number 'm', then 'n' also divides 'm'.

  • 10
    $\begingroup$ More simply, $4$ is a counterexample $\endgroup$
    – Kenta S
    Jan 11 '21 at 1:03
  • 6
    $\begingroup$ The pattern to your first three cases is that the numbers have no common factor. The statement is true so long as your numbers satisfy that, but it fails the moment there's any common factors. $\endgroup$ Jan 11 '21 at 1:05
  • 5
    $\begingroup$ The logical “gotcha” here is that “divisible by 4 and by 2” is redundant! It is like saying “John is a bachelor and unmarried.” The word bachelor already implies John is unmarried, and similarly “divisible by 4” already implies “divisible by 2.” $\endgroup$ Jan 11 '21 at 1:08
  • 3
    $\begingroup$ @Ubihatt FYI, if $a$ is divisible by $b$ and by $c$, then all you can always state is that $a$ is also divisible by the least common multiple of $b$ and $c$, often expressed as $\operatorname{lcm}(b,c)$. Note $\operatorname{lcm}(2,4) = 4$. $\endgroup$ Jan 11 '21 at 1:18
  • 1
    $\begingroup$ Wow, you've come a long way to find that counterexample. $\endgroup$ Jan 11 '21 at 6:31

In general your rule holds if $n$ and $m$ are coprime. Otherwise the common factor may be only one time in the prime factorisation, but is two times in the product.
In your case: $2$ and $4$ are both divisible by $2$, that means you should take $4$ instead of $8$.
There is a great function which works in all cases, the least common multiple $lcm(x,y)$. It can be computed directly by many algorithms and plays an role in lots of mathematical subjects, for example there is an equivalent formulation of the Riemann Hypothesis on the growth of $lcm$.
Since this has already been mentioned in the comments, you can find internet links there as well.


If $n$ is divisible by $4$, then $n$ is divisible $2$, and the second part of your hypothesis is redundant.

Hence the implication reduces to:

If $n$ is divisible by $4$, then $n$ is divisible by $8$, which is not true since we only need two $2$'s in the prime expansion of $n$ to satisfy the hypothesis.

  • $\begingroup$ I just realized this idea is already in a comment, oh well. $\endgroup$
    – Derek Luna
    Jan 11 '21 at 6:27

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.