The negative statement of Wilson's Theorem is also interesting: n is composite if and only if (n-1)! is *not* congruent to -1 mod n. In attempting to prove the forward direction, you discover the (n-1)! is not always congruent to 0 mod n as one may have suspected. Instead, you can prove the only exception is n=4. Note (4-1)!=6 which is congruent to 2 mod 4.
I'm calling bullshit you don't know if it's necessarily negstive 1 mod or..but you know it is NOT equal to zero mod p..since if it did then it would divide p..but you don't necessarily know if the remainder is negstive 1 or not..
At first the logic around 9:00 is difficult for me to understand . But I go back and watch his video on linear congruences. It is all clear now . Let ax=1 (mod p) .Because gcd (a,p)=1 . There is only 1 unique solution x for a ( both a and x is from set 1,2,3,...p-1) . by excluded 1,p-1 due to it make x=a . the set getting smaller to both a and x is from set 2,3,...p-2 . Set 2,3,...p-2 will only have even number of the member . If I pick one number from set 2,3,...p-2 for a , there will be only 1 inverse modular solution for x . The set 2,3,...p-2 will get smaller by 1 pair that we used . Repeat the process will get all paired number that have a and x that inverse to each other . ax=1 mod(P) . Finally only have 1 and p-1 left .
Thus doesn't make any sense..what if ibdknt want to watch this over ranbdover..Jesus mathb js sonfuxkong exhausting and stupid and annoying and contrived way too often..how can anyone be expected to tolerate it??
Spoiler alert. For anyone who wants to check their working on the warm-ups. The pairs of inverses for 16! mod 17 are: 16! = 1 . 16 . (2.9) . (3.6) . (4.13) . (5.7) . (8.15) . (10.12) . (11.14) ≡ 16 mod 17 ≡ -1 mod 17 Observe that 3|14! and 5|14! hence 15|14! so 14! ≡ 0 mod 15. Optionally note that 4*4 = 16 ≡ 1 mod 15, so 4 is its own inverse mod 15 so it cannot be paired with anything in the expansion of 14! to produce a value ≡ 1 mod 15. Wilson's Theorem has some interesting corollaries (or rather, alternate formulations): Since -1 ≡ (p-1) mod p, we can write: (p-1)! ≡ (p-1) mod p. if we divide each side of the above by (p-1), which is not zero, we get: (p-2)! ≡ 1 mod p Here's one possible proof of the expression Michael Penn gave us: Let 2(p-3)! ≡ a mod p Multiply each side by (p-2): 2(p-2)! ≡ (ap - 2a) mod p But (p-2)! ≡ 1 mod p and ap ≡ 0 mod p, so 2 ≡ - 2a mod p Therefore a = -1 showing that 2(p-3)! ≡ -1 mod p
For anyone who are confused at 8:55, why the set a ={2,3,4....p-2}, a^2 is Incongruent to 1 (mod p), i think it could be explained better. He also said that +/-1 are excluded from the set, which was very confusing. There are a few facts to note: (1) a*b (mod n) is equivalent to (a mod n)*(b mod n) (mod n), meaning the same congruence relationship can be found in a pair of integers in the residue set of n, i.e {0,1,2....n-1}. (2) a * x congruent to 1 (mod n), only has solution if a and n are coprime (i.e gcd(a,n)=1). That means to find the inverse congruence, 'a' must be coprime to n. (3) if n is prime, then from (2), all integers in the residue set of n have inverse congruence, because if n is prime, all its residue are coprime to it. (4) for x^2 congruent to 1 (mod n), if n is prime, then x congruent to +/-1(mod n). This is covered in early part of this video. This fact also has the meaning that if x is an inverse of itself, with n being prime, then x+1 and x-1 are divisible by n. Look back at (3), what integers in the residue set when plus 1, or minus 1 are divisible by n ? Only 1 and n-1. This means 1 and n-1 are inverse of themselves. All in all, when he said all the integers in set a, which is residue set of n(which is prime) with 1 and n-1 removed, do not satisfy the a^2 congruent to 1 (mod n), in other words not its own inverse, that's why. So why said +/-1 were excluded from the set? The 2 integers removed were 1 and n-1, which were the integers with property x^2 congruent to 1 (mod n). Sps x=1, w.r.t fact in (4), it satisfied n|x-1. Note that x=1 and x=n+1 are both congruent to 1 (mod n). If x=n-1, then it satisfies n|x+1. For me as someone trying to understand all these as new concept, it doesnt sound anything like "+/-1 are exclude from the set".
9:00 This bit was unclear to me, but it makes sense now. ax=1 mod p has a unique set of solutions all congruent mod p since gcd(a,p) = 1. By division algorithm, we can write any integer as kp+r. So we set x = kp+r with r between 0 and p-1. We get a(kp+r)=1modp. Clearly also, kp+r=r modp ---> a(kp+r)=armodp. By transitive property of congruence we have ar=1modp. This is not true if r=0,1, p-1 or a.
@@maxwellsequation4887I haven't watched the movie..But there is a movie where he talks with a Ball when he gets stranded on an Island whom he called Wilson...
@@Vladhid This property of primes - that p|ab => p|a or p|b, proved using Bezout's identity, which in turn comes from the Euclidean algorithm - is fundamental and is sufficient to prove the Fundamental Theorem of Arithmetic, which says that every positive integer > 1 can be written as a product of primes in an essentially unique way. I find it helpful to appreciate this property of primes in the ring of integers by considering contexts where it does not hold. For example, consider the ring Z[√(-5)], where 6 can be factorised into primes in two really distinct ways: 2×3 and (1+√(-5))(1-√(-5)). As you can see, the above mentioned property fails here, since 2|6=(1+√(-5))(1-√(-5)), but 2 divides neither (1+√(-5)) nor (1-√(-5)). For more details, see the Wikipedia article on Unique Factorisation Domains en.m.wikipedia.org/wiki/Unique_factorization_domain .
23:55 so both together, this means that there are infininite number of twin primes and a twin prime is two primes such that there is only one composite number between them my question is why do I feel that I need a proof for the fact that the only "doubly twin prime" so to refer to these two twins: 3,5 and 5,7 and that five is the only number ever to belong to two "different" twin primes? somehow the fact that 6 exists makes me doubt whether a proof for "3,5, and 7 are the only possible primes such that p, p+2, and p+4 are all prime" is really necessary
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
The proofs are not very intuitive as most of them were done by reverse engineering the theorem. When the theorem was found, i suppose there must have been some discovery processes that led to the discovery of it and that should be how it is taught.
Proving mathematical theorems really is an art form.
That's because it is my friend
Yes
it is
number theory is closer to art than science.
The negative statement of Wilson's Theorem is also interesting: n is composite if and only if (n-1)! is *not* congruent to -1 mod n. In attempting to prove the forward direction, you discover the (n-1)! is not always congruent to 0 mod n as one may have suspected. Instead, you can prove the only exception is n=4. Note (4-1)!=6 which is congruent to 2 mod 4.
I'm calling bullshit you don't know if it's necessarily negstive 1 mod or..but you know it is NOT equal to zero mod p..since if it did then it would divide p..but you don't necessarily know if the remainder is negstive 1 or not..
At first the logic around 9:00 is difficult for me to understand . But I go back and watch his video on linear congruences. It is all clear now . Let ax=1 (mod p) .Because gcd (a,p)=1 . There is only 1 unique solution x for a ( both a and x is from set 1,2,3,...p-1) . by excluded 1,p-1 due to it make x=a . the set getting smaller to both a and x is from set 2,3,...p-2 . Set 2,3,...p-2 will only have even number of the member . If I pick one number from set 2,3,...p-2 for a , there will be only 1 inverse modular solution for x . The set 2,3,...p-2 will get smaller by 1 pair that we used . Repeat the process will get all paired number that have a and x that inverse to each other . ax=1 mod(P) . Finally only have 1 and p-1 left .
Thus doesn't make any sense..what if ibdknt want to watch this over ranbdover..Jesus mathb js sonfuxkong exhausting and stupid and annoying and contrived way too often..how can anyone be expected to tolerate it??
07:24 “these cases don’t really work” ( referring to 2,3 ). Matt Parker calls them “sub-primes”
Spoiler alert.
For anyone who wants to check their working on the warm-ups.
The pairs of inverses for 16! mod 17 are: 16! = 1 . 16 . (2.9) . (3.6) . (4.13) . (5.7) . (8.15) . (10.12) . (11.14) ≡ 16 mod 17 ≡ -1 mod 17
Observe that 3|14! and 5|14! hence 15|14! so 14! ≡ 0 mod 15.
Optionally note that 4*4 = 16 ≡ 1 mod 15, so 4 is its own inverse mod 15 so it cannot be paired with anything in the expansion of 14! to produce a value ≡ 1 mod 15.
Wilson's Theorem has some interesting corollaries (or rather, alternate formulations):
Since -1 ≡ (p-1) mod p, we can write:
(p-1)! ≡ (p-1) mod p.
if we divide each side of the above by (p-1), which is not zero, we get:
(p-2)! ≡ 1 mod p
Here's one possible proof of the expression Michael Penn gave us:
Let 2(p-3)! ≡ a mod p
Multiply each side by (p-2):
2(p-2)! ≡ (ap - 2a) mod p
But (p-2)! ≡ 1 mod p and ap ≡ 0 mod p, so
2 ≡ - 2a mod p
Therefore a = -1 showing that 2(p-3)! ≡ -1 mod p
Great, thanks
For anyone who are confused at 8:55, why the set a ={2,3,4....p-2}, a^2 is Incongruent to 1 (mod p), i think it could be explained better. He also said that +/-1 are excluded from the set, which was very confusing.
There are a few facts to note:
(1) a*b (mod n) is equivalent to (a mod n)*(b mod n) (mod n), meaning the same congruence relationship can be found in a pair of integers in the residue set of n, i.e {0,1,2....n-1}.
(2) a * x congruent to 1 (mod n), only has solution if a and n are coprime (i.e gcd(a,n)=1).
That means to find the inverse congruence, 'a' must be coprime to n.
(3) if n is prime, then from (2), all integers in the residue set of n have inverse congruence, because if n is prime, all its residue are coprime to it.
(4) for x^2 congruent to 1 (mod n), if n is prime, then x congruent to +/-1(mod n). This is covered in early part of this video. This fact also has the meaning that if x is an inverse of itself, with n being prime, then x+1 and x-1 are divisible by n.
Look back at (3), what integers in the residue set when plus 1, or minus 1 are divisible by n ? Only 1 and n-1. This means 1 and n-1 are inverse of themselves.
All in all, when he said all the integers in set a, which is residue set of n(which is prime) with 1 and n-1 removed, do not satisfy the a^2 congruent to 1 (mod n), in other words not its own inverse, that's why.
So why said +/-1 were excluded from the set?
The 2 integers removed were 1 and n-1, which were the integers with property x^2 congruent to 1 (mod n). Sps x=1, w.r.t fact in (4), it satisfied n|x-1. Note that x=1 and x=n+1 are both congruent to 1 (mod n).
If x=n-1, then it satisfies n|x+1.
For me as someone trying to understand all these as new concept, it doesnt sound anything like "+/-1 are exclude from the set".
7:06 Quick homework
28:10 Homework
29:00 Good Place To Stop
How did you comment 3 weeks ago?
@@ahmadmazbouh 🤫
LOL 3 week ago jajajaja
9:00 This bit was unclear to me, but it makes sense now.
ax=1 mod p has a unique set of solutions all congruent mod p since gcd(a,p) = 1. By division algorithm, we can write any integer as kp+r. So we set x = kp+r with r between 0 and p-1.
We get a(kp+r)=1modp. Clearly also, kp+r=r modp ---> a(kp+r)=armodp. By transitive property of congruence we have ar=1modp. This is not true if r=0,1, p-1 or a.
I have a few new formulae for p greater than 3.
Fact(p-1) is congruent to 0 mod(p+1).
Fact(p-1) is congruent to 0 mod(p**2 -1).
Every day i discover how awesome is math , and how it make us see the shortcuts of the universe .......!!!
Tom Hanks knows all about Wilson's Theorem.
?
@@maxwellsequation4887I haven't watched the movie..But there is a movie where he talks with a Ball when he gets stranded on an Island whom he called Wilson...
Absolutely stunning proof man
Hello. Great video, as always.
Can someone please explain, where in the proof of the first lemma was used the fact that p is prime?
Michael used the idea that if n divides xy, then either n divides x or n divides y. This is only true if n is prime.
@@jacemandt right! thank you
The fact that p divide one of the factors.
@@Vladhid This property of primes - that p|ab => p|a or p|b, proved using Bezout's identity, which in turn comes from the Euclidean algorithm - is fundamental and is sufficient to prove the Fundamental Theorem of Arithmetic, which says that every positive integer > 1 can be written as a product of primes in an essentially unique way.
I find it helpful to appreciate this property of primes in the ring of integers by considering contexts where it does not hold.
For example, consider the ring Z[√(-5)], where 6 can be factorised into primes in two really distinct ways: 2×3 and (1+√(-5))(1-√(-5)). As you can see, the above mentioned property fails here, since 2|6=(1+√(-5))(1-√(-5)), but 2 divides neither (1+√(-5)) nor (1-√(-5)).
For more details, see the Wikipedia article on Unique Factorisation Domains en.m.wikipedia.org/wiki/Unique_factorization_domain .
23:55 so both together, this means that there are infininite number of twin primes
and a twin prime is two primes such that there is only one composite number between them
my question is why do I feel that I need a proof for the fact that the only "doubly twin prime" so to refer to these two twins: 3,5 and 5,7 and that five is the only number ever to belong to two "different" twin primes?
somehow the fact that 6 exists makes me doubt whether a proof for "3,5, and 7 are the only possible primes such that p, p+2, and p+4 are all prime" is really necessary
Can someon explain what the t-shirt hes wearing means?
It's something to do with vertex algebra... Idk anything about that lol, but he has some videos on the subject so maybe they will explain it.
@@Alex_Deam I don't know about vertex algebra but I read on Dr Penn website that he is a researcher at this area
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
This is tight!
What happened to your hand. I am worried.
Dr. Penn had surgery to correct Dupuytren’s contracture, or trigger finger.
He'll be fine soon he posted about it
@@maxwellsequation4887 thanks for the reply. I thought he faced an accident. I was very sad.
💕💕💕
The proofs are not very intuitive as most of them were done by reverse engineering the theorem. When the theorem was found, i suppose there must have been some discovery processes that led to the discovery of it and that should be how it is taught.
I think they found that this rule held so they tried to prove it.
What happened to your arm!?? Hope you getter better very soon
😮
i understand less than nothing except whatever is not math-related
👋👋🥰