A cool divisibility fact.

[@aa-lr1jk]

Fantastic. Is by watching these kind of videos with the length of almost 20 minutes about a complicated proof, without losing our attention, that we can appreciate how good a teacher Michel Penn is.

[@schweinmachtbree1013]

What an excellent application of elementary modular arithmetic!

[@goodplacetostop2973]

17:52 Homework 17:59 Good Place To Stop

[@arjunchawla2248]

You have definitely become my favourite math KZbinr! Love you and keep posting

[@udic01]

11:00 why do you need to break to 2 subcases?! (a+1) is exactly in the middle. So a=-1(mod a+1) and (a+2)=1(mod a+1) And so on until 1=-a(mod a+1) and (2a+1)=a(mod a+1). And they all cancel each other. Or you can do just one side. Wlog lets take the right side. (a+2)=-a(mod a+1) and so on until (2a+1)=-1(mod a+1) and they all again cancel each other

[@kakolideogharia7805]

I was looking for this comment..I also thought this

[@minamagdy4126]

This solution does require one thing: that gcd(a+1,2a+1)=1, which is simple but necessary to prove

[@serious-goober]

he said: "you can check that those are relatively primes pretty easily" around 15:00 If you want a proof that much: we have the gdc(a+1,2a+1) that divides all linear combinations of those two (since you can always factor it out of the combination), so we have gcd(a+1,2a+1) that divide "2(a+1)-(2a+1)", so the gcd divides 1 so gcd=1

[@tiemenfiat1321]

Your publication rate of video's is phenomenal! Keep on doing so!

[@mlerma54]

I think there is a quick and simpler proof that does not require to look at cases and subcases. Let S(n,m) = 1^m + 2^m + ... + n^m. We are trying to prove that S(n,1) divides S(n,m). Rewriting 2 S(n,m) = sum for k=0 to n of ( k^m + (n-k)^m ) and using that m is odd we see immediately that 2 S(n,m) = 0 (mod n). Also 2 S(n,m) = sum for k=1 to n of ( k^m + (n+1-k)^m), so 2 S(n,m) = 0 (mod n+1). So n and n+1 divide S(n,m), hence 2 S(1,m) = n (n+1) divides 2 S(n,m). This means 2 S(n,m) = 2 M S(1,m) for some integer M. Divide both sides by 2 and we are done.

[@andremouss2536]

10:25 It is much easier to use the same trick as above, writing a = -1 (mod (a+1)) ; a-1 = -2 (mod(a+1)) and so on until -1 = a (mod(a+1)), which leads to the conclusion immediately.

[@MarkusDarkess]

N^m can be factored by any multiple that goes into it. It can also have factors higher then N

[@MarkusDarkess]

1^3+2^3+3^3=36 36/6 36/12 36/9 36/18

[@AnneshaDas_IITB]

Can you plz solve: Prove that there exists infinitely many pairs (a, b) of integers such that the equation x^2020 = ax + b has among its solutions two distinct real numbers whose product is 1.

[@CauchyIntegralFormula]

This one is surprisingly straightforward (though maybe the answer will be a bit of a letdown). We exhibit an infinite family of such polynomials, indexed by a positive integer k >= 3. For each integer k >= 3, the polynomial P_k(x) = x^2 - kx + 1 has two distinct real roots whose product is 1. If we could choose a and b such that P_k(x) | (x^2020 - ax - b), then the two roots of P_k would be distinct real solutions of x^2020 = ax + b whose product is 1, as desired. But this choice is very easy to make. Consider dividing x^2020 by P_k(x). There will be a quotient, and then a remainder; the remainder will have the form m_k x + n_k for some integers m_k and n_k. If we choose a = m_k and b = n_k, then (x^2020 - ax - b)/P_k(x) has remainder mx + n - (mx + n) = 0, so it divides evenly, which was what we wanted. As such, the collection {(m_k, n_k)| k >= 3} is a family of pairs of integers satisfying the property. We have not demonstrated that this family is infinite (it's possible a priori that multiple choices of k give the same pair and we only have finitely many distinct pairs), but since x^2020 - ax - b has at most 2020 distinct roots and since no two different P_k(x) have a root in common, each ordered pair in our collection can come from at most 1010 different values of k, so since we have infinitely many values of k, we also have infinitely many ordered pairs.

[@tianyizhou775]

@@CauchyIntegralFormula Could you please explain why the remainder of x^2020 / P_k(x) will be like m_k x + n_k where both m_k and n_k are integers? I understand why the form will be like this but cannot understand why the coefficients will be both integers. Is this related to properties of \mathbb{Z}[x]?

[@CauchyIntegralFormula]

@@tianyizhou775 Since P_k(x) has leading coefficient 1, the division algorithm will leave a polynomial with integer coefficients after each step of the division

[@tianyizhou775]

@@CauchyIntegralFormula Thank you! It is clear now.

[@arvindsrinivasan424]

Gotta love faulhaber polynomials

[@saranyadas5522]

Really loved it sir,you are amazing

[@exatizandoaulas7856]

This was a problem 5 of Junior Brazilian Math Olympiad with n = 2005.

[@dnre123]

Thank you so much for explaining how mod and negative numbers work! I have gone through all my life not understanding - no one told me!

[@udic01]

I have discovered that when m is odd (and >=3 ) then the sum is divisible by [n*(n+1)/2]^2 (which means it is divisible by the left upper sum on the board) And when m is even, it is divisible by n*(n+1)*(2n+1)/6

[@calebarulandu3068]

Great video as always! (really nice property too)

[@arimermelstein9167]

This is a generalization of the Ralbag’s theorem! I love it!

[@xCorvus7x]

14:06 Why only if m is odd? Isn't 2*(b+1)^m either way equal to 2*(b+1)*(b+1)^(m-1) which is a multiple of 2*(b+1) ?

[@SatanicNerfd]

Probably to avoid anyone mentioning 0 is even, for which it wouldn't be true

[@josebeleno1213]

I think that you don't have to do cases to prove that sum is congruent to zero mod a+1 (when you take n=2a+1). Since a+1+k ≅ -(a+1-k) mod (a+1) you can cancel all the terms

[@davidbrisbane7206]

We can use the modulo method in this video to prove that 1 + 2 + 3 + ... + n = ½n(n + 1). We use the modulo method to prove that if S = 1 + 2 + 3 + ... + n, then: (1) S is divisible by n/2 & (n + 1) when n is even, and (2) S is divisible by n & (n + 1)/2 when n is odd. We can also show that: (3) When n is even, then gcd(n/2, n + 1) = 1. Proof: Suppose d | n/2 & d | (n + 1), where d ≥ 1 is an integer and a common division. ⇒ d | 2[n/2] & d | (n + 1), ⇒ d | n & d | (n + 1) ⇒ d | [(n + 1) - n] ⇒ d | 1 ⇒ gcd(n/2, n + 1) = 1. (4) When n is odd, then gcd(n, (n + 1)/2) = 1. Proof: Suppose d | n & d | (n + 1)/2, where d ≥ 1 is an integer and a common division. ⇒ d | n & d | 2[(n + 1)/2] ⇒ d | n & d | (n + 1) ⇒ d | [(n + 1) - n] ⇒ d | 1 ⇒ gcd(n, (n + 1)/2) = 1. This being the case, we can conclude that ½n(n + 1) divides 1 + 2 + 3 + ... + n. Now ½n(n + 1) divides S ⇒ ½n(n + 1)k = S, where k ∈ ℕ. Now consider n(n + 1) n(n + 1) = n(n) + n = n(1 + 1 + 1 + ... + 1) [1 "n" times] + n = n + n + n + n + ... + n [n "n" times] + n > 1 + 2 + 3 + 4 + .. + n = S Hence n(n + 1) > S. Now ½n(n + 1)k = S, where k ∈ ℕ and S < n(n + 1) ⇒ ½n(n + 1)k < n(n + 1) ⇒ k/2 < 1 ⇒ k < 2 ⇒ k = 1, as k ∈ ℕ Hence when k = 1, then ½n(n + 1)k = ½n(n + 1)*1 = ½n(n + 1) = S. I.e. 1 + 2 + 3 + ... + n = ½n(n + 1).

[@marienbad2]

This guys maths is so far beyond me but I love watching the channel! Maybe I should study it, but at my age I don't think my brain could handle maths any more lol.

[@HideyukiWatanabe]

10:56 2(1^m + 2^m + ... + a^m) = (1^m + a^m) + (2^m + (a-1)^m) + ... + (a^m+1^m) = (1^m-1^m) + (2^m -2^m) + .... + (a^m - a^m) = 0 (mod a+1); We need no subcases.

[@buxeessingh2571]

Now, this is one of *my* favourite equations from elementary mathematics. :-)

[@Blabla0124]

Can't you just use induction at 10:45?

[@souverain1er]

cool videos. Can you please recommend an elementary text to learn number theory? Elementary in a lay sense, for amateur math learners.

[@vladkojancar4007]

if i wanted to use this in olympiad, without writing proof on paper, what literature or name or fact can i refer to ?

[@rbnn]

It feels like there must be a shorter way to prove this, maybe using some more advanced tools. Maybe traces of powers of a triangular matrix of 1s?

[@Elouard]

What about m? Should be odd to cancel out the (-1)to m with the first 1 to m ? At 8:29

[@shapovalov00]

It's not odd to cancel them out -- and that's exactly because m is odd! For example if odd m=3, then (-1)^3 = -1 which is exact opposite of 1^3. The same trick wouldn't work though if m was even: for example if even m=2 then (-1)^2 = 1^2 = 1 wouldn't be possible to cancel out the same way.

[@Elouard]

@@shapovalov00 I totally agree. That's my remark to Michael because he didn't assume in the begining that m is odd !

[@jussari7960]

@@Elouard It was part of the original goal though

[@enomisgian]

interesting. one curiosity, for any given m, does exist a (m-1 degree) polynomial in n that is equal to the ratio of the two?

[@VerSalieri]

what happens when m is even? as a side note, it's been a while since I complimented your work and content... so great job, and keep it my friend. Also... bring the flips back!!

[@HAL-oj4jb]

When you have (-a)^m and the like for an even number m it is the same as a^m and no longer cancels out, so the sum is not a multiple of (2a + 1) and the proof fails at the first step

[@VerSalieri]

@@HAL-oj4jb yeah saw that... by meant what happens... i meant is it a multiple of something else (well known.. in terms of n)?

[@petersievert6830]

His proof does not work anymore, bec then the terms c^m and (-c)^m do not cancel out. So I would assume, that you can find an example that contradicts the statement. And in fact n=m=2 already has 1² + 2² = 5 being not a multiple of 1 + 2 = 3, while with n=2 and m=3 , then 1³ + 2³ = 9 is a multiple of 1+2 again.

[@shapovalov00]

@@petersievert6830 I think you meant 1³ + 2³ = 9 is a multiple of (1+2) again. Good examples though!

[@petersievert6830]

@@shapovalov00 Thank you, I corrected that.

[@polish3717]

thanks to your videos i'm slowly learning how to solve such problems. thanks!

[@shanmukeshr1696]

Woah this was what I was trying to solve for around 30 mins I got something using binomial but didn't fully get

[@jonathasdavid9902]

I have a good problem similar to this, if someone can give me a solution to this problem please. Find all integer n such that (n(n-1)+2)/2 divides 1^7 + 2^7 +....+ n^7

[@zouhairees-sqally3830]

I'm 15 and i haven't studied the modular arithmetic is that normal or I'm too late ? Thanks in advance

[@adambascal]

Modular arithemetic isn't really taught much in schools, but it's something you can pick up pretty easily and is used a lot in maths competitions

[@luccaassis2148]

@@adambascal Agree

[@paolopiccione7470]

Thanks for the nice video Michael. I think there is a minor point that is missing from your proof. You claim that in order to show that 1^m+2^m+...+(2a+1)^m is a multiple of the product (a+1)(2a+1) it suffices to show that it is a multiple of both (a+1) and (2a+1). This is only true because (a+1) and (2a+1) are relatively prime, and this fact should be proven. Note that, in general, if some natural number x is a multiple of y and a multiple of z, this does not imply that x is a multiple of the product y.z. Now, showing that (a+1) and (2a+1) are relatively prime is easy. If some natural number x divides both (a+1) and (2a+1), then it also divides a. This implies x=1, because x divides a and (a+1).

[@Notthatkindofdr]

He mentions this (including the easy proof that they are relatively prime) at 15:03 to 15:12. But it looks like he inserted that segment into the video in post-production, so I wonder what he had in that section before!

[@paolopiccione7470]

@@Notthatkindofdr Thanks Wayne. I have the impression that this was added later. Anyhow, now the proof is nice and complete.

[@MarkusDarkess]

1^4 +2^4+3^4=98 doesn't work 1+16+81 The reason it looks like because 1 is never changing no matter the power difference. And odds work better then evens. 98/7=14 98/2=49 That's about all I can figure out

[@titassamanta6885]

This problem was given in a soviet olympiad

[@jrkirby93]

I still wanna know what the result is when you actually DO the division. It's pretty easy to figure out the result of the division when m=3 per your example at the beginning. But I wanna know what happens when you actually divide those two sums (and simplify) that you've just proven can be divided evenly. Alas, I'm not sure I have the mathematical chops to figure this one out. I'll give it a good hearty try though.

[@maosatela]

no you can't it's notoriously difficult because you get Bernoulli number s if you want to know more mathologer had a nice video about this called ''Power sum MASTER CLASS: How to sum quadrillions of powers ... by hand! (Euler-Maclaurin formula) '' edit KZbin just recommended me a video on this topic by Norman Wildberger called ''Faulhaber's Formula and Bernoulli Numbers | Algebraic Calculus One | Wild Egg '' this might be even clearer

[@GeorgeFoot]

Nice, I was convinced you were going to prove by induction, but this was more direct. I think it's worth proving that (a+1) and (2a+1) are relatively prime, I don't think we should just claim it.

[@project.eutopia]

I think that is worthwhile too. The argument hinges on showing that both being divisors means that the product is a divisor, which is only true if they are relatively prime.

[@Qsdd0]

Using the Euclidean algorithm should be sufficient.

[@Felissan]

It's just a simple use of Bezout's theorem, as 2(a+1) - (2a+1) = 1.

[@shapovalov00]

Yeah, but I kinda saw it as a homework. Let a+1=m*x and 2a+1=n*x, where x is the common factor. Then 2a+1=2*(a+1)-1, or n*x=2m*x-1, or (2m-n)*x=1. The only solution in natural numbers is when both 2m-n=1 and x=1 QED

[@user-A168]

Good

[@nathanisbored]

you said its a multiple of (1+2+3+...+n), but its really a power of (1+2+3+...+n) right?

[@JalebJay]

Cubes is a special case, there's a fomula for 5th powers out there and it gets very messy.

[@nathanisbored]

@@JalebJay another question is, at 12:04 he cancels the positives and negatives, without pulling out the negative sign first, and im not sure how that works... i think to pull out the minus sign, you need b to be odd, which isn't guaranteed here

[@nathanisbored]

oh nevermind, you only need m to be odd. sorry i havent woken up yet

[@keshavb3128]

Hello Michael, your videos are amazing! Can you do videos on the AMC8 and MATHCOUNTS?

[@mad4hat]

i think your videos will get millions of views in future keep it up👍

[@michelsantana2642]

Nice content. I've missed the "where m is an odd number" in the thumbnail. Peace!

[@blueblackpenn6368]

Determine the no. Of real solutions a of the equation floor a/2+floor a/3+floor a/5=a

[@MelonMediaMedia]

a=30q+r? where 0

[@luccaassis2148]

@@MelonMediaMedia But it says that a is real :( so euclidean division doesn't work here

[@MelonMediaMedia]

@@luccaassis2148 oh rip okie

[@MelonMediaMedia]

@@luccaassis2148 but isn't LHS an integer, so RHS must be an integer, so a is an integer?

[@luccaassis2148]

@@MelonMediaMedia Oh that's true. Makes sense.

[@mihaipuiu6231]

1. Interesting and very nice demonstration. 2. Sometimes the blackboard is not very well clean,...and for me is a little bit hard to watch him. 3. M.Penn is a good speaker .

[@Manluigi]

Vert cool

[@sajjad213]

can you please talk about singular solutions of DE and why a singular solution is an envelope of family of curves? Thank you

[@prithujsarkar2010]

Awesome , plz bring some AIME problems too

[@xizar0rg]

For the identity to be true, isn't it sufficient for 1^m+...+n^m to be a multiple of *either* (2a+1) or (2a+2) (for the odd case)? (similarly for the even case with (a) or (2a+1)) That it's a multiple of both just seems like a nice fact to fall out of this.

[@Lucashallal]

No, 6 is a multiple of 3 but not a multiple of 3x5

[@fasihullisan3066]

you is my best teacher.

[@vinc17fr]

Shorter: S = 1^m + 2^m + 3^m + ... + n^m. For u = 0 or 1: (n+u−k)^m ≡ (−k)^m ≡ −k^m (mod n+u) since m is odd. By grouping k^m and (n+u−k)^m for m from 1 to ⌊n+u⌋/2, one has: if n+u is odd, then S ≡ 0 (mod n+u); if n+u is even, then S ≡ ((n+u)/2)^m (mod n+u), so that S ≡ 0 (mod (n+u)/2). Let {u,v} = {0,1} such that n+v is even. Since n(n+1)/2 = (n+u)((n+v)/2) and gcd(n+u,(n+v)/2) = 1, one has S ≡ 0 (mod n(n+1)/2).

[@guruone]

A challenge for ya, Mikey..... Find a general solution for the division of two series (not using long division) .......... hehe........ Cheers from Down Unda

[@quirtt]

trivial but noice :)