So, *that*'s why they call them 4-letter words! Also, that's a lovely proof!
@billh17
11 ай бұрын
The idea of this approach is similar to that used by McKay to prove Cauchy's group theorem (p divides order of a group G implies G has an element of order p).
@spiderjerusalem4009
11 ай бұрын
yes, using tank to kill a mosquito
@noahtaul
11 ай бұрын
I wrote this in the comments of your complex numbers proof, but that proof and this one are the same idea: find a group action of Z/p on a set of size a^p with a fixed points, and you’re done! In fact, you can do the same sort of thing with Wilson’s theorem! There is a Z/p group action on the set (or group!) of permutations on the set {1, … p}. Namely, a generator of Z/p sends the permutation taking a to b, to the permutation taking a+1 (mod p) to b+1 (mod p). For example, the permutation 1->2->6->1, with 3, 4, 5, 7 as fixed points, is mapped to the permutation 2->3->7->2, then to 3->4->1->3, etc. In fact, there are this action preserves the property of being a complete cycle (I.e. all elements are part of one big cycle, a la 1->5->7->2->4->6->3->1). How many such cycles are there? 1 has p-1 places to go, then that number has p-2 places, then the next has p-3, etc. So there’s (p-1)! of these cycles. We’ll look at the action on this set. How many of them are fixed points? If p -> a, then 1 must go to a+1, 2 goes to a+2, etc. So the permutation is addition by a, which is in fact a complete p-cycle if a is nonzero. So there are p-1 fixed points. Therefore, the rest are grouped into sets of size p. Hence (p-1)! - (p-1) is divisible by p, which is Wilson’s theorem. We used the fact that p is prime in a similar vein as Michael’s video: for non-prime p, there are a so that addition-by-a is not a complete p-cycle, such as addition by 3 mod 15. That makes up 3 5-cycles. But that’s the only possible type of counterexample.
@curtiswfranks
11 ай бұрын
😮
@evanperez3079
11 ай бұрын
I love your content and videos!! Thank you so much for making math fun and helping fuel curiosity.
@kdpwil
11 ай бұрын
Careful. @11:29 in the video you've assumed a> 0: but a is from the integers, NOT the natural numbers, hence could be negative. It's easy to fix the proof, but it needs to be done.
@austin2150
11 ай бұрын
Great video. We greatly appreciate your work!
@pablosarrosanchez460
11 ай бұрын
In 10:11, in the second case where p=n, why is it that m=1? I don't see it.
@oliviermiakinen197
11 ай бұрын
Same for me.
@ZipplyZane
11 ай бұрын
Because p is divisible by mn, and p is prime. So mn must be either p or 1. if p=mn, and p = n, then you get n=mn and m=1. If p = 1 , then mn = 1, and mn are both natural numbers, so you can only get m=1 and n= 1.
@Bodyknock
11 ай бұрын
@@ZipplyZaneIt’s the other way around, p divides mn, not mn divides p.
@joelganesh8920
11 ай бұрын
That's where the proof falls short. m could be any number, and while that doesn't change the fact that the a_1, ..., a_p must be the same, the video really doesn't prove that. What would have been the way to go is to prove that if m is coprime with p (which is the case if p does not divide m), then am + 1 for a = 0, 1, ..., p-1 are all distinct modulo p. This just comes down to showing that the map f: Z/pZ -> Z/pZ, x -> m*x is injective, where Z/pZ denotes the set of integers modulo p. Suppose that m*x = m*y (mod p) for some choices of x, y. Then m*(x-y) = 0 (mod p). Since p does not divide m, it follows that x - y = 0 (mod p), so that x = y (mod p).
@wesleydeng71
11 ай бұрын
m=1 is incorrect. But a_1=a_2=...=a_p is correct since there are p of a's in the equations, which is the point he tries to make.
@dogedev1337
11 ай бұрын
I'm pretty sure Mathologer made a video on this proof method with nice animations, I recommend watching it. My favorite elementary proof of (the related) Euler's theorem relies on commutativity of multiplication mod p and invertibility of nonzero remainders mod p / Bézout's identity (for simplicity the modulus is assumed to be a prime here, but the proof can be easily extended to any modulus), as follows: Pick any nonzero remainder a mod p, then since a is invertible, multiplication by it is a bijection, and the sequence 1*a, 2*a, ..., (p-1)*a (all mod p) is a permutation of the nonzero remainders mod p. By commutativity of multiplication, we get that 1*2*...*(p-1) ≡ (1*a) * (2*a) * ... * ((p-1)*a) mod p, let x be the value of the left hand side, then the right hand side can be rearranged to form the equation x ≡ x*a^(p-1) mod p. Since x can't be zero, it must be that a^(p-1) ≡ 1 mod p.
@anshumanagrawal346
11 ай бұрын
This is the standard proof of Euler's Theorem
@curtiswfranks
11 ай бұрын
That is a good one.
@kylecow1930
11 ай бұрын
i had a few issues, why is n
@eric3813
11 ай бұрын
beautiful video!!
@MathFromAlphaToOmega
11 ай бұрын
This gives me flashbacks to my logic and model theory class (AKA the most traumatic math class I ever took). Let L be the language {0,1,+,-,*} with 0 and 1 constants and +,-,* binary functions on R...
@goodplacetostop2973
11 ай бұрын
17:50
@swenji9113
11 ай бұрын
I didn't understand what was the "n" in the lemma proof. Where does it come from and why is it less than p? Also why does p|mn imply that m=1 in the case where p=n? It just says p|mp then, which is always true. I'm a bit confused, I think i did not understand this proof at all, or it's just not correct. You want to use a Bezout identity here to find k such that mk=1 mod p. Then you get a_i=a_{mk + i}=a_{1 + i} so all letters in the word must be equal, right?
@aug3842
11 ай бұрын
it is because w is a p letter word, so the index can be at most p meaning that if n = p then m must be at most 1
@DeanCalhoun
11 ай бұрын
This is a roundabout method for the proof via lagrange’s theorem. The words with not all distinct letters form a group, and all of the permutations then form a cyclic subgroup with p elements. Thus by Lagrange’s theorem p divides a^p-a and we are done.
@curtiswfranks
11 ай бұрын
This is a proof from The Book. No doubt about it.
@laux_dtm5027
11 ай бұрын
Isn't this theorem just the definiton of the modulo ? Like, I think (a congruent to b mod n) means (n divides a-b) by defintion
@allanjmcpherson
11 ай бұрын
No, it is true that a is congruent to b mod n is equivalent to n dividing a-b, but what this proves is that for all integers a and primes p, a^p is congruent to a modulo p. It uses the definition of the modulo, but it proves a result that is much more powerful than that definition alone. It allows us to take any integer raise to a prime and know that if we reduce modulo that prime, we retrieve the integer, which we would not know from the definition of the modulo alone.
@laux_dtm5027
11 ай бұрын
@@allanjmcpherson ohhh ok that is not what i understood, thank you. So it's a really pretty theoreme then
@allanjmcpherson
11 ай бұрын
@@laux_dtm5027 no problem! I'm glady explanation helped
@EltonPapanikolla
11 ай бұрын
Be careful, hold on when you fall 5:29.
@robshaw2639
11 ай бұрын
I have seen this proof somewhere on youtube before, but I forget where.
@Lakedaimōn-h8j
11 ай бұрын
7:00 Why are indices mod p?
@gmcflyer
11 ай бұрын
same here
@gmcflyer
11 ай бұрын
ok, if 2m+1 is greater than p once you do p cycles you are back to the original word already so indices are working mod p
@nevoitzhak2092
11 ай бұрын
What about p=4 and the word:"abcd"? Its cyclic permutations are distinct
@terencetsang9518
11 ай бұрын
Of course for any length _there exists_ words which gives unique cyclic permutations. But it's only for prime lengths that _every non-uniform word_ gives them.
@nevoitzhak2092
11 ай бұрын
@@terencetsang9518 but why does the length have to be prime? I get the thing about EVERY word giving unique cyclic permutations but why do prime numbers in particular work here?
@TheEternalVortex42
11 ай бұрын
@@nevoitzhak2092because primes have no nontrivial divisors. Every nontrivial divisor corresponds to a repeated cyclic permutation
@nevoitzhak2092
11 ай бұрын
@@TheEternalVortex42 and why is that?
@Convergant
11 ай бұрын
Because the proof relies on ALL of the words of length p having distinct cyclic permutations (up to p applications). Suppose you have a word of length N. Let m be a divisor of N. Then, a word composed of a sequence of m distinct letters from the alphabet, repeated N / m times, will repeat after m cyclic permutations. You can verify this yourself easily, so I won't write it out. Clearly, based on this, if every word is going to have distinct permutations, the length of the word needs to be a prime number. Hope this helps!
@charleyhoward4594
11 ай бұрын
sorry - his explanation falls short for me
@magicalgirlgleamingmoonlight
11 ай бұрын
m = 1 here cause m p, we can write it as p+m' , and then do p less permutations (i.e, nothing) and just use m' and rename it to m. then if its still less than p, repeat til it isnt.
@Bodyknock
11 ай бұрын
Hypothetically you can tweak the proof of the lemma using a₀ through aₙ₋₁ instead of a₁ through aₙ. You get for some m that a₀ = aₘ = a₂ₘ = ... = aₙₘ . Therefore 0 ≡ mn (mod p), so p|m or p|n. (Similar to the video but without the "+1" on both sides.) As in the video, that means m = 1. But then, since m=1, every single cyclic permutation is identical, but the only way that happens is if the word had only one letter.
@zVepox
11 ай бұрын
Just wondering, why is m=1? I might be missing something but I don’t see it…
@Bodyknock
11 ай бұрын
@@zVepox Yeah, he doesn’t explain that step well in the video.
@joelganesh8920
11 ай бұрын
It is impossible to explain because it is just plainly false, m could be any other integer without any problem. The key step is to prove that if m is coprime with p (which is the case if p does not divide m), then for a = 0, 1, ..., p-1, the integers am+1 are distinct modulo p. Then it is also obvious that the integers am modulo p are different for the different values of a = 0, 1, ..., p-1, which would complete the tweaked proof.
Пікірлер: 58