I was given a question:
1234567891011121314151617181920 / 3
Is the remainder 0 or not 0?

I did some classic long division to solve this question:
1234567891011121314151617181920 / 3
= 41522630337040438050539060640
R = 0

I thought I did it quickly, but apparently there is a much faster way. Add each digit in 1234567891011121314151617181920 together:
1+2+3+4+5+6+7+8+9 = 45
1+2+3+4+5+6+7+8+9 = 45
1+1+1+1+1+1+1+1+1+1 = 10
0+0+2 = 2
45+45+10+2 = 102

Now add each digit in 102 together:
1+0+2 = 3

3 is divisible by 3, therefore 1234567891011121314151617181920 is divisible by 3.

Prove it

Expand 'abcd' where a, b, c, and d are digits 0 through 9:
'abcd' = a*1000 + b*100 + c*10 + d

1000 can also be expressed as 999+1, so:
'abcd' = a*(999+1) + b*(99+1) + c*(9+1) + d

999 can be expressed as 3*333, so:
'abcd' = a*((3*333)+1) + b*((3*33)+1) + c*((3*3)+1) + d

Multiply a, b, and c in:
'abcd' = ((3*333)a+a) + ((3*33)b+b) + ((3*3)c+c) + d
'abcd' = (3*333*a+a) + (3*33*b+b) + (3*3*c+c) + d
'abcd' = (3*333a+a) + (3*33b+b) + (3*3c+c) + d

Factor out 3, and reorganize:
'abcd' = 3(333a+33b+3c) + (a+b+c+d)

That's a bit fucked up, but it checks out. That still does not prove that this division cheat actually works in all cases.

Now presenting: The Division Algorithm

a / d = Q + R, so a = d * Q + R
Where:
d is the divisor
a is the dividend
Q is the quotient
R is the remainder

The Modulo Operation

a ≅ R (mod d)

Returning to the previous section, we left off at:
'abcd' = 3(333a+33b+3c) + (a+b+c+d)
Since a=dQ+R:
a is 'abcd'
d is 3
Q is (333a+33b+3c)
R is (a+b+c+d)

Then, considering the modulo operation, a ≅ R (mod d):
'abcd' ≅ (a+b+c+d) (mod 3)

Conclusion

I hate mathematicians.

This division cheat works when your divisor is 3 or 9.

Support the Author

Devon Taylor (They/Them) is a Canadian network architect, security consultant, and blogger. They have experience developing secure network and active directory implementations in low-budget and low-personnel environments. Their blog offers a unique and detailed perspective on security and game design, and they tweet about technology, security, games, and social issues. You can support their work via Patreon (USD), or directly via ko-fi.