Universal divisibility rule

Discussion in 'Math' started by tjohnson, Jul 21, 2015.

  1. tjohnson

    Thread Starter Active Member

    Dec 23, 2014
    614
    121
    One night several years ago, as I lay in bed waiting to fall asleep, I remembered having read that there were easy divisibility rules for each of the numbers 2-10 except 7. Hoping to discover one but not expecting to, I tried to think of a pattern formed with division by 7, and in a few minutes I actually discovered one! I was so excited that I jumped out of bed to tell my father, who was half asleep already.:p

    I had discovered that a number is evenly divisible by 7 if:
    3 * {digits before the last digit, or 0 if there are none} + {last digit}

    is a number evenly divisible by 7. For example, to test 105 for divisibility by 7:
    N = 105
    3 * 10 + 5 = 35
    35 / 7 = 5

    Since we know that 35 is divisible by 7, we can conclude that 105 is as well.

    I later realized that I had discovered a divisibility rule not just for 7, but for all numbers, which was something I had never heard of before. A number is evenly divisible by N if:
    (10 - N) * {digits before the last digit, or 0 if there are none} + {last digit}

    is a number evenly divisible by N.

    My excitement died down eventually, particularly after I found out that someone else had already discovered a simple divisibility rule for 7 that is similar. However, I don't think I have yet heard of a universal divisibility rule. Have any of you?

    My father helped me find a proof for this rule, but I won't publish it yet because I want to give you an opportunity to try to produce it.:D
     
    Last edited: Jul 21, 2015
    atferrari likes this.
  2. WBahn

    Moderator

    Mar 31, 2012
    17,777
    4,805
    All you have discovered is that (10-N) is congruent to 10 in a (mod N) world.

    Let's look at another application of the same principle.

    Is 479325 divisible by 7?

    This is equivalent to determining if 479325 mod 7 = 0.

    We can write this as

    479325 mod 7 = [100(4793) + 25] mod 7 = [100(100(47) + 93) + 25] mod 7

    We can reduce each of these mod 7. For numbers less than 70 we can do this readily using the (hopefully) internalized multiplication table through 10. For numbers greater than 70 we can just subtract 70 first. So this is the same as

    [30(30(47) + 23) + 25] mod 7

    Reducing the two factors of 100 first (because we can do that regardless of the number) we have

    [2(2(47) + 23) + 25] mod 7

    And this would give us the basis for a very fast algorithm to start from.

    Reducing the rest of the numbers we have

    [2(2(5) + 2) + 4] mod 7

    2(5) = 10 = 3 (mod 7)

    [2(3 + 2) + 4] mod 7

    Similarly, 2(3+2) = 10 = 3 (mod 7)

    [3 + 4] mod 7 = 0

    So the number is divisible by 7.

    What to know if a number is divisible by 71? Just follow a similar approach.
     
    tjohnson likes this.
  3. WBahn

    Moderator

    Mar 31, 2012
    17,777
    4,805
    Another way, which is the exact same principle, lets you easily do all the math in your head.

    The basis is that any multidigit, number, say ABCB, can be written as

    ((((A)10 + B)10 + C)10 + D

    We already know that 10 mod 7 is 3, so this becomes

    ((((A)3 + B)3 + C)3 + D

    But we can also reduce each of the digits mod 7 as well.

    So 479325 becomes 402325.

    Applying our algorithm, we have

    4*3 mod 7 = 5
    5+0 mod 7 = 5
    5*3 mod 7 = 1
    1+2 mod 7 = 3
    3*3 mod 7 = 2
    2+3 mod 7 = 5
    5*3 mod 7 = 1
    1+2 mod 7 = 3
    3*3 mod 7 = 2
    2+5 mod 7 = 0

    Since the final result is zero, the original number is divisible by 7.
     
  4. tjohnson

    Thread Starter Active Member

    Dec 23, 2014
    614
    121
    Thanks @WBahn for your proofs. I see that my discovery was nothing remarkable.:oops:

    I seem to have a knack for discovering mathematical relationships before learning about them in my courses.:p I remember how years ago I discovered that (x-1)(x+1)=x^2-1 before learning much algebra, and more recently I discovered that the circumference of a circle is the derivative of its area before learning much calculus. I suppose this shows that I'm good at math (which is substantiated by my ACT math score), but it can be discouraging to find out that what seem to me like amazing discoveries are already well known facts.
     
  5. WBahn

    Moderator

    Mar 31, 2012
    17,777
    4,805
    It's remarkable in that you came up with it on your own. The fact that others came up with it before you doesn't take away from that.
     
    Sinus23, nsaspook and tjohnson like this.
  6. MrAl

    Well-Known Member

    Jun 17, 2014
    2,440
    492
    Hi,

    Yes occasionally you might come up with some interesting rules that help even if they were already discovered. At least you have them now.

    When i took my first calculus course i found a way to approximate factorials to a very high degree of accuracy without having to calculate for every single successive digit like we usually do. I found out later that it worked out to be Sterling's Formula, a formula that had been discovered years before, maybe as far back as the 1930's. But it was still interesting.
    I also found a way to switch base systems that had something to do with a derivative with a juxtaposition of variables. Cant remember what it was now though :)
    I also used to enjoy trying to come up with different ways to calculate the digits of pi, using the simplest way to calculate the maximum number of accurate digits. For example, 22/7 was a common estimate a long time ago.


    It's always fun to discover, even if it is a rediscovery instead.
     
    Last edited: Aug 2, 2015
    tjohnson likes this.
  7. tjohnson

    Thread Starter Active Member

    Dec 23, 2014
    614
    121
    For the number 7, this divisibility rule seems to be the simplest and most popular:
    although I don't understand why it works.

    I looked at Wikipedia's detailed evaluation of divisibility by 7, which actually mentions the rule I discovered:
    but it doesn't mention the universal divisibility rule that can be derived from this.

    Since a universal divisibility rule such as this one exists, I wonder why we were never taught any in school and no one seems to mention them? Do you think it's because it isn't very practical to use in one's head?
     
    Last edited: Aug 8, 2015
  8. WBahn

    Moderator

    Mar 31, 2012
    17,777
    4,805
    To see why it works you need to look at things in a mod-7 world.

    The "universal" rule you are talking about is not taught because much simpler and efficient rules exist for the other single-digit divisors.

    Would you really apply the universal rule to see if a number was divisible by 5? Or 2? Or 4? Or 8? Or 3? Or 6? Or 9?

    Well, that only leaves 7.
     
    tjohnson likes this.
Loading...