When I first read the title, I thought it said "An inductive proof of Fermat's Last Theorem." And then I realized that was not the case. I'm disappointed now. Jk great video as always! Keep up the good work
this is one of my favorite proof, when i was around 18yo i saw the following problem featured in the anime Madoka Magica: (n+1)^p - n^p - 1 = 0 (mod p). I saw the binomial theorem right away but how do you use the fact that p is prime? I wrote it off as "probably some higher level of math required". It hit me 2 weeks later while doing something completely unrelated: you can factor out a p in the "p choose k" part and write it p * (p-1)! / k!(p-k)! That proves that p divide into every number on the p'th row of Pascal Triangle. Turns out it's actually a characterization of the primes, because the other way around is also true: if n divide every number on the n'th row of Pascal Triangle, then n is prime! I thought I was done with the problem but much later I realized... the (n+1)^p was congruent to n^p+1 (mod p) which itself is congruent to (n-1)^p +2 and so on... so you can go all the way down to (n-n)^p+n and (n+1)^p is congruent to n+1 (mod p). According to wikipedia the proof is from Gauss book, and Gauss himself credit Euler.
You did skip over something subtle in discussing your sum(mod p). p choose n is zero (mod p) which means that multiplying by integers necessarily yields divisibility by p; however, if p choose n is nonzero (mod p), then the product [(p choose n) b^n] (mod p) would cycle through the integers in [0, p=1]. Having a congruent to b(mod p) ordinarily does NOT imply that ax is congruent to b(mod p); this is necessary ONLY when b=0.
change in sign: (-m)^p = ((-1)^p)(m^p) which reduces to (-1)(m) = -m mod p. (-1)^2 = 1 which is the same as -1 mod 2, and if p is odd we obtain (-1)^p = -1.
One noteworthy consequence of the lemma is that if p is prime, every number in the pth row of Pascal's triangle (except for the 1's at the ends) is a multiple of p.
Hey, thanks for another great video. Just wanted to confirm the final statement you made at 7:26. You said (b+1)^p ≣ b (mod p), but wrote (b+1)^p ≣ b+1 (mod p). Which is correct?
This is an interesting proof and I think it highlights the connection between Fermat's Little Theorem and the Freshman's Dream. But I don't think you actually needed the induction. You can write n as (n-1) + 1. Then, just like in your proof, ((n-1) + 1)^p = sum(p choose k)(n-1)^k which is congruent to (n-1) + 1 = n. It's essentially identical to your proof but it doesn't rely on induction.
Why can we say that (n-1)^k is congruent to (n-1)modP? This is something that the inductive hypothesis only assumes; we see it to be true for n=1 and so then induction allows us to prove it for consecutive natural numbers as we prove the (n+1)th case also holds, given this initial assumption. Without induction though we can’t have this assumption?
Let A negative integer and p prime We suppose p = 2 We have A^2 and A are both even or both odd Then A^2 = A mod(2) We suppose p 2 Then p odd A^p = ((-1)|A|)^p = (-1)^p |A|^p = - |A|^p = - |A| (modp)=A(modp)
If the other day we watchched that: ----- In primitive Pythagorean triples, a or b must be a multiple of 3. Why? Since all three are squared, by Fermat's little theorem, a ^ 2 + b ^ 2 = C ^ 2 ... Is. 1 +1 = 1 Mod 3 ... Absurd. Unless a or b are multiples of 3. 1+ 0 = 1 ... So a or b has to be multiples of 3 ... No problem. --- Today say: Lemma 2 of primitive pitahogrian number...There no a¨2 + b 2 = 0 mod 7....Why.....I give a clue...See the group class of 7 Z/7....And, in this group, search the subgroup { 1, 2, 4}....
Simplest proof of Fermat's Little Theorem I've ever seen, very nice!
There's an even simpler proof if we used Freshman's Dream as our Lemma to prove Fermat's Little Theorem ;)
Hi Michael,
I appreciate the fact you have shown many nice proofs of my theorem!❤️
lol nice one
Aw he's just little
I never read this proof, which is quite elegant and the easiest to retaining and to teach I know? ... now !
Thank you !
Good one, this is exactly how I proved it back in my Linear Algebra II class :)
I am not the only one who thought for a second that it's Fermat LAST theorem
When I first read the title, I thought it said "An inductive proof of Fermat's Last Theorem." And then I realized that was not the case. I'm disappointed now.
Jk great video as always! Keep up the good work
Ha ha !
The Little Theorem is much more useful, to be honest.
Ha ha 😂 you shouldn't be 😜 suprised my friend
this is one of my favorite proof, when i was around 18yo i saw the following problem featured in the anime Madoka Magica: (n+1)^p - n^p - 1 = 0 (mod p). I saw the binomial theorem right away but how do you use the fact that p is prime? I wrote it off as "probably some higher level of math required". It hit me 2 weeks later while doing something completely unrelated: you can factor out a p in the "p choose k" part and write it p * (p-1)! / k!(p-k)!
That proves that p divide into every number on the p'th row of Pascal Triangle. Turns out it's actually a characterization of the primes, because the other way around is also true: if n divide every number on the n'th row of Pascal Triangle, then n is prime!
I thought I was done with the problem but much later I realized... the (n+1)^p was congruent to n^p+1 (mod p) which itself is congruent to (n-1)^p +2 and so on... so you can go all the way down to (n-n)^p+n and (n+1)^p is congruent to n+1 (mod p).
According to wikipedia the proof is from Gauss book, and Gauss himself credit Euler.
Never thought about such a great proof! Well done!
Just a little precision : it is not enough to say that n! does not divide p, but that none of the factors of n! divides p. The proof is the same.
Right
That's a really nice proof and well explained. THanks very much.
You did skip over something subtle in discussing your sum(mod p). p choose n is zero (mod p) which means that multiplying by integers necessarily yields divisibility by p; however, if p choose n is nonzero (mod p), then the product [(p choose n) b^n] (mod p) would cycle through the integers in [0, p=1]. Having a congruent to b(mod p) ordinarily does NOT imply that ax is congruent to b(mod p); this is necessary ONLY when b=0.
4:06 Classic mp
7:33 Good Place To Stop
classic mp indeed
change in sign: (-m)^p = ((-1)^p)(m^p) which reduces to (-1)(m) = -m mod p. (-1)^2 = 1 which is the same as -1 mod 2, and if p is odd we obtain (-1)^p = -1.
Hey Michael, I'm a former student of yours from way back... could you make a video on the Mandlebrot set? I find it fascinating
Can you please link to your other videos proving Fermat's little theorem?
One noteworthy consequence of the lemma is that if p is prime, every number in the pth row of Pascal's triangle (except for the 1's at the ends) is a multiple of p.
I was able to come up with this proof when I was trying to prove that n^p - n is always divisible by a prime p
Thank you, professor.
great proof
Hey, thanks for another great video. Just wanted to confirm the final statement you made at 7:26. You said (b+1)^p ≣ b (mod p), but wrote (b+1)^p ≣ b+1 (mod p). Which is correct?
I think the thing written
(b + 1)^p = b + 1 (mod p) is the desired result assuming that some c = b + 1. c^p = c (mod p)
If a is in Z, then a is congruent to b mod p, with b in N.
I know it isn't what your channel does but some advanced undergrad or postgrad module series would be amazing
Nice proof. Very easy to follow.
What about some Galois theory videos? Even an introduction would be awesome!
Good!
I'm waiting for the big theorem later on
4:25 'Fermazzletheorem' 🤣
mod is just pow upside down
good observation
This is an interesting proof and I think it highlights the connection between Fermat's Little Theorem and the Freshman's Dream. But I don't think you actually needed the induction. You can write n as (n-1) + 1. Then, just like in your proof, ((n-1) + 1)^p = sum(p choose k)(n-1)^k which is congruent to (n-1) + 1 = n.
It's essentially identical to your proof but it doesn't rely on induction.
Why can we say that (n-1)^k is congruent to (n-1)modP? This is something that the inductive hypothesis only assumes; we see it to be true for n=1 and so then induction allows us to prove it for consecutive natural numbers as we prove the (n+1)th case also holds, given this initial assumption. Without induction though we can’t have this assumption?
@@toby.barnett Oh right, sorry. I guess I had a brainfart and forgot the power of k on it.
There’s also a good group theoretic proof using LaGrange’s Theorem. Nice proof!
My very first sentence would have been that's a good place to stop
Beautiful
Let A negative integer and p prime
We suppose p = 2
We have A^2 and A are both even or both odd
Then A^2 = A mod(2)
We suppose p 2 Then p odd
A^p = ((-1)|A|)^p
= (-1)^p |A|^p
= - |A|^p = - |A| (modp)=A(modp)
Nice!
I have a proof for this too, but it's too large to fit in a TH-cam comment.
If the other day we watchched that:
-----
In primitive Pythagorean triples, a or b must be a multiple of 3. Why?
Since all three are squared, by Fermat's little theorem, a ^ 2 + b ^ 2 = C ^ 2 ...
Is.
1 +1 = 1 Mod 3 ... Absurd. Unless a or b are multiples of 3.
1+ 0 = 1 ... So a or b has to be multiples of 3 ...
No problem.
---
Today say: Lemma 2 of primitive pitahogrian number...There no a¨2 + b 2 = 0 mod 7....Why.....I give a clue...See the group class of 7 Z/7....And, in this group, search the subgroup { 1, 2, 4}....
For the demonstration of the lemma, you have (p n) = p!/((p-n)!n!) too (easier to write) 😉