Number Theory Lecture 8 (English) | Congruences, Powers, Fermat's Little Theorem

Hello students, welcome to lecture 8 on number theory where we are going to talk about congruences, powers and the most important topic the firmma's little theorem. So let's get started. So first we'll talk about properties related to powers involved in congruences. Right? So let's take a number a and consider its various powers like power of 1 2 3 with respect to modulo of a number m. Okay. and then we'll try to see whether there is some pattern that is evolving with respect to these powers. So before we look at any general number m we will talk about m being a prime number. So we are basically interested in reading the modulus with respect to a prime number p because with the prime numbers the pattern is very easy to spot. Okay. So let us stop by and examine these tables and try to formulate some conjectures out of it. So what I've done basically I have taken some prime numbers to begin with. I have taken a prime number 3 5 and 7. Okay. I've taken a number a of course the number a which I'm going to take up is one less than the prime number which I'm going to talk about. Let's say if I talk about the prime number three I have considered a values to be 0 1 and 2. If I take the prime number five I have taken my a as 0 1 2 till 4. If I talk about the prime number seven, I'd have taken a value from zero all the way to six because beyond that if you go the same pattern is going to be repeated over and over again. Right? So look at this table you know very very carefully. So there's a lot of things that we can actually figure out from these tables. So there are many interesting patterns which are visible from these tables. But the one which we are mainly concerned about is the one which is seen in the column where the power is one less than the prime number itself. For example, I'm looking at this column where we have a raised to the power of two. Okay? And it has entries 0 1 1. Similarly, if you look at this column where a is raised to the power of four, right? Again if you see the entries are 0 1 1 1 in case of the prime number seven I'm looking at a to the^ 6 column and here also we see a similar kind of a pattern being repeated right so when we look at these columns we realize that every entry in these columns aside from a equal to0 of course when a is equal to 0 a a square a cq etc all of them will be zero and if you divide 0 by any prime number you will get a remainder of zero so we'll not talk about that but apart from that entry you see that every other entry is actually a one right so does this pattern hold for larger primes for example if I take a prime number 11 right and do the process with a value starting from 1 2 3 all the way till 10 and raise it to a power which is one less than 11 that is 10 itself will I always get a remainder of 1 like if I have 1 to the power 10 or 2 to the^ 10 or 3 to the^ 10 da da da da all the way till 10 ^ 10. Will we get a remainder of 1 when we divide it by 11? The pattern seems to suggest so yes we are going to get the remainder of 1 when we divide it by 11. That means we can say that a to the power 10 will be congruent to 1 modulo 11 for a values lying between 1 to 10. Okay. So this leads us to make a following conjecture that a ^ p minus one will be congrent to one module p for every integer a which is not a multiple of p. So actually when we realized this pattern we took numbers a which is between 1 to p minus one right but in reality it has been figured out that if your a is not a multiple of p and of course p is a prime number then a to the power p minus one will always leave a remainder of 1 when divided by p. In other words a to the power p minus1 is going to be congruent to one modulo p. This result was actually stated by the lawyer come mathematician Perry deform but he did not give any proof for this like he always did. So this theorem was actually named after him as the firma's little theorem. Now people ask this question why little theorem because this was one of the several theorems given by FMA which was actually easier to prove as compared to his you know so-called difficult ones. For example, the former's last theorem was so so difficult that it could not be proven for 350 years. So this one was very simple and the first known proof for this was given by the famous German mathematician Gorfried Wilhham Lenes. But this was actually unpublished. The first published one was actually given by Leonard Oiler. But still Lebanese is the one whose work seems to suggest that he was the one who had actually proven Ferma's little theorem before anybody else could. So now officially talking about the former's little theorem which states that if p is a prime number and a be any number which is not congruent to zero mod p then a to the power p min -1 will be congruent to 1 modo p. That means in short if p is a prime number and a is not divisible by p then a to the power p minus one will always leave a remainder of 1 when divided by the prime number p. So this is the firma's little theorem. So mind you this actually is an if then implication right the converse of this need not be true. We'll soon see that in our subsequent part of this course where we'll talk about the carmical numbers. Okay. So first let us try to see some applications of little theorem. For example if somebody wants to compute what is the remainder when 2 to the^ 35 is divided by 7. That means somebody wants to find out what is 2 ^ 35 modulo 7. Then using FMA's little theorem first of all we can say that two and seven are such numbers where seven is prime and two is not a multiple of seven. So 2 ^ 7 - 1 which is nothing but 2 ^ 6 will be congrent to 1 modulo 7. Right? This comes directly from our firm's little theorem. Now what we realize is that 35 is made up of 6 into 5 + 5. Right? So what I'm going to do is this 2 ^ 6 congruent to 1 modulo 7. I will raise both sides to a power of five. Right? So we have already seen from the properties of congruences that this is going to work. So what I'm going to do is I'm going to raise both sides to the power of five. Right? As we've already seen in the property of congruences that this is quite possible. So we'll end up getting 2 to the^ 30 is congrent to 1 modulo 7. Right? Now I'll multiply again both sides with 2 ^ 5. So that eventually I end up getting 2 ^ 35. So that will be congruent to 1 ^ 5 into 2 ^ 5 which is nothing but 32. So 32 modulo 7 is as good as 4 modulo 7 because 32 when divided by 7 will leave a remainder of four. So we can find the answer to what is 2 ^ 35 remainder when divided by 7 so easily by the use of firmar's little theorem. Let's see one more application of it. Suppose that we want to solve what value of x when raised to the power of 103 will be congrent to 4 modlo 11 given that x is not congruent to 0 modo 11 that means x is not divisible by 11 right so the condition of form's theorem is actually met over here that 11 of course our p which is a prime number here and x is not divisible by 11 right so I can straight away jump to the conclusion that for former's little theorem x to the^ 10 will be congruent to one model 11. Right? Let's raise both sides to the power of 10. Then we'll realize x ^ 100 is congruent to 1 module 11. Let's multiply with x ^ 3 on both sides which will eventually make x ^ 103 congruent to x ^ 3 mod 11. Now all we need to check is what is the value that x can take so that x cube is congruent to 4 modo 11. So for this what we can use it. We can brute force it by putting the values of x as 1 2 3 all the way till we go till 10. And I've listed these values down. And here if I see this table carefully, I realize that the x cube is congruent to 4 modulo 11 appears when x is 5. So we can clearly come to a conclusion that x will be congruent to 5 modulo 11 and that will be the solution to this congruence equation. So thanks to FMA's little theorem that we are able to solve such kind of congruence equation so easily. So now let's prepare ourselves for proving the FMA's little theorem officially. But before proving that we would like to see a solution of a question and we'll try to also observe what is happening when we are trying to solve it. So here is a question that we'll first like to prove. Can we prove that 3 to the^ 6 is congruent to one mod 7? Okay, let's see how we can prove this. So in order to prove that 3 to the^ 6 is congrent to 1 modulo 7, we start with these numbers 1 2 3 4 5 6. Now what we do with these numbers is that we multiply each one of them by three and find the modulo 7. So I've stated this result in this table. So for example, if I take x as one and I multiply one with three, I'll get a three. So what is three modulo 7? Three itself because when you divide three by 7, the remainder is going to be three. If you take two and multiply it with three we get a six. What is six modulo 7? Six itself. If you take the number three multiply it with three we get a 9. What is 9 modulo 7? We can say 9 will be congruent to 2 modulo 7. Similarly for 4 5 6. What you basically realize here is that so when you look at this table carefully we have certain observation. The observation is that if you notice the same number 1 2 3 4 5 6 have even appeared in this row. See 1 2 3 4 5 6 right? Of course the order of the appearance is not exactly the same as the first row. So what we realize that the same set of numbers are appearing in both the rows. So of course when you multiply all the numbers of the first row and the second row I should get the same end product. Isn't it? So this is a very very key observation which I would like to highlight that multiplication by three and taking a model 7 just rearrange the same numbers 1 2 3 4 5 6 of course in not the same order right now how is this helpful in proving ours for my little theorem. So now you will ask how is this useful in proving my firma's little theorem. So let's see in our subsequent slides. So what I do now I take the same numbers 1 2 3 4 5 6 and I multiply them each with three and take them in their raw format. Now what I'm going to do next is since 3x was giving me the same answer modulo 7 as x was giving me for modulo 7. So what I'll do is I'll multiply all the modulus of 3x and all the modulus of x together which is going to give you the thing that you see right now on your screen. Now all of us know the idea of factorial right? What is factorial? Factorial is a continued product from one all the way till that particular number whose factorial we are finding. So let's say if n is a whole number and I say n factorial. What does it mean? It means the product from 1 2 3 all the way till n. Right? So I'm going to use this factorial because it's going to ease up my notation a little bit. So if you see on the left hand side there is three occurring with all these six terms. Right? There's a three occurring here, here, here, here, here, here, here. Right? So, what I'm going to do is I'm going to take all those three common out and that leaves us with 1 into 2 into 3 into 4 into 5 into 6 which is nothing but 6 factorial. And on the right side of the congrence, we already have 6 factorial module 7. So now what I'll do next is I'll cancel out the six factorial on both the sides. Now how I can do that? Because see if you remember the congrence property which we had dealt in our previous lecture. If a c is congrent to bc modulo m and c and m are relatively primes then we can cancel out c from both the sides. So 6 factorial is actually relatively prime to seven. Why? Because 6 factorial doesn't have seven in it. Isn't it? 1 2 3 4 5 6. It doesn't have a seven in it. Right? So 6 factorial and seven are relatively prime to each other. And as for the congren property I can cancel them out from both the sides. If I do so I would realize that I would be left with 3 ^ 6 congrent to 1 modulo 7. Right? So for this particular example you can see that the approach has proven the firm's little theorem for us. Mind you this approach is important because I'm going to generalize this approach in order to prove the firm's little theorem. So we are now going to prove it in general but before that I'm going to prove the same thing in a generalized fashion once again right I know you have understood it for this particular example but let's have a look at a generalized version of the same approach so let's start with this lema first the lema says let p be a prime number and let a be a number such that a is not congruent to zero mod p then the numbers a 2 a 3 a all the way till P min - 1 A mod P are all distinct means they're all in congruent and same as the number 1 2 3 all the way till P minus one mod P although they may differ in their order that means they may not be exactly the same corresponding to each other right so let's try to prove this so let's start with the fact that we realize that a 2 a 3 a all the way till p minus a contains p minus one numbers of course and none of them is divisible by p Why? Because see a is not divisible by p for sure as a former little theorem says and neither the numbers 1 2 3 till p min -1 are divisible by p because they're all smaller than p right so a into 1 or a into 2 or a into 3 d till a into p minus one none of them is going to be divisible by p right isn't this obvious so what we'll do I have divided this proof into two parts first I will prove the distinctness of these numbers that means I'll prove that if If I take any one of these numbers a 2 a 3 a all the way till p min -1 a and I divide it by p then the remainders are going to be all different right they're all going to be distinct so let's use our way of contradiction to prove it so let's say we have two numbers ja and ka from this list which happen to be congruent that means ja is congruent to ka modulo p right what does this mean it means p divides the difference of j and k That means P divides J minus K * A. So P will either divide A or P will either divide J minus K. But P doesn't divide A. As I've already told you in the beginning of this formal theorem concept. So P must divide J minus K. Right? Now each J and K happen to be between 1 to P minus one. Isn't it? So their difference will always be lesser than P minus one. Because if you take up any two numbers which is lesser than P minus one, their difference will also be less than P minus one. In other words, J minus K difference is less than P minus one. So if P has to divide difference of J and K, then the only number lesser than P minus one which P can divide is zero. Right? That means your J minus K value should have been a zero. In other words, J should be equal to K. Right? So in other words, J and K cannot be distinct. They must be the same quantity. And hence J and K must be the same number. So basically J and K cannot be different. They must be the same quantity if they are congruent. That means each J and K has to be distinct from each other. So this proves the distinctness of FMA's little theorem concept. So this proves the distinctness part mentioned in this lema. Now let us realize that there are only p minus one distinct nonzero modulo p numbers between 1 to p minus one isn't it? So if you talk about what could be the numbers which p cannot divide lesser than p you can say it can only be 1 2 3 4 all the way till p minus 1 isn't it? So what I can say is that 1 2 3 till p min -1 and the list that we had a 2 a 3 a all the way till p min -1 a this list should have the same numbers isn't it because if they're distinct the only distinct ones could be 1 2 3 all the way till p minus one isn't it so if there is another set of numbers which are also distinct and they are a 2 a 3 a till p minus 1 a that means these two set of numbers must be the same set of numbers isn't it of Of course the order may differ that will not matter to us. So these two sets must contain the same distinct inongruent numbers. Right? So this proves the lema for us. Now using this lema we'll try to finish the proof for the FMA's little theorem. Okay. So let's go to the general proof of FMA's little theorem that we all waiting for. Now we'll start with the same idea that since we know a 2 a 3 a all the way till p min - 1 a modo p and the numbers 1 2 3 all the way till p min -1 modo p contain the same set of numbers however the order may be different in both of them if you multiply these corresponding ones we would realize that a 2 a 3 all the way multiplied to p min -1 a will be congruent to 1 2 3 all the way multiplied to p min -1 mod p now Again, we're going to take up all the p minus1 copies of a from our left hand side of this congruence equation. That's going to become a to the power p minus one. And it leaves behind 1 2 3 all the way till p min -1 which is p min -1 factorial. And of course the right side of the congren is also p - 1 factorial. And as I already told you that p min -1 factorial is relatively prime to p right because in p min -1 factorial p has not made its appearance yet. So that whole quantity is not divisible by p. So we can cancel out p minus one factorial from both the sides in line with our congruence properties. And that leaves us with this idea that a ^ p minus one will be congruent to 1 modulo p. This proves former's little theorem. Okay. So now let's move on to our questions. Let's start with our first question using little theorem. So what are the tasks? Task is find a number a which is between 0 to 73. of course less than 73 such that a is congruent to 9 ^ 794 modulo 73 okay so first what we'll do we'll note down something related to 794 right can I write it as some multiple of 1 less than 73 which means 1 less than 73 is 72 right plus some remainder yes I can write it like this 11 into 72 + 2 right so now we can apply former's little theorem because see first of all 73 3 is fine. That is one condition of former theorem is met. And second of all, 73 does not divide 9. Right? 73 and 9 are relatively prime to each other. So applying for little theorem on this, I can say 9 to the^ 72 will be congruent to one model of 73. Right? Now in order to get to 794 power, I'll first raise both sides to the power of 11. Right? Remember since right side is a one raising 1 to the^ of 11 keeps it one only. So can I say now that if I multiply both sides with 9 to the power 2 again I will end up reaching 9 to the power 794 ultimately which gives me 9 ^ 794 congruent to 81 modulo 73 which is further congruent to 8 modulo 73. So since there is a restriction on a to keep it between 0 to 73, 8 is one of the options that I can choose. So let's say the range was something else. So I could have taken some another value which is congruent to that value here. Right? So in this case I can say 8 is our answer for a. Okay. So let's move on to the second part of question number one. Using FMA's little theorem, we need to solve x ^ 86 congrent to 6 modulo 29. Okay. Now can I say here for sure that x will not be congruent to 0 modulo 29 because if x was congruent to 0 modo 29 then x ^ 86 would have been congruent to 0 to the^ 86 modo 29 which is actually zero and hence that will not satisfy this equation. So one thing I can say for sure x is not congruent to zero modo 29 that means x is not divisible by 29 and if x is not divisible by 29 and 29 is a prime number I can start using firma's little theorem over here. So I can say by firm's little theorem x to ^ 28 will be congrent to one mod 29 right. So now what I realize is that 86 is 3 into 28 + 2 right just like the same example as I did before I can directly say that x ^ 86 will be congrent to x² module 29. Now how do you solve this quadratic modulo? Of course we'll use brute force where we'll try to write all x values from 1 all the way till 28. So we'll see squaring which of them is congruent to three mod 29. So that means square of which number from 1 to 28 is going to leave a remainder of three when divided by 29. So what I've done is I've made a list out of it. So if you see this position x= to 8 you realize that you are getting a 6 when you are dividing x² by 29 and at this position when x is 21 you get a remainder of 6 when you divide by 29. So can I say x is congruent to 8 module 29 will be our required solution as well as x= to 21 modulo 29 will also be our required solution to this congruence equation. So thanks to former theorem that we're able to solve this. Of course here we have used a brute force to get our values which is the only way possible right now. Okay. So let's move on to our part c of question number one. Let's try to solve x to the^ 39 congruent to three modulo 13. Okay. Same usual approach I can write 39 as 3 into 12 + 3 right 1 less than 13 is 12. So can I say finally that x ^ 39 is going to be congruent to x ^ 3 module 13 right now what again I'm going to do I'm going to use my brute force. Of course 0 cannot be the answer. So I'll take all the numbers starting from 1 all the way till 12. I'll cube it and check which one is leaving a remainder of three when divided by 13. So I've actually done that calculation over here. So I would like you to see that calculation. So the calculation shows that if I take all numbers from 1 to 12, x cube module 13 either is a 1 or a zero or a five or a 8 or a 12. Right? None of them is giving me a three. Right? So it could be zero if I take a zero which I have not mentioned here. It's either one or it is five or it's 8 or is 12. That's all. There is no three anywhere. So if there's no three anywhere that means such a congruence equation will have no solution. Right? So again thanks to FM's little theorem that we are able to solve such a congress equation. Let's now move on to question number two. The quantity p minus one factorial mod p where p is a prime appeared in our proof of firm's little theorem. So if you remember the proof for the firm's little theorem we had this p minus one factorial coming up on both sides of the congren equation right which we canled it out. But here the question says if you compute P minus one factorial module P for some small values of P find a pattern to make a conjecture. Okay. So if I take some small prime numbers P and try to find out P min -1 factorial mod P that means I try to find out what remainder will be left when P minus 1 factorial is by P. Then what I'm going to see so let's have few instances. So if I take the prime number two, 2 2 - 1 factorial is a 1 which is congrent to minus 1 modulo 2. Similarly 3 - 1 factorial which is going to be a 2 that is congrent again to minus1 modulo 3. 5 - 1 factorial is 24 which is again congrent to minus1 modulo 5 and 7 - 1 factorial is 720 which is again congrent to minus1 modulo 7. So what conjecture we make here is that p min -1 factorial is always congruent to minus1 mod of p where p is a prime number. This is just a conjecture which we'll try to prove little later on. By the way this conjecture is actually a theorem which is called the Wilson's theorem. Okay. So let's talk about more about this question. So let's see the part B of the question which asks us to prove that this conjecture is correct. Okay. So let us use our linear congrence theorem. Right. So see linear congress theorem if you realize it says that ax congrent to c modulo p will have a solution if the gcd of a and p divides c right so so what I'm going to do here is that I'm going to take up a which is between 1 to p minus one okay so let's choose our a between 1 to p minus one so basically all my a values are relatively prime to p because they're smaller than p of course so the gcd of a and p is going to be one. So ax is congrent to one mod p will definitely have a solution because a and p's gcd which is one itself will divide one. Correct? So now so one important information I would like to add here is that x is called the multiplicative inverse of a mod p right it's somewhat like you know what we do in our simple multiplication like 5 into 1x 5 is one right so 1x 5 is the multiplicative inverse of five and vice versa right even five is the multiplicative inverse of 1x 5 so a similar situation is arising over here where we are saying ax is congrent to one mod p that means a and x are such numbers which are acting like multiplicative inverse but with respect to the modulo right they're not multiplicative inverse per se but with respect to the modulo p they are multiplicative inverse of each other so now x is also going to lie somewhere between 1 to p minus one now many people ask me this question why why x is going to lie between 1 to p minus one see let's say if x is somewhere bigger than p then remember we can always reduce a factor of p from x and bring it to that range of 1 to p minus one right because see if x not is a solution then x not + pk will also be a solution correct so if if I can subtract pk from that I can always bring it down to a lower value isn't it so my multiplicative inverse will be a number which will also be lying between 1 to p minus one now two cases arises here let's take the first case let's find out such a's which are their own multiplicative inverses is mod p. Okay. So let's say if my x is a itself, right? So let's say the solution of ax congrent to one modulo p. x itself is a. Okay. Then we can say a square is congrent to 1 modulo p. Which means p divides a square minus one. That means a is congrent to 1 modulo p. Now the only value of a which is between 1 to p minus one giving you a remainder of 1 when divided by p is what 1 itself. So here can I say a is going to be one here and if p divides a + 1 that means a is congrent to minus1 mod p. Now which is the only number between 1 to p minus one which is going to leave a remainder of minus1 when divided by p of course you'll say p minus one. So we say okay these are the two numbers which are their own multiplicative inverses. What about the other numbers? Okay. So let's see our case number two. Okay. So case number two we'll talk about the remaining numbers. So from 1 to p minus one we have already taken care of 1 and p minus 1. What about the middle numbers? Okay. So let's talk about all the numbers a which is between 2 to p minus2. Now it has been figured out that these numbers which are in between they can be paired off in such a way that the product of each pair is going to leave a remainder of one when divided by P. And this pairing is unique. That means one number can pair up with one number only. It can't be paired up with any other number. I'll give a simple example to understand this slightly weird idea. Let's say I take P as 11. Okay. So now I'm going to talk about all numbers from 2 to 9. Remember because uh 1 and 10 they are self inverses right? So 2 to 9 I'm going to talk about now two can actually be paired up with six because 2 into 6 is 12 and 12 leaves a remainder of 1 when divided by 11. Similarly 3 can be paired up with four because 3 into 4 is 12 again and that is going to leave a remainder of 1 when divided by 11. Similarly 5 can be paired up with 9 because 5 into 9 is 45. Again when you divide 45 by 11 remainder is going to be 1. 7 can be paired up with 8 because 7 into 8 is 56. 56 when divided by 11 again will give you a remainder of 1. So what we realize is that each of these pairs multiplies to give you one modulo 11. Right? So how is this helpful to us? Let us now connect all the dots. Now if you multiply all the way from 1 2 3 till p minus one that means if you try to generate p minus1 factorial you would realize that 1 and p minus1 are their self inverses. So they will remain the others which is 2 till p minus2 they will pair up to give you one module 11. So they all of them vanish right leaving behind only 1 into p min -1 and 1 into p min - 1 is p min - one which is actually min -1 modulo p and this is the proof of the will's theorem that we were talking about. All right let's move on to question number three students. Question number two asks you to determine the value of p min -1 factorial mod p when p is a prime number. So remember this was our Wilson's theorem where we always got the answer as -1 modulo p. Now compute the value of m minus one factorial mod m for some small values of m that are not prime. That means so that's what precisely question number b asks do you find some pattern as you found it for the prime. So let's see. So what we had seen earlier that we got a minus1 modulo p as our answer to p min -1 factorial mod p. So here we're now going to take a few composite numbers. I've listed down in the table. So let's start with the four which is the smallest composite number. So 4 - 1 factorial is congrent to 2 modo 4. Let's go to the next one which is 6. 6 - 1 factorial which is 120 is congrent to 0 modo 26. Similarly for 8 9 10 and not only that if you take 12 14 15 16 18 as you can see it from the table all of them are giving me zero modulo that composite number right so here is a conclusion that I can draw looking at this rather sweet and simple short table that if m is composite then m minus one factorial will be congruent either to zero or 2 modulo m most of the time it zero. In one case, I got a two which was for mal 4. So, we guess that if m is composite and m is greater than equal to 6. So, I'm more specific here. When m is greater than equal to 6, we'll get m -1 factorial will be congruent to 0 modulo m when m is greater than equal to 6. Okay. Now if you know the value of n minus one factorial mod n how can you use this value to definitely distinguish whether m is prime or composite. Of course I'm going to use the previous idea. So if n minus one factorial mod n is giving me 0 or 2 that means definitely n is composite right and it is giving me minus1 then it is definitely prime Wilson's theorem right. So thanks to the Wilson theorem and thanks to the observation that we had pre in the previous question that if the remainder of n minus one factorial when divided by n is a minus1 then n happens to be a prime and if it happens to be a zero or a two then n happens to be a composite. Now we will not move further till we have actually given some kind of a generic proof why for composite number n minus one factorial is congruent to a zero or a two. Okay. So let's try to prove it in a certain way. Let's say I take a composite number m and we also know that m minus1 factorial if m is a composite number will definitely be greater than m. For example, if you take 4 - 1 factorial which is six. 6 is definitely greater than four. If you take 6 -1 factorial which is 120 that is definitely greater than 6. Now what we can say here is that m minus one factorial is a product from 1 all the way till m minus one which is actually greater than m. Can I say that in building this number every prime which was used for m will appear in the prime factorization of this number. Right? Because see m minus one factorial is more than m. So m was made up of product of subprimes. So the same primes must definitely appear in m minus one factorial. So what I can say each one of your p i is going to divide m minus one factorial. So ultimately your m must divide m minus1 factorial. Right? So this basically proves that the remainder when mus1 factorial is divided by m will most of the time be zero except in a rare case where m was actually a four. So this proves that when m minus one factorial is divided by m the result will be zero most of the time except for one case when your m value is of four. Okay. So let's move on to the next question which is question number four. So if p is a prime number and if a is not divisible by p then firmer's little theorem tells us that a to the power p minus one is congrent to one mod p. We had already seen this theorem before. So now let's see what question is based out of that. 7 to the power this number is congruent to 1 1660565 modulo 173 4251 which is exactly one more than this number. Okay. Can you conclude that this number 173 4251 is a composite number. Okay. Now please understand now former theorem actually implies that if p is a prime and p does not divide a then a to the power p minus one is congrent to 1 modulo p. So basically this is an if then statement. Now we all know that if then statement is equivalent to its contraositive. That means so if I say p implies q it is as good as saying not p implies not q isn't it? So if a ^ p minus one is not congruent to one module p then either p is not a prime number which means p is a composite number or p divides n or p divides a right so if I write the same thing it means that if a to the power n minus one is not congruent to one module n so I'm just taking a negation of your end result. So I'm basically taking a negation of the conclusion. Right? Then it will implies that either P is composite or N divides A. Correct? Now if you look at the number 1 7 3 4 2 5 1 and 7 they are relatively prime to each other. That means the fact that n divides a is ruled out. That means the other one must be true that n is composite. Isn't it? So since n cannot divide a the this part of the property doesn't hold true. So I must ensure that n must be composite for that entire thing to hold true. That means the number 173 4251 is actually a composite number. So without actually doing this factorization right by the way this factorization could be slightly difficult you know if you have to perform that you can actually use the former little theorem directly to conclude the fact that this bigger number without doing any factorization mind you guys is a composite number. Let's move on to the next part of the question. It says that 129 to the^ 64026 is congruent to 15179 modulo 647. By the way again this number is one bigger than this number is true. Can you conclude that 6407 is a composite number? Again if you take the previous approach what does former little theorem say that if a to the power p minus one is not congruent to 1 modulo n that means n is either a composite number or n should divide a or both of them can be possible. So now see the gcd of 129 and 64027 is 43. The fact that the GCD is not one, what does it mean? It means that the number 6427 is composite. Right? That clearly proves that 6427 is composite which is actually clearly divisible by 43. So let's move on to our next part of the question. The congruence 2 ^ 52 632 is congruent to 1 modulo 52 633. Again this number is one more than this. If this is true, can you conclude that 52 63 is prime number? So students, as I've already told you in former's little theorem, the hypothesis is P is a prime number and P doesn't divide A leads to the conclusion that A to the power P minus one is congrent to one mod P. Right? And I said the converse need not be true. Right? So if there is some number p that exists which is going to give you a to the power p minus one congrent to one modulo of p and a and p do not have any common factor that means gcd of a and p is one still I cannot claim that p is a prime number I'm going to talk about this in our subsequent part of number theory which is going to be in the carmical numbers so as of now we can say the answer to this question is no because as I told you furma's little theorem works only one Okay, in this case which is there in the problem 52 633 is actually not a prime because it is factorizable as 7 into 73 into 103. So as I told you, we'll speak more about this in our subsequent part which is going to be discussed in the carmichle numbers. So guys, this brings me to the end of our lecture 8 on number theory.