Writing Assignment 2: Due Monday March 7, 2011

[Note: the symbol "≡" is supposed to be the three line equals sign that means
having the same remainder modulo a number. There may be some browsers that don't interpret the html code for this three line equals symbol correctly, and if you're using such a browser, just keep in mind that whenever you see
"≡" it's supposed to be the three line equals symbol.]

Suppose a fellow teacher has heard that you can find the remainder of a number when dividing by 9 by adding up its digits, but wonders why it works. The writing assignment is to explain how and why this works.

Start with an introduction that explains the issue you are addressing.

Your write up should then explain how you can find the remainder by adding up the digits of a number. (If after adding up the digits you get a number with more than 1 digit, what do you do? What do you do if you get a sum of 9?) It should also explain why it works. (Explain it in terms of remainder arithmetic and our usual base 10 place value system. For example, using remainder arithmetic modulo 9, we have 345 = 3x10^{2} + 4x10 + 5x1 which reduces to 345 ≡ 3x1 + 4x1 + 5x1 = 3 + 4 + 5 = 12 mod 9 and in the same way 12 ≡ 1 + 2 = 3 mod 9, so the remainder when you divide 345 by 9 is 3. But explain why any power of 10 is 1 mod 9, so this works also for 4 digit numbers and in fact for any number.) You should also give some examples to show that this does not work modulo other numbers; e.g., the remainder of 345 when dividing by 7 is not 3.

**In case you're interested**: Some teachers may spend some time teaching numbers written in other bases, so your teacher audience may be interested to know that this trick does work for dividing by 7, but you have to use base 8. Not everyone, by the way, always uses base 10. In computer science base 8 (octal) is important, for example. The trick of adding up the digits to find the remainder also works when dividing by other numbers if you use the right base. (In base 10 we can find the remainder when dividing by 9 of a number written in base 10 by adding up the digits in base 10; in base 8 we can find the remainder when dividing by 7 of a number written in base 8 by adding up the digits in base 8; in base 12 we can find the remainder when dividing by 11 of a number written in base 12 by adding up the digits in base 12, etc.)

Since, when using more than one base, it can be confusing which base you mean at any given time, we'll use a subscript to indicate the base. So 345_{10} means 345 in base 10; i.e., 3x10^{2} + 4x10 + 5x1. And 345_{8} means 345 in base 8; i.e., 3x8^{2} + 4x8 + 5x1 = 229_{10}. Since base 10 is what people usually use, when writing numbers in base 10 we'll usually just not use a subscript; i.e., when there is no subscript, you can assume the number is in base 10.

Now 345_{8} = 229 = 32x7 + 5, so the remainder when dividing by 7 is 5. But 345_{8} = 3x8^{2} + 4x8 + 5x1, and 8 ≡ 1 mod 7 so 345_{8} = 3x8^{2} + 4x8 + 5x1 ≡ 3*1^{2} + 4x1 + 5x1 = 3 + 4 + 5 mod 7. But 3 + 4 + 5 = 14_{8} in base 8 (since 14_{8} = 1x8 + 4 = 12), and 14_{8} = 1x8 + 4x1 ≡ 1x1 + 4x1 = 1 + 4 = 5 mod 7, so the sum of the digits of 345_{8} in base 8 is 5, and this is indeed the remainder when dividing 345_{8} = 229 by 7.