Theorem 31: the non-zero integers (mod p) form a group under multiplication

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;
  • 3248 \equiv 8 (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 3248 + 73 \equiv 8 + 3 \equiv 11 \equiv 1 (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
0 0
1 1
2 4
3 4
4 1

OK, here’s my version of the completed tables for 3, 5 and 7.

x (mod 3) 0 1 2
0 0 0 0
1 0 1 2
2 0 2 1
x (mod 5) 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1
x (mod 7) 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6
2 0 2 4 6 1 3 5
3 0 3 6 2 5 1 4
4 0 4 1 5 2 6 3
5 0 5 3 1 6 4 2
6 0 6 5 4 3 2 1

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).

  1. 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: 0 \times a = 0 in ordinary arithmetic, so 0 \times a \equiv 0 (mod n) for any n.  So we can be confident that the same will happen in other multiplication tables too.
  2. There’s a symmetry about the diagonal going from top left to bottom right.  A little thought reveals that this is because a \times b \equiv b \times a (mod n) — multiplication (mod n) is commutative.  Again, a pattern that occurs in any of these multiplication tables.
  3. 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: 5 \equiv -2 (mod 7), for example.  The symmetry then says that (-a) \times (-b) \equiv a \times b (mod n); once again, a pattern that works for any modulus.
  4. 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
0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1

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 p), where p is a prime.

One strategy is to think of the row corresponding to a as being made by repeatedly adding a (mod p), and then argue that it takes p steps to get back to the beginning because a and p are coprime.

Another is to use Bézout’s theorem.  That tells us that since a and p are coprime, there are integers m and n such that am + np = 1.  Interpreting that equation as a congruence (mod p), we see that am \equiv 1 (mod p).  We can think of m as the multiplicative inverse of a (mod p): it’s the number by which we multiply a to get 1 (in the mod p) world).  The fact that a has a multiplicative inverse (mod p) 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 p-1 possible values to go in the row corresponding to a (not including 0, remember), because there are p-1 non-zero values in the mod p world.  If we could show that all the p-1 multiples of a we’re looking at (a, 2a, …, (p-1)a) are different, then we’d be in business: they’d have to be 1, 2, …, p-1 in some order.

So our job now is to show that if ka \equiv la (mod p), then k \equiv l (mod p) (if two multiples of a 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 ka \equiv la (mod p), then, multiplying by this inverse m, we have kam \equiv lam (mod p).  That is, k \equiv l (mod p).  Putting that another way, if a is coprime to the modulus p, then we can `cancel’ the a 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 p) 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 p) and multiply them, we get another non-zero integer (mod p).  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).

Further reading

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.

Advertisements

16 Responses to “Theorem 31: the non-zero integers (mod p) form a group under multiplication”

  1. Theorem 31: the non-zero integers (mod p) form a group under … : Best Mod . com Says:

    […] 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 … See the article here: Theorem 31: the non-zero integers (mod p) form a group under … […]

  2. Theorem 35: the best rational approximations come from continued fractions « Theorem of the week Says:

    […] 35: the best rational approximations come from continued fractions By theoremoftheweek Like Theorem 31, this post is based on a session that I did with some school students.  And as I did there, I […]

  3. Junwoo Jung Says:

    Dear the author of “Theorem of The Week”,

    It is a very impressive and interesting post.
    It is very useful to me and my work.
    So, I wanna to say “thanks a lot”.

    Junwoo Jung,
    South Korea.

  4. Number Theory: Lecture 2 « Theorem of the week Says:

    […] of congruence notation, and the notation […]

  5. Theorem 38: There is a primitive root modulo a prime « Theorem of the week Says:

    […] This is something that I was lecturing on the other day.  There I was talking to third-year Cambridge undergraduates, who know quite a bit of mathematics about groups and the like, and so I presented the topic accordingly.  My challenge in this post is to describe some of the ideas in a way that assumes less technical background, since my aim is wherever possible to make these posts accessible to people who haven’t studied maths at university.  I am going to assume that people know a small amount of modular arithmetic, but that’s OK because I’ve written about it previously. […]

  6. Brian Says:

    Amazing post. Indeed, Herstein’s Topics in Algebra has a question regarding the proof of the group of non-zero integers modulo p, which I was stuck with it and your post explained it very well. I’m currently working through your other blog posts and very pleased with them. Please keep them coming!

  7. Luqing Ye Says:

    I’ve also wrote a post about such matter.
    http://h5411167.wordpress.com/2011/11/09/group-and-modulo/

  8. Sutton Trust summer school 2012 « Theorem of the week Says:

    […] lemma.  In the second, we mentioned the Fundamental Theorem of Arithmetic, and we learned about modular arithmetic.  In the third and final lecture, we mentioned that is irrational, and talked about continued […]

  9. Theorem 43: the Steinitz Exchange Lemma « Theorem of the week Says:

    […] is , which is a vector space over the field of integers modulo (here is a prime).  Vectors in this space are -tuples of integers modulo […]

  10. Sutton Trust summer school 2013 | Theorem of the week Says:

    […] lemma.  In the second, we mentioned the Fundamental Theorem of Arithmetic, and we learned about modular arithmetic.  In the third and final lecture, we mentioned that is irrational, and talked about continued […]

  11. Number Theory: Lecture 2 | Theorem of the week Says:

    […] Lemma 7: Let be a natural number, and let be an integer coprime to .  Then has a multiplicative inverse modulo .  That is, there is an such that .  We proved this using Bézout. […]

  12. SImon Says:

    I wonder, when you used Bezout’s theorem, whether you proved that the inverse m exists in the group..thx

  13. theoremoftheweek Says:

    We just need it to be an integer coprime to p, don’t we? I think that follows immediately.

  14. Groups and Group Actions: Lecture 1 | Theorem of the week Says:

    […]  It turns out I sort of wrote one myself on this blog a while back, looking specifically at some modular arithmetic (which we’ll meet later in the course but which you could read up on now in the blog post). […]

  15. Groups and Group Actions: Lecture 7 | Theorem of the week Says:

    […] written before about the result that the non-zero integers modulo a prime form a group under multiplication, which […]

  16. Groups and Group Actions: Lecture 1 | Theorem of the week Says:

    […]  It turns out I sort of wrote one myself on this blog a while back, looking specifically at some modular arithmetic (which we’ll meet later in the course but which you could read up on now in the blog post). […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: