Modular Systems of Numbers | Dr. Carlene Arceo

More videos

Podcast

Modular Systems of Numbers

Prof. Carlene Orceo

Hello! I’m Carlene Arceo from the Institute of Mathematics of the University of the Philippines Diliman. Thank you for joining me for a discussion of Modular Systems of Numbers.

When we talk about mathematics, invariably what first comes to mind are numbers, and when we think numbers, the primary—the most basic function we have for them—is counting. In our discussion today, we will be dealing with whole numbers.

So, for modular systems of numbers, we first think about the adjective modular. What comes to mind when we talk a module? A Module is each of a set of standardized parts or independent units that can be used to construct a more complex structure. Other sources on online dictionaries will also define it as one of a set of separate parts that can be joined together to form a larger, complete whole. It can be also referred to a separable, self-contained component of a system.

What are familiar modular system or structures to us? Think about the modular cabinet. It’s a pre-made unit that can stand alone. And then, when you bring it on-site, you just attach it to the wall of the house or the building. What is a modular building? A modular building is said to be composed of modules produced off-site which are put together on-site, reflecting the identical design intent and specifications of a site-built facility still without compromise and resulting in a complete construction in half the time. A modular design, in general, subdivides a system into smaller parts—called the modules—that can be independently created and then used in different systems. I think it’s a definition of modular design that we can use when we take on the concept of modular systems of numbers.

So, what is modular system of numbers? A modular system of numbers would, in parallel, use only a small set of whole numbers. A fixed number is assigned as the modulus. And if we set that modulus to be, say, whole number k, then the corresponding subset of whole numbers is 0, 1, 2, 3 up to k-1. That is, we stop at the whole number right before the modulus k. This system is called a mod-k system.

Now, how are these numbers in the subset related to the modulus? They are the possible remainders when one divides by the module. Indeed when one divides by the number k then the only possible remainders would be all whole numbers smaller than k, so that would be the set 0, 1, 2 up to k-1

Now, I’m sure some examples of modular systems of numbers are already familiar to you. For example, if you look at the face of a clock, that’s already a modular system from 1 to 12. The months of the year—you go to the first month to the twelfth month and then go back to one. Both zodiacs, meaning the Western zodiac and the Chinese zodiac, all count by twelve, and when you get the twelfth sign, you go back to the first one. You also know how to count by mod-7. What is mod-7 in our everyday system? It’s exactly the days of the week—Sunday, Monday all the way up to Saturday and then back to Sunday again. And no matter how we want to jump to Friday, sorry, we can still up to go through Monday, Tuesday and all the way up to Thursday again, then Friday, Saturday back to Sunday. There’s a small modular system you’re very familiar with. Those of us stuck in tracking traffic would be familiar with a mod-3 system represented by  the traffic lights. We go from red to green to yellow, as if we were counting 0, 1, 2, 0, 1, 2. And those of us who practice or are enthusiasts of music would know very well that our musical notes start with DO, RE, MI, then all the way up to LA, TI back to DO. So, that is another modular system that many, if not all of us, are actually familiar with.

How many of you know how to play the game FLAMES? You’re familiar with flames, right? So, we associate a certain number with F, L, A, M, E and S, so that if you hit the number one—if you get the number one—then, this would represent F and then you’d look for the meaning for F. If you get the number 2, then it would be L and so on, so that when you get to the number 6, you assign the letter S for the relation that S represents, and when you go to 7, 8, 9 and correspondingly you’d go back to F, L and A. And then, when you accidentally bite your tongue, what do you usually do? Don’t you look to your left or to your right? You look at a seatmate and immediately ask for a number. Why you do ask for that number? Because [with] that number, you will match with the letter in the alphabet and then you will match it to a certain person with that name, whose name start with that letter and then think “Oh! he or she is thinking of me”. And if you do that assignment of a number to a letter, how many letters are there? There are 26 letters that we use, so, that you are actually already doing modular counting according to modulus 26.

So, you see? Those are at least five examples of modular systems that you’re already familiar with. So, how will you count again whether its a modular 5, 6, 7 or 26? It’s actually a “wrapping” or a “turning around” or a “going back” to the start once the modulus is reached.

So, how do we perform modular arithmetic with these numbers? It’s a usual arithmetic—usual addition, usual multiplication—but with the added step of getting the remainder upon dividing by the modulus. Remember, the module is made up of the remainders 0, 1, 2 up to k-1, which 1 gets when you divide by the modulus k. And take note: that small module, 0,1,2 up to k-1, can actually cover the entire set of whole numbers. So, you can think of the set {0, 1, 2, … k-1} as the module through which one can complete the whole numbers.

How is this done? Let’s talk about mod-5.

The mod-5 system is composed of the numbers 0, 1, 2, 3 and 4.  0, 1, 2, 3, and 4 are the possible remainders when you divide by 5. And this set completes the set of whole numbers as follows: 0 will represent all whole numbers which yield the remainder of 0 upon division by 5 . So, what are those numbers? 0 would represent 5, 10, 15, 20 and so on—all the multiples of 5.  How about the number 1? 1, therefore, is going to represent all whole numbers which will yield the remainder of 1 upon division by 5. So, that would be the whole numbers 6, 11, 16, 21 and so on. How about the number 2? Similarly, these would be the number which yield remainder 2 upon division by 5. So we’ll start with 7, 12, 17, and so on. 3 will represent in the same manner 8, 13, 18, 23, and so on. 4 will represent the set 9, 14, 19, 24, and so on. And then, we don’t go to 5, right? We go back to 0 and the multiples of 5, which again, give you a remainder 0 upon division by 5. So that’s how set 0 to 4—that’s very small, five symbols only—that’s how that small set actually completes the set of whole numbers.

And how do we do the arithmetic on them? It’s a closed set, so that if you do addition or multiplication, the results should still belong to that set. So if I’m going to add, let’s say, 3 and 4. 3 + 4 usually is 7, but remember in modular arithmetic we need an additional step and that step is dividing by the modulus and getting the remainder. So 3 + 4 is 7 but 7 does not belong to 0, 1, 2, 3, 4. 7 must therefore be, in final form, one of 0, 1, 2, 3 and 4. And we get that by dividing 7 by 5 and getting the remainder. So 7 divided 5 gives the remainder of 2. So the simple addition 3 + 4, which usually gives 7, in mod-5 would give us 2. 3 + 4 is 7 which is equivalent to 2 in mod-5.

If we do multiplication, let’s say 3 ✕ 3. 3 ✕ 3 usually is 9, but 9 does not belong to the mod-5 system. 9 is represented by—which number? You remember?—9 is represented by 4 because in mod-5, when you divide 9 by 5, you get 4. So 3 + 4 is 2 in mod-5 and 3 ✕ 3 is 4 in mod-5. That’s how we perform modular arithmetic.

You do the same for mod-6 or mod-10 or mod-12…  Let’s take as an example mod-12. Our day is divided into twenty four hours of which we have in the first twelve in the morning—in the AM—and the next twelve in the PM. If we schedule shifts, or for example, take medicine, we have to know how to count our hours. Let’s say your shift starts at  8:00 AM and you’re going to work eight straight hours before the next shift comes on. What time will the next shift came on? This is modular counting mod 12, because when you count 8 plus 8 hours we don’t say 16, right? We don’t say the next person will come on 16:00 PM, but instead, when we count eight hours, it’s 8, 9, 10, 11, 12 and then back to 1 when we start the PM. So we know that the next shift will start at  4:00 PM. That is already an example— an immediate example—of knowing how to count in mod 12. If you’re supposed to take your medicine every six hours and you take your first dose at 8:00 AM. In six hours, you don’t say “the next time I’m going to drink my medicine is 14:00 PM”, right? In mod 12, 14 is equivalent to what?  2—2:00 PM in this case. So, scheduling shifts and taking our medicines, this is another example where we show that we are familiar with counting in mod 12

Now, I will revert back to mod-26. Again, we use mod-26 in a very simple representation of our English alphabet. Because the application I would like to discuss today is in encoding or cryptography.

Cryptography literary means hidden writing. The purpose of which is [to] secure

communication. For our discussion today, let’s just assign numbers to letters of the alphabet. So, the most natural assignment would be 1 for the letter A , 2 for the letter B, 3 for the letter C and so on, until 25 for the letter Y, and then for the letter Z not 26—but remember for our modular system we go to 0 once you divide by 26. So Z is represented by the whole number 0 instead of number 26.

How do we apply the coding? We start with an encoding formula. An encoding formula is most simply represented by some linear function, let’s say, y = f (x). Of course eventually, to be able to decode a message, you have to isolate x in that formula, just as if you are getting the inverse of the function or the formula.

So, think of, y equals, let’s say 3x + 213x + 21

And, I will choose a letter, for starters, letter A. We attribute to letter A  the representative 1. So, if we let x take the value 1 and put it into the formula 3x + 21 it gives us the y value 24, and then we assign again—we go the letter corresponding to the 24 which is the letter x. What does that mean for us? That means, every time we want to write something using the letter A, we will replace the letter A with the letter x

Maybe another example will help. How about the letter C? The letter C is the third letter in the alphabet. Therefore if we assign x to be 3 for the letter C and put into the formula 3x + 21, that will yield 3 times 3 plus 21 or 30. But 30 in mod-26 is..? 30 divided by 26, the remainder is 4. So, the y value corresponding to the letter C is 4 and that would correspond to the letter D. So every time we want to write a word using the letter C, it will now be replaced with the letter D. So, you can do  the same for all the other letters. So, for example if you want to write the word RACE in code using the encoding formula y = 3x + 21, you will end up writing in secret R, A, C, E using the letters W, X, D, and J. Of course, for proper communication, the receiver has to know how to decode the secret message. If the message is encoded using y = 3x + 21, then we just do our usual algebra to isolate x. And using mod-26, you can check this as well. The decoding formula you will you will arrival at should be x = 9y + 19. So, if you received a message in code, for example, I use R, A, C, E earlier which is W, X, D, J or, according to our partnering or the correspondence with the numbers, this will be 23, 24, 4, and 10. If you take these four numbers and plug them in as y values you should retrieve—if your algebra is correct—you should retrieve 18, 1, 3, and 5, and the corresponding letters would be R, A, C, and E so get back correctly the message RACE.

So, how are we so far? I hope everything is clear. You might be ready for an example. I’ll give you: Decode the letters D, N, N, and E— just a four-letter word D, N, N, E. Maybe you’d want to pause this video for three to five minutes and try to solving it first.

So, how was it? Were you able to decode D, N, N, E? What was the feeling after you decoded it? Let’s see if your answer is correct. The answer—the decoded word D, N, N, E—should come out to be the word COOL! C, O, O, L. And I hope that was your reaction once you are able to decode properly. Isn’t it cool to be able to encode and decode?

Now, for more sophisticated codes, do you need a modular system bigger than mod-26? Do you think that, to be able to make more things happen—more complicated staff, security and such—that you need symbols more than twenty six? No, on the contrary, you need a much smaller mod system. [Do] you have any guess what that modular system is? [For] the more complicated the system or the intended representation, here’s how the logic goes: the simpler should be your choice and number of symbols. So, that they are just repeated in what we call strings.

That modular system will contain only—I hope you guessed right—two symbols. It’s a Binary or Boolean system, which involves only 0 and 1. Therefore, for very complicated encoding or cryptography, don’t be surprised; all you’ll need are the two symbols 0 or 1 or the mod-2 system. It actually provides [the] clearest logic because, [with] 0 or 1, you just have a binary choice; just two decisions to make; open or closed; on or off; true or false; in color, black or white, right?

For example, you see very often black and white codes. The product codes you see in the [groceries]—those columns which are black and white—those are strings, actually, of zeros and ones. In two dimensions, you have the quick response codes. You also have strings in zeros and ones to make possible your personal identification numbers. When you send messages, when you send photographs in real time—this is all made possible by strings of zeros and ones. And, the reason you are able to download this video and watch it in high resolution is—you guessed right!—due strings of zeros and ones. In other words, the reason you are able to download this video and watch it in high resolution is due to a modular system.

Thank you for listening.