Transcription
This video was sponsored by Brilliant. Pick any integer and raise it to the 5th power, and the ones digit will remain the same. Or take any prime number besides two and three, square it, then subtract one. That number will guaranteed be divisible by 24. In fact, take any prime number squared and subtract another smaller prime number squared, so long as they're both greater than three. That result will be divisible by 24.
These are a few examples of problems from a number theory book I spent a few months going through after gaining an interest in the math behind cryptography. Oh, there's a lot of detail in this branch of math. I wanted to show you guys some of the very basics in a visual way that isn't as common to see. So let's start here.
If you want to determine whether 119 was prime, or whether no integers go into it evenly besides one in itself, how many divisors would you have to check? Like, 2 doesn't go into 119, of course. Then if you went to your calculator and did 119 over 3, you'd see it doesn't go in evenly either. But how many numbers do I have to try before I can say it's prime or not for sure? The answer is sort of four, but really two. And by that, I mean hand me a calculator, and I'll tell you in two tries whether 119 is prime or not. And we'll see why in a second.
Now, these right here are the first several prime numbers. Nothing goes into them but one and themselves, and they're infinitely many of these. All other numbers that don't appear here, like 30, are made up of two or more of these primes. So instead of seeing a number for what it is, you can see it as what it's made up of. And note, there's only one way to make up a composite number using primes. Well, as a new example, 3 times 7 times 11 is 231. These three numbers are prime, and thus the only ones that go into 231. From this, I can tell you that 231 is divisible by combinations of these primes, like 21, or 77, or 33. But it's not divisible by 13, or 17, or 19, and so on, because like we said, there's only one possible representation.
So now, if you were asked, like, is 18 factorial divisible by 23? You could immediately say no. You, whatever 18 factorial is, it's made up of primes that are all less than 18, like 17, and 13, and 11, and so on. Then any composite, such as 15, are some be made up of primes less than that, or 5 and 3 in this case. You won't find a prime greater than 18 in here. And since there's only one way to represent 18 factorial as a multiple of primes, just like any other number, and I can safely say it's not divisible by a 23, or 29, or 31, and so on forever.
With that background, you now should be okay with this theorem: For any composite number, x, one of its prime factors must be less than its own square root. To see why this is true, let's just see what would happen if it wasn't. For example, the square root of 129 is about 11.35. Now, let's just say there are two prime factors of this number. The theorem above says one of those must be less than 11.35. Because if that weren't the case, and they were both greater than 11.35, like let's say 13, the next prime number up, we've already exceeded 129 when we multiply those. So one of the primes has to be smaller than that square root. In this case, 129 is made up of 43 and 3, which goes with what the theorem says.
Now, if we take the number 119, the square root of that is about 10.9. Thus, if it is composite, one of its factors must be less than 10.9. And the only primes less than that are two, three, five, and seven. I know two and five don't go into 119 just by looking at the ones digit, of course. So really, I just need to check two numbers. Three does not go into 119, but seven does. Thus, its composite, and only took two tries to figure that out. And now, if you wanted to determine whether 901 is prime, you know you only have to check primes less than the square root of that, or about 30, which is only ten numbers, or really eight if you exclude the obviously wrong ones of two and five.
But now I want to show you something called wheel math. Okay, not really, it's called modular arithmetic, but I'm gonna stick with wheel math to keep this video as visual as possible. First, I'm gonna make a wheel of numbers. And to begin, it will have seven spokes or sections to it, although I could have picked any number I wanted. So let's see what this tells us. The wheel starts at zero and goes around to six, and then jumps up to seven, and it continues going around in this spiral. One thing to note is that as we move up some section, we simply are adding seven each time, which means this section starting at zero is the numbers divisible by seven section. Another thing you'll notice is this tells us the remainders when we divide by seven. Like, if I have 15 guests over for a party, I want to make teams of seven. I can make one, two teams with one person left over, aka one is the remainder. And if I had 25 friends over, I can make one, two, three teams of seven, which would leave four left over. Any number that's divisible by seven, of course, would have no remainder. By the way, two values being in the same section, like two and nine, means they're congruent modulo seven, but again, I'm gonna keep this video as visual as possible and hold off on all the official notation.
Now, math on this wheel gets interesting. To start off, pick any two numbers, let's say two and three. Then add them, and the result of course be five. But if we pick any two numbers on those same initial sections, like nine and seventeen, the sum of 26 will lie on the same final section. And the same thing happens with multiplication. Two times three is of course six. So something like nine times seventeen must give us something on that same resulting spoke. In this case, 153. Then if I add one to that, we get 154, taking us to the next spoke over. And now, just by looking, I know that number is divisible by seven since it's in that divisible by seven section of the wheel. See, this is where it gets more interesting. Like, since I know that two times three plus one is divisible by seven, I also know, let's say this time, 16 times 24 plus one is also divisible by seven. And that's because these sets of numbers all lie in the same section on our seven spoke wheel.
And to continue with the basic arithmetic, this applies to exponents as well. Two squared is of course four. And this tells us that anything in this blue section squared will output a number in this green section, where we found the two and four respectively. So since, like, 16 squared is 256, I know I'm gonna find that number further up this green section. This isn't deep math or anything, by the way. I mean, when we square some number X, it becomes X squared, of course. And when we take a number on that same spoke as X, which would just be the same thing plus some integer multiple of seven, and square that value, after some simplifying, it just turns into X squared plus an integer multiple of seven. Therefore, it's on the same spoke as X squared from above. And yes, this will work with any integer exponent, by the way.
So now, take a look at the number one on our wheel. Since one to any power, I'll just use 26, is itself, or one, and therefore maps to its own spoke. I know that anything else in that section, like 15, will always map to the exact same section when you include any integer exponent. Thus, I know 15 to the 26, or any other integer exponent, has a remainder of 1 when divided by 7, since it'll be in that same section as 1.
So now, in a matter of seconds, you can answer some seemingly tough questions that you may not have been able to do a minute ago. Like, is 8 to the 167th minus 1 divisible by 7? This is actually really easy to do. I don't know what 8 to the 167th is, but I know 1 to the 167th is 1. Thus, 8 to the 167th will give us a value also in that same section, just higher up. Then when we subtract 1, as the question asked, we move one spoke over and land in the one where all numbers are divisible by 7. So the answer to the original question is yes, with no intensive work required.
But here's the least intuitive property I'll discuss, which works since we're using a prime number of spokes, or 7 in this case. Take any number not divisible by 7, like 2, 5, 15, or whatever, and raise it to the 6th power, or 1 less than the number of spokes we have. And that resulting value will always land in the section that has a remainder of 1. This will always be the case with prime wheels. As then, if we had a 5 spoke wheel and took maybe 12 and raised it to the 4th, our prime number minus 1, the resulting will definitely be in that same section that has one as the remainder, just like before. And also, like we saw earlier, we can do fast math and say that 12 to the 4th minus 1 is divisible by 5 because it lands in the divisible by 5 section of this new wheel. This is Fermat's Little Theorem, again, written like this. To break this down, it says that on a wheel with a prime number of sections, any number, we'll call A, raised to the power of our prime minus one will be in the same section as the number one, so long as A is not divisible by the prime.
So when asked something like, what is the remainder when 2 to the 100th is divided by 101? It's actually really easy. Since 101 is prime, then anything that's not a multiple of 101 raised to the 100th, or that prime minus one, will be in the same section as 1, and thus that will be the remainder.
Another cool property that works for any wheel with a prime number of sections is that if you take any number, raise it to that prime power, or 5 in this case, the result will be in the exact same section. And this kind of answers what we saw in the beginning of the video. You'll notice that on any section, every other number has the same ones digit since they're 10 apart. So like, all of these numbers are ones that end in two or seven. Now, we just saw that any number to the fifth stays in its own section on this wheel. So doing that operation either keeps the same ones digit or changes it by five, such as two going to seven, or seven going to two. Except when you raise the number to the fifth, odds will stay odd, and evens will stay even. Thus, the second option isn't possible, and any number to the fifth will retain its ones digit, as mentioned in the beginning.
Now, if we make a wheel of 12 numbers, some cool things come from it. One thing to note is that all the primes show up on only four spokes. The only exceptions to this are the numbers two and three, which are the only primes on these two right-hand spokes here. Again, this is nothing deep, as with most of this video, honestly. It happens simply because the primes that make up 12 are only two and three. So in those sections, as we add 12 and move up our wheel, the result numbers will all be divisible by two or three. In fact, all the sectors that consist of composite numbers start with a number divisible by two, three, or both. The sectors with primes on the other hand, all start with a prime number or the number one. So this isn't groundbreaking or anything, but I find it to be an interesting way to just look at numbers and primes.
Then going back, if we multiply two primes together besides two and three, the resulting value will also be in the same sections as the prime, just filling in some of the gaps. But the weirdest thing is that any prime number squared, besides two and three, will land in this section. This means any prime number squared minus one lands in the next spoke over, or the section where everything is divisible by 12. I mentioned this earlier, but an even stronger case where any prime squared minus one is divisible by 24. If you want to know why, just note that P squared minus one can be written as P minus one times P plus one. And on a number line, we can write P minus 1 and P plus 1 around the original prime P. Now, since P is prime, then it's not even because it's greater than 2, meaning that P minus 1 and P plus 1 are even, or divisible by 2. But every other even number is divisible by 4. So either P minus 1 or P plus 1 has a factor of 4. It's easier to see this with examples, like if these numbers were 30, 31, and 32, one of the even numbers must be divisible by 4, which 32 is. Then of 3 numbers in a row, one of them must be divisible by 3. It's not P since P is prime, so it's gotta be one of the others. This means that 2, 3, and 4 are factors of P minus 1 or P plus 1, and those multiply to 24. Thus, 24 is a factor of the original number.
Now, earlier in the video, I talked about dividing a number by 3. As I'm sure many of you know, when it comes to 9 and 3, divisibility is actually really easy due to a certain rule. The rule is, if the sum of the digits of a number is divisible by 9, then the number itself is divisible by 9, and the same goes with three. As in, 972 is divisible by 9 because 9 plus 7 plus 2 is 18, which itself is divisible by 9. The reason for this is I can write 972 as 900 plus 70 plus 2, which can break down further to 9 times 100 plus 7 times 10 plus 2. A hundred can then be written as 99 plus 1, and 10 as 9 plus 1. Then if I distribute everything, we're left with this. These terms are both divisible by 9 due to the 9 and 99 in them. So in order for the entire number to be divisible by 9, the last terms combined must be, which are the digits of the original number.
A slightly more official term for working with 9s, though, is the digital root. To calculate the digital root of a number, let me just show an example. If we want to find the digital root of 921, let's say, we just add the digits together, giving us 12. We then add those digits together, giving us 3. Once we're down to one digit like this, we have the digital root. The cool thing about this is that it tells us how far a number is from being divisible by 9, aka the remainder. In this case, we see that 921 minus 3 is divisible by 9, which you now also know because the digit summation.
Another property, if we go to Brilliant's site, is that digital roots do not change when you add or remove nines from a number. So like, we saw 921 has a digital root of 3, yet so does 9,921, and 99,921, and so on. Adding nines doesn't change anything, which means this huge number's digital root is 3, and thus it is 3 away from being divisible by 9. And this just comes down to the fact that if we remove all the nines, leaving us with 21, that's also 3 away from being divisible by 9.
Then something even weirder is that digital roots multiply. As in, if you want to know how close this result is to being divisible by 9, you multiply the individual digital roots. Since these nines don't matter, like we just saw, we can remove them. This means the digital root of each number is 1, and that's when we multiply them, the final digital root is of course 1. So I don't know what this large value is, but I know if I subtract 1, it will be divisible by 9.
And just because we've seen 24 come up in this video in a kind of surprising way, here's another example dealing with digital roots. These are the first 24 numbers of the Fibonacci sequence, if we exclude 0, where you add the two previous numbers to get to the next. And these are the associated digital roots. Strangely, the digital roots you see here repeat this pattern forever as you go through the Fibonacci sequence, reoccurring every 24 numbers. Not going to go into more detail beyond that, but I just found that interesting.
Now, after all this, you may be saying, yeah, this can help me do fast math, but can it help me write secret codes? Okay, maybe you weren't thinking that, but still, the answer is yes. Like I briefly mentioned in the beginning, I've done an entire video on the math behind cryptography, but for those who just want to know how the things we saw here apply to encrypting messages, here's a quick explanation.
First, just imagine a world before cryptography where you want to communicate with someone you've never met before, yet there's an eavesdropper in the middle of you two who can hear anything you say or see anything you do. My question is, how would you communicate a message to the other person secretly, just by shouting over to them? You can communicate anything: a place to meet, a secret number, a secret phrase, or whatever. But the eavesdropper, who can hear everything, is not supposed to understand what you said. And assume you all speak the same language, and none of you guys know each other. So see what you can come up with. Yeah, it's definitely not easy if you don't have time to communicate beforehand.
But here's one thing you can do. Tell the person we'll be doing some math on a wheel with 17 sections, and we're going to pick a base value of 5. I didn't have to pick these numbers, but I'm just using them for some place. So yes, you've said this out loud, which means the eavesdropper will be in on everything so far. But then you tell the person to think of a secret number and don't say it out loud. Well, you do the same thing. So let's say they choose 4, and you choose 3. Now, you do that base value of 5 to the power of your secret number, which gives us 125. And then you find the smallest number on that section of the wheel with 17 numbers. 125 will be in the same section as 6, and 6 is what you tell the other person. Then they do the same by calculating 5 to the 4th, which is in the same section as 13 on our wheel, and they tell you that value. So now the eavesdropper has these two values as well, but not the secret numbers. Lastly, you take their value of 13 and raise it to your secret number of 3, and again, find where that is on our wheel, which is 4 in this case. The other person does the same, and they will guaranteed get 4 as well. This number is then your secret key. We haven't shared a message, really, but we have established a secret key that we can then use to encrypt messages. For example, now we could like shift the letters in our message by 4 to communicate. Although, no, that is not what modern cryptography does.
What you saw was the basics of the Diffie-Hellman protocol, and the reason it works to establish a secret key is because it is easy to do the math. You just solve for words, but it is very hard for the eavesdropper to take the numbers he has and work backwards to figure out your secret numbers and therefore the final key. Algorithmically, it would just take too long. Not with this example, but when dealing with numbers hundreds of digits long, going forward is doable fairly quickly, yet going backwards at the moment just isn't feasible in a short amount of time. So you can have a secure form of communication even if someone's watching.
Now, everything you saw was really just scratching the surface of this branch of math. But if you found this content interesting, I recommend checking out Brilliant's number theory course, where you'll learn a lot more. There you'll be taken through all the basics like you saw here, but they also include interactive exercises and show unique applications of all the underlying math in much more detail. This includes things like analyzing the trajectory of a pool ball on an ideal table, certain dimensions, or how to mathematically solve a number theory puzzle those famously portrayed in the movie Die Hard 3. On top of number theory, they have differential equations, complex analysis, logic, and over 50 other courses to choose from that all come with practice problems and interactive exercises to ensure you fundamentally understand each concept before moving off. On top of this, they have daily challenges that turn learning into a habit, so you can look forward to learning a range of topics from quantum physics to geometry puzzles and more.
So if you wanna get started right now and support the channel, you can click the link below or go to brilliant.org/majorprep to get 20% off your annual premium subscription. And with that, I'm going to end that video there. If you guys enjoyed, be sure to LIKE and subscribe. Don't put the follow me on Twitter and join the major Facebook group of hits on everything. Hit the bell if you're not being notified, and I'll see you all in the next video.