This post is inspired by a question asked by Dan - thank you, Dan!
So here's the gist of Dan's question:
Take a random sum, e.g. 496866 + 446221 = 943087. Add up all the digits in each number (39, 19 and 31). Keep adding up the digits in each number until you're done: 12, 10 and 4; 3, 1 and 4. Replace each of the numbers in the original sum with the final number and you get something that's true: 3 + 1 = 41 . WHY?!
This is one of my favourite tricks, but I hadn't seen it used exactly this way before. The process in the question - repeatedly adding the digits until you get a single digit - is called finding the digital root.
It's particularly useful for finding out whether you can divide a number by 9 - only numbers with a digital root of 92 are in the 9 times table. For instance, none of the numbers in the sum in the question earlier are multiples of 9. However, 1,035,936 is - you can add its digits up to get 27, which becomes 9. (It's 9 × 115104, by the way).
You can also digital roots to find out if a number is a multiple of 3: if it is, its digital root will be 3, 6, or 9. From earlier, 496,866 is a multiple of 3, but neither of the other numbers are.
Modulo arithmetic is a fancy word for 'doing sums with remainders'. You probably do this most often with clocks - if the big hand points to 45, 20 minutes later it'll be on 5 rather than 65 - you ignore the 60 (on clocks, it's taken care of by the hour hand, but in modulo maths, you just forget it: 65 is the same thing as 5, modulo 60). Modulo 60 just means 'the remainder when you divide by 60' - 65 ÷ 60 = 1, remainder 5.
There's a whole load of university-level maths about modulo arithmetic involving ring theory, equivalence classes and all the rest, but you (probably) don't care about that: what you need to know is that if you do a sum (either add, subtract or multiply3 ) normally and find the answer under a given modulo, you'll get the same answer as if you did the whole sum under the modulo.
For example, if I wanted to work modulo 4: 57 + 94 = 151 = 3 (modulo 4). 57 is the same as 1 (modulo 4) and 94 is 2 (modulo 4), so we end up with 1 (modulo 4) + 2 (modulo 4) = 3 (modulo 4), which I think is right.
Try another one, modulo 7. 32 × 64 = 2048 = 4 (modulo 7). 32 is 4 (modulo 7) and 64 is 1 (modulo 7) - it works again!
Dan's question has us working - for reasons that may become clear shortly - modulo 9. You can verify, if you like, that 496866 is 3 (modulo 9), 446221 is 1 (modulo 9) and 943087 is 4 (modulo 9), but trust me, they are.
All of which begs the big question:
... and the smaller question:
'Only nearly' is the easy one: the digital root of 189 is 9, but 189 is 0 (modulo 9). If you're dividing, you never get a remainder equal to the number you're dividing by! You get a 0 instead. But, luckily, 9 is the same as 0 (modulo 9).
But why should the sum of the digits give you the remainder when you divide by 9? Well... remember all that stuff you did in primary school with hundreds, tens and units? Let's revisit that, and then you can go and play in the sandpit.
Let's take a number like 12345. That's the same as 1 × 10,000 + 2 × 1,000 + 3 × 100 + 4 × 10 + 5.
Now, 10 is 9 + 1; 100 is 99 + 1, and so on. So let's rewrite:
12,345 = 1 × (9,999 + 1) + 2 × (999 + 1) + 3 × (99 + 1) + 4 × (9 + 1) + 5.
Multiply out the brackets and rearrange a bit; you get:
12,345 = (1 × 9,999 + 2 × 999 + 3 × 99 + 4 × 9) + (1 + 2 + 3 + 4 + 5).
That first bracket - I don't know what it is and I don't really care, except that it's a multiple of 9 - each of the numbers added if in there is clearly a multiple of 9. The second bracket is... just the sum of the digits, which is 15 - or 6 (modulo 9). If you do a quick check, 12,345 is indeed the same as 6 (modulo 9).
(As an exercise - try doing it with a normal division method and watch what happens to the remainders - it's always the digital root of all the digits to the left.)
You can use modulo arithmetic to check your answers to arithmetic questions - if you've got the sum right the long way, you can check that it works with the digital roots as well. If it doesn't work, then you've definitely got something wrong; if you get the same answer for both, it doesn't necessarily mean it's right, but it's a good indicator.
Apart from that, modulo arithmetic can seem pretty abstract and useless (I certainly thought of it that way through first year at university). However, it turns out that modulo arithmetic is what keeps the internet working. The RSA algorithm is pretty much the state of the art in public-key cryptography - and it works on the back of modulo arithmetic. In particular, it works because dividing is very difficult with modulos, even for computers - but more on that another time. This post is already longer than I meant it to be, and I need some coffee.
* Edited 2015-07-08 to fix footnotes.
* Edited 2016-04-15 to fix them again.
* Edited 2017-08-01 to correct a 6 to a 4. Thanks to Richard Olsen for pointing out the error.