Divisibility Rules: Why are 3 & 9 Special?

We look in depth at why the rule "divisible by 3 or 9 if and only if the sum of digits is" works for 3 and 9, but not for other numbers (in base 10). To gain a better understanding, we also explore similar rules in different bases.

00:00 Intro
00:43 Illustrative example
02:59 More formal proof
06:33 Bigger picture: different bases
08:09 Other divisibility rules

[yakovify]

I've always had a personal conjecture that this worked in base n with n-1 but never thought too hard about it. Glad to see other people thinking about it too! Keep up the amazing content :).

[nathanisbored]

another fun one to analyze is why 'a number ending in an even digit multiplied by 6 always ends in the same even digit'. my boyfriend who knows i like math noticed this and ask me about it a couple weeks ago.

i thought about it for awhile and realized it basically has to do with the fact that 10 = 2 * 5, and 6 is 1 mod 5. so multiplying by 6 changes nothing in base 5, and therefore multiplying by 6 changes nothing in base 10 as long as theres also a factor of 2 in there.

and it turns out this works similarly for a base like 3 * 5 (base 15). this time multiplying by 6 doesnt change the last digit if the last digit is a multiple of 3 (in base 15). or you could also change the magic number from 6 to something else if you play around with the factors of the base.

[landsgevaer]

So, using binary, a number is divisible by 1 if the sum of its binary digits is divisible by 1. Amazing!

On a more serious note, in base N, a number is divisible by N+1 if the difference of the sums of odd and even digits is divisible by N+1 (with the same generalization for its factors)!

[Jack_Callcott_AU]

I wonder if it's possible for both (n-1) and n to have a lot of divisors. If so, n would be a good base for a number system. For base 16 there are 4 divisors (not counting 1), and for (16-1) = 15, there are 3. It seems hexadecimal would be a better number system for everyday use.

[nicolastorres]

Just from looking at the thumbnail: Because 10 is congruent to 1 mod each of them. So for every natural n, 10^n is congruent to 1^n = 1

[kruksog]

10 mod 3 and 10 mod 9 are both 1. The rest kind of falls out from there, but that's what I always remember.

[RGP_Maths]

I was surprised you bothered to write out the binomial theorem, since 10≡1 (mod 9) immediately shows 10^k≡1 (mod 9), and likewise mod 3.

[wesleydeng]

Divisibility of 11's rule is also a consequence of base 10. There is no simple rule for 7 is because 7 is coprime to 9, 10, 11.

[holyshit]

In hexadecimal system we have nice divisibility rule for 3, 5 and F ?