If anyone finds it confusing when Michael multiplies the elements of the 2 sets, all the residues in s' are mod p. It follows from an important fact that if we have a = b(modn) and c = d(modn), we essentially have ab = cd(modn n), and this process can be generalized to how many numbers we want.
Yes, and that fact is easy to prove. If n|(a-b) and n|(c-d), then a-b = kn and c-d = ln for some integers k and l. Hence, ac = (kn+b)(ln+d) = (kln +kd+bl)n+bd and ac-bd = (kln +kd+bl)n
5:38 No need for Wilson's theorem here. We have p | (p-1)!(a^(p-1)-1). Since p is prime, it must appear in the prime factorization of (p-1)!(a^(p-1)-1). It cannot appear in prime factorization of (p-1)! so can only appear in prime factorization of a^(p-1)-1. Hence p | a^(p-1)-1. I love the videos! Subscribed.
Equation A: z.(p-1)! = (p-1)! (mod p) with p being a prime number implies equation B: z = 1 (mod p). It can be easily proven without using Wilson's theorem. (p-1)! is a product of terms k where k is betwen 1 and p-1. I can cancel the term k at both sides of equation A if gcd(k,p) =1. Of course gcd(k,p) = 1 by the definition of the prime number p. Thus I can cancel any term k at both side of equatin À and I end up with z = 1 (mod p).
Hi Professor Penn, I noticed that you've used Wilson's theorem in this proof of Fermat's Little Theorem (although it was not necessary). Ok, but my question to you is, is it possible to prove Wilson's theorem using Fermat's Little Theorem ? I saw a proof on Wiki but couldn't get it. Could you please tell me if you have already made a video on this ? If not, may I request you to make a video on how to prove Wilson's theorem using Fermat's Little Theorem ?
I think so. We can cancel something (which in essence is dividing) iff gcd(whatever we're dividing, the number we're mod in) is 1. So it would be safe to cancel (p-1)! if it was coprime with p. Since p is a prime, it would be coprime to all numbers less than it therefore, yes, it is safe to cancel. On a similar note, It's also safe to cancel the a's at the proof of the claim (at the start of the proof) since a is coprime to p (given), but he didn't do that either. Maybe it's just bad practice to cancel something when dealing with modular arithmetic (I dunno)
i agree with most of what ribhu said, apart from the reasoning of why p is coprime to (p-1)!, since p is probably less than (p-1)! - i think some better reasoning might be that p can't be a part of the prime factorisation of (p-1)! due to the fact that all primes in the expansion of (p-1)! will be less than p also, to add a little bit, i prefer to think of 'cancelling' in modulo arithmetic as multiplying by the inverse as u avoid the weird stuff, but what ribhu said is correct
As Ribhu said, we only need to check that the divisor is relatively prime to the number we're mod in. -1 is congruent to p-1 mod p, we also know that consecutive integers must be coprime to each other, so p-1 and p are coprime and we can safely cancel -1 from both sides.
The integers modulo a prime form a field (a fact which does not depend on Fermat's little theorem), so every number not congruent to 0 modulo p has a multiplicative inverse. But (p-1)! is obviously not a multiple of p (all of its prime factors being less than p). So it has a multiplicative inverse.
@@ObviousLump I think Ribhu may have been implicitly using the fact that a number is still coprime to the product of other numbers to which it is coprime. For instance, if c is coprime to a and c is coprime to b as well, then c is coprime to a*b. This is discussed on a Stack Exchange post, and I chose c, a and b to make things consistent with a reply there ( math.stackexchange.com/questions/2264623/is-the-product-of-two-coprime-numbers-coprime-with-a-third-if-the-three-numbers ). I feel like this result should be some kind of named theorem, but I'm not quite sure if that's the case and if so, what it's called...
Hi I am struggling with how you know that p does not divide k-l ? I get that k-l would not be equal to p or not be a multiple of p but I don’t understand why
If k and l aren't the same, you can't get k-l=0. Then let's assume k>l, so k-l>0. The biggest k can be is p, the smallest l is 1, so the biggest value of k-l is p-1 which is not big enough to be any multiple of p. The same logic applies to the case k
If anyone finds it confusing when Michael multiplies the elements of the 2 sets, all the residues in s' are mod p. It follows from an important fact that if we have a = b(modn) and c = d(modn), we essentially have ab = cd(modn n), and this process can be generalized to how many numbers we want.
You are right.
For lazy students (I'm joking) here's the link
ruclips.net/video/33p04rolbHA/видео.html
Yes, and that fact is easy to prove. If n|(a-b) and n|(c-d), then a-b = kn and c-d = ln for some integers k and l. Hence, ac = (kn+b)(ln+d) = (kln +kd+bl)n+bd and ac-bd = (kln +kd+bl)n
I think you mean if a = b (mod n) and c = d (mod n) then ac = bd (mod n) not ab = cd (mod n)
5:38 No need for Wilson's theorem here. We have p | (p-1)!(a^(p-1)-1). Since p is prime, it must appear in the prime factorization of (p-1)!(a^(p-1)-1). It cannot appear in prime factorization of (p-1)! so can only appear in prime factorization of a^(p-1)-1. Hence p | a^(p-1)-1. I love the videos! Subscribed.
Equation A: z.(p-1)! = (p-1)! (mod p) with p being a prime number implies equation B: z = 1 (mod p). It can be easily proven without using Wilson's theorem. (p-1)! is a product of terms k where k is betwen 1 and p-1. I can cancel the term k at both sides of equation A if gcd(k,p) =1. Of course gcd(k,p) = 1 by the definition of the prime number p. Thus I can cancel any term k at both side of equatin À and I end up with z = 1 (mod p).
Professor Penn, thank you for a power analysis and explanation of Fermat's Little Theorem.
Fermat's? More like Fear-not's! Thanks for another video that really breaks down the topics and makes them easy to understand!
Love the Zelda background
I only realize it now lol
didnt even realize this lmao
Great content 👍
Thanks for this!
You have saved me in my discrete math CS class
Hi Professor Penn, I noticed that you've used Wilson's theorem in this proof of Fermat's Little Theorem (although it was not necessary). Ok, but my question to you is, is it possible to prove Wilson's theorem using Fermat's Little Theorem ? I saw a proof on Wiki but couldn't get it. Could you please tell me if you have already made a video on this ? If not, may I request you to make a video on how to prove Wilson's theorem using Fermat's Little Theorem ?
Very cool proof! I enjoyed it.
You're awesome, thx.
Can someone confirm that whether it's safe to cancel both the (p-1)! around the last steps? I think it is..., Is it?
I think so. We can cancel something (which in essence is dividing) iff gcd(whatever we're dividing, the number we're mod in) is 1. So it would be safe to cancel (p-1)! if it was coprime with p. Since p is a prime, it would be coprime to all numbers less than it therefore, yes, it is safe to cancel.
On a similar note, It's also safe to cancel the a's at the proof of the claim (at the start of the proof) since a is coprime to p (given), but he didn't do that either. Maybe it's just bad practice to cancel something when dealing with modular arithmetic (I dunno)
i agree with most of what ribhu said, apart from the reasoning of why p is coprime to (p-1)!, since p is probably less than (p-1)! - i think some better reasoning might be that p can't be a part of the prime factorisation of (p-1)! due to the fact that all primes in the expansion of (p-1)! will be less than p
also, to add a little bit, i prefer to think of 'cancelling' in modulo arithmetic as multiplying by the inverse as u avoid the weird stuff, but what ribhu said is correct
As Ribhu said, we only need to check that the divisor is relatively prime to the number we're mod in.
-1 is congruent to p-1 mod p, we also know that consecutive integers must be coprime to each other, so p-1 and p are coprime and we can safely cancel -1 from both sides.
The integers modulo a prime form a field (a fact which does not depend on Fermat's little theorem), so every number not congruent to 0 modulo p has a multiplicative inverse. But (p-1)! is obviously not a multiple of p (all of its prime factors being less than p). So it has a multiplicative inverse.
@@ObviousLump I think Ribhu may have been implicitly using the fact that a number is still coprime to the product of other numbers to which it is coprime. For instance, if c is coprime to a and c is coprime to b as well, then c is coprime to a*b. This is discussed on a Stack Exchange post, and I chose c, a and b to make things consistent with a reply there ( math.stackexchange.com/questions/2264623/is-the-product-of-two-coprime-numbers-coprime-with-a-third-if-the-three-numbers ). I feel like this result should be some kind of named theorem, but I'm not quite sure if that's the case and if so, what it's called...
one of the rare ressource on this topic on internet. My friend and I both found the same video, it p[roves that this is the only one on the topic.
(1+...+1)^p≡1^p+...+1^p (mod p)⇔a^p≡a (mod p) ■
Very helpful
such an elegant proof
Lovely proof
But so why p has to be prime?
because it doesn't hold of any integer that isn't prime, it can be disproven by a counter example
Hi I am struggling with how you know that p does not divide k-l ? I get that k-l would not be equal to p or not be a multiple of p but I don’t understand why
If k and l aren't the same, you can't get k-l=0. Then let's assume k>l, so k-l>0. The biggest k can be is p, the smallest l is 1, so the biggest value of k-l is p-1 which is not big enough to be any multiple of p. The same logic applies to the case k
Agh, your chalk makes an awful sound in this video that makes it impossible for me to watch! Love your work tho.