Wilson's Theorem (extra footage)
Vložit
- čas přidán 3. 08. 2014
- Follows on from this video: • What do 5, 13 and 563 ...
Featuring Dr James Grime
Brown paper: bit.ly/brownpapers
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Google Plus: bit.ly/numberGplus
Tumblr: / numberphile
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
Videos by Brady Haran
Brown papers: bit.ly/brownpapers
A run-down of Brady's channels: bit.ly/bradychannels
I think the picture of the Numberphile2 should be Tau, since Numberphile's is Pi, and Tau is Pi times 2...
You have it backwards, pi is tau times 2, and tau is one half of pi
Your idea works, but you worded the last sentence wrong
ehh... *shrug*
Just an idea.
Pi is 180 degrees, Eta is 90 degrees, Tau is 360 degrees.
Eta = Pi/2 = Tau/4
Pi = 2*Eta = Tau/2
Tau = 4*Eta = 2*Pi
...huh
That's helpful... Thanks!
I've never seen anyone look so genuinely happy about making a multiplication table.
James's cheerfulness is so infectious. I'm feeling down right now, but watching him do math is cheering me right up. :)
The mathematicians in these channel are incredibly amazing .
I could listen to James talk for hours.
I have a mod 7 equivalence chart hanging on my wall. I call it a calendar.
The way James presents math really makes it a lot of fun!
I just thought for a second "hey, this proves (n-1)! is divisible by n for all composites, but then I realised that this is actually quite a trivial statement: all composite numbers that have more than one prime factor will have their factors multiplied in the factorial, giving a number necessarily divisible by n, and all numbers with only one prime factor (i.e. powers of primes) bigger than 4 will have multiples of its factor in the factorial, and always in sufficient amount to get n (because p×k1 p>1 p,k≠2)
now i made such squares for all edgelengths from 1 to 9.
I found some cool properties on them:
-They all can be mirrored along both of their diagonals.
-If you fold them horizontal or vertical in the middle (for odd edgelengths forget about the row/column, you creased along, it´s just made out of "0"s and the half of the number you divided with to get the reminders), the "0"s exactly meet each other and the other numbers always sum up to the number you divided with.
Extra footage after 3:16 of full table on numberphile3
I love how James is always going over strategies for fast prime searching
I'm always amused by the fact that once you've learned something new, it suddenly seems to pop up everywhere. Or until you get used to it anyway. I just started a book on group theory, and BAM there it is! :)
Actually, the thing is that our brains receive so much information everyday that we tend to ignore things we simply don't understand or don't seem any utility to it or can't relate to it.
For example, you may see a lot of cars everyday, but not remember anyone in particular (unless it was impressive by some motive), but let's say you buy some kind of red car, from now on, you will notice that same car more often because your brain associates it with the one you have.
Similarly, because now you study GT you will notice those things and make connections to understand and remember things related to it.
Baader-Meinhouf effect
It's incredibly cool to see modular arithmetic taught in such a simple clear way.
Should't you be using congruence instead of the equal sign, because the
(p-1)! is definitely not equal to p-1.
***** I got, what you meant. Originally i was asking WHY he wasn't using the sign, because i wanted to know.
***** Correction, it's only confusing to the people who already know what's going on. Only somebody who understand maths well enough to understand the problem to begin with will notice there was a writing error. Ollervo100 is right though, it is congruent, not equal.
Modular arithmetic, I almost had forgotten about it hahaha. Ollervo100 yes, he should use the congruence sign, buuuut giving in the fact that Dr James is only speaking about modular arithmetic, it can be omitted.
+Ollervo100 it equals, (2-1)!=2-1 (3-1)!=3-1
no kidding my prof hammered me for way less
I want a numberphile-dvd-collection to happen! I love your work, thank you for showing us a broad look at mathematics and its wonders :)
this is probably one of the coolest and most useful proofs ive ever seen numberphile do.
These channels are amazing
I'm not sure about this rem(ab) = rem(a)rem(b) thing. Sure it works for 8*3=24, but 6*4 also equals 24, and that would give us a remainder of 6 and 4 (for division by 7), which means rem(a)rem(b) = 6*4 = 24 which doesn't equal rem(ab) which is 3.
ntm4 24 is not defined in the set mod(7), so you have to take the reminder of 24 divided by 7 again, the step by step way of writing the calculation would be: rem(z) = rem(rem(x) * rem(y)) or { x * y = z, x * y ≡ z mod(7) }
It is one of the fundamentals om modular arithmetic.
magnus östgren Ok, thanks, that makes sense. Makes me wish that they had gone into it in the video since it seems like such an obvious problem to their initial statement.
So interesting. This video and the preceding one really enlightened me to a whole new way of looking at arithmetic.
Check out modular arithmetic
When you take (n-1)! mod n, what happens if p is a prime, is that you get the product of all the numbers that are less than n, and that whole thing does definitively not divide by n because n is a prime, and that means that you need a factor p in there for it to divide, what happens instead is what is explained in the video, the numbers can be paired up in such a way that each pair has a reminder of 1, except for two exceptions, the product starts with a 1, and ends with p-1. 1 is by itself 1, while p-1 is the result. And since p is either an odd number or 2, that means that the number of terms is always even, or 1, meaning that p-1 is left over. So when you add the 1, the whole thing divides by p.
If n is composite on the other hand, it can either be a square of a prime or it can be written as the product of two different primes. And since those two primes are smaller than n, then (n-1)! contains both of those numbers, meaning that you can pair those up, which means that the reminder of the factorial is 0, giving you a reminder of 1 when you add the 1 and divide by n. If n is the square of one prime, that prime can be either 2, or an odd number. If it is the square of an odd prime, then the prime multiplied by 2 is one of the factors (unless the prime itself is 2), along with the prime itself, which means that the product of the factorial is divisible by n, so when you add the 1 at the end, the result is a reminder of 1. So n=4 is the exception because it's so small that root(n)*2 < n-1.
New video and I LOVE IT!
x 1 2 3
1 1 2 3
2 2 0 2
3 3 2 1
This contains a zero just because it is a square number. In (P-1)! the number 2 is not repeated.
You're welcome.
mate wilson's applies to primes no?
4snek WolFirE He’s explaining why 4 is a special case.
Thanks !Happy new year!
Seeing this rang a bell: in professor Frenkel's book there is an explanation of modular arithmetic as part of the explanation leading to the Shimura-Taniyama (ex) conjecture.
Interesting thing I noticed. One of the factors you split the number into has to be bigger than what you divide by. If you split 24 into 4*6 and do this process you get 4*6=24 again.
Are you a simple ice cream salesman?
doesn't work for 12*2 either since you get 5 so that can't be the rule
Mind of Seb 12*2 would then give 5*2 which is 10. the remainder if you divide 10 by 7 is 3. that one works
you know you did a second remainder step for his example and not for the one you complain about.
No I didn't. The remainder for 4 is 4, and the remainder for 6 is 6. So you get 24 again. In his example, the remainder for 12 is 5, and the remainder for 2 is 2, so you get 10, not 24.
I love how the set fails the closure axiom when the input is composite.
Very beautifully explained .... excellent explanation
I once was thinking about prims and came up with something similar: every prim P cant divide (P-1)! and every composed number C can divide (C-1)!. Here 4 is also a special case. To eleminate 4 as special case you could test if C divide ((C-1)!)^2. And the proof is that if P was a composed number its divisors must be lesser than P and would appear in (P-1)!.
And the reason why 4 as a special case (and 100% the only one) is that its the first prim squared.
There’s also no 1’s, in that multiplication table for 6; other, than 1*1 and 5*5.
Superb demonstration! 👍
That looks really cool the patters that it makes. Like how when you did 6! there was a 3 surrounded by 0's then those zero's were either surround by 2's 4's or 3's.
4 is only an exception to the test for composites because it gives a result of 3 at the end, whereas all other composites give a result of 1. It isn't a "false positive" on the prime test, because in order to pass the prime test the result is supposed to be 0.
I thought I was coming here for proof of a paper change... I mean, I got it, and I'm not disappointed or anything, but...
What was lacking in the explanation for me in 6:20 is the fact that for any prime (p) [ (p-1)^2 -1 ] / p will result in a, when a is a full number. Meaning, the highest remainder for each prime ( like 6 is to 7, the p-1 ) square will always result in remainder 1, thus it makes sense why it cannot be paired .
Thanks so much. Make sure that you wear your rubbers, an overcoat and eat plenty of soup.Your'e a good teacher and you are both loved and admired, from our community, Dan
Technically, 1 doesn’t get paired, either; but it doesn’t need to, since it’s already 1.
Dr. Grime approaches times tables with the same intensity that he would approach modern statistical theory.
3:42 the epitome of the "Parker Square".
Pretty cool seeing some discrete mathematics stuff again.
Great video! Liked and subscribed :)
a new definition for "getting caught short"
If you know basic group theory, then Wilson's Theorem follows from the fact that the product of all the elements of an abelian group is either the unique element of order 2 or the identity if no such element exists. In this case, (p-1)! is the product of the group of units modulo p, and -1 is the unique element of order 2.
I actually tried to do the proof myself when watching the first video, I couldn't figure out how to prove that it worked for primes, however I found a proof that it couldn't work for composite numbers that I think is simpler: A composite number c can be divided by at least one number smaller than it other than the trivial case of 1. For any n!, the resulting number can be divided by any number n or smaller (because factorial), therefore n! + 1 can by definition not be divided by any number n or smaller except for 1, which is still a trivial case. Thus, the composite number c can be divided by at least one number that (c-1)! + 1 cannot be divided by, meaning (c-1)! + 1 cannot be a multiple of c.
Caveat emptor: This does not prove the theorem. This is a demonstration of the idea behind the proof by showing a special case. You don't prove a theorem by just showing how one case works (unless that case is a counterexample, in which case you disprove the theorem). That would be like saying the Pythagorean theorem is true because 3^2 + 4^2 = 5^2; of course, you would need to consider ALL right triangles with integer side lengths.
To prove the theorem, you would need to show that the rows will, in the general case, always have a one.
mikecmtong It annoys me a little because this video was introduced in the other video as a "proof" of Wilson's theorem when it is decidedly not a proof.
So, I agree with the choice to give a simplified version of the proof, but I'm quite peeved that it is presented as a proof. Why not just say that it's an explanation, or a partial proof?
This theorem stumped high level mathematicians, until Euler, I think, came up with the pairing idea. When I saw that they were going to prove this I thought "I have to see this!" because as simple as the proof is, the unfamiliar territory could take hours to explain to some one who knows not a thing about number theory. I was impressed how nice a job they did, making it pretty convincing, without wandering in the labyrinth.
You don't have to go by way of group theory, if that is how they do the proof nowadays. There are direct ways of proving that all the remainders but 0 will appear, which is the way I learned it. If two of the products in a row had the same remainder, then their difference would have a remainder of 0. The difference, however, is factorable into the number that both were multiplied by, and the difference between two numbers that are both less than the prime, neither of which are divisible by the prime. It still remains to prove that there are only two cases where a number would be paired with itself to get 1. The only way I know of doing this is factoring x^2 -1 into x -1 and x +1. Getting to that point would take some algebra.
since the table for a prime number will not contain any multiples and therefore no zeros, the table for 7 generalizes to any prime and proves the theorem.
I guess this happens with 4 because if C is a composite number equal to p^2 (given a prime P), it will pass Wilson's theorem if C =< 2p. This only happens when p = 2.
The poor 4, he doesn't respect his criteria, he calls him a special case. :-)
much easier to understand that the five line proof that I had to learn for my Number Theory 2 exam which involved refering back to fermats congruence and an theory about roots of a polynomial
brilliant
Well 1's not prime by definition due to the fundamental theorem of arithmetic
7:30 the center of the table is (0) of "sandpile" 3x3
other 3x3 on this are all the sandpile 3x3.
Oh, I want to see some stuff about Latin Squares, please! ^_^
A whole semester of this in 2nd year undergrad pure maths and I only just got it, three years later.
I'm surprised there was no mention of groups.
In case someone wonders why each possible remainder except 0 shows up in every row and column in the remainder table for a prime p, I'll come up with an explanation here:
(1) The product of two numbers less than p can't be divisible by p, since they don't have any common factor with p (except 1). Thus, 0 is not in the table.
(2) If a remainder shows up twice in the same row, then the next remainder must be the same in both cases. (For example, if the 2nd and 7th remainder are equal, then the 3rd and 8th remainder must also be equal.) The reason is that rem(a+b)=rem(a)+rem(b). [So if for example rem(5*3)=rem(5*7), then rem(5*4)=rem(5*3+5)=rem(5*3)+5=rem(5*7)+5=rem(5*7+5)=rem(5*8).]
(3) Continuing the previous argument, we notice that if we get to a remainder that we've got earlier in the same row, then we won't get any new remainder later in that row.
If we included column p in the table, then this column would contain only 0s. By (1), that's the first 0 in each row. Thus, by (3), no number can be repeated before column p, since 0 is a new remainder. Thus, the first p-1 remainders are different and not 0, so they must necessarily be 1,2,3,...,p-2,p-1.
Of course, the same arguments apply to the columns.
Just to be clear, there is a much easier way to prove why those composite numbers don't work.It's not prime,so the factorial will have its divisers anyway,so it will be divisible,but when you add 1,it won't be.
The sum of each of the diagonals in the multiplication table for 7 gives a number divisible by 7. This doesn't hold for the table for 6.
Is this also true for all primes and false for all composites, or is it just a coincidence?
awesome
Look, a channel with a proper subscriber/views ratio.
You forgot a set of brackets around one of the P-1s
yay! some group theroy and a prime cayley table
8:09 Only for n > 4 because 3! is 6 and 6 mod 4 = 2
Neat, finite fields.
Brady, are there any you can think of where it works three times?
Also 1 s a special case. It's not prime, but it passes the test infinitely many times.
So basically, if you pick a divisor, you can say a number is equal (technically, equivalent) to its remainder.
Proof for the general result I think!
1#The remainder table he wrote is the multiplication table in a prime (p) field. In this case GF(7). (p=7)
2#Inverses are unique in the field. 1 and p-1 (6 in this case) are their own inverses. The rest have inverses which aren't themselves.
3# Proof: let k < n. If k is it's own inverse, k^2 = a*p + 1, where a is an integer. k^2 - 1 = a*p. => k^2 - k + k - 1 = a*p. => (k-1)(k+1) = a*p. But k is a number less than p, and p is prime. So the only way k+1 is a divisor of a*p is in the boundary case when k = p -1=> k+1 = p. Also k-1 can be a divisor only when k-1 = 0=> k =1.
4# Therefore from 1x2x3....×(p-1) other than 1 and p-1, the other numbers are multiplied out in inverse pairs. Therefore we have (p-1)! = 1x1x1..(p-1). => (p-1)! + 1 = p. Proved!
I cant believe I understood coding theory enough to prove this :D *flies away*
I have totally no idea what this is about other than a remainder.
Regarding the last sentence: Four is not a special case because it is small but because it is a power of a prime. You can''t find a pair of numbers whose product leaves reminder zero, because its only non-trivial divider is the prime itself.
What do you and James mean by 4 is a special case? That the modular multiplication table doesn't look right? As far as I can tell, the prime/composite test should still work:
(4-1)! + 1 = (3)! + 1 = 6+1 = 7, which is not a multiple of 4, so 4 is a composite number
+Failpower it's a special case because it's small. you can't just say it's not, it's the same explanation, maybe even better, than yours
+davidMlavallee for other composite numbers the remainder is 1, that's why
If you do the multiplication table of rem, then you find there's not enough pairs to make 1, so you actually get a rem3, that's the specially part. There's nothing about it passing or falling the test, it's the actually solving part that makes it special.
Edit: you get a rem2, not rem3. The special case is that you get rem2 instead of rem1
Look up Sloane's Gap. You could pick any reasonably small number and find some unique facts about it. The "smallness" does factor in.
there was so much brown paper shown at the end of the original video though xD
So remainders are just modular spaces/modular arithmetic...
If you take every number up to a composite, you have traveled past all the factors of that composite. For example, (8-1)! contains 2 x 4. Hence why (P-1)! is divisible by composite P, and why (P-1) + 1 is not.
Also, going up to something with repeated factors like 9 is taken care of by the fact that before 9, there is also 6. (9-1)! contains 3 x 6 = 2 x 9.
I think four might be a special case. The remainder of (4-1)! divided by four is not zero, but two. It still correctly fails the prime test, but for a different reason.
I finally figure out what is the inverse of each number in 2x3x...x(p-1) thanks to the sudoku representation, my mind was stuck in the addiction inverse until I see the example where 4 is the inverse of 2, not 5
how to demonstrate for all the prime p, there always are many "pairs" those product has the remainder 1(mod p)
James is such a good mathematician that he can put things in a really easy way!! I think I get better idea now than learning in terms of ring theory and 0 divisors!! Of course ring theory is better than this demonstration. But we need some simple idea of what's going on with the theory. which happens all the time in math that the content taught in textbook is too generalized to grab the idea of it!
i think we should check if 2^74207281 -1 is a wilson prime. Shouldnt be too hard to do a factorial on it
3:38 Is that like a *Parker* Square?? :)
A few years too late, but I was thinking...
If we take a composite number 'x' that is NOT a perfect square, then (x-1)! is the product of all the numbers smaller than x, which would necessary include all of it's factors. Since, these factors come in pairs, there will be at least ONE pair that will multiply together to form the original number, and hence for every composite non square number (x-1)! will be perfectly divided by x, and (x-1)! + 1 will always have a remainder of 1.
Special case for higher powers: take for example x = y cubed. (x-1)! will definitely have both y and y squared as it's factors so it still works. Say x = 27, 26! will have both 3 and 9 in its multiplication, so 27 will definitely divide it perfectly. Same goes for higher powers.
For squares it's a bit trickier, but for every x = y squared, both y AND 2y would be smaller than x-1 and would be part of (x-1)!. Take for example x = 9 and therefore y = 3, and 2y = 6, both of which are smaller than (9-1) = 8. Therefore, 8! by definition would have 3*6 as its factor, which is 18 and a multiple of 9. The only exception would be 4 where 2y = y squared.
Finally, for a prime number, well it has no factors, therefore it will never divide by (x-1)!. But, let's look at it a little deeply. Say you have a prime P. We want to calculate (P-1)! but let's calculate it this way, let's say (P-1)! = (P-1) * X, where X of course is (P-2)!. Now, (P-1)*X = PX - X. PX definitely divides P, and X definitely doesn't. But, X = (P-2)!, which we can write as (P-2)*Y, where Y of course is (P-3)!. Now, (P-2)*Y = PY-2Y, PY definitely divides P, and 2Y definitely doesn't, we can ignore the 2, since if we can show that Y is a multiple (or NOT a multiple of P, than 2Y definitely follows suit). But, Y = (P-3)! which we can write as (P-3)*Z where Z is of course (P-4)!. And we can continue down the factorial to 1, which we remove in the end (we need to calculate (P-1)! + 1) and hence get a perfect multiple of P. We can do this with primes because none of the numbers are factors. Does this make sense?
Why Wilson Number's do it twice, I haven't figured out yet...
Are you basically using modular arithmetic? I remember making these types of multiplication tables when learning about groups of symmetries, where you basically write the remainders to see how doing sequential transformations would affect an object.
That's exactly what he's using. He just didn't want to confuse people by teaching them about modular arithmetic in the same video as something else.
That's the last of the paper, guys. Numberphile is over!
im sub'd to all of your channels(or i thought) and this one pops up?! i mustve missed something!!!!! nooooo!!!!!
This video is unlisted.
Majskolvenz i meant the channel, in general. :)
seems i got lucky on 2 counts, then.
you must be new
DoinItRightTheFirstTime periodicvideos.blogspot.co.uk/2014/08/numberphile2-faq.html
Alan Douglas
ive been sub'd to 4-5 of bradys channnels for a few years now, but i guess thats 'new' in 2014. and thanks for the link, brady!
All this talk of P-1 makes me think of the Pollard P-1 factoring method. Would it be possible to do a video on that?
Another way to proof would be by contradiction, that by assuming when P = ab(meaning P is not a prime), [(ab-1)! + 1 ] mod ab = 0, which is impossible. Is this possible?
Grimes is one of those guys who don't write everything out (their thought process) when doing a proof (which kinda bothers me but I guess it's a personal distaste since I tend to forget things quite often)
Why didn't you explain modulus? This would have been a perfect time to do so! xD
Am I the only one who thinks this should be the main video and the other thing the extra?
Yup, how they dare not to add this to the main video! By the state awesomeness, this is the main video, first one was just intro. But this is youtube, keep it short and let the viewer choose what to watch. This way it pleases the biggest part of audience. But it was just more amazing to see how prime test could anyhow possibly work, than that it just works.
5:23
You cannot put your equal- sign (=) right there...
Becuse you now look on the reminder, and not the multiplication of the numbers themselves.
Can we do this with primes like that THREE times
What happens if the remainder is prime?
Why isn't this showing up in the video list for Numberphile2?
actually there is a symmetry between two triangle of numbers
I didn't get the 4 thingy....
(4-1)! + 1 = (1x2x3) + 1 = 6+1 = 7 / 4 = 1 rem(3)
And even when you go to the table you get 2x2=>0
the only pair that can make a zero would be to pair 2 with 2 but you cant do that so 4 will have a different remainder and all other non primes will have remainder 1
The video mentions 4 because in the rigorous demonstration this theorem involves group theory, and in that context, 4 is a special case. In fact lot of the basic theorems only work for n>2 or n>4.
In this sense this theorem is kind of a corollary as it talks about prime numbers while being demonstrated typically by group theory, and the demo requires for n to be >4. That's why he states that "4 is a special case".
He means that 4 is a special case for his composite test, which states that for composite n, (n-1)! has a remainder of zero when divided by n. That works for all composites except 4, in which case 3! = 6 which has a remainder of 2 when divided by 4. See the Wikipedia page on Wilson's Theorem for details.
@@twwc960 Yup. 4 is a special case for the (n-1)! having remainder zero part, but it doesn't break the main non-prime rule: (4-1)!+1 isn't divisible by 4.
So if the quotient of [(p-1)! + 1] and p is a number that is also divisible by p, shouldn't the theorem for the Wilson Primes be [(p-1)! + 1]/p^2
how is there a rem(8) if you devide it by 7?
shouldt it be rem(1)?
CZcamsKidsTV rem stands for remainder, there's a remainder of 8 when you divide it by 7, and that is 1.
He's just concerned about multiplication modulo 7. In the proof, you work modulo p, and, even cooler, in the group U(p), the multiplicative group of integers modulo p.
Could this somehow help with faster sudoku slowing and PvsNP?
No
isn't it obvious that it won't work for even numbers like 6?
If you do any factorial that bigger than 1! it always includes x2, which means the result will be an even number.
so if you then take one away, it will be odd and therefore not divisible by an even number.
7:12 The Count from Sesame Street?
Or maybe the Tootsie Roll owl.
Indeed, 4 *is* a special case, but *not* in that Wilson's Theorem doesn't apply to it (for it does: (4-1)! + 1 = 3 \= 0 (mod 4)), but in that (4-1)! is not equal to 0 mod 4. Indeed, (4-1)! = 1*2*3 = 6 = 2 (mod 4).
Now, consider p^2 for any prime p. If 1 < x < p^2 and gcd(x, p^2) > 1 (which, in algebra lingo, is the necessary and sufficient condition for x to be a 0 divisor in the ring Z_{p^2}), then gcd(x, p^2) = p which forces x = p. So, (p^2-1)! *cannot* be shown to be 0 by the "taking pairs" argument used in the video (note that 4 = 2^2 is a special case of this). In particular, Grimes' proof of Wilson's Theorem doesn't hold for the general composite. Interestingly, (1) it *is* nevertheless true that if n > 4 is composite, then (n^2 - 1)! = 0 (mod n); and (2) Wilson's Theorem *is* indeed true for the general composite. For proofs of both of these facts, see:
en.wikipedia.org/wiki/Wilson's_theorem#Composite_modulus
I notice the "Sudoku" rules were't true for the 6 table. Is that because it's not prime?
Yes it is. Good catch!
it's a latin square - vote now which you like more latin or parker square