Divisibility!

Mike Schilling

Mike has been a software engineer far longer than he would like to admit. He has strong opinions on baseball, software, science fiction, comedy, contract bridge, and European history, any of which he's willing to share with almost no prompting whatsoever.

Related Post Roulette

6 Responses

  1. Jaybird says:

    Okay, so my brain hurts, but this is making me wonder…

    Clock 10 has 9 numbers that have quick and dirty tricks to help you figure out divisibility. (Well, two gimmies and 7 others (2, 3, 4, 5, 6, 8, 9)) leaving only one number that is legitimately tricky.

    Is this representative of a pattern? I suppose that nobody uses any Clocks other than 10 with any frequency, though. Well, not to the point where we need to learn division…Report

    • Mike Schilling in reply to Jaybird says:

      The following are true for any base N:

      1. If M divides N evenly, you only need to check the units digit, because the rest is obviously divisible by M. In base 10, that gives us 2 and 5.
      2. If M is the k’th power of a number that divides N evenly, you only need to check the rightmost k digits, because the rest is obviously divisible by M. In base 10, that gives us 4 and 8.
      3. For N-1, you can do the trick of adding up all the digits.. In base 10, that gives us 9.
      4. If M is a root (square root, cube root, etc.) of N-1, you can also do the trick of adding up all the digits. In base 10, that gives us 3.
      5. For N+1, you can do the trick of subtracting the sum of the even digits from the sum of the odd digits. In base 10, that gives us 11.
      6. If M is a root (square root, cube root, etc.) of N+1, you can also do the trick of subtracting the sum of the even digits from the sum of the odd digits. That doesn’t help in base 10, because 11 is prime, but in base 8 that would give us 3.
      7. If M is K*L, and K and L are relatively prime, and there are tests for both of those, do both tests. In base 10, that gives us 6.

      7 is tricky because none of these apply.

      So, looking at some other simple bases:

      • Base 4 has tricks for 2 by rule 1, 3 by rule 3, and 5 by rule 5.
      • Base 6 has tricks for 2 and 3 by rule 1, 4 by rule 2, 5 by rule 3, and 7 by rule 5.
      • Base 8 has tricks for 2 and 4 by rule 1, 3 by rule 6, 6 by rule 7, 7 by rule 3, and 9 by rule 5. 5 is tricky.
      • Base 12 has tricks for 2, 3, 4, and 6 by rule 1, 8 and 9 by rule 2, 11 by rule 3, and 13 by rule 5. 5, 7, and 10 are tricky.

      Report

  2. EB says:

    I assume that my fifth grade math teacher had all that in mind at the time 🙂

    Thanks for the explanation, will have to take some time to digest.Report

  3. Kazzy says:

    My cat’s breath smells like cat food.Report

  4. Murali says:

    Which part of this diversion is mindless?Report