×

Forget something during Black Friday/Cyber Monday? Check out the Week of Deals!

Blaise Pascal

Member Since: March 4, 2011

Country: United States

  • The key here is that you are taking your number N and breaking it down into two numbers a and b such that N = 10a+b. If you work mod 7, this becomes

    N = 10a + b (mod 7) N = (7+3)a + b (mod 7) N = 7a + 3a + b (mod 7) N = 3a + b (mod 7)

    So 3a+b gives the same remainder divided by 7 as N, and that's your procedure.

    The same reasoning shows why it works for any divisor less than ten. In particular, it shows why the casting out 9's procedure works (or, why in octal, the casting out 7's procedure works for divisibility by 7).

    We can also show why the divisibility rule for 3 works:

    N = 10a+b (mod 3) N = (33+1)a + b (mod 3) N = (33)a + a + b (mod 3) N = a + b (mod 3)

    so N and a+b have the same remainder, mod 3. So you can just add the final digit to the others to get a smaller number with the same remainder, etc.

    It's also generalizable to other bases and divisors: In base B, choose n such that n divides B-1 (so B = kn+1 for some k):

    N = aB + b (mod n) N = a(kn+1) + b (mod n) N = akn + a + b (mod n) N = a + b (mod n)

    So the "sum the digits" rule works for divisibility tests in hexadecimal for 3, 5, and 15 (the divisors of 15).

    More generally, if B = kn+l, then the rule becomes "multiply a by l, then add b"

  • To tie together two of the difficult patches in this article... If you sum the octal digits and get a number divisible by 7, then the original number is divisible by 7.

    For example, 1015 (decimal) = 01767 in octal, and 01+07+06+07 = 025 (octal), and 02+05 = 07 (octal), so 01767 (octal) (or 1015 decimal) is divisible by 7. Which it is. 442 decimal is 0672, and 6+7+2 = 017 (octal), which reduces to 1+7 = 010 (octal), which is not divisible by 7, so 442 is not divisible by 7.

No public wish lists :(