Euler's Totient Theorem & Fermat's Little Theorem Explained (Complete Proof) (51 chars)

[00:00:00]so we are going to talk about euler's totient theorem and for ma's little theorem now euler's totient theorem is the statement that if a is coprimed to n in other words if the greatest common divisor of a and n is 1 then a to the power of phi of n is congruent to 1 mod n in this case phi of n is euler's totient function so it counts the number of integers from 1 to n that are co prime to n as an example of this theorem if we choose n equals 100 then you can prove that 77 to the power of 40 is congruent to 1 mod 100.

[00:00:40]so this statement right here is an example of applying euler's theorem now in the proof of euler's totient theorem i'm going to use a few properties that have to do with coprime numbers and how they interact with modular arithmetic so if you aren't familiar with any of the identities that i use you can check the link in the description where i go through the derivations the start of the proof of euler's totient theorem is pretty simple we're going to construct a set which we'll call s and it's going to include all of the numbers between 1 and n that are co prime to n so let's say we're looking at x1 x2 and so on up to x sub phi here i'm using the letter phi because we know by definition that there are phi of n of these numbers so these are all of the numbers from 1 to n that are co prime to n what we're going to do is take all of these numbers and multiply them by a so let's see what happens if we do that we're going to get a new set which we call t and that's going to include a x1 ax2 and so on up to a x v so these are the same numbers as we had before but we're multiplying all of them by the number a we want to look at a few properties of how these two sets are related first we're going to look at some properties of this set t remember that all of the x sub i's all the x's in this set here are co prime to n by definition and we also know that a is co prime to n but one of the properties of coprime numbers is that if a is co prime to n and x1 is co-prime to n then their product will also be co-prime to n what that means is that ax1 ax2 and so on up to ax v all of these numbers are co prime to n now we're going to construct another set which we'll call t prime and the way that we get t prime is by taking all of the elements of t and reducing them mod n again i talk about reducing numbers mod n in the video on coprime numbers so here we're looking at ax1 mod n ax2 mod n and so on up to ax v mod n now there's another important property of coprime numbers which says that if a number is co prime to n then when we reduce it mod n this result will still be co prime to n what that means is that because all of these numbers are co prime to n all of these numbers that we get by reducing mod n these are all still co prime to n now we're going to look at one more property that is key to the proof remember that there's a rule for cancelling numbers in modular arithmetic if ax is congruent to a y mod n and we know that a is co prime to n then we can cancel a on both sides and get that x is congruent to y mod n now this has a very important consequence which is that multiplying by the number a is an injection mod n so if x is not congruent to y then ax will not be congruent to a y that's by the contra positive so what that means is we know all of these numbers in here are not congruent mod n because they're all between 1 and n now we get from s to t by multiplying the constant a but if none of these numbers were congruent to mod n then when we multiply by a all of these numbers are still going to be incongruent mod n because this is an injection so these numbers are still all different mod n and when we reduce the mod n they're still going to be different so these are all distinct numbers now we need to talk a little bit about reducing numbers mod n when we reduce a number mod n the result that we get will always be between 0 and n not including n the reason for that is that if the result we get is bigger than n for example say we're looking at n plus 2.

[00:05:17]in that case when we're reducing mod n we could subtract another multiple of n and we would get a smaller integer that's still congruent to mod n so what that means is we can keep reducing the integer until it's in this range between 0 and n so because all of these integers are the results from reducing a number mod n we know that all of these a x sub i must be between 0 and n in fact we can go one step further than this we can get more specific because what would happen if a x i mod n were equal to zero well if that's true then it means a x i is congruent to zero mod n but notice that zero is equal to a times zero so we would have a times x sub i is congruent to a times zero we can use the cancellation rule here of course a is co-prime to n so this would mean x i is congruent to 0 mod n but we know that's not possible because all of these numbers are between 1 and n and none of these x's are equal to n because of course n is not coprimed to itself for any number greater than 1.

[00:06:44]what that's telling us is it's not possible to have axi congruent to 0 because that would contradict our original set so 0 is not one of the possible values of t prime they have to be between 1 and n so let's think about the properties of t prime that we have right here we have a set of numbers between 1 and n they are all incongruent mod n and they are also all co prime 2 n this is the fun part these conditions should seem a little bit familiar and that's because they're very similar to the conditions that we had on our original set s all of these numbers x1 x2 up to xp those original numbers those were numbers between 1 and n they were all incongruent since they're different numbers and they were all co-prime to n that's how we defined this set these sets seem like they're pretty closely related in fact remember that when we looked at s we said these are all of the numbers every single number between 1 and n that's incongruent and co-prime to n and this last set here t prime has the same number of elements since each element in t prime comes from one of the elements in s so if this original set contains all the numbers that satisfy these three conditions and t prime has the same number of elements that all satisfy those conditions s has to have the same elements as t prime they both contain all of the elements that satisfy these conditions so they have to have the same elements now remember that we got the elements of t prime by reducing the elements of t mod n what does it mean to reduce a number mod n well when we take a number and reduce it mod n the result we get is the least non-negative integer that's congruent to our original number mod n in other words we can say that every number in t prime is congruent to one of the elements of t mod n in this example it's pretty clear to see that ax1 is congruent to ax1 mod n but from here remember that s has the same elements as t prime so if every element in t prime is congruent to one element in t and s has the same elements as t prime then every element in s is congruent to one element in t now it might not necessarily be the case that for example x1 is congruent to ax1 mod n however we know that there's going to be some number in this set we'll call it x sub i1 there's some number x in this original set that's congruent to ax1 mod n and this is true of every element all the way down to x sub i phi being congruent to ax v every single element in t is congruent to exactly one element in s see if you can guess how we get from these congruences to the final statement up here a to the phi of n is congruent to one mod n the way we're going to do that is using the multiplication rule for modular arithmetic remember that if we have two numbers that are congruent to each other mod n we can multiply the numbers on the left and the numbers on the right and those two products will be congruent to mod n so what we're going to do is multiply all of the numbers on the left with all the numbers on the right and see what products we get on the left side we're going to get the product here i'm using this notation here to talk about multiplying all the numbers the product of x sub i sub j that's going to be congruent to over here the product of all a x sub i so these are all congruent mod n now remember that when we were looking at these x sub i 1 x sub i 2 and so on all of these x's together they were every single element in this original set s but all these numbers over here a x sub i these x sub i's we got from the set t and these are also all the x's in s so these two products are the same products on both sides we're looking at the product of x sub i product of x sub i but then we have this extra factor of a and we're looking at the product we're multiplying a over every single x sub i so how many are there well the number of x sub i is the number of integers between 1 and n that are co prime to n and by definition that is phi of n so when we multiply phi of n copies of a the result we're going to get is a to the power of phi of n so these are congruent to mod n but all of these x i's are co prime to n by definition and we know there's a cancellation rule for modular arithmetic if all these numbers are co-prime to n their product is also co-prime to n which means we can cancel them on both sides these two cancel out very nicely and we get the result one is congruent to a to the phi of n mod n and that is euler's totient theorem now when it comes to remembering why euler's totient theorem is true i think it's easier instead of looking at the final nice statement here to look at the statement that includes the products because what euler's totient theorem is really saying is that if we take all the numbers co prime to n and we multiply by a the result that we get all of these numbers are going to be congruent to all the original numbers mod n in some order meaning that when we multiply them all together those products are going to be the same and of course the products will cancel out on both sides and all we have left is fee of n copies of that number a that we multiplied so now we're going to take a look at for maw's little theorem now for moz little theorem is actually a special case of this totient theorem that we just derived and it is the special case for when n is a prime number so now we're working mod p in that case remember that the totient of a prime number p is equal to p minus 1 because every number less than p is co prime to p and what that means is that up here in the exponent what we're going to get is p minus 1. so a to the p minus 1 is congruent to 1 mod p that's going to be true anytime a is co prime to p and because p is prime that just means we need a to not be a multiple of p so as long as a isn't a multiple of p this identity will be true now the reason that we talk about framaz little theorem separately is that a lot of the time when we're doing modular arithmetic we're doing it mod a prime number a lot of important ideas such as primitive roots come from the idea of doing arithmetic mod p so it's important enough that it's easier to just remember this specific identity a to the p minus one is congruent to one mod p so that is euler's totient theorem and for moz little theorem they both relate to taking exponents of numbers mod n or mod p and they have some very important applications further on in elementary number theory [Music] [Applause] [Applause] you