I did a couple of sessions with groups of 15 and 16 year olds last week. I wanted to work with them on ideas involving squares (quadratic residues) in modular arithmetic, but that meant understanding what modular arithmetic was about, so I started by introducing that idea. I’d like to write about part of what I did in the sessions, because I felt it was quite a successful activity and I hope you might find it interesting too. I encourage you to try these things for yourself, rather than just reading!
So, modular arithmetic. We started by noticing that 3248 cannot be a square, because no square ends in an 8. What was important to us was just the last digit, and we can record that using the notation of modular arithmetic. Here are four equivalent statements:
- 3248 leaves remainder 8 when divided by 10;
- (mod 10);
- 3248 and 8 leave the same remainder when divided by 10; and
- 10 divides 3248 – 8.
They are all useful ways of thinking about the same idea.
We moved on to see how addition works: we saw that (mod 10). We can simply focus on the last digits, because that’s all that’s important in the mod 10 world.
Then we drew up multiplication tables in the mod 5 world, the mod 3 world and the mod 7 world, and looked for interesting patterns that we might be able to explain. Here’s the grid for the mod 5 version; the completed tables are over the break (but I encourage you to draw them up for yourself!). I’ve filled in the diagonal, so that you can check you’ve got the right idea.
|x (mod 5)||0||1||2||3||4|
OK, here’s my version of the completed tables for 3, 5 and 7.
|x (mod 3)||0||1||2|
|x (mod 5)||0||1||2||3||4|
|x (mod 7)||0||1||2||3||4||5||6|
See any interesting patterns? The students with whom I was working came up with three or four patterns, which I’ll describe below, but I think there are other interesting things to notice (and explain).
- Perhaps the most obvious thing is that the 0 row and 0 column of each table are filled with 0s. This does not come as a surprise: in ordinary arithmetic, so (mod ) for any . So we can be confident that the same will happen in other multiplication tables too.
- There’s a symmetry about the diagonal going from top left to bottom right. A little thought reveals that this is because (mod ) — multiplication (mod ) is commutative. Again, a pattern that occurs in any of these multiplication tables.
- There’s a symmetry about a diagonal going from top right to bottom left (being slightly careful about which diagonal we choose). To make sense of this one, it’s helpful to use negative numbers in the mod arithmetic world: (mod 7), for example. The symmetry then says that (mod ); once again, a pattern that works for any modulus.
- Ignoring the 0 row and 0 column, each row and column contains each possible number exactly once. The numbers form a Latin square (think Sudoku, if you prefer!). Does this work for all moduli? The rest of this post is really going to be making sense of this pattern; I encourage you to consider it further before reading on.
Does it work for all moduli? Perhaps we should try some more. Let’s try an even modulus: let’s try 4.
|x (mod 4)||0||1||2||3|
Ah. So we don’t have a Latin square here. Why?
A little thought reveals that the problem somehow occurs when we multiply a number that is not coprime to the modulus. You could test this by trying other moduli (e.g. 6 or 9 or 10).
So for the rest of this post I’d like to concentrate on prime moduli, because it makes our lives a little simpler. Similar arguments can be adapted to deal with composite moduli in a suitable way — this would be a good exercise if you’re interested.
So let’s think about the multiplication table (mod ), where is a prime.
One strategy is to think of the row corresponding to as being made by repeatedly adding (mod ), and then argue that it takes steps to get back to the beginning because and are coprime.
Another is to use Bézout’s theorem. That tells us that since and are coprime, there are integers and such that . Interpreting that equation as a congruence (mod ), we see that (mod ). We can think of as the multiplicative inverse of (mod ): it’s the number by which we multiply to get 1 (in the mod ) world). The fact that has a multiplicative inverse (mod ) at all is really useful (it’s not obvious), and an added bonus is that Bézout’s theorem gives us an explicit way to compute it.
How does this help? Well, there are possible values to go in the row corresponding to (not including 0, remember), because there are non-zero values in the mod world. If we could show that all the multiples of we’re looking at (, , …, ) are different, then we’d be in business: they’d have to be , , …, in some order.
So our job now is to show that if (mod ), then (mod ) (if two multiples of are the same, then they’re the same multiple). But we can do that, using the existence of the inverse that we saw just now. If (mod ), then, multiplying by this inverse , we have (mod ). That is, (mod ). Putting that another way, if is coprime to the modulus , then we can `cancel’ the from both sides of a congruence, by multiplying by its multiplicative inverse.
So that explains the pattern.
It’s now not far to this week’s theorem (which is, I confess, an excuse for this post!).
Theorem The non-zero integers (mod ) form an Abelian group under multiplication.
To prove this, we have four (or five) things to check.
- Firstly, the binary operation is indeed a binary operation: if we take two non-zero integers (mod ) and multiply them, we get another non-zero integer (mod ). This is an exercise!
- The operation is associative. This follows from the associativity of multiplication in the integers — again, I’ll leave it to you to write out the details.
- There is an identity element, namely 1. We can see this appearing in our multiplication tables above: the row corresponding to 1 makes no change.
- Each element of the set has an inverse. This is what we’ve just proved.
- The operation is commutative (we saw this earlier, when discussing one of the lines of symmetry in the multiplication tables), so the group is indeed Abelian.
I’ve used this theorem previously in this blog. I used it to give an example of a group in my post about Lagrange’s theorem in group theory, and mentioned it again in Proof 3 in my post about Fermat’s little theorem. It’s a handy sort of thing to know (and the existence of inverses is really crucial to all sorts of things in number theory).
I’m not quite sure what to put here, to be honest. The existence of inverses like this is elementary number theory (and so covered by Davenport’s The Higher Arithmetic, for example), but to find applications of the fact that these numbers form a group, you might do better to find an introductory book on group theory. There’s further information (such as what happens when the modulus isn’t prime) on Wikipedia.