I love how the video is trying to explain it to 3 year old and comments are trying to use every number theory theorem to solve it.
@chaosredefined38342 ай бұрын
I use Fermat's Little Theorem, but only for the case when p = 5, which can be proven on a blackboard in the same manner that he did. And is pretty satisfying on it's own. If the students can keep up with an inductive proof (which Dr Barker has done before), you can prove it true for any specific prime. (As a hint, to prove it for p=3, note that (a + 1)^3 = a^3 + 3a^2 + 3a + 1 = a^3 + 1 mod 3.) And if they know the binomial co-efficients are n(n-1)(n-2)...(n-k+1) / k!, then you can prove it true in general.
@gunhasirac2 ай бұрын
I’m not actually suggesting that’s a worse approach if it sounded that way. On the one hand, yes, Fermat’s little theorem is like the very first thing you will try in these kind of problems, but on the other hand, it’s still a piece of knowledge you will only know as mathematicians or math nerds. And again I just found it funny lol
@mathslover982 ай бұрын
@@chaosredefined3834 this theorem is called Freshman's dream. I saw it on finite fields lectures. I meant inductive proof, not Fermat's btw.
@gabrielfoos9393Ай бұрын
@@chaosredefined3834 you can also prove it using group theory (not necesseraly easier but its interesting nonetheless), if you consider p a prime number then considering the field Fp, in that case Fp* is a group for multiplication (all non zero elements are invertible because they are coprime with p), then we know that the cardinal of Fp* is p-1 so using the fact that the order of each element divides the cardinal of the group then necesseraly if a is a natural number non divisible by p a^p-1=1 mod(p), this proof can be generalized to prove Gauss's lemma, if a and n are coprime then a^phi(n)=1 mod(n) ( the reasoning is the same except we consider the group of invertibles of the ring Z/nZ, (Z/nZ)* which has cardinal phi(n))
@chaosredefined3834Ай бұрын
@@gabrielfoos9393 Sure, but explain that to a high schooler.
@chaosredefined38342 ай бұрын
For all of this, a = b means a = b mod 5. I just don't want to have to write mod 5 everywhere. By Fermat's Little Theorem, we know that: m^5 = m Multiplying both sides by m^4 m^9 = m^5 We already know that m^5 = m, so m^9 = m. Multiplying both sides by m^8 m^17 = m^9 We already know that m^9 = m, so m^17 = m Nothing here is reliant on the value of m, so all of this is true for n as well. So, we can rewrite the statement m^17 n - m n^17 as mn - mn, or 0
@legamerfandesience29872 ай бұрын
I love this proof
@samueldeandrade85352 ай бұрын
Yep. You even explained it too much.
@chaosredefined38342 ай бұрын
@@samueldeandrade8535 I try to make it as approachable as possible. I find it excessive sometimes, but I find a lot of math youtubers can be a bit excessive in their explanations as well.
@samueldeandrade85352 ай бұрын
@@chaosredefined3834 oh yeah, for sure. I completely agree. I can't tell you a great math youtube channel anymore. I just can't. But, in terms of presentation, I love Combo Class. Hahahahahaha. I love that guy. Domodro, or something like that. I never remember his name.
@chaosredefined38342 ай бұрын
@@samueldeandrade8535 Michael Penn. He occasionally goes into excessive detail, but nowhere near as often as the rest.
@marcocosto67482 ай бұрын
my life is now complete
@StefanReich2 ай бұрын
If this video is what it took, your life was 99.9% complete just an hour earlier (I'm sure there is an inspiring thought in here somewhere)
@sonicwaveinfinitymiddwelle85552 ай бұрын
Isn't this a basic thought experiment which you can find upon thousands of videos on KZfaq?
@Ephemeral_EuphoriaYT2 ай бұрын
@@sonicwaveinfinitymiddwelle8555he's making a joke that this theorem has no effect on his life
@alipourzand64992 ай бұрын
It's easy to be wise after the event, at least for me! If we consider: n.m^x - m.n^x This divisibility holds for x = 5, 9, 17, 33, ..., 1 + 2^n Looking forward the next friday!
@robertveith63832 ай бұрын
Do do use a decimal point for multiplication. n*m^x - m*n^x
@niom94462 ай бұрын
Cool
@antosandras2 ай бұрын
It holds also for x = 4n+1 for any n>=1, like x=13.
@alipourzand64992 ай бұрын
Right!
@geoffstrickler2 ай бұрын
@@antosandras Yep, took me less than 2 minutes to figure that out from the thumbnail, didn’t watch the video., just saw the factors would include (m^16-1) and (n^16-1), ran the ((last digit of m/n ^4th)-1) x (last digit of m/n) = multiple of 10.
@user-cd9dd1mx4n2 ай бұрын
Incredibly clear and thorough. The content is accessible and engaging with your step-by-step explanation, I really like it. Thank you for such informative videos❤
@StephTBM42 ай бұрын
Nice! I have a shorter proof. Same method for divisibility by 2. Now consider divisibility by 5. If m or n = 0 mod 5, we're done. Now consider m = 1, 2 , 3 or 4 mod 5. m^4 is either 1, 16, 81 or 256, all = 1 mod 5. So m^4 - n^4 is 0 mod 5. CQFD. This is shorter because I studied 5 cases instead of 25 😊
@kensmusic11342 ай бұрын
For the divisibility by five, we can factor m^{17}n-mn^{17} into mn(n^8+m^8)(n^8-m^8). By Fermats Little Theorem we know that for a prime p and all integers a that are no multiple of p, that a^{p-1} = 1 (mod p). (if m or n is a multiple of p the statement follows directly). We can write m^8-n^8= m^4*m*4-n^4*n^4 and reducing modulo 5 we get 1-1 =0. Therefore the whole term is divisible by 5
@sr64242 ай бұрын
This is how I’d solve this using logic. We only need to prove the last digit is equal to zero. Any integer raised to the power 5 has the same last digit as the original integer. This is also true if it’s raised to the power of 9,13,17 etc.then the last digit of M^17.N will be equal to the Last digit of N^17.M . So subtract them one from the other it will equal Zero.
@jpharnad2 ай бұрын
This is not a self-contained alternative proof, since you are stating and using a non-obvious previous result; namely that, for any integer N, N^17 is congruent to N mod 10. But proving that statement requires an argument that is equivalent to the one presented here.
@sr64242 ай бұрын
@@jpharnad love your reply - I do puzzle evenings in a local bar . I will raise a number to the power of 9 and give 5 answers all with different last digits and allow up to a be minute to solve. I thought raising any integer to the power of 4X + 1 will always have the same last digit of the original!
@bobh67282 ай бұрын
@@jpharnad Assignment: Shiw the proof of theorem 18 on page 30 of your textbook. My Solution: Claim: Therefore theorem 18 is true Reason: Previously proven theorem 18 QED//
@bruh.j4mes2 ай бұрын
@@bobh6728😂
@iMíccoliАй бұрын
@@bobh6728😂😂😂😂 genius
@TheNegationist2 ай бұрын
I have an ugly solution, but it’s quick and doesn’t require paper. The statement is basically equivalent to saying that m^17n and mn^17 have the same ones digit, since if they do m^17n - mn^17 is divisible by 10. Well as it turns out, since all the possible units digits (0-9) when raised to the power of 17 retain their units digit(for example 2^17 = 131072), the units digit of m^17n is the same as the units digit of mn and the units digit of mn^17 is the same as the units digit of mn. Thus, m^17n and mn^17 must have the same units digit and m^17n - mn^17 is divisible by 10. Done.
@thomasr247219 күн бұрын
"it's quick and doesn't require paper"… so how did you calculate 7^17?
@jursamaj2 ай бұрын
Given that we only needed the 1st few factors, m^5n-mn^5 would have been sufficient.
@rob8762 ай бұрын
Since you only used up to m^2 + n^2 for divisibility of 5, isn't m^5n - mn^5 also divisible by 10?
@jursamaj2 ай бұрын
Yes. In fact any exponent 1+2^k, k greater than 1, works.
@chaosredefined38342 ай бұрын
@@jursamaj It's even better than that... 1+4k for any non-negative integer k works.
@iMíccoliАй бұрын
True
@quandarkumtanglehairs47432 ай бұрын
Really, REALLY dig the idea of this modulo table for digits 0-9. Done it for Boolean and Truth tables, dunno why I never considered it for modulo. That's really cool, and so now of course my mind wants to take it to geometry and sets...
@aradziv892 ай бұрын
I figured out the divisibility by 2 the exact way you did. for divisibility by 5 - fermat's little theorem states that a^(p-1) ≡ 1 mod p. therefore m^16 - n^ 16 = (m^4)^4 - (n^4)^4 ≡ 1^4 - 1^4 = 0
@bartekabuz8552 ай бұрын
phi(10)=4 and 17 mod 4 = 1 thus x^17=x mod 10. Hence m^17 * n - m * n^ 17 = m * n - m * n = 0 mod 10
@mrphlip2 ай бұрын
This holds when m and n are each coprime to 10, but needs more to cover the cases where they are not
@peterpan18862 ай бұрын
Just write m*n^17-n*m^17=nm(n^16-m^16) then. If nm is not divisive by 10, then both m and n are in (Z/10Z)*.
@SillySussySally2 ай бұрын
@@mrphlip do it for 2 and 5 which are primes, you'll get mod = 0 for both for any m and n
@robertveith63832 ай бұрын
@@peterpan1886 -- You have a typo instead of n^16.
@antosandras2 ай бұрын
x^17=x mod 10 already holds for any x considering a few case. Note that what is referred here is called Euler's theorem (or Little Fermat's theorem for primes).
@seshagirivaddadi59912 ай бұрын
Nice one. Since we just needed to go up to squares, we can say that any expression of the form: mn^5 - nm^5 is also divisible by 10
@wesleydeng712 ай бұрын
It is well known that m^5==m (mod 10). Therefore, m^17*n - m*n^17 (mod 10) == (m^5)^3*m^2*n - (n^5)^3*n^2*m == m^5*n - n^5*m == mn - nm == 0 (mod 10).
@KashTheStampede2 ай бұрын
Thanks for this video. I tried to do the divisibility by 5 myself by checking the different remainders. Later that day I wondered if the same thing works for all primes. I vaguely recalled seeing something like that, so I looked it up, and yep it was Fermat's Little Theorem. I'm never going to forget that theorem now.
@manojpillai8287Ай бұрын
Goodness. All you need to know is that if x between 1 to 10, then x^5 and x have the same unit's digit: ie x^5 = x mod 10. Of course, it's clearly true for all x. now modulo 10: m^17 * n =( m^5)^3 * m^2 * n = m^3 * m^2 * n = m^5 * n = m * n exchanging m, n and taking the difference you get the result.
@jasimmathsandphysics2 ай бұрын
I did it using modular arithmetic, an integer to power of 17 is congruent to itself mod(10). So m^17 is congruent to m mod(10) and n^17 is congruent to n mod(10). Multiplying these by n and m respectively and subtracting shows that nm^17-mn^17 is congruent to 0 mod(10).
@cadekachelmeier72512 ай бұрын
Yeah that's the way I went as well. My first instinct was just to check all 100 combinations of m and n mod 10 on a computer.
@darcash17382 ай бұрын
If either is even, we have an even number by m*n. We also have addition in one of the factors, so this becomes even if both are odd. So divisible by 2. 5 has the residue classes 0, 1, 2, 3, and 4. If either belongs to 0, mn as the factor leads the whole thing to be zero. We also know addition/subtraction and multiplication are valid operations for modulo. So, we can rewrite 4 as -1 and 3 as -2 by the addition aspect. 1 2 -2 -1 1 2 -2 -1 The whole main diagonal is 0 by m - n since if m = n, this = 0. The opposite signs become = 0 by m + n. And by m^2 + n^2, the rest also = 0, for any sign of 1s and 2s together.
@mtwohАй бұрын
Very elegant.
@xnx_36092 ай бұрын
For generalization, if x=p*q, where p and q are primes, then [a^(phi(x)+1) = a] mod x. In our case, x=10=2*5 and phi(10) = 4. Then (m^17 * n = m^5 * m^5 * m^5 * m^2 * n = m * m * m * m^2 * n = m^5 * n = m*n) mod 10 Same thing with (n^17 * m = n*m) mod 10 So we have (mn - nm = 0) mod 10
@faizanhussaini9658Ай бұрын
Divisibility by 2 can be easily checked but for 5 theres a really clean method where you show 1^4=1 2^4=1 3^4=1 4^2=1 So a^16=1 (mod 5) Meaning a^17=a and mn^17-nm^17 reduces to mn-nm=0
@mauisstepsis55242 ай бұрын
If x = 1, 2, 3, 4 mod 5, it's fairly easy to find out that x^16 = 1 mod 5. for example with x = 3. x = 3 mod 5, x^2 = 4 mod 5, x^4 = 1 mod 5, x^16 = 1 mod 5. So for any situation such that m, n e 0 mod 5, m^16 - n^16 = 0 mod 5.
@pietergeerkens63242 ай бұрын
Very nice. Much more concise and elegant than my workings.
@QuaDue2 ай бұрын
very nice, I factorised only to (m2+n2)(m2-n2) this is a liitle bit more complicated maybe but if we superpose the two 4x4 matrices (m or n multiple of 5 is trivial of course) of the two factors of this product we get such a beautiful symetric on the x and y axis superposition of zeroes and nonzeroes which is just so elegant.
@leftysheppey2 ай бұрын
Beautiful use of number theory! I don't think I'd have ever gotten there, but I at least noticed the DOTS reduction all the way down. I just hadn't figured it out from that point
@Giannis_KrimitzasАй бұрын
Top tier math. Thank you
@samueldeandrade85352 ай бұрын
Or simply use the amazing fact: x⁵=x (mod 10) Considering powers mod 10, we have 0,1,5,6 doesn't change 9 has period 2 2,3,4,7,8 have period 4 Done.
@monudavinci112 ай бұрын
For divisibility by 5, the factor m^4-n^5 is divisible by 5 by fermat's little theorem, if m and n are coprime to 5 else the factor mn is divisible by five.
@TaladrisKpop5 күн бұрын
Since 2^2=4=-1 mod 5, then m^4 = 1 mod 5 for every m such that m != 0 mod 5. Hence m^16 = 1 or 0 mod 5.
@tylosenpai6920Ай бұрын
Simply put... Ends with 1 -> 1 Ends with 2 -> 2 4 6 8 Ends with 3 -> 3 9 7 1 Ends with 4 -> 4 6 Ends with 5 -> 5 Ends with 6 -> 6 Ends with 7 -> 7 9 3 1 Ends with 8 -> 8 4 2 6 Ends with 9 -> 9 Ends with 0 -> 0 (Dividable by 10) These are cycles that finishes itself at n^(x+4), and starts again at n^(x+5) 17 fulfills this criteria, so let's pick randoms and test it... xx7*x1^17-x1*xx7^17 = (Some digits)7-(Some digits)7 = Something dividable by 10 (Some digits)2*(Some digits)9^17-(Some digits)2^17*(Some digits)2 = (Some digits)9*2-(Some digits)9*2 = (Some digits)8-(Some digits)8 = (Some digits)0 True for every 4n+1
@mcrow3121662 ай бұрын
For me this was engrossing. Thanks.
@GrimAxel2 ай бұрын
The interesting thing is that you could've just stopped your factorization at mn(m^4-n^4)(m^4+m^4)(m^8+m^8), For all k not divisible by 5, k^4 is 1 mod 5 (1^4=1=0*5+1, 2^4=16=3*5+1, 3^4=81=16*5+1, 4^4=256=51*5+1). Thus, if both m and n are not divisible by 5, then m^4-n^4 is equivalent to 1-1 mod 5, which is 0 mod 5.
@ianfowler93402 ай бұрын
If neither m,n get's you the 5, I thought about the relationship between m and n to force you to go to m^2 +n^2. If m = 3n then (3n)(n)(3n+n)(3n-n) doesn't get you the 5 but (9n^2 + n^2) = 10n^2 does. 24 and 8 is an example.
@josepherhardt1642 ай бұрын
Okay, that's even spookier than the 24 people in a room with a > 50% chance of sharing a birth month + day. But i^i being an element of the Reals is, of course, obvious, and I'm happy with that. :)
@BramCohen2 ай бұрын
It's also true of mn^5-m^5n. You factor out mn to get mn(m^4-n^4) and by fermat's little theorem if m and n aren't zero then that second part is 1-1 (mod 5) and 1-1=0
@samyachakraborty263Ай бұрын
thats indeed a very beautiful proof
@JR137512 ай бұрын
For 2, exponents don't matter. For 5, reduce exponents by mod 4.
@aliensconfirmed3498Ай бұрын
If we are using modulo arithmetic anyway then it would be easier to teach how things work modulo 10
@p07a2 ай бұрын
This one was very pleasant. Thank you.
@CharlesB1472 ай бұрын
So really, this works for ((m^5)*n-m*(n^5)) as a base case - the original equation makes it look a little flashier. Pretty clever stuff.
@ItzJordzYT2 ай бұрын
This is very cool
@MechaGuruАй бұрын
Using basic rules of module comparison: if m^17 * n - m * n^17 ⁝ 10 then: m^17 * n ≡ m * n^17 (mod 10) using theorem: if a ≡ b (mod m) and c ≡ d (mod m) then ac ≡ bd (mod m) we get: m^17 ≡ m (mod 10) Originally saw a top comment that proves this statement using Fermat's Little Theorem, but why would you need that if you have the basic rules of number theory that every 8th grader knows?
@MrConverse2 ай бұрын
Since you didn’t use the quartic and octic(?) factors then you could find smaller expressions with this same property, namely m^9*n - m*n^9 and m^5*n - m*n^5. I suppose the latter isn’t as interesting to discover always produces a multiple of ten given the exponent of five.
@ethannguyen27542 ай бұрын
You could also say that when m, n ≠ 0 mod 5, m^4 = n^4 = 1 mod 5 Then if either m or n = 0 mod 5, then mn(m^16 - n^16) = 0 mod 5 And if neither m nor n is 0 mod 5, then mn(m^16 - n^16) = mn(1^4 - 1^4) = 0 mod 5
@txikitofandango2 ай бұрын
Very cool! If I was in a flexing mood I might have run the table from -2 to 2 for even more symmetry and fun
@tomhase70072 ай бұрын
If you use (-2) and (-1) as representatives mod 5 instead of 3 and 4, then you can make your life easier.
@nnaammuuss2 ай бұрын
Good. Note also that m, n both not divisible by 5 implies m⁴=1 (mod 5) => m^16 = 1 (mod 5). Similarly, n^16 = 1 (mod 5). Therefore, their difference is 0 (mod 5). 👍
@sjswitzer12 ай бұрын
Mesmerized by how Dr. Barker always closes brackets with an upward stroke
@markgraham23122 ай бұрын
Nice mechanical proof.
@davidgillies6202 ай бұрын
It's a one-liner. k^(4 j + 1) mod 10 ≡ k mod 10. Then m^17 n mod 10 ≡ m n^17 mod 10 ≡ m n mod 10 ⇒ difference ≡ 0 mod 10 QED.
@vishalmishra30462 ай бұрын
F(m,n) = n m^17 - m n^17 = mn (m-n) (m+n) (m^2+n^2) (m^4+n^4) (m^8 + n^8). If mn is odd then both m and n are odd, so m+n and m-n are both even. Otherwise mn is even. So, mn (m+n) (m-n) is always even. So F(m,n) is always even. Now it remains to prove that at least one of the factors of F(m,n) is a multiple of 5 even when m and n are both not multiples of 5. m and n (mod 5) are either +/- (1 or 2). If equal then m - n is multiple of 5, If opposite then m + n is a multiple of 5. So, they have to be unequal (one 1 and the other 2). So, (m^2 mod 5) and (n^2 mod 5) would add to 1 + 4 = 5 (a multiple of 5). So, (m^2 + n^2) is a multiple of 5. In all cases, mn (m-n) (m+n) (m^2+n^2) is a multiple of both 2 and 5, hence a multiple of 10. So, the entire F(m,n) is a multiple of 10. Hence proved.
@moonwatcher2001Ай бұрын
Excellent!!!
@tioulioulatv93322 ай бұрын
الله يحفظك
@remischmitt93082 ай бұрын
nice, but grinding proof. 'Divisible' in this sense means: when 'divided by 10 gives an integer' (since 1/10 = 0.1 so 1 is divisible by 10). Exception: m=n OR m*n=0 gives 0 and . . . nope, not divisible by 10.
@maxytgaming31992 ай бұрын
alternatively for 5, if one of m or n is a multiple of 5 then done, else fermat little finishes
@maxytgaming31992 ай бұрын
since m^16=1 mod 5
@mihaleben60512 ай бұрын
Nice.
@justarandomdood2 ай бұрын
very simple very quick very impressive nice stuff :O
@user-cq4xu6hc1z2 ай бұрын
thank you so much!!!
@MizardXYT2 ай бұрын
m^(2^k+1)*n - m*n^(2^k+1) is divisible by the product of all primes of the form 2^r+1 less than or equal to 2^k+1. Those are called Fermat Primes, and the only known such primes are 2, 3, 5, 17, 257 and 65537. m^2*n - m*n^2 are divisible by 2. m^3*n - m*n^3 by 2*3 = 6. m^5*n - m*n^5 by 2*3*5 = 30. m^17*n - m*n^17 by 2*3*5*17 = 510. m^257*n - m*n^257 by 2*3*5*17*257 = 131070. Last one is m^65537*n - m*n^65537 is divisible by 2*3*5*17*257*65537 = 8589934590.
@Khashayarissi-ob4yj2 ай бұрын
With luck and more power to you.
@swank85082 ай бұрын
i checked every ones place digit and they all equal themselves when taken to the 17th power, so a*b-b*a=0 for the ones place digit
@CristianBaeza-rh7zq2 ай бұрын
Loved it 👌👌👌
@adrianopa14402 ай бұрын
No offense, but this answer wasn't satisfying. I liked the resolution, but you didn't need all those factors. So I have a different question: what's the GCD of that number? Is it possible to figure that out?
@deept32152 ай бұрын
510
@xyzain_18272 ай бұрын
Satisfying indeed.
@andrewmccauley62622 ай бұрын
Disappointed we didn't get to use that (m^8 + n^8) term
@Sam_on_YouTube2 ай бұрын
So 17 was a red hereing. You could have done any number 1 more than a power of 2, 5 or greater.
@cauchym98832 ай бұрын
A nice proof!
@WinstanleyMaths2 ай бұрын
Fab as always
@dorkmania2 ай бұрын
Satisfying indeed!
@fulltimeslackerii82292 ай бұрын
So could you have just done mod 10 from the start instead of doing 2 and 5?
@bambangnugroho6147Ай бұрын
Too much lived in Moebius Strip
@shinogu9212 ай бұрын
cool😮
@deept32152 ай бұрын
Now prove it's also divisible by 17
@jackkalver46442 ай бұрын
17=1(mod 4) so x^17=x(mod 10) so m^17n-mn^17=mn-mn=0(mod 10)
@emguagАй бұрын
Cant the problem be to the power of 5 also
@IsaacDickinson-tf8sf2 ай бұрын
2^n -1 /q is integer for odd q and n is a(q-1/2) where a(x) is A002326 and a(0) is 1, a(1)=2 etc.
@robertveith63832 ай бұрын
You are missing grouping symbols. For starters, look at placing some around 2^n - 1.
@Vanilla-bf9wl2 ай бұрын
But what if m and n are both equal to 1? Surely 0 isn't divisible by 10?
@deept32152 ай бұрын
0/10=0, so yes, it is
@pittyconor24892 ай бұрын
not really satisfying when u had to check all the mod 5s and not give like a general solution to slice it all up
@user-nq7hi2tt9jАй бұрын
wish it was more theoretical
@ItzJordzYT2 ай бұрын
Can i get a shout out
@wernergamper62002 ай бұрын
No.
@ToanPham-wr7xe21 күн бұрын
😮
@nenadZF2 ай бұрын
Strange way to write n
@oleksandrmedvediev29162 ай бұрын
by the same logic you can have mn5-m5n : 10 (and it works) - why do you use 17?
@robertveith63832 ай бұрын
You wrote that wrong. You did not show exponentiation: m*n^5 - m^5*n
@Blabla01242 ай бұрын
Small typo on the whiteboard: N, not Z
@BryceHunt-eu7zw2 ай бұрын
This is incorrect, the set of all integers is denoted as Z, which is what he stated in the beginning. N denotes the set of all natural numbers, which is part of Z
@Blabla01242 ай бұрын
@@BryceHunt-eu7zw You're right, I'm wrong
@ivanmordvintsev28282 ай бұрын
It is not satisfying, it is working out 25 cases of n and m modulo 5