Divisibility!

Avatar

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

14 Responses

  1. Avatar rmtodd says:

    IIRC, there is actually one for division by 7, but it’s kinda complicated. Martin Gardner gave it in one of his many collections of his Scientific American articles. I don’t recall all the details, but you can probably derive one that’ll work by noting that if you’ve got a 6-digit number N with digits abcdef, then N mod 7 is equal to
    (a*5+b*4+c*6+d*2+e*3+f) mod 7, and if that number is >7, do the same trick with its digits etc. The reason the 5,4,6 numbers etc. are in there is that 5=(10^5 mod 7), 4=(10^4 mod 7), and so on; the sequence of values of the powers of 10 mod 7 turns out to be periodic with period 6.Report

    • Avatar Mike Schilling in reply to rmtodd says:

      Interesting. Using the same technique, you could check for divisibility by 6 by repeatedly adding the units digit to 4 times the sum of the other digits. For 822, for instance, you get 40 + 2 = 42, 16 + 2 = 18, 4 + 8 = 12, and finally 4 + 2 = 6, thus divisible. For 866, the sequence is 56 + 6 = 62, 24 + 2 = 26, 8 + 6 = 14, and 4 + 4 = 8, thus not divisible.Report

  2. Avatar Pete Mack says:

    Divisibility by 7 is easy! Just convert to base 8, then apply the same rule as you use for 9.Report

  3. Avatar Alan Scott says:

    The new trick is (sum of digits in even position) – (sum of digits in odd position) = 0?

    I just guessed based on two and three digit multiples of 11, and then worked out the math:

    Take the number n represented by the digits abcdef, (that is, n = a * 100000 + b * 10000 + c * 1000 + d * 100 + e * 10 + f)

    n = (b * 10000 + d * 100 + f) + (a * 100000 + c * 1000 + e * 10)
    n = (b * 9999 + d * 99 + b+ d + f) + (a * 100001 + c * 1001 + e * 11 – a – c – e)
    n = (b * 9999 + d * 99) + (a * 100001 + c * 1001 + e * 11) + (b + d + f) – (a + c + e)

    99, 9999, and so forth all follow the pattern of 11 * 909…09
    1001, 100001, and so forth all follow the pattern of 9090…9091 * 11Report

    • Avatar Mike Schilling in reply to Alan Scott says:

      Very nicely done, and correct with one small change: the sum of the odd digits minus the sum of the even digits might not be zero, but needs to be a multiple of 11. 605, for instance, is 11 * 55.

      This is another case of the technique rmtodd mentioned, using the fact that the odd powers of ten (10, 1000, 100,000, …) are one less than a multiple of 11, and the even powers (1, 100, 10,000, …) are one greater.Report

  4. Avatar Kazzy says:

    My cat’s breath smells like cat food.Report

  5. Avatar ScarletNumbers says:

    My favorite fact from number theory is:

    ab=gcf(a,b)*lcm(a,b)Report

    • Avatar Mike Schilling in reply to ScarletNumbers says:

      That’s pretty clear if you look at it the right way. gcf(a,b) is the product of the prime factors that a and b have in common. lcm(a,b) is the product of

      1. the prime factors that a has but b doesn’t, times
      2. the prime factors that b has but a doesn’t, times
      3. the prime factors that a and b have in common

      or lcm(a,b) = a/gcf(a,b) * b/gcf(a,b) * gcf(a,b) = (ab)/gcf(a,b)Report

  6. Avatar EB says:

    No promises, but the trick I remember for 7 is:
    Given n-digit number, take off the nth digit, multiply by 2, and subtract the product from the (n-1) digit number. If the result is divisible by 7, the original number is also divisible by 7.

    So for the case of, say, 245:
    5 x 2 = 10
    24 – 10 = 14
    14 is divisible by 7, so 245 is as well.
    Lo and behold, 245/7=35.

    Interestingly, you can repeat for longer numbers and it still works.
    For 1512:
    151-4=147
    14-14=0
    0 is divisible by 7, so 1512 is as well.

    I have no idea why this works.Report

    • Avatar Mike Schilling in reply to EB says:

      I’ve never seen that before, and it is very cool. Here’s why it works:

      First we write 10a + b as a multiplication by 7 plus a remainder between 0 and 6:

      10a + b = 7x + r for some x and r.

      Subtracting from both sides:

      10a + b – 7a = 7x + r – 7a, or
      3a + b = 7(x-a) + r

      We don’t really care about x-a; the important thing is that the remainders are the same.

      Now multiply both sides by 3:

      9a + 3b = 21x-21a + 3r = 21x-21a+7r – 4r

      and subtract this from the original equation:

      a – 2b = 21a-14x-7r + 5r

      Again, we don’t care about 21a-14x-7r, except to notice that it’s always divisible by 7. What’s interesting is that the remainder you get when you divide a-2b by 7 is 5r. (Actually, the remainder is a positive number between 0 and 6, so it may be 5r-7n for n between 1 and 4). That is, if the remainder was 0 to begin with, it still is. So if 10a+b is divisible by 7, so is 2a-b.

      The only question that’s left is if you can start with a non-zero remainder and end up with zero. The answer is no, because there is no r between 1 and 6 for which 5*r is divisible by 7. So 10a+b is divisible by 7 exactly when 2a-b is too.Report

Leave a Reply

Your email address will not be published. Required fields are marked *