Which sweet treat shall I have? Ina mina mona might, basco rola bora bites, buga buga bao eggs butter cheese bread stick stock stone dead out, not that one. You probably know your own version of the song. Most cultures have their own selection rhymes of songs. I'm using it to eliminate the sweets one-by-one and I'll leave the last one. So I was here. So ina mina mona might, basco rola bora bites, buga, oh I don't really need to do it this way. I can just count the sweets, count the words and see how many times the sweets fit into that length. Let's look at that. There are 19 words in this rhyme. So it goes like this. I start all my cupcake. So I'm going to start here, and I count 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19, this one is out. So the fourth sweet is out that's one eliminate, and then, I'm going to start from the fifth sweet. So start, so this is voice out, so I start from the fifth. And now I go. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19, it's okay, this is out the. So the two is out, and I would start again on the third sweet. That's going to take a long time. We can do better than that, because really we're wrapping around the number 19 around the number of sweets, around five sweets. So that means that 19 covers the five sweets three times, and then there's four more words to use, so the fourth chocolate is out. Yes that's what we got, and then I start counting on the fifth and I've got four chocolates to count over. 19 covers it four times, that's 16 and then there's three more words left. So the third chocolate after the fifth, which is a third, that is number two and that is out. Then, I've got three chocolates left, I start on the third chocolate, 19 covers it six times, that makes 18, and then there's one word left. So the third chocolate is out. Then I'll do it again, I'll have two chocolates left. I start on the fifth, and then I'll just go even and odd, even odd alternating between the fifth and the first and the fifth is out. So I will eat the first sweet first, I'll eat my cupcake first. You can do it yourself, whether with your traits and check my Maths. So we really didn't need to do the counting around every time, what we needed was the remainder of the division of 19 by how many sweets were left on the table. So 19 divide by five is three, with remainder four. So the fourth chocolate is out, and I start on the fifth. So I've got the fifth, the first, the second and the third available. Then starting on the fifth, I do 19 divide by four which is four remainder three, and from five, one, two, the second is out. Then I start on the third chocolate, and I have the third, the fifth and the first. So 19 divide by three is six with a remainder one, so the third chocolate is out. Then I start on the fifth chocolate, I've got the fifth and the first. 19 divided by two is nine with remainder one, so the fifth chocolate is out, and so I will eat the first. All we needed were the remainders. This wrapping around numbers and requiring only remainders of division, is the core of what we do in modular arithmetic. You and I use it every day to work with hours and minutes and seconds. You see 20 minutes after 1:56 PM is 2:16 PM. You add 56 minutes with 20 minutes, that makes 76 minutes, and then you take away the 60 minutes giving you 16 minutes past the hour and then that extra 60 minutes you convert into one more hour. So you add one to the 1:00 PM making it 2:16 PM. Modular arithmetic is often referred to as clock arithmetic. But instead of working always with 60 minutes of 12 hour clock faces, we work with the size of the clock we need for each problem. With chocolates, we did 19 divided by five equals three, with remainder four, so here we were working with a clock face with five hours. When we did 19 divide by four equals four with remainder three, we actually want a clock face with four hours. 19 divide by three which was 16 with remainder one, we were working on a clock face with three hours and 19 divide by two which is nine with remainder one, we actually want to clock face with two hours. Well the two-hour clock just highlights if the number we were working is even or odd. Like in binary, odd numbers end with a one, and even numbers end with zero. What's cool about this concept of working with remainders of division, is that the rules of arithmetic are very similar to the ones with common numbers. What I mean is that 45 divide by four, leaves remainder one, and that's because four times 11 is 44, and that's the highest multiple of four fitting into 45, so the remainder is one. I'll write that. So 45 divide by four leaves remainder one, and 18 divide by four, I'm ignoring the integer part for now, leaves remainder two, because four times four is 16 and then 16 to 18 is two, so that's remainder two. Now the cool thing about the rules of arithmetic here is that, if I add 45 with 18, the remainder of that sum, when divided by four, is the same as adding the remainder one, and the remainder two, so it's going to be remainder three. So I don't need to add the numbers up to the division by four and work out the remainder, I can just say well it's going to be the remainder one from here, plus two from there. I can add up the remainders and that is one of the key properties we're going to tap into. Now this also works for multiplication. So 45 times 18, the remainder of division by four, is the multiplication of the two remainders. So one times two, so the remainder is going to be two, check for yourself. That means that if we are only interested in remainders, then we can work out remainders of smaller numbers, and then add, subtract and multiply remainders provided we are working in the same size of clock. We are going to call that the modulus, sometimes I call it mod. Now this property does not extend to division. It is only for addition, subtraction and multiplication. From the first examples with sweets, the pattern of numbers we keep eliminating looks random. One way of generating pseudo-random numbers for computing purposes, employs modular arithmetic, working with remainders. And one incredible use of modular arithmetic, is the strongest form of encryption using classical computing, the RSA encryption that relies both on large prime numbers and modular arithmetic. RSA stands for the name of the mathematicians that developed it, Rivest, Shamir and Adleman. In this lesson, you will learn how to work on encrypting and decrypting messages using the RSA algorithm banking on modular arithmetic. Get ready for this adventure.
