The Freshman's Dream (a classic mistake) - Numberphile

so today I'm going to tell you about something called the freshman's dream so uh this is a very common mistake that uh you might be tempted to make it an algebra if you're naively playing around with exponents a plus b s is a 2 + b s why why is this called the freshman's dream I tried to look this up a little bit it's less than 100 years old there are some text references to saying that this is a fallacy you might expect or uh you might teach incorrectly to freshman but it's uh it's gained

sort of a name of its own and it's h it's referred to it like that it even has its own Wikipedia page at this point you are like a university Professor type person aren't you so you deal with freshman quite a lot would a freshman actually make that mistake of thinking that's true well um uh it happens on a regular basis right so uh and maybe it happens a lot earlier in school as well um there are variants of it that people also make all the time and just playing around with other things let me

put a a random another way to write it down you might be tempted to hope that the square root of a sum is the sum of the square roots and of course both of these things are false this is very easy to see just for some silly example of course 1 plus 1 s is four right which is not the same is 2 1 2 + 1 2 what is the correct way to do a s+ b s great back when I was in school we called this foil but you want to expand this out

term by term right and so here the freshman's dream forgets all of the mixed terms or the middle terms so the 2ab so while it's false in general right it's true if two happens to be zero today I want to talk to you about the the scenarios in which it is true all right and uh some ways where you can exploit it and uh some things where you can see that it's true and why it's why it's true how are we going to do it where do we start this journey all right so um so

the start of the journey is really to talk about clock arithmetic in clock arithmetic you treat all numbers the same if they differ by 12 the number of hours on the clock in usual clock arithmetic uh two numbers are the same if they differ by even a multiple of 12 so 1:00 13:00 are the same 12:00 24:00 36:00 are all the same we just want to treat all of the whole numbers the same if they differ by multiples of 12 so um if you fast forward 50 hours you have increased whatever you had by only

two instead of 50 for the freshman's dream I want to kind of play on that and talk about the two clock imagine a clock where instead of having numbers from 1 up to 12 it only has say one and two right there's only two hours in uh that are accounted for that leads you to the idea well what if I just play around with numbers um I treat all of them the same if they differ by two all right so 1:00 3:00 5:00 are all the same 2:00 4:00 6:00 all the same and and playing

off the same idea I could go in the other direction too minus 1:00 is the same as 1:00 - 5:00 is the same as 7:00 so uh I treat all numbers the same in particular two and zero are the same in two clock arithmetic or or mod two as you would call it there's only really two numbers up to this equivalence that you'd play around with right there are the odd numbers and the even numbers right so either you're an odd hour or an even hour and there's nothing else on this clock so the freshman's

dream when you're playing around with two clock arithmetic or mod 2 arithmetic is going to be true right so if two and zero or the same thing of course this middle term just goes away completely and I end up precisely with the freshman's dream a + B2 is equal to A2 + B2 because that two no longer has any influence this two here is the same thing as zero so no matter what I put in it doesn't matter when I'm playing around with arithmetic on the two clock I might write 5 + 4^ SAR now

I could add these two together and get um right 9 s so gives me 81 which I know is the same thing as just one on the two clock all right and of course that's the same as if I did 5^ 2 + 4^ S here again this is really 1:00 plus 0 o' or 1:00 plus 2 o'cl however you want to say it right gives you 1:00 and so the equations all still hold right and it's because whatever I had from these middle terms didn't matter right so it was zero mod two okay if

we lived in a world where the number system was mod two The Freshman wouldn't be mucking up that'd be quite correct in how they expanded that equation it's almost like you're saying that the world has only daytime and night time and all that matters is whether the sun is out or whether it's not everyone uh at some point a lot of people make the mistake of trying to write down square of um 5 plus the squ of 4 equals the sare of 9 and hope that this all works again if you're working mod two or

on the two clock right then this just works right squ of 3 plus of 7 of course it doesn't equal this uh normally right but on the two clock square of three again well three is just one right so one squar is one so this might as well be one again of course 1 + 1 is zero on the other hand again 10 is z on the two clock somewhat of a variant of the freshman's dream is that the sum of square roots is the square root of the sum and that just works cool what

happens to the freshman's dream in other mods you could talk about other clocks so for instance I could talk about the three clock right and while um I in that case I wouldn't want to play around with square roots I would want to play with or or squares I would use cubes instead right so um on the three clock so we're dealing with a different freshman's dream here the the a plus B Cubed that's right on the three clock the only ones that show up on the clock are 1 two and three or 0 1

or two depending on what your your conventions are on the three clock now I get 3 equals z so again we can convince ourselves that on the three clock a plus B Cubed is a cub plus B Cubed of course again normally never true if I take a 1 Bal 1 I get 2 Cub which is8 and that's totally different than 1 Cub + 1 Cub which is two just to remind me how how would one normally expand this I really can break this up multiply out one by one take the first part take a

plus b^ s and then I have to multiply one more time times a plus b If I multiply all that out and group all the terms right I'll get a cub + 3 A2 b + 3 a^ 2 + B Cubed and again because we're working on the three clock in much the same way I have these threes showing up here right and both of those don't matter right so the three times anything right any multiple of three is zero on the three clock so again this works and I can do the same games with

cube roots and things like that in this case as well so I guess the next thing I want to tell you about is why this works or or what might be true more generally right more than just on the two CL and the three clock and so that leads us very naturally to um the binomial expansion and to pescal Triangle and and things like that if I want to do this on other clocks bigger clocks the first thing I need to know for sure is how to take that expression a plus b to the something

and write it all out right so here we did it for three by first expanding the square and then multiplying again and I had to group all the terms the first thing to say is there's a a shortcut I can just tell you what it is without having to expand it all out so this is the binomial expansion but here I have Pascal's triangle here I'm going to start off with a one in the first row right and in my mind it's blanketed by zeros uh across it on both sides and as I descend I

just add two numbers above each other to create a new row right so 0 and one gives me a one 0 and one gives me a one over here all right now at this point 0 and one gives me a one on the outside but 1+ one is two 0 and 1 gives me a one and I keep iterating this 1 1 + 2 is 3 2 + 1 is 3 again 1 over here and you can already see that the numbers that I had from squaring it uh A2 + 2 a + b^ 2

or a cub + 3 a 2 b + 3 a 2 + B Cub right are the coefficients that are showing up in front of those numbers right so if I keep doing this right and I'll write a few more rows down then I could keep going if you wanted this is the little hack that's going to tell me exactly what to do so you want to figure out what a plus b to some number is I just um go to my my triangle and that tells me what the coefficients are and I just write

the expansion down sort of decreasing the power of a 1x one right so for instance if I wanted to do something like a + b 5th right very quickly I just go over to my my triangle over here right and it tells me well I'm going to get a to the 5th right + 5 a 4 * b + 10 * a cubed b^ 2 + 10 Again * a 2 B Cubed + 5 a b 4th plus b 5th showing up and here I can then see from this I ask you does the freshman's

dream hold on the five clock in five clock arithmetic any multiple of five doesn't matter right or if five is the same as zero right so well five 10 is a multiple of five five again so I see on the five clock this works but uh we can also see examples where it's going to fail immediately so for instance let's go one more row down a plus b to the 6 on the sixth clock right I can see that well six is fine the other six is fine but uh here 15 and 20 are not

multiples of six anymore right so even in six o00 arithmetic the freshman's dream a plus b 6 equals a 6 plus b the 6 does not hold coefficients haven't come to our rescue and eliminated the letters that's right so I can tell you what does hold it's not very satisfying maybe so that's the freshman's dream on the 6:00 not just you get to forget two terms but that's that's it right so not very satisfying so we can read off Pascal's triangle there quite easily in what mods it's going to work you can read all right

so and maybe you can already see it from what I've got is you might guess right so um well I see it works for 2 three five what do those numbers have in common in particular also see it doesn't work for four right and six right so this is on the Six Clock over here right 1 + 1 to the six right on the Six Clock right 2 to the 6 is 64 which is the same thing as four right but of course one to the six plus one to the six is two and so

those two are not the same on the Six Clock okay but in general you're telling me primes are the key here primes are the key so the claim is that if you look at Pascal's triangle right so and maybe it's worth writing down uh sort of also the general case I I I can do you want me to so right so right so the the general case here so in general the binomial expansion the numbers that show up on Pascal's triangle are those uh the numbers have the form n choose K so the binomial expansion

here says that a plus b to the N is going to give me the sums of these powers of A and B were the sum of the exponents add up to n and the coefficients you get here n choose K is the binomial coefficient n factorial over K factorial n minus K factorial it's not clear if I write it this way that this really is an integer I wrote a fraction on the page right and it just so happens that everything cancels um and you can write this down nicely to see this right so that

you actually end up with an integer right so and these are the numbers on Pascal's triangle uh in particular you also have the relation that allows you to the whole triangle by adding things if the power is prime that clock will give us the Freshman stream stream will come true right or or translated over here the claim is that for any of the Prime rows I claim that all the numbers on the middle of pescal triangle all of them are divisible by the prime p and we can see that from the formula for the binomial

expression or whatever these n choose K right okay um so uh in particular right so if I take uh P choose k let me just for fun give this a give this a name so I'm going to call this number here capital N right and here I want K to not be be zero or P well from this expression what do I know I have that n is p factorial over K factorial um P minus K factorial or If I multiply to the other side K factorial P minus K factorial time n is equal to

P factorial so I need one more thing to convince you that it's a multiple of P yeah right I have to remember that the integers have the primes as their building blocks so um uh so the integers uh I can make any one of them by multiplying uniquely U powers of products of primes right so I have unique factorization so but if I look on the right side of this equation there is a at least one p this is the product of all the integers p on down to one right so there is a p

on the left side which means that I have to end up with a p somewhere if I break this into primes on the left another way of saying it is p divides the right side so it divides the left and the thing about primes is when a prime divides a product of numbers it divides one of those numbers so P has to divide either K factorial P minus K factorial or n but K is some number that is less than P so it can't divide that P minus K is some number that's also less than

P it can't divide that one so the only thing left is that it has to divide n it has to divide this binomial coefficient ah and that's why we know all the co and that's why we know all for all the Primes this works you can also see then that this doesn't work as soon as you have something that's not prime you have to be more clever if you want to analyze which of the coefficients are divisible by n or divisible by P or divisible by whatever you like and there are them theorems like that

so there's a famous theorem called Lucas's theorem that talks about divisibility for binomial coefficients uh how what powers of primes they divide them but uh that's maybe a subject for a different video all right what's next the thing that's really behind the freshman's dream is that powers behave very differently in clock arithmetic than when you use regular arithmetic and it seems a shame not to tell you um uh another another way one of the very famous ways and very useful ways um that powers behave differently in clock arithmetic particularly for Prime clocks all right so

this is what's known as fromal little theorem it's the distinguish of course from fma's Last Theorem right so um which has a much longer and storied history than Forma little theorem but maybe uh at least in the real world it's not clear which one is more useful to the common man so um in fact fasula theorem is at the heart of a lot of encryption schemes has been used for RSA encryption and other things for a long time so maybe here's the statement for you if I take a prime right then um the claim is

and maybe I'll use slightly more fancy notation here right so a to the p is is congruent to or is equal to a mod P or another way of saying it right so mod P here just means in in P clock arithmetic uh we can pick out many examples give me your favorite Prime oh I mean seven seven is acceptable yeah right give me a number less than seven okay four right all right so the claim here is that oh we have to know what four to the 7th is oh four to the power of

7 4 the^ of 7 right so um we could we could get one but I I'm going to cheat a little bit here and again the point here is that raising things to powers in clock arithmetic is just easy here I'm going to look at let's say p is 7 right is four all right so I want to raise four to the 7th power and I certainly don't remember what that is but I can break it up right into something that I do remember the first thing I'll do is well pull out two of those

fours right and now four squar is 16 right but 16 on the seven clock is two right and I can repeat the same trick so I pull out another two another one right so 2 Cub * 4 and now we're in the money again right 2 cubed is8 which is the same thing as one on the seven CL there I have from o little theorem right 4 to the 7th on the 7 o00 CL is the same thing as four so I just verified um right that on the seven clock and it took me several

steps here but this also gives you an idea that playing around with powers on these clocks is much easier I didn't have to write anything down here that was a double digit number on the page right um so it's very easy for me to raise things to really high Powers this is pretty cool it's pretty good fun all this stuff you showed me with clock arithmetic or modular whatever you want to call it but of course numbers don't do this like numbers just keep going they don't wrap back around on themselves and come back to

zero so it's like you've kind of made up this this other kind of mathematics to make all these things work that shouldn't work what's the point of this modular arithmetic is it like a useful thing like is it a legit thing sure it's very useful it's a little hard to say the number of places cuz it's just vast clocks right so certain clocks are one of them here I've played around with a lot of the clocks where they were very small clocks right but it's very hard for me to explain to you if you we

could be living in a world right ostensibly where we were always working with one really huge clock right what's the biggest number you know oh like like Graham's number tree three yeah yeah these huge numbers right if I had a clock that was bigger than that and you never saw a number bigger than that in your life right right in reality you might as well be working on a huge clock most of the time and in fact there's a a lot of times computer systems to prevent themselves from going Beyond and timing out on things

they don't like to deal computers don't like to deal with infinite processes they like to terminate so this gives you away as a stop Gap right um maybe that's not the most satisfying explanation but it shows up a lot of places uh like that a lot of the time you also want to put yourself in a situation where you can do these tricks because the arithmetic is just so much more comp computable right so a lot of other computer systems will be based around these things so you've probably heard of the binary numbers or things

like that um right so yes no arithmetic even a arithmetic um this has a lot of real world applications as well so I have uh basically the slickest proof I know to convince someone that this really works um and again it it involves looking a little bit more at the properties that these kinds of clocks satisfy and what clock rithmetic really looks like the number we're testing it was 341 thumbs up yeah great so it's passed the test let's try another one let's try another test let's do it with three then we do this 3

^ 341 minus 3 is this divisible and this is where it fails the test