Tuesday, June 28, 2022

A Math Professor Taught Me An Amazing Trick

What is going on guys you are in for a treat today this is not my typical video i actually did a collaboration with another youtuber who is a math professor michael penn he has a channel almost 200 000 subscribers where he does all kinds of different math uh problems and he actually did this particular one that you can see here counting on a chess.

Board where he counted the total number of rectangles on a chess board so like all the different combinations of squares he went through how you could solve that anyway i hadn't actually seen that video but one of his subscribers saw that video and then.

In that video he actually reached out and asked if there were any chess youtubers who wanted to like give him a lesson and do a collaboration and learn some math tricks and so anyway one of his viewers who was also a subscriber to me let me know and that's how i kind of got in touch so thank you suli for sending me that message and letting me.

Know anyway we did the collaboration just earlier tonight i gave him a basic chess lesson and then he taught me a little math trick to to figure out something cool about numbers uh what you're going to see in the rest of this video is the math part of that collab so when he was teaching me the lesson.

Uh hopefully i don't make too much of a fool of myself and if you want to see the chess lesson where i give him the basic chess lesson that's over on his channel you can go over there i'll put a link in the description below so check that out if you're interested i think you're going to enjoy this.

I will say it's been a long time since i've done some of the things that we were looking at and so yeah uh anyway it's easier for me to play chess than solve math problems that's what i learned but yeah i hope you enjoy so i think i think these number puzzles are really cool.

In that they're pretty easy to do much easier than playing chess but they seem absolutely crazy right like it seems like uh impossible to just figure out in your head what the last digit of 433 to the 1297 is is that correct that it seems crazy or am i just so jaded uh.

Does it sound crazy yes it sounds it sounds okay cool that's the right answer um but by the end of this you'll be able to do it very very quickly i think if you plug this into a computer it would be too big for the computer to calculate.

Oh really okay and if it's not too big for the computer to calculate like the number uh you could make one up where it would be too too hard for the computer to calculate but you could still find the last digit very very easily with this trick okay with this trick okay but we need some.

Definitions okay okay so uh this is the definition of two numbers being congruent modulo in so here let me get a laser pointer so let's say you've got two these this is the symbol for integers so that just means like positive and.

Negative whole numbers and then this is all a positive whole number so we've got two integers a and b and we've got a natural number n and they're congruent mod n that's that's the word we use and this is the symbol this like a with a triple equal sign b mod n if.

When you take their difference that you get a multiple of n and so like that's equivalent to them having the same remainder when you divide by n so this idea of the remainder being the same is like super helpful and super important.

And may be way more helpful than it seems like it should be in that this sort of arithmetic where you forget about everything except for the remainder is like the underpinning of like all of modern cryptography and code breaking and like all of the.

Security on the internet is based around this sort of arithmetic okay so like for some examples yeah go no you have a question i think i'm okay i think i'm okay okay so here's some really basic examples so 10 is uh 1 mod 3 because notice if you take 10 minus 1.

You get 9. well let's write that so because 10 minus 1 equals 9 and 9 is a multiple of 3 right right yeah and or you can think of it as like if you do 10 divided by 3 you get a quotient of 3 with a remainder of 1.

And so this like remainder of 1 is the important part and that's why that's why you would say that these are congruent mod 3 because they have the same remainder and then 24 is 4 mod 5. so you can change this thing that you're working with.

Like uh you know depending on the example so here we're working mod 3 and here we're working mod 5. and so 24 is 4 mod 5 that's because if you do 24 minus 4 you get 20 but that's a multiple of 5 right it's 5 times 4. okay.

So that's why like you would say 24 is congruent to 4 mod 5. and then finally 138 is uh 8 mod 10 right because this one is even easier because you only look at the last digit right that's because if you do 138 minus 8 you get 130.

But since that ends in a zero it's clearly a multiple of 10. okay um and then you could do more complicated ones like i made some exercises for you for example okay.

So what would you say 15 is mod 4 i guess three because yeah yeah exactly so yeah okay right so that that's a good way to think about it the closest multiple of 4 would be 12. okay sure um yeah yeah so here you've got 15 minus 3 is 12. yeah and then.

29 29 so we would go let's see 24 so five yeah exactly five okay and then 13 26 40 what is that 52 so seven i think uh yeah yeah exactly yeah i tell my students like.

They're all afraid of like multiplying 13s but right the deck a deck of cards there's only 13 cards in each suit so it should be easy to multiply up to four that's a good uh good point and then this last one it's the easiest one nine yeah nine okay cool so as you as you can see like.

What we've seen maybe we'll say observation is that finding the last digit of a number maybe we'll call it n right and that number could be crazy you know let's say maybe it's a crazy number.

Um that's equal to and this is like the more technical way of writing this down so reducing it modulo 10 right so up here let's see if i can up here it's easy.

Right you we see the number 1279 it's easy to look at that and say oh i know the last digit is nine right because i see all of the digits sure sure and so like asking what the last digit of 1279 is is a totally boring question because you can see the last digit.

And so to answer that question you don't have to reduce it mod 9 but if you sorry mod 10 but if you go over here to our big goal i don't i can't see all the digits of this right right i mean this is like 533 to the power of.

1297. that's a that's enormous right it's probably got like uh 4 000 digits or something so it's probably got like 4 000 digits i can't see all the digits but i can find the last one if i have a trick of reducing at mod 10.

Without calculating the digits and it turns out there's a way to do that and so a priori it's not clear that there's a way to reduce it mod 10 without finding all the digits but there is a way and it involves this thing called.

Euler's theorem so euler was just like mathematician in the 1700s who like made up all of this number theory made up all of this number theory discovered a lot of this number theory back then and it's actually one of the biggest cases.

For pure math being important because the number theory had like no applications until the 1970s so it took like 300 years before any of this had any applications.

Okay but the application makes the internet possible okay so it's pretty important right yes so like whenever anyone's like ah pure math you know there's no point well there was no point in number theory for 300 years but.

Now it's like one of the most important things out there you guys said okay so in order to understand euler's theorem we need this thing called the euler totient function which is this this fancy fee right here so we read that as fee of n like the greek letter and what it does is it counts up.

All of the numbers between one and n that are we say relatively prime to n that means that they just don't share any divisors and so there's like a fancy way of calculating this fee of n but we don't need that for our examples and so let's look at these examples so fee of 6.

Well let's just list all the numbers between 1 and 6. so i think we probably know all those 1 2 3 4 5 and 6. and then we want to throw away all of the ones that have common factors with six so six clearly has a common factor with itself right uh two.

That's a factor of six right three is a factor of 6 and then 4 is not a factor of 6 but it shares one 2 right so 4 is even and 6 is even so they share 2 as a factor so we have to throw that away and so if we were to count up all of the.

Numbers that are relatively prime to six between one and six we would get just two so this fee of six is two and now if we were to do the same thing for 12 well you know let's list all these 1 2 3 4 5.

6 7 8 9 10 11 12. and then just go we'll go through and x those out too right so we can't keep two we can't keep three or four but five is cool right because it's not a factor of 12 or does it share any factors of 12. 5 is prime so we know 5 is going to be.

Cool regardless we've got to throw 6 away we can keep 7 we have to throw 8 away we have to throw 9 away 8 has a factor of 2 12 also has a factor of 2. 9 has a factor of 3 12 also has a factor of 3. we got to throw 10 away gotta throw 12 away but we can keep 11.

So notice we've got 4 in total so that means that fee of 12 is 4. and now we can do the same thing with 10. so let's do 10 1 2 3 4 5 6 7 8 ten so what what number would be fee of ten so we would throw out two uh we would throw up five.

Yeah in this one we we would throw out four because we have two and we throw six and eight i guess by the same reasoning uh that's right i think we would keep those so we had one two three four so five is that right no we have to throw.

Out ten also oh right right right so yeah and actually like that's super lame this is this is the general way that you write down this uh euler totien function with this like less than or equal to here and so we include the last number but the fact is.

You never like use this last number so you might as well like just make it a strict inequality to never have the last number on there but i don't know just if you were to read it in a textbook it always has this okay for somebody for some reason yeah so we would get four and then here's one more so if p is a.

Prime then the answer is always p minus 1 because every number 1 2 3 4 up to p minus 1 they're all relatively prime to p because because of the definition of a prime it only factors into one in itself interesting so that's just.

That's just kind of exactly the only one you throw out is itself okay um and i mean this like euler's theorem is a as a general case of this thing called format's little theorem for ma's little theorem which has to do with the primes for what it's worth okay so now that we.

Understand this function uh the euler's theorem says this it says that if you've got something that is relatively prime to n then if you raise it to the fee of n power you always get one mod n.

Not one just in the world but one mod n so let's see for example this seven to the 6 is equal to 1 mod 9 and that's because phi of phi of 9 is equal to 6. we didn't count up 9 but we could right 1 2 3 4 5 6 7 8. then we would throw away like six.

And three and one two three four five six numbers are left right uh yes so so we've got seven to the six has got to be one mod nine by this theorem this theorem has a fairly easy proof but you know it takes like 20 minutes to set it up and it's not super interesting if you're not into that kind.

Of stuff right and we could we could check this if we wanted to because 7 is fairly small and we would do it just by calculating 7 to the 6 which seems like totally daunting but since we're working mod 9 we can reduce it at every step so we can pair the sevens like this.

Then we know like 7 times 7 is 49 so really we've got three copies of 49 but then since we're working mod 9 we can reduce 49 mod 9. so what's 49 mod 9 pop quiz um so sorry i was thinking about something.

Else so 49 mod 9 um it's gonna be zero no no no no sorry um wait wait wait um let me think 49 mod 9. uh four four yep sorry i was uh.

Because it's uh four more than 45 right yeah so now we've got 4 times 4 times 4 but then if you multiply 4 times 4 times 4 you get 64 but 64 is 1 mod 9 because it's 1 more than 63. right.

64. i was following you right until we got to the example seven to the sixth one nine that's that's when everything kind of fell apart if i'm honest with you yeah yeah so this is just an application of this big result okay so this big result.

Says that if you raise a number right here to the power of this fee of n you always get one okay you have to get one so for example like let's do a simpler one maybe so let's do like this.

So let's use one of these over here so let's take like seven so if we take seven no we already use seven that's boring so let's say we take five so if we take five to the four power we'll get 1 mod 12. and so you might say well why is.

That how do we know that that's not how you spell y there are so many things wrong with that okay so how do we know that's true okay so first of all 5 and 12 don't share.

Factors we can agree with that right yes yes and that that's good because that means we satisfy this hypothesis right here so see this hypothesis that says the gcd has to be one that just means that a and n don't share.

Factors okay yeah okay so they don't share factors so that's the first set up and then so we'll say that's that's number one of y that should be a different color right then number two of y is fee of 12 is equal to four.

Because we counted it up over here right we count we counted it up over here and so euler's theorem so we'll just say euler he says that because one and two are true.

then 5 to the 4 has to be 1 mod 12. so like a theorem says that if your hypotheses are true so in this case these are the two hypotheses.

Right this uh let's see if we can do so this this hypothesis that i just highlighted there and in this hypothesis that i have here so these are both true then that means the outcome has to be true and the outcome in this case is that if you raise this number to this.

Other number you always get one okay uh one question so the the mod 12 was 12 was 12 just an arbitrary number that you picked or yeah yeah no we picked 12 uh just because it was like kind of in line with uh.

Our example that we did right here oh okay okay i see yeah so this this n right here can be anything okay yeah it just has to match this number okay yeah so we could do another one like check it out.

Um let's use let's use one of our ones like uh let's maybe do eight so let's let's say we work mod eight so that means we need to count up first one two three four five six seven eight so we gotta kill the even numbers because those shares factors with eight.

But we can keep all the odd numbers those are cool right yes because they don't share factors with eight so that's this tells us that fee of eight equals four so you might say michael it seems like a lot of numbers have a fee value of four like we've got 12.

10 and eight now that's just because we're only looking at small numbers okay so that does get bigger as you go yeah yeah yeah yeah it's unbounded it can go as big as you want um yeah it's just because it's like kind of.

A pain to look at larger numbers and you don't you don't win anything for looking at bigger numbers okay okay so now if we took like uh 17 so 17 doesn't share any factors with eight right correct because it's odd.

And then we raise that to the fourth power so euler's theorem says that has to be one mod eight okay now we could check that if we wanted to but we don't have to because there's a proof of this theorem.

And i mean that's one of the great things with math is that it's true right there's like no question of it being true or false it's like there's a question of is it useful or not but it's true so like this was proven.

And it was proven once for everything and it wasn't like data was collected and it's like something that seems like it's true oh it was it was proven from logical first principles that this is always true so that means that that we know that any example that we come up with is is going to be true so here we know.

That 17 to the four is one mod eight or like 23 or maybe 21 to the four is also one mod eight okay i think i'm on board with you there now okay cool.

So let's but what was happening with that 13 to 20 to the 24th yeah let's do that one so this seems this 13 to the 24 seems a little bit trickier but let's notice this.

24 is equal to 6 times 4. you would agree to that right and you might say well why did we factor it as 6 times 4 well it was important to factor it as 4 because 4.

Is equal to phi of 10. and you might say well why are we saying that we're interested in fee of 10 well that's because we're working mod 10 over here so if what you're reducing mod so like here we're reducing mod 10 so it's going to.

Be helpful to express things in terms of fee of 10 which happens to be 4. okay so what what's does that equal one there also yeah so this is going to equal one exactly even though you multiplied that four by six it doesn't change anything exactly.

That's because if you remember from sometime in your past so here's one thing that you can do is that you can notice that this can be reduced mod 10 before it even gets started so that's the same thing as 3 to the 24.

So you're allowed to do that so 13 is bigger than 10. so we can make it less than 10 by reducing it mod 10 before we even get started see what i did there uh-huh yeah and then.

You can do this next thing well which is like write this as three to the four and then to the sixth power mod ten because if you remember like i don't know i'm like so jaded that i don't know what people like.

To learn these kind of things but somewhere in your past you learned that there was this exponent rule that says when you raise an exponent to an exponent you multiply the exponents right yeah i promised that sometime that was thrust upon you yeah i'm sure it would i'm sure yeah.

Yeah yeah but that's cool because this fee of 10 uh it's 4 so that means that this 3 to the 4 is really 1. so that's 1 to the 6 but 1 to the 6 is just 1. okay so well what did we just do.

We just saw that the last digit of this 13 to the 24 is just equal to one and we didn't have to calculate it at all right right i don't know any other digits of 13 to the 24. i only know the last one and i.

Know that it's one but that's like exactly our big goal right right okay but before we go back to our big goal let's do a bigger example and let's do this mod 10 instead of no.

Let's change it a little bit let's do it let's make that into a one and let's do this mod 10 instead of mod 15 just because i don't think it adds anything to do it the other way so in other words let's maybe put in here that ie.

One of my students once like told me the difference between ie and eg i didn't know there was a difference and i don't remember what it was the difference i don't i don't know i don't remember okay uh yeah she was like more trained in that kind of stuff than.

I was okay so so in other words we're gonna find the last digit of 37 to the 1231. right so that's what this is doing right okay so here's what we can do so we want to do a little bit of a setup first.

and the setup is based around the fact that we used on the last board that fee of 10 is equal to 4. so that means that 4 is like really the most important exponent for.

This game that we're playing right correct because of because of what euler told us sure okay so now we look up here and we say okay well this number is like pretty gnarly but maybe we could like.

Extract as many fours out of it as we can and how do you do that well you do it with fifth grade arithmetic and i'm really just going to do long division right here so you would say okay well 4 goes into 12 three times.

Get a remainder of zero i bring the three down uh four doesn't go into three i bring the one down four goes into 31 seven times right oh yes yeah and that's 28 and then i got a remainder of three so here's a remainder.

Of three okay and now i'm gonna like do something that is hardly ever done in fifth grade arithmetic but it's exactly the same thing and i'm gonna write this 12 31 as.

Four times 307 plus three okay so that's the same right yes um now now we can get to work so we can take this 37 so let's see okay so we can take this 37.

To the 1 2 3 1 and we can start by saying okay we're reducing it mod 10 so that means i don't care about the 30 part of the 37 i just care about the 7 part right uh-huh then next i can look at this and see oh actually i don't care about any of these fours.

Because i know all of these fours will just give me a one right because of euler so that means none of these fours matter and all that matters is this remainder right here the three yeah the three so now i've reduced my problem.

To instead of calculating 37 to the power of 1231 all i have to do is calculate the number 3 to the 7. and now you could like rip that out pretty easily but there's that actually an even quicker way of doing it and that would be to write it as 7 squared times 7.

Then use the fact that 7 squared is 49 right okay and then 49 mod 10 is well known right you can reduce that to nine times seven but what's nine times seven five.

63 i guess yeah 63. yeah but now 63 is just three huh right so like look we could have i you know i don't i think i'm not really good at my cubes or.

Whatever but i think 7 to the 3 is 243. um but if we were to multiply that out you know would take a long time but if we just do simple multiplications along the way like we did right so we just did this like splitting.

And then one simple multiplication at a time and then reduction every time it gets too big it's a lot easier right right so and that's what we did everywhere right we said oh 37 that's too big i don't want to work with that let's work.

With seven instead this like 1231 that's too big i can just work with three instead because of euler right and so like any time things start getting too big you can just reduce it interesting okay so now.

since you can't interact with my uh ipad or whatever you can just tell me what to do so what do i do uh so we need to let's see first take away as much as we can from the 433 yeah so.

I guess using 10 we can turn that into three is that right yeah yeah exactly so yeah the 433 we don't care about the 43 or the 430 part because we're reducing mod 10 and we're reducing mod 10 because this last digit game.

Right and so now we've reduced our problem to this which is still looks pretty gnar because we've got that huge number of the exponent but at least we've like reduced it a little bit so what would you do.

Next right um so we have to reduce the exponent using the uh boilers part yeah yeah yep um so i'm trying to remember exactly how you did that uh so because it's mod 10 we know that that's four right right so we have to.

Basically divide 1297 by four right okay and then we'll we'll get some remainder yeah so what remainder will we get um yeah good question three again wait is that right.

Yeah four times 24. yeah we get a remainder of three okay okay so given that we have a remainder of three what do we do now so you can rewrite that 1297 to be uh four times 326 plus three.

Exactly okay so we have three to the 4 20 times 326 plus 3. yeah so 3 to the 4 times 3 2 6 plus 3. i think that's what you said and i'm trying to remember what was the next.

Step um so now i'm gonna i'm gonna we sort of skipped a step over here i was like sort of showing you a trick to skip a step so notice we just skipped from here to here wait let me get my laser pointer we skipped from here just to the remainder in the exponent.

Which is like oh right i don't know that it's i wouldn't say that it's cheating but it's definitely like a second time through a problem like this you would want to do something like that not a first time so here i'll do another step in the middle right here so.

This is maybe the step that i would do in the middle this is 3 to the 4 all to the 326 times three to the three so that's using these like exponent rules where right if you have certain uh operations in the exponents they trickle down to other operations in the base.

Okay so this is maybe a more proper way than our example over here but you're saying we could have just went straight to three to the three power yeah yeah but maybe talk through or okay why why we could just go straight three to three like what happens to this first chunk.

Right like what happens to this first chunk um so let's see so the question is why don't we care about it um yeah so remember what euler says euler says that if you raise a number to fee of n you always get one.

So it doesn't matter how many uh copies of that we have we it's still gonna just exactly so i think i don't want to put words into your mouth but i think you're saying that this is just one right and then if you have one.

To the 326 you don't care right exactly because it's just one exactly i think that's what i was saying i believe i believe that's what i was saying okay so we so we ended with three to the three so i think we're at the stage where you can just.

Say the answer so what's the last digit of three to the three um so that's 27. so 7 yeah so that's it wow so.

Let's see what we did what we did in fancy math terms is we just see if i can find the color i want is we just took this number and showed that this number was congruent to 7 mod 10 but in terms that you can like stop someone.

On the street and talk about we just showed that the last digit of this very very large number 433 to the 1297 was 7. and we did it in one two three four five lines right yeah one line was a little bit extra and the hardest thing that we did was.

Fourth grade long division right pretty sweet right yeah that's pretty cool that was pretty neat alright guys i hope you enjoyed that um if nothing else it reminded me of how rusty i am when it comes to some of the math stuff that i've learned in the past it's crazy how.

When you don't use something you just kind of forget a lot of it um but anyway i hope that was enjoyable don't forget check out his channel you can see the chess lesson over there the link is in the description below and as always thanks for watching stay sharp take care.

RELATED ARTICLES

Most Popular