MAML, Number Theory: Modular Arithmetic

MAML, Number Theory: Modular Arithmetic


Hello, everyone, this is Noble H. Mushtak and today, we are here with another Maine Association of Math Leagues problem, Meet 1, 2011-2012, Round 4, Number Theory — so a new topic — Now, we have to deal with the properties of numbers. Problem 3. Find the remainder when 23 to the 15th multiplied by 47 to the 17th is divided by 5. This is a very big number and we need to find the remainder. There’s two choices you have: (Well, more than two choices.) (Actually, much more than two choices.) But two choices that come into mind: a) Guess. If you have no idea how to solve this problem, you have a 1 in 5 chance of getting this problem right. It’s either 0, a 1, a 2, a 3, or a 4. If you know some properties of numbers, you might be able to guess that it’s not 0 because this is not divisible by 5. I’ll get to that why in a second. So it’s not divisible by 5, so we have a 1 in 4 chance: 1, 2, 3, 4 You can just guess, see if you get the right answer. But we’re not going to guess because we know what we’re doing and we know modular arithmetic. Now, modular arithmetic is dealing with the reaminders of numbers. So, let’s say 6 modulo 5. That is congruent to 1. In this video, we’re just going to use the equals sign, but it’s actually three lines and it’s a “congruent” sign. So, yeah. Right here, I’ll put an annotation to a modular arithmetic tutorial on Khan Academy. And I’ll also put a link in the description. I really like this tutorial on modular arithmetic. So, yeah. Basically, this is just finding the reminders of numbers. So, like, 3 modulo 5 — The remainder of that is 3. 5 modulo 5 — The remainder of that is 0. On and on… — Yeah. This is actually really helpful in cryptography and information theory and it’s also in group theory because modulo is a group which is very complicated; you don’t need to know what that is. Basically, if you don’t know the properties of the modulo operator and modulo arithmetic, then I have no idea how you’re going to solve this problem. They don’t teach modular arithmetic in school, which makes this even harder to do. So if you do know how to solve this problem, good job! Good job. But if you don’t, that’s OK. They don’t really teach you how to do this in school at all. Just like many other MAML problems. How do we find the remainder of this number divided by 5? First, it’s not divisible by 5 because 23 is not divisible by 5, obviously, and 47 is not divisble by 5. So you have to realize that this is just a bunch of 23s and 47s multiplied together. So since there’s no number divisible by 5 multiplied into that, you can’t have any 5 times this number equals our number right here because there’s no 5 in here. So we know that the answer is not 0 because it’s not divisble by 5. And if it was divisible by 5, then, obviously, the remainder would be 0. So it’s not 0, we know that much. If it was 0, then we could just write down 0 which would make it very easy to solve. The first thing you want to check is if it is divisible by the divisor, because if it is, then that’ll make this much eaiser. But it’s not. So now, we need to find whether or not it’s 1, 2, 3, or 4. So the way we do that is we use the following property. So when we have a product of two numbers, a and b, and we find the remainder of them with the divisor c — That is the same as finding the following: The remainder of a divided by c TIMES the remainder of b divided by c. This is kind of like a distribution of modulo c to a and b over multiplication, and this can be really helpful because it really makes it easier to solve. So…Yeah. We can just break it up into two modulo problems like this. So we’ll do that here. [writes math expression on screen] 23^15 modulo 5 times 47^17 modulo 5. Now, we have two modulo problems. 23^15 and 47^17. So, they’re both still very big numbers, but, now, as you can see, we have them both in the form of a^b modulo c. So — c is just modulo 5. So, you see here, this is 47^17: That’s just one exponentiation problem. This is 23^15: That’s just one exponentiation problem. So that’s what we wanted to do to this. We wanted to get it into this form. Now, you might ask: How do we solve a^b modulo 5? Well, let’s start with the specifics, let’s start with 23^15 modulo 5. Now, remember that 23^15 is just 23*23*23*… all the way through. So it’s just (23 modulo 5) times (23 modulo 5) times… And we keep going and this is 15 times. So it’s 23 modulo 5 to the power of 15. What’s 23 modulo 5? Well, that’s the remainder of 23 divided by 5 and that’s just 3. So 3^15. Now, 3^15 is a very big number which we are _not_ going to calculate. But — And it’s definitely not 1, 2, 3, or 4 — So we need to take the remainder of this divided by 5. So now we need to find the remainder of 3^15 modulo 5: So how do we that because that’s (3 modulo 5) to the 15th and that’s — and saying that isn’t going to help us because that’s just 3^15 again. The way we do this is that we break it up into a product of powers. And the way we do that is that we get 15, which is our exponent, in binary. So it’s 15 in binary. Well, it’s 8+4+2+1 I just know that off the top of my head. Different people have different ways of converting numbers to binary; You should have one way of converting numbers to binary because it’s really helpful in MAML. So this is 1111 in binary. Now, what we really need to know — and this is the important part — is 8+4+2+1. So if you remember your exponent properties, then you can remember that this can be broken up into 3^8… [writes math expression on screen] So 3^15 is 3^8 times 3^4 times 3^2 times 3^1, which is 3, modulo 5. The way we got that is because 8+4+2+1 is 15, so we can break it up into different powers. So like 3^4 is 3^2 times 3^2 because 2+2=4. This is just the same thing, except with 8+4+2+1=15. Now, we need to figure out the modulo of 3^8, 3^4, 3^2, and 3. [writes math expressions on screen] OK, like that. So, we already know 3 modulo 5, that’s just 3. What’s 3^2 modulo 5? That’s — 3^2 is 9. And 9 divided by 5’s remainder is 4. And then 3^4 — Well, 3^4 is too big for us to calculate. So, we’ll just keep that and we’ll just keep that. [writes math expression on screen] OK, so we — [fixes typos] Sorry, lots of typos here. So we can just calculate, now, 3^4 modulo 5 and 3^8 modulo 5. The way we do that is that we break 3^4 up into 3^2 and 3^2. So, first, 3^4. [writes math expressions on screen] So, we need to calculate 3^4 modulo 5. We can just break that up into 3^2 and 3^2. [writes math equation on screen] Now, we already calculated that 3^2 modulo 5 was 4, so this is just 4*4. [writes math expression on screen] 4*4 is just 16. 16 divided by 5: The remainder of that is 1. Now, we know that this is 1. OK, so now, remember that. And now, to calculate 3^8, we just break it up into two 3^4s, because 4+4=8. So 3^4 modulo 5 [writes math expressions on screen] So, 3^4 modulo 5 is 1, so this is just 1 times 1 modulo 5. 1 times 1 is 1: The remainder of 1 when divided by 5 is 1. So this is also just 1. So this is 3*4*1*1 modulo 5 which is 3*4. 3*4*1*1 is just 3*4 because 1 times anything is the same thing. 3*4 is 12. The remainder of 12 when divided by 5 is 2. So that’s just 2. So you see this? We just solved this problem. This is 2. That’s it. Now, we just need to do the same thing with 47^17. [writes math expressions on screen] [waits in silence] Oh. First, we need to break up 17 into binary. So you might know your powers of 2: 1, 2, 4, 8, 16: 16. 16+1. That’s it. So we just need to figure out 47^16 No, 47 times 47^16 modulo 5 47 modulo 5 times 47^16 modulo 5. So what’s 47 divided by 5? The remainder of that. That’s 2, so that’s just 2. And we can also — Remember how we replaced 23 here? We replaced it with 3 when we were calculating the modulo because 40 — 23 divided by 5 modulo 5 is just 3. Well, we can do the same thing here, so instead of 47^16, we have 2^16 modulo 5. Now, if you know your powers of 2 really well, we actually can just calculate 2^16. So, we’ll just calculate our powers of 2. [waits in silence] 2 to… 2^2 is 4. So 2^4 is (2^2)^2 is 16. 2^8 is (2^4)^2, which is 256. And 2^16=(2^8)^2, which is… OK, so this is where we have to stop because the numbers are too big. But, basically, now that we know that 2^8 is 256, so we can just calculate 2^8 modulo 5 times 2^8 modulo 5 The reason we can do that is because we know that 8+8=16, so we’re breaking it up into 2 8s. We’re breaking 16 up into 2 8s. So what’s 256 modulo 5? That’s congruent to 1, so this is 1. 1*1 modulo 5. 1*1 is 1: The remainder of that when divided by 5 is 1. 2^16 modulo 5 is 1. So now, 2*1 modulo 5: 2*1 is 2: 2 modulo 5 is 2. So that’s also just 2. Just like before. [backspaces work] Now, we need to figure out 2*2 modulo 5. What’s 2*2? 4. What’s 4 modulo 5? 4. That’s it. So, yeah. That was a pretty hard problem, especially since they don’t teach you this in school. They don’t teach you that at all in school. They teach you logarithm properties, but they don’t teach you modulo properties, which I think is kind of a shame because I like modular arithmetic. So…Yeah. I thought this was a fun problem if you know modular arithmetic. If you don’t, then it was probably very hard. Especially if you were confused by the binary part. If I took the time to really teach you how to do binary, I think this would be the wrong video for it because it’s modular arithmetic on top of binary, so.. Very complicated problem. Don’t feel bad if you didn’t get it. But if you did get it, really good job! So the answer’s 4. Very — V-v-v-very — They’re very hard problems to do, but it’s either 1, 2, 3, or 4, so you have — Like it’s a multiple choice question, except it’s EXTREMELY hard. So it’s an EXTREMELY hard multiple choice question. Even though it’s not multiple choice really, but… So, yeah. I hope you had fun doing this problem and have fun doing math!

One thought on “MAML, Number Theory: Modular Arithmetic

  • July 27, 2015 at 10:09 pm
    Permalink

    Good work, thanks for sharing.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *