A Satisfying Divisibility Proof
A Satisfying Divisibility Proof
We prove that m^{17} n - m n^{17} is divisible by 10, for all integers m, n.
00:00 Divisibility by 2
01:55 Factorisation
03:25 Working modulo 5
A Satisfying Divisibility Proof
We prove that m^{17} n - m n^{17} is divisible by 10, for all integers m, n.
00:00 Divisibility by 2
01:55 Factorisation
03:25 Working modulo 5
Пікірлер: 125
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.
@chaosredefined3834
5 күн бұрын
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.
@gunhasirac
5 күн бұрын
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
@FazilAmirli-ri3tr
4 күн бұрын
@@chaosredefined3834 this theorem is called Freshman's dream. I saw it on finite fields lectures. I meant inductive proof, not Fermat's btw.
my life is now complete
@StefanReich
7 күн бұрын
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)
@sonicwaveinfinitymiddwelle8555
6 күн бұрын
Isn't this a basic thought experiment which you can find upon thousands of videos on KZread?
@Ephemeral_EuphoriaYT
5 күн бұрын
@@sonicwaveinfinitymiddwelle8555he's making a joke that this theorem has no effect on his life
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
@legamerfandesience2987
7 күн бұрын
I love this proof
@samueldeandrade8535
7 күн бұрын
Yep. You even explained it too much.
@chaosredefined3834
7 күн бұрын
@@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.
@samueldeandrade8535
7 күн бұрын
@@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.
@chaosredefined3834
7 күн бұрын
@@samueldeandrade8535 Michael Penn. He occasionally goes into excessive detail, but nowhere near as often as the rest.
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!
@robertveith6383
7 күн бұрын
Do do use a decimal point for multiplication. n*m^x - m*n^x
@niom9446
6 күн бұрын
Cool
@antosandras
6 күн бұрын
It holds also for x = 4n+1 for any n>=1, like x=13.
@alipourzand6499
6 күн бұрын
Right!
@geoffstrickler
4 күн бұрын
@@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.
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❤
Given that we only needed the 1st few factors, m^5n-mn^5 would have been sufficient.
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
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.
@jpharnad
7 күн бұрын
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.
@sr6424
6 күн бұрын
@@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!
@bobh6728
6 күн бұрын
@@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.j4mes
5 күн бұрын
@@bobh6728😂
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...
Since you only used up to m^2 + n^2 for divisibility of 5, isn't m^5n - mn^5 also divisible by 10?
@jursamaj
7 күн бұрын
Yes. In fact any exponent 1+2^k, k greater than 1, works.
@chaosredefined3834
5 күн бұрын
@@jursamaj It's even better than that... 1+4k for any non-negative integer k works.
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
@mrphlip
7 күн бұрын
This holds when m and n are each coprime to 10, but needs more to cover the cases where they are not
@peterpan1886
7 күн бұрын
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)*.
@SillySussySally
7 күн бұрын
@@mrphlip do it for 2 and 5 which are primes, you'll get mod = 0 for both for any m and n
@robertveith6383
7 күн бұрын
@@peterpan1886 -- You have a typo instead of n^16.
@antosandras
6 күн бұрын
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).
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.
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
Very nice. Much more concise and elegant than my workings.
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
For me this was engrossing. Thanks.
This one was very pleasant. Thank you.
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
thats indeed a very beautiful proof
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.
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 😊
thank you so much!!!
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).
Loved it 👌👌👌
Satisfying indeed.
This is very cool
Top tier math. Thank you
Fab as always
A nice proof!
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.
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).
@cadekachelmeier7251
6 күн бұрын
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.
Satisfying indeed!
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
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.
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.
very simple very quick very impressive nice stuff :O
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.
Nice.
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
With luck and more power to you.
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.
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.
Disappointed we didn't get to use that (m^8 + n^8) term
cool😮
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
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. :)
الله يحفظك
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.
Mesmerized by how Dr. Barker always closes brackets with an upward stroke
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.
For 2, exponents don't matter. For 5, reduce exponents by mod 4.
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). 👍
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
alternatively for 5, if one of m or n is a multiple of 5 then done, else fermat little finishes
@maxytgaming3199
6 күн бұрын
since m^16=1 mod 5
So could you have just done mod 10 from the start instead of doing 2 and 5?
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.
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
Nice mechanical proof.
If you use (-2) and (-1) as representatives mod 5 instead of 3 and 4, then you can make your life easier.
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.
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.
So 17 was a red hereing. You could have done any number 1 more than a power of 2, 5 or greater.
Now prove it's also divisible by 17
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.
not really satisfying when u had to check all the mod 5s and not give like a general solution to slice it all up
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?
@deept3215
6 күн бұрын
510
17=1(mod 4) so x^17=x(mod 10) so m^17n-mn^17=mn-mn=0(mod 10)
But what if m and n are both equal to 1? Surely 0 isn't divisible by 10?
@deept3215
6 күн бұрын
0/10=0, so yes, it is
Can i get a shout out
@wernergamper6200
6 күн бұрын
No.
Strange way to write n
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.
@robertveith6383
7 күн бұрын
You are missing grouping symbols. For starters, look at placing some around 2^n - 1.
by the same logic you can have mn5-m5n : 10 (and it works) - why do you use 17?
@robertveith6383
7 күн бұрын
You wrote that wrong. You did not show exponentiation: m*n^5 - m^5*n
Small typo on the whiteboard: N, not Z
@BryceHunt-eu7zw
7 күн бұрын
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
@Blabla0124
5 күн бұрын
@@BryceHunt-eu7zw You're right, I'm wrong
It is not satisfying, it is working out 25 cases of n and m modulo 5
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.