[ELECTRONIC JINGLE] In a previous episode, we talked about multiplying things that aren't numbers.
But what happens if you divide things that aren't numbers?
[FUTURISTIC MUSIC] We all know you can't divide by the number 0.
But in some sense, the notion of dividing by 0 appears every time you use modular arithmetic.
The structures that underlie this modding business are called equivalence relations and quotient sets, and that's what I'd like to dive into today.
In Gabe's episode on the Diffie-Hellman key exchange, he referred you to Kelsey's video How to Break Cryptography.
There she introduced modular arithmetic, which, as she described, is what happens when you count in a circle.
Let's focus on Mod 5 arithmetic, where 3 plus 4 equals 2, for example.
What's really going on here?
If you were to look for an explanation in a textbook or online, you'd come across equivalence classes and quotient sets.
But what are those?
Let's try to understand equivalence classes first.
To start, we'll look at this set of integers.
Now any integer either is a multiple of 5 or it is not.
Pretty simple.
But an integer can fail to be a multiple of 5 in several ways-- four, to be exact.
An integer can be off by one-- that is, its remainder upon division by 5 is 1.
For example, 11 is not a multiple of 5 because 11 is 10 plus 1.
Or an integer can be off by 2-- that is, its remainder upon division by 5 is 2.
For example, negative 8 is not a multiple of 5 because negative 8 is negative 10 plus 2.
Similarly, an integer can be off by 3, or an integer can be off by 4.
So this lets us organize or partition the integers according to their divisibility or lack thereof of by 5.
Let's put those integers that are a multiple of 5 in a box, which we can cleverly label 5Z, since every multiple of 5 is of the form 5 times k, where k is an integer.
Or we can also label it 0 to remind us that if we divide any multiple of 5 by 5, the remainder is 0.
Notice I'm using square brackets just to differentiate the box from the actual number 0.
Similarly, we can put the integers that are not multiples of 5 because they have a remainder of 1 in their own box.
Let's label it 1.
Likewise, integers that are off by 2 go in their own box, 2.
Integers that are off by 3 go in a box 3, and integers that are off by 4 go into 4.
The upshot is that integers essentially come in five flavors-- those that are multiples of 5 and those that aren't, of which there are four varieties.
Once we partition the integers in this way, the individual numbers themselves aren't so important anymore.
What's more important is how they relate to the number 5 and its multiples.
Really, we're identifying or packaging together the integers that share a common relationship, namely, the remainder you get after dividing by 5.
In this sense, integers lying in the same box are equivalent.
Let me explain equivalence a bit more.
Look in the box 1, for example, where each integer has a remainder of 1 after division by 5.
This is the same as saying that the difference between any integer and 1 is a multiple of 5.
For example, negative 9 minus 1 is negative 10, and 6 minus 1 is 5, and so on.
So let's lay down some terminology.
Two integers relate to each other, written with this tilde, if their difference is a multiple of 5.
So negative 9 relates to 1 because negative 9 minus 1 is negative 10, and 6 relates to 1 because 6 minus 1 is 5, and so on.
So the box 1 is really just the set of all integers that relate to 1.
Similarly, 2 is the set of all integers that relate to 2.
3 is the set of all integers that relate to 3, and so on.
But this relation isn't just any relation.
It satisfies three special properties, which you can check.
It's reflexive-- that is, every integer relates to itself.
For example, 6 minus 6 is 0, which is divisible by 5.
The relation is symmetric.
For example, 6 relates to 1 and 1 relates to 6.
And it's transitive.
Example?
Negative 9 relates to 6 because negative 9 relates to 1 and 1 relates to 6.
Because these three properties are satisfied, the relation is called an equivalence relation, and the set of all integers that relate to a given integer is called an equivalence class or congruence class.
So what we were labeling as boxes are really equivalence classes.
And what's neat is that we can do arithmetic with equivalence classes.
For example, 3 plus 4 is defined to be the equivalence class 2, because 7 has a remainder of 2 upon division by 5.
And other operations in modular arithmetic, like multiplication and exponentiation, can be done on the equivalence classes themselves.
Finally, the set of these five equivalence classes-- 0, 1, 2, 3, 4-- also has a name.
It's a quotient set, which we label Z slash 5Z, pronounced Z mod 5Z.
And this allusion to division is no coincidence.
By organizing the integers according to their divisibility by 5, we are essentially dividing out the integers by all multiples of 5, 5Z.
But remember, 5Z is really the equivalence class 0.
So in that sense, we're dividing by 0.
After all, in modular arithmetic, adding or subtracting by any multiple of 5 doesn't do anything.
Multiples of 5 act like 0.
For example, 1 plus 10 is 1.
We can also see this visually.
Here's a pinwheel with five blades.
Its rotational symmetry is encoded by the elements of Z mod 5Z.
0 represents a rotation by 0 degrees.
1 is a rotation by 72 degrees.
2 is a rotation by twice that, or 144 degrees, and so on.
Notice 5 corresponds to a full revolution, 360 degrees, which puts the pinwheel back in its original location.
Since 0 and 5 transformed the pinwheel in the same way, 5 and all of its multiples are the same as 0.
So 1 plus 10 really is just 1.
The pinwheel looks the same whether we rotate it by 72 degrees and then two full revolutions or just 72 degrees.
And there's nothing special about the number 5.
For any positive integer n, the quotient Z mod nZ encodes n-fold rotational symmetries.
In the set nZ, the multiples of n behaves just like 0.
Whether we rotate by 0 degrees or by one or more full revolutions, the effect is the same.
By the way, this is the beginning of group theory, which we'll cover in an upcoming episode.
So how do you divide by 0?
You write down an equivalence relation and form the quotient set.
And the idea of quotienting extends far beyond the integers.
Given any set x and any equivalence relation on that set, we can form a quotient set by identifying or clumping or gluing together all of the points that lie in the same equivalence class.
In fact, x can be a group or ring or vector space or whatever, and we can form a quotient of that group or ring or vector space.
This gets really cool when x is a topological space, like a disk or a square, because that's where this gluing analogy becomes like actual mathematical glue.
And that's what Gabe will talk about in our next episode.