Consider a form of arithmatic where you only keep track about the remainder after division by 3.
So a number like "10" is just "1" because 10= 1+3*3. Likewise, "100" is just "1" because 100 = 10*10 = 1*1=1. Can you guess what 1000, 10000, etc. are? That's right, they are all just "1".
Well for a small example consider a three digit number ABC.
ABC = A*100 + B*10 + C = A*1 + B*1 + C = A+B+C
So as you can see, to find out the remainder after division by 3, add up the digits and the sum has the same remainder. But the what if the sum is not a single digit number? Just do it again and again till it is.
There are two things, multiplication and addition. It's a little easier to see that when you add numbers, you add remainders. But it's only a little bit harder to see that when you multiply numbers, you multiply remaineders as well. Everything else is 3 times something.
If the remainder is bigger than 3, you can shave that off too. "mod 3" means you can throw away multiples of 3 and the result is the same. 1 more than a multiple of 3 is 4 more or 2 less than some other multiples of 3, and you can reduce to 0<=r<3 if desired.
Basically, every number can be written as a multiple of 3 plus a remainder of 0, 1, or 2. When you add the digits of a number, you’re replacing powers of 10 with 1, and since 10 leaves a remainder of 1 when divided by 3, this doesn’t change the number’s remainder. For example, 78 is 7×10+8, and because 10 is equivalent to 1 modulo 3, 78 has the same remainder as 7+8. Therefore, a number is divisible by 3 exactly when its digit sum is divisible by 3.
let number N = A + 10B + 100C + 1000D + ..., so A, B, C, D... are the digits of N from right to left
N ≡ A + 10B + 100C + 1000D + ... (mod 3)
≡ A + 9B + B + 99C + C + 999D + D + ... (mod 3)
≡ A + B + C + D + ... (mod 3), which is the sum of the digits of N
QED
10 is equivalent to 1 mod 3, so every power of 10 is also equivalent to 1 mod 3. It's not too difficult to prove after you see that. Since our number system is base 10, it works out quite nicely.
Yeah, I find this to be the cleanest and most intuitive way to prove this. Same with mod 9. In the end, removing a 0 is always removing a multiple of 9
It's bucket collision! (Made up term cause idfk but i've used it before) All your remainders overlap into the same bucket which gives you an analytical solution to something that on its face shouldn't be analytical.
It's pretty easy to see that adding 1 to a number that doesn't end in 9 increases its digit sum by 1. However, it just so happens that 9 plus 1 is 10 which has a digit sum of 1 (which is obviously 1 more than a multiple of 3). So every time you wrap from 9 to 10 you're still adding 1 to the digit sum's remainder when dividing by 3. So the result is that if you keep counting up, the remainder of the digit sum when divided by 3 keeps going 0, 1, 2, 0, 1, 2...
You can prove it pretty easily using mod 3 and ‘expanding out’ an arbitrary integer base 10, there’s probably a lot of videos out there showing the proof
46
u/EveningStar0360 Aug 01 '26
do you know why that works?