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

[@gunhasirac]

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]

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]

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]

​​@@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.

[@chaosredefined3834]

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]

I love this proof

[@samueldeandrade8535]

Yep. You even explained it too much.

[@chaosredefined3834]

@@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]

@@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]

@@samueldeandrade8535 Michael Penn. He occasionally goes into excessive detail, but nowhere near as often as the rest.

[@marcocosto6748]

my life is now complete

[@StefanReich]

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]

Isn't this a basic thought experiment which you can find upon thousands of videos on KZbin?

[@Ephemeral_EuphoriaYT]

​@@sonicwaveinfinitymiddwelle8555he's making a joke that this theorem has no effect on his life

[@user-cd9dd1mx4n]

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❤

[@alipourzand6499]

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]

Do do use a decimal point for multiplication. n*m^x - m*n^x

[@niom9446]

Cool

[@antosandras]

It holds also for x = 4n+1 for any n>=1, like x=13.

[@alipourzand6499]

Right!

[@geoffstrickler]

@@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.

[@StephTBM4]

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 😊

[@TheNegationist]

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.

[@kensmusic1134]

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

[@pietergeerkens6324]

Very nice. Much more concise and elegant than my workings.

[@KashTheStampede]

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.

[@jursamaj]

Given that we only needed the 1st few factors, m^5n-mn^5 would have been sufficient.

[@rob876]

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]

Yes. In fact any exponent 1+2^k, k greater than 1, works.

[@chaosredefined3834]

@@jursamaj It's even better than that... 1+4k for any non-negative integer k works.

[@iMíccoli]

True

[@quandarkumtanglehairs4743]

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...

[@sr6424]

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]

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]

@@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]

@@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]

@@bobh6728😂

[@iMíccoli]

​@@bobh6728😂😂😂😂 genius

[@p07a]

This one was very pleasant. Thank you.

[@leftysheppey]

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

[@mtwoh]

Very elegant.

[@mcrow312166]

For me this was engrossing. Thanks.

[@samyachakraborty263]

thats indeed a very beautiful proof

[@seshagirivaddadi5991]

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

[@aradziv89]

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

[@moonwatcher2001]

Excellent!!!

[@Giannis_Krimitzas]

Top tier math. Thank you

[@user-cq4xu6hc1z]

thank you so much!!!

[@CristianBaeza-rh7zq]

Loved it 👌👌👌

[@txikitofandango]

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

[@cauchym9883]

A nice proof!

[@ItzJordzYT]

This is very cool

[@WinstanleyMaths]

Fab as always

[@QuaDue]

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.

[@darcash1738]

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.

[@justarandomdood]

very simple very quick very impressive nice stuff :O

[@dorkmania]

Satisfying indeed!

[@mihaleben6051]

Nice.

[@xyzain_1827]

Satisfying indeed.

[@jasimmathsandphysics]

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]

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.

[@Khashayarissi-ob4yj]

With luck and more power to you.

[@bartekabuz855]

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]

This holds when m and n are each coprime to 10, but needs more to cover the cases where they are not

[@peterpan1886]

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]

@@mrphlip do it for 2 and 5 which are primes, you'll get mod = 0 for both for any m and n

[@robertveith6383]

​​@@peterpan1886 -- You have a typo instead of n^16.

[@antosandras]

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).

[@wesleydeng71]

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).

[@shinogu921]

cool😮

[@monudavinci11]

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.

[@josepherhardt164]

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. :)

[@ianfowler9340]

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.

[@CharlesB147]

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.

[@xnx_3609]

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

[@mauisstepsis5524]

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.

[@BramCohen]

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

[@swank8508]

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

[@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.

[@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

[@fulltimeslackerii8229]

So could you have just done mod 10 from the start instead of doing 2 and 5?

[@tioulioulatv9332]

الله يحفظك

[@maxytgaming3199]

alternatively for 5, if one of m or n is a multiple of 5 then done, else fermat little finishes

[@maxytgaming3199]

since m^16=1 mod 5

[@samueldeandrade8535]

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.

[@nnaammuuss]

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). 👍

[@sjswitzer1]

Mesmerized by how Dr. Barker always closes brackets with an upward stroke

[@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

[@aliensconfirmed3498]

If we are using modulo arithmetic anyway then it would be easier to teach how things work modulo 10

[@GrimAxel]

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.

[@markgraham2312]

Nice mechanical proof.

[@MrConverse]

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.

[@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?

[@ethannguyen2754]

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

[@emguag]

Cant the problem be to the power of 5 also

[@JR13751]

For 2, exponents don't matter. For 5, reduce exponents by mod 4.

[@tomhase7007]

If you use (-2) and (-1) as representatives mod 5 instead of 3 and 4, then you can make your life easier.

[@bambangnugroho6147]

Too much lived in Moebius Strip

[@remischmitt9308]

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.

[@andrewmccauley6262]

Disappointed we didn't get to use that (m^8 + n^8) term

[@vishalmishra3046]

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.

[@adrianopa1440]

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]

510

[@Vanilla-bf9wl]

But what if m and n are both equal to 1? Surely 0 isn't divisible by 10?

[@deept3215]

0/10=0, so yes, it is

[@Sam_on_YouTube]

So 17 was a red hereing. You could have done any number 1 more than a power of 2, 5 or greater.

[@davidgillies620]

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.

[@deept3215]

Now prove it's also divisible by 17

[@ItzJordzYT]

Can i get a shout out

[@wernergamper6200]

No.

[@pittyconor2489]

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

[@jackkalver4644]

17=1(mod 4) so x^17=x(mod 10) so m^17n-mn^17=mn-mn=0(mod 10)

[@nenadZF]

Strange way to write n

[@IsaacDickinson-tf8sf]

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]

You are missing grouping symbols. For starters, look at placing some around 2^n - 1.

[@oleksandrmedvediev2916]

by the same logic you can have mn5-m5n : 10 (and it works) - why do you use 17?

[@robertveith6383]

You wrote that wrong. You did not show exponentiation: m*n^5 - m^5*n

[@Blabla0124]

Small typo on the whiteboard: N, not Z

[@BryceHunt-eu7zw]

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]

@@BryceHunt-eu7zw You're right, I'm wrong

[@ivanmordvintsev2828]

It is not satisfying, it is working out 25 cases of n and m modulo 5

[@MizardXYT]

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.