I was a little surprised that no one was too familiar with "casting out 9's". It is a method of checking arithmetic which has been part of the school curriculum since the early Renaissance. Probably it is no longer taught because it is obsolete -- a calculator is a far better way to check arithmetic now. As I'll show in examples, it checks addition of large numbers, for example, by associating with each large number a small number: then you add the small numbers. The result should just be the small number associated with the actual result. Here is an example:
| 876 | ---------> | 3 |
| +158 | ---------> | +5 |
| ------ | --- | |
| 1034 | ---------> | 8 |
As you see, we are adding 876+158 on the left to get 1034. But each number on the left gives rise to a small number on the right, where you see 3+5=8. This second sum is obviously right, and it checks the first sum, where we might easily have made a mistake. That the second sum is right makes me pretty sure the first sum is also right.
First: how do we get the small numbers? Answer: Add the digits in the big numbers, and do this again with the result, if necessary, until you get down to a single digit. So with 876 we form 8+7+6 = 21 --> 2+1 =3, and with 158 we form 1+5+8 =14 --> 1+4 =5. The last number is 1034 --> 1+0+3+4 = 8. This process of reducing down to a single digit is called "casting out 9's" because you can always ignore the number 9 and sometimes speed up the process that way. In doing 158, for example, you can see that 1+8 is 9, so it is quicker to ignore it, and what you have left is just 5 (correct).
Second: why does this peculiar process give numbers which add up the same way as the original numbers?? Rather than prove it, I will just call attention to what a nice property this is. A transformation like this, -- indicated by the horizontal arrows in the table above -- which leaves the addition unchanged, is called a HOMOMORPHISM. The word is made out of roots which mean "same" and "change." That is, you certainly CHANGE things when you cast out 9's, but in a sense they are still the SAME. When you know a homomorphism, you have your choice of how to do computations, like addition. You can add in the original system (on the left), getting 1034, and then use the homomorphism to go to the system on the right, getting 8, OR you can go immediately to the system on the right, getting 3 and 5, and do the addition there, getting 8. Whichever "route" you choose, you must get the same thing. That is how the homomorphism can check the addition on the left.
Casting out 9's is also a homomorphism of multiplication! Here is an example:
| 876 | -------> | 3 |
| x 158 | -------> | x 8 |
| -------- | ---- | |
| 7008 | 24 --> 2+4 = 6 | |
| 4380 | ||
| 876 | ||
| -------- | ||
| 138408 | -------> | 6 |
The homomorphism gives the small numbers on the right. Multiplying now, we find that 3x8 give rise to 6. On the other hand the multiplication of large numbers on the left gives 138408, which under the casting out 9's homomorphism gives 1+3+8+4+0+8 --> 3+4+8 =15 --> 1+5 = 6. Since we got the same thing by both routes, I believe there were no mistakes.
What is really going on here is that "reduction mod n," the operation we have been doing for some time now, is a homomorphism from Z to Zn, i.e., from the integers to the integers-mod-n. And casting out 9's is precisely "reduction mod 9." So the reason casting out 9's works is that it is a special case of modular arithmetic, in which the reduction can be done quickly and easily by the peculiar rule of adding the digits. That may not be so clear, so here is a little more on it. When you write a number like 8765, what you mean is 8x1000+7x100+6x10+5. To reduce it mod 9, you would probably do what we have been doing up to now, i.e., try dividing in a 9, and see what the remainder is. But now we can use the homomorphism property, and note that 10=1 (mod 9), also 100=1 (mod 9), also 1000=1 (mod 9), etc. (obvious?). Thus, since we mean to reduce mod 9 anyhow, why not do it right away, and write 8x1000 as 8x1 (mod 9), 7x100 as 7x1 (mod 9), etc. Then 8765=8+7+6+5 (mod 9), and that is just what "casting out 9's" says to do! Add the digits.
Here is a sort of silly idea for another homomorphism which could be used in the same way. I call it "casting out 11's," even though you will probably never meet an 11 to cast out. It starts by noting that reduction mod 11 is a homomorphism -- to add or multiply two numbers (mod 11), you can first do the operation, then reduce mod 11, or you can first reduce mod 11, then do the operation. Then it points out that there is a very quick and easy way to reduce mod 11! Since 10 = -1 (mod 11), 100 = 1 (mod 11), 1000 = -1 (mod 11), etc., we can reduce as follows. Using numbers from the multiplication example, 876 = 8-7+6 = 7 (mod 11), 158 = 1-5+8 = 4 (mod 11), and 138408 = -1+3-8+4-0+8 = 6 (mod 11). That is, you just form alternating sums of the digits, with plus and minus signs alternating. And sure enough, 7 x 4 = 28 = -2+8 = 6 (mod 11), checking the multiplication.
Homomorphisms, when they exist, reveal that two systems which look different may be, in essence, the same. Here is an example of that. You know about Z7*={1,2,3,4,5,6}, the multiplicative group mod 7. It is cyclic, and has 3 as a generator, as most of you showed in a recent problem. Thus we can think of Z7* as {3^1, 3^2, 3^3, 3^4, 3^5, 3^6}. To give these elements their usual names, in the same order they appear when they are generated by 3, they are {3, 2, 6, 4, 5, 1}. If you want to multiply 6x4 (mod 7), you can think of it as follows:
6x4 = (3^3)x(3^4) = 3^(3+4) = 3^7 = (3^6)x(3^1) = 3^1 = 3 (mod 7).
Here we look at 6 and 4 and notice which exponents represent them when we use the generator 3 to get all the elements of Z7*. In particular, 6 = 3^3 (mod 7), so 6 is represented by exponent 3, and 4 = 3^4 (mod 7), so 4 is represented by exponent 4. Multiplying 6 and 4 is the same as adding their exponents: 3+4=7. But then exponent 6 represents the element 1 in Z7*, which is a factor superfluous to write, so we can reduce the exponent (mod 6) and what is left is the exponent 1, corresponding to the element 3 in Z7*. That is, if we represent the elements of Z7* by their exponents, then multiplication is just addition mod 6. This is a homomorphism! Each number in Z7* gives rise to a new number (the exponent), and multiplying just corresponds to adding the exponents to get new exponents. This addition is only necessary to do mod 6, because 3^6=1 (mod 7). The exponent 6 is equivalent to the exponent 0.
A second example: to multiply 6x6 (mod 7), think of it as
6x6 = (3^3)x(3^3) = 3^(3+3) = 3^6 = 1 (mod 7).
Here 6 is represented by the exponent 3, and adding 3+3 we get exponent 6, which represents 1 in Z7*. We have done multiplication by doing addition (using the homomorphism, of course).
This homomorphism is actually a particularly nice kind, called an isomorphism. The meaning is you can actually map either system to the other, Z7* to Z6+, or the reverse. Given an element of Z7*, you can find what exponent represents it. Given an exponent, you can find what element of Z7* it gives you.
Addition mod 6 seems much simpler than multiplication mod 7, so it is rather surprising that they are in fact the same! You can thus work in the additive group Z6+ to solve what seem to be harder problems in Z7*. For example, what are all the generators of Z7*? Well, just find all the generators of Z6+ (additively), and what they correspond to in Z7* are the generators of Z7*. So what generates Z6+, by adding? Obviously 1 does. Add 1 to itself over and over, mod 6, and you get everything in Z6+: 1, 1+1=2, 2+1=3, 3+1=4, 4+1=5, 5+1=6. Other elements fail to do this. The element 2, for example, just generates the even elements: 2, 2+2=4, 4+2=6, 6+2=8=2 (mod 6)... (and we are beginning to repeat, having never seen 1, 3, or 5). Also 3 doesn't generate: 3, 3+3=6, 6+3=9=3 (mod 6)... (repeating already). Also 4 does not generate: 4, 4+4=8=2 (mod 6), 2+4=6, 6+4=10=4 (mod 6)...(repeating). On the other hand 5 does generate Z6+ additively: 5, 5+5=10=4 (mod 6), 4+5=9=3 (mod 6), 3+5=8=2 (mod 6), 2+5=7=1 (mod 6), 1+5=6. So the additive generators of Z6+ are just {1,5}. These are just the numbers which are relatively prime to 6 -- no accident. That 2, 3, and 4 have common factors with 6 is precisely why they cycle around and miss certain elements of Z6+. Now we know all the multiplicative generators of Z7*: they are just {3^1, 3^5}, the elements corresponding to {1,5} under the homomorphism. In more standard notation, these generators of Z7* are just {3,5}. Many of you had already found them, but this is another way to do it, and a way to see that there couldn't be any others.
Your assignment is to do an example like the one immediately above: find all the generators of Z13*. It would be possible, of course, to do it by tedious trial and error, but you get more insight into what is happening if you use a homomorphism with Z12+, the additive group mod 12, which is a much simpler place to do computations.
First: show that Z13* is cyclic with generator 2, by computing {2, 2^2, 2^3, 2^4, ...} mod 13.
This gives you a way to associate with each element of Z13* an exponent, namely the exponent of 2 which gives that element. That association is a homomorphism from Z13* to Z12+, exactly as in the preceding example: each element of Z13* is assigned its exponent in Z12+.
Now what are the elements of Z12+ which generate it additively? Just the elements which are relatively prime to 12: {1, 5, 7, 11}. It is easy to see that each of these by itself, if you just add it to itself over and over, mod 12, gives every element in Z12+={1,2,3,4,5,6,7,8,9,10,11,12}. That is most obvious with 1, but easy to see in the other cases too. Other numbers, like 2, 3, 4, 6, etc. fail to give everything in Z12+ when you add (mod 12). In fact they give only integer multiples of the gcd, and if the gcd is bigger than 1, that will not be everything in Z12+.
Hence the generators of Z13* should be {2^1, 2^5, 2^7, 2^11}. Check that this is so by showing explicitly that each of these numbers -- so far not known explicitly, but find them explicitly -- really do generate the whole multiplicative group.
NOTICE! When you are working in Z13*, you multiply; when you work in Z12+, you add. Be clear WHERE you are when you are computing things, so that you don't get confused!