Hello everyone, and welcome to Carmen's Core Concepts. My name is Carmen Bruni, and this is Week 7 Part 2. So I felt the need to break off this last section because it is fairly abstract that's for 1. For 2, the other video’s getting quite long, so I thought I would cut it off there and start a new video here. And thirdly, there's a lot of parts that I'm going to talk about in this video that are…what do I want to say… sort of above and beyond what a Math 135 student should know at the end of the course, but at the same time, I feel like these concepts are very important and that there's no reason not to include them in Math 135. So that being said, those factors combined gave us a Week 7 Part 2 video that is the following.
Basically what we're going to talk about in this video is the ring $\mathbb{Z}_m$. That's our key, key, key feature in this presentation. But to get there, I'm going to define a couple of concepts in abstract algebra. I'm going to describe Congruence Classes, I'm going to describe the concept of being well-defined, this is a very important notion in algebra and it extends to many fields, and then we're going to finish off with a couple of tables. An addition table and a multiplication table for the integers $\bmod 4$.
So let's start with part 1: the definition of a commutative ring and a field. A ring is a very common structure. You actually know what a ring is without really knowing what a ring is. The idea behind this slide and this definition is to give you a way to group sets that you know together basically. So let's describe what I mean by this.
Definition: A commutative ring is a set $R$ along with two closed operations, $+$ and $\cdot$ such that for $a,b,c \in R$
In the beginning by closed operations we mean if I add 2 elements of the set R, I stay inside R, and if I multiply 2 elements of the set R, I stay inside R.
Another note is that multiplication and addition don't always have to be commutative in a ring, but they do in a commutative ring.
For $3)$, I've written “distinct” in brackets. Some books don't require this, some books do. Take your pick. It doesn't matter that much.
As I said at the beginning, a commutative ring is something that you already kind of know. You already know examples of commutative rings: $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, all of these are commutative rings.
The natural numbers don't form a commutative ring. They are associative, they are commutative, they don't really have an identity, right? The additive identity isn't inside $\mathbb{N}$. Remember our natural numbers start at $1$. And additive inverses are missing. This is the key one that's missing from the natural numbers. If I have $1$, I don't have $-1$ inside the natural numbers. But I do inside the integers, and that's what forms a commutative ring.
Okay, so here's the definition. Again these are things that you know, right? So I'm just kind of grouping together a set of objects that you already know have these properties and I'm giving them some sort of classification name, okay?
And I haven't defined a field yet. What's a field? Maybe you can guess, but maybe you can’t.
Definition: If in addition, every nonzero element has a multiplicative inverse, that is an element $a^{-1}$ such that $a\cdot a^{-1}=1$, we say that $R$ is a field.
So every field is a ring, every field is a commutative ring, but not every ring is a field. So for example, $\mathbb{Q}$ and $\mathbb{R}$, these are fields and these are commutative rings, but $\mathbb{Z}$, for example, is not a field because elements like $2, 3, 4$ their multiplicative inverses, $\frac{1}{2}, \frac{1}{3}, \frac{1}{4},$ those aren't inside the integers.
So maybe this is giving you a little bit of context as to why we have all these symbols and definitions and how this all came about. That's sort of what I'm trying to give you with this slide. It's just a way to describe sets that have special properties, and we'll see in the next couple of slides, we're going to define a new commutative ring and that's going to be the integers $\bmod m$, and it's kind of what you think based on what we've done this week but we'll talk about that in a minute, okay?
So here's the definition of a commutative ring and fields. We’ll also see fields later on. We're going to talk about the set called the complex numbers, and we'll see that the complex numbers form a field. But again, I'll save that for later.
Congruence classes, so now let's bring this back down to where we were. So rings, fields, we have these things in our back pocket when we need them. What is a congruence class?
Definition: A congruence or equivalence class modulo $m$ of an integer a is the set of integers
$$[a] := \{x \in \mathbb{Z}:x \equiv a \pmod m\}$$Further, define
$$\mathbb{Z}_m=\mathbb{Z}/m\mathbb{Z} := \{[0],[1],...,[m-1]\}$$The $":="$ means “defined as” or 'defined to be' something along those lines.
So for example, if $m=7$ and $a=1$, the set $[1]=\{...-20,-13,-6,1,8,15...\}$ So there's an example of the congruence class of $1 \bmod 7$.
Further, we define this $\mathbb{Z}_m$. So the integers modulo $m$, sometimes it's denoted by $\mathbb{Z}/m\mathbb{Z}$. In this course, we're going to use this first description, $\mathbb{Z}_m$. Later on in your mathematical careers, you're more likely to see $\mathbb{Z}/m\mathbb{Z}$, for reasons which I won't get into now, but it's a good notation so you should know it.
Notice that you don't need to always use the symbols from $0, 1,$ all the way up to $m-1$. Remember that $[0]=[m]$. So if you wanted, you could write the set as $\{1, 2, 3,...m\}$, ignoring $0$. You can also use different elements as well. These elements are just the most convenient ones to describe $\mathbb{Z} \bmod m$. So that's our congruence classes.
How do we put this all together? So I had this previous slide defining rings and fields and I have this slide defining congruence classes. Well the merger between the two is given by giving the set $\mathbb{Z}_m$ a ring structure, okay, and the ring structure is going to be what you think it is, but I'm still going to define it formally.
So the ring $\mathbb{Z}_m$. So we're going to turn this set into a ring by defining addition and subtraction and multiplication as follows. So subtraction, again, you can think of subtraction as the additive inverse. Now how do we do this?
So remember, $[a]$ is the congruence class of $a$, and $[b]$ is the congruence class of $b$. These two things are sets. So what we're trying to do is we're trying to define an operation on sets. And on these two sets, how do we define the operation?
$$[a] \pm [b]:=[a \pm b]\,\text{and}\,[a]\cdot [b]:=[ab]$$That doesn't look like we're doing very much, right? It looks like we're just pushing symbols, but there's some going on here, right? We're adding two sets together. How do we claim that we add the two sets together? Take the arguments and add them.
And in the same way, we're going to multiply two sets together, and how are we going to multiply these two sets together? Well take the two arguments, $a$ and $b$, multiply them together, and look at that congruence class.
Something I'll get you to check is that this makes $0$ the additive identity and $1$ the multiplicative identity. And again, notice that $[a+b]$ means add and then reduce modulo $m$. That's basically what's happening here. You're adding first, and then reducing modulo $m$. That's how the addition is defined on this set $\mathbb{Z}_m$. And that's going to turn this into a ring.
This is not something I'm going to prove, but this is definitely something that you do. Test yourself, go back to the definition of a ring and try it out with this set, and make sure you understand why this operation makes it a ring.
The members $[0],[1],...,[m-1]$ are sometimes called representative members. So that's like I said, right, we can change the $0$ to $m$ and it doesn't really change the definition of the set, it's still the same thing.
Something else to note, when $m$ is a prime, let’s call it $p$, the ring $\mathbb{Z}_p$ is also a field as non-zero elements have multiplicative inverses, they're invertible. We'll see this later. We will see this later. I'll leave it at this for now, but this is why I want to introduce the concept of a ring and a field right now because it fits in quite nicely.
Now with this definition, in a vacuum, you kind of look at this and you're like, “Okay, this kind of makes sense. I mean this is how I think we should add these two sets. We just add the arguments together, and that’s how I think we should multiply the two sets. We just multiply the arguments together. So at the surface, it seems really obvious, but there's something that you have to actually do here and that's not maybe so obvious on your first time around, and that's this issue of this notion of being well defined. So that's we're going to talk about in the next slide.
So this operation depends a little bit on the representation of your congruence class. What do I mean by this? Let's take a look at this abstractly, and then let's take a look at this concretely, and then I think it's a little bit easier to understand.
Abstractly: Suppose that over $\mathbb{Z}_m$, we have that $[a]=[c]$, and $[b]=[d]$, for some $a,b,c,d \in \mathbb{Z}$. Is it true that $[a+b]=[c+d]$ and $[ab]=[cd]$?
So in other words, if I add $[a]$ and I add $[b]$, right, that gives me $[a+b]$, is that the same as if I add $[c]$ and if I add $[d]$? Similarly, if I multiply $[a]$ and $[b]$, is it the same as when I multiply $[c]$ and $[d]$?
This would be a very weird world if this wasn't true. If we had two different representations for something, did an operation to them, and got two different results, that seems to be a problem, right? The results that we should get should be the same.
This is what we mean when we call something well-defined, okay? An object is well-defined if I take two different representations, do the same operation to them, I get the same result. Okay? Let's take a look at a concrete example which might make this a little bit clearer.
Concretely: As an example, in $\mathbb{Z}_6$, is it true that $[2][5]=[14][-13]?$
We should expect that this is true, right? Why? Because $2 \equiv 14 \pmod 6$, and $5 \equiv -13 \pmod 6$. So this should be true. If this operation is well-defined, these two things should work out okay.
So again, take a minute, try to work this out by hand. What is $[2][5]$? What does that really mean? What is $[14][-13]$? What does that really mean? Are those 2 congruence classes the same?
Let's take a look at a brief solution, or a solution sketch, of this problem now. So what are we doing? Well in $\mathbb{Z}_6$, we're looking at this left hand side which is $[2][5]$. By definition, we have:
$$[2][5]=[2 \cdot 5]=[10]=[4]$$That is true since $10 \equiv 4 \pmod 6$. So $[10]=\{...-2,4,10,16,22...\}$ and $[4]$ consist of the same elements, right? That's true because $10 \equiv 4 \pmod 6$.
Also, on the other side, the right hand side is $[14][-13]$, so we multiply those together. Right? That's what this is defined as. When doing congruence class multiplication, you multiply the arguments together
$$[14][-13]=[14 \cdot (-13)]=[-182]=[-2]=[4]$$We have that $[-2]=[4]$ since the congruence class of elements congruent to $-2 \bmod 6$ is the same as the congruence class of the elements consisting of $4 \bmod 6$, and that's the key idea here, okay?
So here's what it means to be well defined. A very, very subtle notion. This is something that took me a very long time when I first learned it to really understand and appreciate, but now hopefully I've given you at least a starting point to try to understand what it really means to be well defined. If you have two different representations of an object and you do the same operation to those two different representations, you should end up with the same answer. In this case we do.
Now to prove this formally and abstractly, you'd have to do this for all cases. Not going to do that. It's a big symbol manipulation and hopefully this gives you at least the idea down of this.
With this in place, there's only a couple of more things I want to talk about for this week with the integers modulo m and congruence classes and things like that. I want to talk about addition and multiplication tables.
So here we have an addition table for $\mathbb{Z}_4$.
| $+$ | $[0]$ | $[1]$ | $[2]$ | $[3]$ |
|---|---|---|---|---|
| $[0]$ | $[0]$ | $[1]$ | $[2]$ | $[3]$ |
| $[1]$ | $[1]$ | $[2]$ | $[3]$ | $[0]$ |
| $[2]$ | $[2]$ | $[3]$ | $[0]$ | $[1]$ |
| $[3]$ | $[3]$ | $[0]$ | $[1]$ | $[2]$ |
So $\mathbb{Z}_4$ consists of four elements: $0, 1, 2, 3$. What is an addition table? It's just like your multiplication tables from grade school except with addition. It's going to give you a table for what happens when I add $[0]$ and $[0]$. Well I get $[0+0]=[0]$. If I add $[0]$ and $[1]$, I get $[0+1]=[1].$ If I add $[0]$ and $[2]$, I get $[0+2]=[2]$, and so on.
Maybe something a little bit more interesting, let's look at $[2]$ added to $[0]$, that's $[2+0]=[2]$. $[2]$ added to $[1]$ that's $[3]$. $[2]+[2]=[4]=[0]$. So I'm going to write down $0$ instead of $4$.
Similarly, $[2]+[3]=[5]=[1]$ and $[3]+[3]=[6]=[2]$
Now let's look at a multiplication table.
| $\cdot$ | $[0]$ | $[1]$ | $[2]$ | $[3]$ |
|---|---|---|---|---|
| $[0]$ | $[0]$ | $[0]$ | $[0]$ | $[0]$ |
| $[1]$ | $[0]$ | $[1]$ | $[2]$ | $[3]$ |
| $[2]$ | $[0]$ | $[2]$ | $[0]$ | $[2]$ |
| $[3]$ | $[0]$ | $[3]$ | $[2]$ | $[1]$ |
So now if I'm multiplying two elements together, if I take $[0] \cdot [0]=[0 \cdot 0]=[0]$. $[0] \cdot [1] =[0 \cdot 1]=[0]$.$[0] \cdot [3]=[0 \cdot 3]=[0]$. It's the same in all directions.
If I take, let's say, $[2] \cdot [1]=[2]$. $[2] \cdot [2]=[4]=[0]$, since $4 \equiv 0 \pmod 4$, therefore I write $0$ instead of $4$. Similarly, $[2] \cdot [3]=[6]=[2]$.
So hopefully you realize it's basically you just, you know, one way that I like to think about $\mathbb{Z}_4$ or $\mathbb{Z}_m$ in general, is I like to think of $m$ as somehow being $0$. So I can always add copies of $m$ or subtract copies of $m$ from my number and it's not going to change the equivalence class of the number, right? So $4$ is the same as $0$ which is the same as $8$, and $16$, and $12$, and $400$, they're all the same. Again why? Because they're all multiples of $4$. All multiples of $4$ are the same.
We'll see more about this in the upcoming week to get this idea down and help solidify it in your mind, but hopefully at least this gives you a starting point with $\mathbb{Z}_m$, what they mean, and try to unravel what this notation is really doing.
Thank you very much for listening. Hopefully this was informative. Hopefully you learned a little bit and will remember bits and pieces. Remembering everything, you know, the first time it's hard, right, but after a little bit of time with this topic, hopefully you'll help solidify it and keep it in mind. When you see it in future courses, you'll at least know oh I remember this issue of being well-defined, I remember that I had to show that oh if I do the same thing to two different objects that are actually the same I get the same result, something like this. I'm really hoping that this just gives you an overall view of what these topics are. So again thank you very much for listening and best of luck.