I think the most impressive part of the proof of Wilson's theorem was creating pairs among positive integers 2,3,....,p-2 so that each pair contains two integers being mutually reciprocal modulo p.
Wjat does mutually recuorocalmean..and indont think that's reslly clever it'd just random and co tried and convenient and thus shouldn't be allowed..jts another example of math being stupid and annoying and too contrived..
Another way to write this is: if p is prime, (p - 1) ! = (p - 1) mod p. This expression is a little more symmetric and clearer to understand, but not as compact and more variable.
Sometimes I feel like a castaway when I watch videos on things I don't understand, but with Wilson I feel like I have a bit of company... In all seriousness, thanks for another wonderful video!
you can only pair up an even amount of elements. Therefore the proof is valid for odd primes. For the even prime(p=2) you can check manually that it does still hold, since 1!=1 which is congruent to -1 mod 2.
With that equivalence, many ways to express the nth prime number as a function of n with standard arithmetic ( +, -, /, * , floor function) are available. Too bad Wilson’s theorem was not popular when I was in high school, and the commonly-held view was there is no simple formula for the nth prime. Such simple formulas do not help break codes in usefully short time. Your credit card is no worse off.
great video, I also know a following proof: Consider polynomial x^(p-1)-1 in field Z_p. Roots of this polynomial would be nonzeros remainders modulo p, (by Fermat Little Theorem) so by Vieta's formula the product 1*2*...*(p-1)=-1 Q.E.D.
Is it really? If we assume p composite st d | p, then d | (p-1)!, then d does not divide (p-1)! + 1, but that means p does not divide (p-1)! + 1, contradiction. That'd be about it
If n = 1 then (1-1)! = 0! = 1 === 0 (mod 1). If n = 2^2 = 4 then 3! = 6 = 2 (mod 4) which is not -1 (mod 4). if n = p^2 with p > 2 then p and 2p are distinct factors in (n-1)! and then (n-1)! = 0 (mod n) again. If n is composite, n = s*t with {s, t} subset of {2, ..., n-1} and s different from t: if n is divisible by two or more primes, p and q, then let s indivisible by p and t indivisible by anything else. Otherwise n = p^k with k > 2, so let s = p and t = p^{k-1} > s. But then s and t are two distinct factors in (n-1)! implying (n-1)! = 0 (mod n). So (n-1)! modulo n is: a: 2 if n = 4 b: -1 is n is a prime c: 0 otherwise.
It would be a little prettier didactically if we could see how the factors pair off, the ones that do not pair off with themselves. In mod 11, we have the elements {0,1,2,3,4,5,6,7,8,9,10} First of all let's get rid of the trivial cases. 0 x 0 = 0; 1 x 1 = 1; 10 x 10 = 1 (i.e., -1 x -1 = 1) and now let's see how the others pair off, if we cast out 11's. 2 x 6 - 11 = 1; 3 x 4 - 11 = 1; 5 x 8 - 4 x 11 = 1; 7 x 8 - 5 x 11 = 1. Sweet! How about mod 13? Looking at {2,3,4,5,6,7,8,9,10,11} 2 x 7 - 13 = 1 3 x 9 - 2 x 13 = 1 4 x 10 - 3 x 13 = 1 5 x 8 = - 3 x 13 = 1 6 x 11 - 5 x 13 = 1 So, by casting out 13's, we get the elements 2 - 11 to pair off uniquely as multiplicative inverses. And so on.
If you have this tendency to pair off clearly in mind, Wilson's theorem is trivial. In the factorial, you get a 1; then you get (p-3)/2 pairs, each pair multiplying to 1; and, finally, you get p-1, which makes the product -1.
@@tapaskapat7201 Brother I am from Bangladesh your Neihbour country,,, I want to more learn about Number Theory,,,,Can You give me your Facebook ID!!!!
If gcd(a,n)=1 then a has a unique inverse mod n. Keep an eye out for numbers that are relatively prime to the modulus; they enjoy many special properties like these.
Hello! If you are referring to around 5:31, recalling the definition of the inverse helps! By definition, a*a^-1 = 1 mod p or if a=a^-1, a*a^-1 = a*a = a^2 = 1 mod p.(period used to avoid confusion with factorial!) I hope this helps!
I would think of the group of totatives U(p) = {1,2,...,p-1} under multiplication modulo p. Suppose p is a prime >2. p-1 must be an even number. Consider the equivalence relation ~ where a~b iff ab=1 (mod p) This relation partitions U(p) into (p+1)/2 disjoint classes. The classes [1] and [p-1] are singleton, rest have 2 elements each. Define f([x]) as product of all elements in [x]. (p-1)! = f([1])•f([2])...•f([p-1]) = p-1
At the beginning of the video, we prove that 1 and p-1 are the only residues mod p that are their own inverse. Next, we know that 2,3,4,...,p-2 are all invertible mod p since they are relatively prime to p. Finally, 1,2,...,p-2,p-2 forms a complete set of (nonzero) residues mod p so the inverses of 2,...,p-2 must also be in the list 2,...,p-2. That way, we can pair all of them into inverse pairs.
@@MichaelPennMath Oooohhh, so you weren't multiplying the entire expression by anything else, but rather reordering its own factors... I had not understood that at all at first. OK.
@@MichaelPennMath I think that part could have been explained just a little bit better in the video. You sort of explained when you said "3 might be 2 inverse so we would just write 2 and 3" but the way it is written on the board, it implies that you multiplied by all the inverses, thus squaring the modulo of the inner numbers. Mathematically it works out anyways because the inner numbers multiply to 1 (mod p) anyway and 1^2=1.
First of all, thanks for your video. But i dont understand why the inverse of x have to be between 2 and p-2 . ( x € Z and x € [ 2, p-2] ) . Could you proof this firstly please ? Thanks in advance.
Sorry, but how in the world is the proof at 2:00 valid? I don't see the part where you assure there can be only two solutions, which is the entire thing you're setting out to prove.
the only 2 ways p|(a+1)(a-1) is if p|(a+1) or p|(a-1). these are the only two possible cases since p is prime. that means either a ≡ 1(modulo p) or a ≡ -1(modulo p), and these are the only 2 cases as I mentioned earlier. if you are wondering why these are the only 2 cases, it's because p is a prime, it can not be written as a product of two numbers which are not p. that means, for p to divide (a-1)(a+1), p must be a factor of either (a-1) or (a+1), since no other factors of (a-1)(a+1) can multiply to produce p. that's as clear as I can make it, all of this was mentioned in the video, I'm just reiterating. thanks
Proof of Wilson theorem. Let us consider numbers 2x, 3x, ...., (p-2)x, where x is natural number from 2 to (p-2) and p>=3 is prime. First I claim that all these numbers give different remainders when dividing by p. Indeed, if at least two numbers give equal remainders then their difference should be divisible by p., i.e. i*x - j*x = (i-j)*x should be divisible by p., Where i,j are from 2 to p-2. But 1
I don't understand something: at first part of proof he wants to find a number which is its own inverse mod p. Therefore he wants to solve x^2=1(mod p). He gets x=-1 or 1(mod p). But he haven't used the fact that p is a prime. So for instance replace p with 8. Is clear that 1 and 7 are their own inverses. But 3^2=9=1(mod 8) is a cunterexample. Please, could anyone explain this for me? I am not an expert in number theory, I've just watched some videos before, that is all. (Sorry for my bad english)
At 2:40 he is using a lemma that assumes p is prime, therefore this only works for primes. For example: take a prime, say 7, 7|(35)*(3), the lemma says 7|35 or 7|3 and that is true. but if you pick a nonprime, say 8, 8|(10)*(12), the lemma can not be used. though 8|120, 8∤10 or 8∤12. hence you should only use this lemma for prime's
In every field if a^2 = b^2 then 0 = a^2 - b^2 = (a+b)(a-b) implying 0 in {a+b, a-b} implying b in {a, -a}. Let a = 1, then b in {1, -1}. But then if F is a finite field with F* = F\{0}, then the product of F*\{-1} contains 1 as a factor; for every other factor its inverse is also a factor (the inverse of x is not in {-1, 0, 1, x} when x is not in {-1, 1}). So the whole product is 1. [Be careful to not double count the pairs of inverses: then your product will end up containing 1^2 instead of 1 😛] But then the product of F* is -1. In particular for Z mod pZ we learn that (p-2)! = 1 (mod p) and (p-1)! = 1 (mod p). [I think we can show that Z mod pZ is a finite field without relying on this result: Z mod pZ is a commutative ring thanks to characteristics of divisibility and remainder. No number smaller than p shares a prime factor with the prime p, so gcd(n, p) = 1 when n in {0, ..., p-1}. But then 1 = mn + kp so m is the inverse of n. This relies on prime factorization, for which I also don't think we need this result.]
How come you could assume this equality at the beginning of the proof? (p - 1)! = [ 1 x (2 x 3 x ... (p - 2)) x (p - 1) ] mod p I don't understand how you could put the "mod p" on the RHS of the equation. For example, when p = 7 you have (7 - 1)! = [ 1 x (2 x 3 x 4 x 5) x 6 ] mod 7 = 6 which is false.
This statement is true modulo 7. For instance 2x4=8=1 mod 7 and 3x5=15=1 mod 7, so 2x3x4x5=1x1=1mod 7. That makes (7-1)!=1x1x6=6 mod 7. Maybe I don't understand your question though.
I believe the (mod p) can be thought of as being on both sides of the equation but is only written on one side as convention For example 5 (mod 3) = 2 (mod 3) is equivalent to saying 5 = 2 (mod 3). So (mod p) is acting on the definition of a factorial with the left (mod p) removed for clarity/convention
Remember that 6(mod 7) can be expressed as -1(mod 7), so the statement is true. The reason why the RHS of the equation is put in that way is because he is sepparating the two numbers that are their own inverse mod p (1 and (p-1)) and at the end he just multiplied considering those numbers by separate.
@@MichaelPennMathCan you please clarify where the first lemma Co from kr thjs whole video I don't think is clear at all..at least not to me..and WHY WHY would anyonebthink kf the inverse. .it's contrived and random..surely there is a more organically logical and natural way to do this since I don't see anyone ever doing this so nor Wilson nor anyone else must have proved it this way so why do it this way?
I think the most impressive part of the proof of Wilson's theorem was creating pairs among positive integers 2,3,....,p-2 so that each pair contains two integers being mutually reciprocal modulo p.
That really comes as a surprise! Also, if you want to be fun at parties, you can use it to prove that primes bigger than 3 are odd
Wjat does mutually recuorocalmean..and indont think that's reslly clever it'd just random and co tried and convenient and thus shouldn't be allowed..jts another example of math being stupid and annoying and too contrived..
Another way to write this is: if p is prime, (p - 1) ! = (p - 1) mod p. This expression is a little more symmetric and clearer to understand, but not as compact and more variable.
I agree, thinking in your head 12! == 12 (mod 13) feels so much simpler than 12! == -1 (mod 13)
When I first started this channel it was over my head, but I've nearly completed Richard Hammack's Book of Proof and it all makes sense now
Sometimes I feel like a castaway when I watch videos on things I don't understand, but with Wilson I feel like I have a bit of company... In all seriousness, thanks for another wonderful video!
Professor Penn, thank you for a beautiful proof and analysis of Wilson's Theorem in classic Number Theory.
you can only pair up an even amount of elements. Therefore the proof is valid for odd primes. For the even prime(p=2) you can check manually that it does still hold, since 1!=1 which is congruent to -1 mod 2.
in fact to be more precise Wilson's theorem offers us a double implication because if (p-1)!+1=0 [p] then p is prime
True, the proof of this fact is simple at first glance, but requires a bit of casework upon further inspection.
Please help me I want to know how to solve questions on Wilson's therom do we use any fourmula
@Tate Graysen wdym?
@Rhett Killian how do I solve questions on Wilson's therom? What formula do we use?
With that equivalence, many ways to express the nth prime number as a function of n with standard arithmetic ( +, -, /, * , floor function) are available. Too bad Wilson’s theorem was not popular when I was in high school, and the commonly-held view was there is no simple formula for the nth prime. Such simple formulas do not help break codes in usefully short time. Your credit card is no worse off.
great video, I also know a following proof:
Consider polynomial x^(p-1)-1 in field Z_p. Roots of this polynomial would be nonzeros remainders modulo p, (by Fermat Little Theorem) so by Vieta's formula the product 1*2*...*(p-1)=-1 Q.E.D.
Thank you sir, your explanation is very nice and excellent.
I need to have a floating blackboard too. Are they available outside the desert?
So a corollary of this theorem is that (p-2)! is congruent to 1 mod p .
Nice it is very helpful for my pg semester exam
At 4.33 shouldn't the sign be that of congruence?
Nice! I could understand about it...good video
The converse of Wilson's Theorem is also interesting. It looks obvious at first glance, but surprisingly requires some casework.
Is it really? If we assume p composite st d | p, then d | (p-1)!, then d does not divide (p-1)! + 1, but that means p does not divide (p-1)! + 1, contradiction. That'd be about it
@@SV-yo6nq Sorry, I was thinking of a direct proof. That is a very nice contradiction proof.
If n = 1 then (1-1)! = 0! = 1 === 0 (mod 1).
If n = 2^2 = 4 then 3! = 6 = 2 (mod 4) which is not -1 (mod 4).
if n = p^2 with p > 2 then p and 2p are distinct factors in (n-1)! and then (n-1)! = 0 (mod n) again.
If n is composite, n = s*t with {s, t} subset of {2, ..., n-1} and s different from t: if n is divisible by two or more primes, p and q, then let s indivisible by p and t indivisible by anything else. Otherwise n = p^k with k > 2, so let s = p and t = p^{k-1} > s. But then s and t are two distinct factors in (n-1)! implying (n-1)! = 0 (mod n).
So (n-1)! modulo n is:
a: 2 if n = 4
b: -1 is n is a prime
c: 0 otherwise.
@@jonaskoelker Yes this is essentially the argument I was thinking of, though your last case might have been phrased a little strange.
@@JM-us3fr If you can think of a simpler way of phrasing it I would love to hear it.
How do we prove the converse, that x not prime => (x-1)! != -1 (mod x) ?
It would be a little prettier didactically if we could see how the factors pair off, the ones that do not pair off with themselves. In mod 11, we have the elements {0,1,2,3,4,5,6,7,8,9,10} First of all let's get rid of the trivial cases. 0 x 0 = 0; 1 x 1 = 1; 10 x 10 = 1 (i.e., -1 x -1 = 1) and now let's see how the others pair off, if we cast out 11's.
2 x 6 - 11 = 1;
3 x 4 - 11 = 1;
5 x 8 - 4 x 11 = 1;
7 x 8 - 5 x 11 = 1.
Sweet!
How about mod 13? Looking at {2,3,4,5,6,7,8,9,10,11}
2 x 7 - 13 = 1
3 x 9 - 2 x 13 = 1
4 x 10 - 3 x 13 = 1
5 x 8 = - 3 x 13 = 1
6 x 11 - 5 x 13 = 1
So, by casting out 13's, we get the elements 2 - 11 to pair off uniquely as multiplicative inverses. And so on.
If you have this tendency to pair off clearly in mind, Wilson's theorem is trivial. In the factorial, you get a 1; then you get (p-3)/2 pairs, each pair multiplying to 1; and, finally, you get p-1, which makes the product -1.
Nice . I have PhD on number theory. It is my favorite theorem
Brother can you help me
Why not Carmichael ???
@@makshudulislam7442 yes
@@makshudulislam7442 tell .. How can I help you ?
@@tapaskapat7201 Brother I am from Bangladesh your Neihbour country,,, I want to more learn about Number Theory,,,,Can You give me your Facebook ID!!!!
Thank you sir,,,,your explanation is very nice.,,,,Bangladesh.
I did not understand the part where you wrote. (p-1)(modp)=-1(modp)
Could someone kindly explain.
Obviously, p = 0 (mod p), so you can add p or subtract p and nothing changes
Why the numbers between 2...p-1 has a unique inverse not equal to itself?
And why p-1 and 1 have an inverse that is equal to itself?
I love these magician's tricks :-)
Hi, I don't understand how did you multiply by the inverses ?
If gcd(a,n)=1 then a has a unique inverse mod n.
Keep an eye out for numbers that are relatively prime to the modulus; they enjoy many special properties like these.
Hello! If you are referring to around 5:31, recalling the definition of the inverse helps! By definition, a*a^-1 = 1 mod p or if a=a^-1, a*a^-1 = a*a = a^2 = 1 mod p.(period used to avoid confusion with factorial!) I hope this helps!
I would think of the group of totatives U(p) = {1,2,...,p-1} under multiplication modulo p.
Suppose p is a prime >2.
p-1 must be an even number.
Consider the equivalence relation ~ where a~b iff ab=1 (mod p)
This relation partitions U(p) into (p+1)/2 disjoint classes.
The classes [1] and [p-1] are singleton, rest have 2 elements each.
Define f([x]) as product of all elements in [x].
(p-1)! = f([1])•f([2])...•f([p-1]) = p-1
What if mod p is squared
This is a nice video
The case when p=2 needs to be considered separately.
where do the inverses come from?
At the beginning of the video, we prove that 1 and p-1 are the only residues mod p that are their own inverse. Next, we know that 2,3,4,...,p-2 are all invertible mod p since they are relatively prime to p. Finally, 1,2,...,p-2,p-2 forms a complete set of (nonzero) residues mod p so the inverses of 2,...,p-2 must also be in the list 2,...,p-2. That way, we can pair all of them into inverse pairs.
@@MichaelPennMath Oooohhh, so you weren't multiplying the entire expression by anything else, but rather reordering its own factors... I had not understood that at all at first. OK.
@@MichaelPennMath I think that part could have been explained just a little bit better in the video. You sort of explained when you said "3 might be 2 inverse so we would just write 2 and 3" but the way it is written on the board, it implies that you multiplied by all the inverses, thus squaring the modulo of the inner numbers. Mathematically it works out anyways because the inner numbers multiply to 1 (mod p) anyway and 1^2=1.
Can anybody share with me proof of statement at 5:27 "recall"
I really need it
He proved it at the beginning of the video.
First of all, thanks for your video. But i dont understand why the inverse of x have to be between 2 and p-2 . ( x € Z and x € [ 2, p-2] ) . Could you proof this firstly please ? Thanks in advance.
Where is the proof of inverse thing. Pls share the video of that
Do you mean something like this: ua-cam.com/video/uPFh9_nLw1c/v-deo.html or this
ua-cam.com/video/ktJc8_3pKPw/v-deo.html
@@MichaelPennMath Thank you so much love from India.
@@MichaelPennMath Thank you for both videos. Now I finally understand. Really like your number theory video series.
excuse me, why (p-a) = a^-1 (mod p)? Thank you
It isn't
It is useful for my board exam
why a2=1 modp ??
If p is an odd prime then won't the amount of numbers in between 1 and p-1 be odd? That should imply we can't pair them.
We have an even amount of numbers.
تمام شكراا لك
Sorry, but how in the world is the proof at 2:00 valid? I don't see the part where you assure there can be only two solutions, which is the entire thing you're setting out to prove.
the only 2 ways p|(a+1)(a-1) is if p|(a+1) or p|(a-1).
these are the only two possible cases since p is prime.
that means
either a ≡ 1(modulo p)
or a ≡ -1(modulo p),
and these are the only 2 cases as I mentioned earlier.
if you are wondering why these are the only 2 cases, it's because p is a prime, it can not be written as a product of two numbers which are not p.
that means, for p to divide (a-1)(a+1), p must be a factor of either (a-1) or (a+1), since no other factors of (a-1)(a+1) can multiply to produce p.
that's as clear as I can make it, all of this was mentioned in the video, I'm just reiterating.
thanks
@@atootam thanks I don't know what I missed when I posted this
Proof of Wilson theorem. Let us consider numbers
2x, 3x, ...., (p-2)x, where x is natural number from 2 to (p-2) and p>=3 is prime. First I claim that all these numbers give different remainders when dividing by p. Indeed, if at least two numbers give equal remainders then their difference should be divisible by p., i.e. i*x - j*x = (i-j)*x should be divisible by p., Where i,j are from 2 to p-2. But 1
Thanks
You are welcome.
why is mr michael in the desert
I don't understand something: at first part of proof he wants to find a number which is its own inverse mod p. Therefore he wants to solve x^2=1(mod p). He gets x=-1 or 1(mod p).
But he haven't used the fact that p is a prime. So for instance replace p with 8. Is clear that 1 and 7 are their own inverses. But 3^2=9=1(mod 8) is a cunterexample.
Please, could anyone explain this for me? I am not an expert in number theory, I've just watched some videos before, that is all.
(Sorry for my bad english)
At 2:40 he is using a lemma that assumes p is prime, therefore this only works for primes.
For example:
take a prime, say 7, 7|(35)*(3), the lemma says 7|35 or 7|3 and that is true.
but if you pick a nonprime, say 8, 8|(10)*(12), the lemma can not be used.
though 8|120, 8∤10 or 8∤12. hence you should only use this lemma for prime's
@@66toto7 thanks
In every field if a^2 = b^2 then 0 = a^2 - b^2 = (a+b)(a-b) implying 0 in {a+b, a-b} implying b in {a, -a}. Let a = 1, then b in {1, -1}.
But then if F is a finite field with F* = F\{0}, then the product of F*\{-1} contains 1 as a factor; for every other factor its inverse is also a factor (the inverse of x is not in {-1, 0, 1, x} when x is not in {-1, 1}). So the whole product is 1.
[Be careful to not double count the pairs of inverses: then your product will end up containing 1^2 instead of 1 😛]
But then the product of F* is -1.
In particular for Z mod pZ we learn that (p-2)! = 1 (mod p) and (p-1)! = 1 (mod p).
[I think we can show that Z mod pZ is a finite field without relying on this result: Z mod pZ is a commutative ring thanks to characteristics of divisibility and remainder. No number smaller than p shares a prime factor with the prime p, so gcd(n, p) = 1 when n in {0, ..., p-1}. But then 1 = mn + kp so m is the inverse of n. This relies on prime factorization, for which I also don't think we need this result.]
How come you could assume this equality at the beginning of the proof?
(p - 1)! = [ 1 x (2 x 3 x ... (p - 2)) x (p - 1) ] mod p
I don't understand how you could put the "mod p" on the RHS of the equation.
For example, when p = 7 you have (7 - 1)! = [ 1 x (2 x 3 x 4 x 5) x 6 ] mod 7 = 6
which is false.
This statement is true modulo 7. For instance 2x4=8=1 mod 7 and 3x5=15=1 mod 7, so 2x3x4x5=1x1=1mod 7. That makes (7-1)!=1x1x6=6 mod 7. Maybe I don't understand your question though.
I believe the (mod p) can be thought of as being on both sides of the equation but is only written on one side as convention
For example 5 (mod 3) = 2 (mod 3) is equivalent to saying 5 = 2 (mod 3).
So (mod p) is acting on the definition of a factorial with the left (mod p) removed for clarity/convention
Remember that 6(mod 7) can be expressed as -1(mod 7), so the statement is true. The reason why the RHS of the equation is put in that way is because he is sepparating the two numbers that are their own inverse mod p (1 and (p-1)) and at the end he just multiplied considering those numbers by separate.
@@Pedro-fg4sw can you share with me proof of why inverse of every no. from [2, p-2] exist
@@MichaelPennMathCan you please clarify where the first lemma Co from kr thjs whole video I don't think is clear at all..at least not to me..and WHY WHY would anyonebthink kf the inverse. .it's contrived and random..surely there is a more organically logical and natural way to do this since I don't see anyone ever doing this so nor Wilson nor anyone else must have proved it this way so why do it this way?
The unable mirror anaerobically list because attraction alarmingly risk in a hideous high helmet. common, absorbed armenian