So here, the way to think about modular arithmetic is that it's about relationships between numbers. So some of these you've already seen before and are pretty familiar. So, for example, if I take an even number and add an odd number to it, then I definitely get an odd number. And if I take an even number and add an even number, I get an even number. So even though these things are familiar, even from elementary school, we're going to talk about generalizations and go a lot further with these ideas.
Really, the way to think about this simple example is it's what's called arithmetic modulo 2. So by that, I mean you're doing arithmetic, but you're only keeping track of the remainders when you divide by 2. So for today's lecture, we're going to have the following key definition that's going to take this idea much further, which is we're going to say that two integers, a and b, well, we're going to write the following expression: a congruent to b mod n. So this is pronounced as a congruent to b mod n. And we'll write this expression if and only if a and b differ by a multiple of n.
So that's it. That's our key definition that we're going to explore today. But we're going to see that there's a lot of meat to this in terms of understanding how to work with modular arithmetic. So another way that you'll sometimes hear modular arithmetic described is as clock math. So I'll explain what that metaphor means in a minute. But let me tell you the key result that we're going to use to reason about modular arithmetic. And this will also be something that's familiar from long ago. But we're going to state this a little bit precisely. This is, really, a corollary of what you learned in elementary school, namely, long-form division.
So what I claim is that for any integers a and n where n is strictly positive because it's our divisor, what I claim is that there is a unique pair of, again, integers q and r -- and these are suggestively chosen because q is the quotient, and r is the remainder -- with the following property: we can write a as q times n plus r. And the crucial thing is that this remainder, r, is between 0 and n and cannot be as large as n. So it's really between 0 and n minus 1.
So this is really the corollary of what we learned in elementary school about long-form division. I can take any integer and some divisor n, and I can write a as q multiples of n and then whatever I have left over. And the crucial thing is what I have left over is an integer between 0 and n minus 1. So these are just the basic facts that will help us make sense of modular arithmetic. And let's go over some basic facts about digesting what this expression means -- what are all the equivalent ways to think about what this expression is saying, that a is congruent to b?
So what we're going to do is we're going to learn the language of modular arithmetic. It's a little bit like relearning arithmetic from scratch but trying to remember what rules you're still allowed to do and what rules change. So let's be careful with this. Let's prove our first key fact, and this will be an extremely powerful fact. So what I claim is that this expression, a is congruent to b mod n, well, we know what this expression means: a and b differ by a multiple of n. I claim that this is true if and only if the remainder of a divided by n equals the remainder of b when I divide by n.
So this is a very intuitive fact. This is what was going on right here is that we think about evens as being a set of numbers that are congruent mod 2. And that's if and only if the remainder when I divide by 2 is zero. And something is odd if and only if its remainder is 1 when I divide by 2. But this is true for modular arithmetic even more generally than this. So this gives us a powerful way that we'll use this fact later to great effect for talking about the Euclidean algorithm. But for right now, let's just make sure that we're on the same page and that we can understand why this fact is true.
So we can prove both directions of this implication. So let's prove the backwards direction. So let's suppose that a is equal to qn plus r and that b is equal to q prime n plus r. So r is the remainder, so I'm just assuming that the remainder of a divided by n is the same as the remainder of b divided by n because they both have the same extra term for the remainder. And now what we can do is we can just remember what this expression means. We can look at a minus b, the difference between a and b. And we can write this as q minus q prime times n. And the r's cancel.
So this gives us what we're looking for. The statement that a and b are congruent mod n is equivalent to the statement right here that their difference is an integer multiple of n and q minus q prime is an integer. So we're good. We proved one direction. So this proves the first implication, that if the remainders are the same, then they're congruent mod n. And we can prove the converse direction, too. So conversely, let's suppose that a is equal to qn plus r, and b is equal to q prime n plus r prime.
Now, since a is congruent to b mod n, we know that a minus b is supposed to be equal to an integer multiple of n. And then we can remember what a and b are by assumption. And we can write this out as q minus q prime times n plus r minus r prime. And so now we can just focus on this expression. We know that a minus b is a multiple of n. And we can write the expression alternatively this way. But the key point is what's happening right here, that this term right here, r minus r prime, is an integer that's strictly larger than minus n and strictly smaller than n.
So if k, if a minus b can be divided through by n -- we get some integer multiple -- the only choice, n divides evenly here, and we get an integer, the only way that a number that's between minus n and n, and these inequalities are strict, and it divides through and gets an integer is if r minus r prime equals 0, in which case the two remainders are the same. So that's our key fact right here. It's just that we can use the division algorithm to connect very nicely with modular arithmetic.
The statement that two numbers are congruent mod n is really a statement about what happens when we run the division algorithm on a versus b. We might get different quotients, but they better have the same remainder. So are there any questions? Does this make sense? Yeah? OK. So now let's think about how we can visualize what's going on.
So the visual to keep in your head is of a clock. So we can think about something like 12, which is congruent to 5 mod 7. And what's really going on is that we take the integers 0 to 6, and we put them evenly spread out along our clock. And now what's going on is when we take an integer like 5, we start off at 0, and we go around the clock until we hit 5. And if we take an integer like 12, we go around the clock, but we're going to loop one full time around, and we'll end up at the same, exact place.
So that's sometimes why you'll hear it referred to as clock math is because, unlike ordinary integers here, we're not actually distinguishing between 12 and 5. These are in the same equivalence class because they land on the same position when we go around the clock. So this is the basics of modular arithmetic, but so far, we've only talked about addition. So the other piece we should talk about is multiplication. And then we can get to some action.
So when we think about modular arithmetic, we already know how to add. And we can also ask how we multiply modulo n. So it turns out that you can kind of just do it. So if I have something like 10 is congruent to 3 -- again, modulo 7 -- I can multiply this by 12, which is congruent to 5 modulo 7. And one thing you can check is that you can just do multiplication as usual. You can multiply 12 by 10, and I get 120. And on my right-hand side, I get 15.
But really, 15 is congruent to 1 modulo 7 because I can take away two multiples of 7 and get back down to 1. So basically, when you're doing addition and multiplication, you can always just multiply and add the way that you're familiar with. Just, at the end, after you're done, you take out as many integer multiples of the modulus as you need to to get back to an integer that's between 0 and n minus 1. So a lot of things work out very nicely.
But the way to think about this, really, is if you were to try and unwrap what's behind this notation, the statement that 10 times 12 modulo 7 is congruent to 1 is really the statement that a number with remainder 3, all happening modulo 7, times a number with remainder 5 modulo 7 gives a number with remainder 1, all modulo 7.
So it's good to not get confused by what's happening in terms of this expression. What this expression really means, when I take any number, like some number like 10, whose remainder is 3 modulo 7, and I take any number -- say 12 -- whose remainder is 5 mod 7, and I take the product of those two numbers -- I get this number on my left-hand side, 120 -- and that number should have remainder 1 when I take it with the modulus 7.
So that's really what's going on is it's the same generalization of what I wrote down right here is that you can forget what the actual even number was. All that matters is what its modulus is. Mod 2, I can forget what my odd number is. All that matters is that it has remainder 1 modulo 2. And I can still tell you something about the remainder when I add up those two numbers, even though I've forgotten the rest of the action of how many times around the clock I've gone. So that's the key way to think about it.
So if you've seen it before, this is very easy. If you haven't seen it, this takes a little bit of wrapping your head around. So are there any questions about modular arithmetic, or does this make sense? Good? OK. So I'm trying to give you a lot of different ways to think about it. I'll also mention that you can think about these things abstractly, too. So we'll talk more about this in the next lecture, but when I'm working modulo 7, then I can really think about it as something called a group that we'll talk a lot more about.
And, really, I can just think about the elements of that as being all of the possible remainders. And I have this table of how, exactly, to add up two numbers that belong to this set because when I add up remainders of 0, I get back to 0. When I add up 2 with 2, I get back to a remainder of 4. But see, I have interesting things happening here. When I take 4 and I add 4, I go back to the element 1 because that's the new remainder I would get when I take it modulo 7. And the same type of thing happens here. This is our multiplication table.
When I take something like 3 times 3, that'll give me 9. And when I subtract off the multiples of 7, I'm going to get back to 2. So, really, what's going on is that we're just redoing our addition and multiplication tables, just in the context of only keeping track of what the remainders are. Make sense? All right. So what I'm going to do is I'm going to tell you some more basic facts about modular arithmetic, and then we're going to do a demo just to give you a bit of a hint about why modular arithmetic is important.
So, as I promised, many of the things that you're used to with ordinary arithmetic go through just the same. And I'll point out the things that don't. So one of the properties that we know and love is associativity. If I have some number modulo 7, I can add two numbers, b and c, modulo 7. And then I can add to their result a, all happening mod 7. And I claim that that's the same thing as parenthesizing the expression the other way. It's the same thing as a plus b. And then I add c, all happening mod 7.
A lot of the other basic facts we're used to go through, as well, like commutativity. So, in particular, a plus b modulo 7 is equal to b plus a. That's the same thing as even plus odd. It doesn't matter what order I add them up. I still get the same thing, which is an odd number. And last but not least, we still have the distributive property, which tells us how multiplication and addition interact. So if I'm multiplying over Z7, a times the result of b plus c, that's the same thing as a times b plus a times c.
So almost everything works exactly the way that you're used to. So before we go too far into modular arithmetic, because we're going to be doing a lot of it today, I wanted to give you a little bit of a teaser for later about why we care about modular arithmetic. So it's not totally obvious, but modular arithmetic is a great way to accomplish a lot of things, especially in computer science. So we talked a bit about areas like cryptography in a previous lecture. Cryptography is based on modular arithmetic, so this will be a very important application for us later in the class.
There are also some other really fun applications that also are from other areas of cryptography, which have to do with things which were actually invented here at MIT about zero-knowledge proofs. So I'm going to need some help from the audience for this one. But let's imagine that you're home on a weekend, and you want to watch an embarrassing movie with your friend. Now, you have some favorite movies you might want to see, but you don't want to admit to liking that movie unless your friend likes it, too. This is a common problem, right?
Maybe if you both like the same embarrassing movie, you would then watch it, and that's fine. But otherwise, if you don't both want to watch the movie, you want some kind of plausible deniability -- I don't like that movie. So what are some examples of embarrassing movies that you guys actually like that you might be a little embarrassed to admit? Don't be shy. You guys don't like any embarrassing movies? What? [LAUGHS] We can't move on with the lecture until you guys give me something here.
The Room, OK -- The Room. I was going to go with -- what's this -- OK, I don't know. All right, let's go with Morbius. So can I have two volunteers from the audience, and then I'll explain the game. Who's going to come up here? Don't be shy. Yeah? All right, one more. Let's do it.
So let's explain how modular arithmetic and clock math is going to help us answer this question. What I'm going to do is I'm going to take five cards. Three are red. Two are black. Let's pretend that I don't keep track of the fact that it's a 2, and I just know the color of it. So what I'm going to do is I'm going to give each of you one black and one red card. And then what's going to happen is I put down this one red card in the middle.
Now, what they're going to do is they're going to decide whether they like the embarrassing movie or not, which they want to see on the weekends, which I guess is Morbius, which I should look up after class. And if they like it, what they're going to do is they're going to put their red card closest to the red card in the middle and their black card on the outside. And if they don't like it, they're going to put their black card next to the red card and their red card on the outside.
And so what I'm going to do then is I'm going to stack up the cards on top of each other. And then I'm going to have them both cut the deck randomly. So that way, it's a random cyclic shift when they put it together. And then, what I claim is that if they both like the movie Morbius and they want to see it, what's going to happen is we're going to have two red cards in a row, cyclically. And if either of them doesn't like it, then we will not have three red cards in a row. We will have two red cards in a row.
But even the person who liked it and the other person didn't, they'll have plausible deniability because all of those, after the cyclic shifts, it'll all look the same. So let's try it out. Do you guys want to see Morbius over spring break? So I won't look. Put down your cards, and then we'll see if we've got a match. All right. And just for security purposes, I'm going to ask each of you just to cut the deck. So just take up some number of cards, and put them on the bottom. Perfect.
And then cut the deck randomly. We'll pretend we didn't see how they cut them. And what I'll do is I'll put them out in order. And unfortunately, we don't have a match. So can you tell me what you guys answered?