i thought this was blindingly obvious until i realised the reason i thought that is because i had already picked 10 as my starting number so the proof was immediately intuitive for a brief moment, i thought i was a genius

I raised to the power of 1. Made a load of sense.

"Wait it's all 9s" "Always has been"

Love the second proof! In the vein of the first proof, there's the identity b^n - a^n = (b-a)*(b^n-1 + b^n-2 * a + .... + b * a^n-2 + a^n-1) that makes the divisibility quite clear.

I thought of b=1

Nice proof by induction I made: b^1 - 1 is obviously divisible by b - 1, as they are the same If b^n - 1 is divisible by b - 1, then so is b^(n+1) - 1, as b^(n+1) - 1 = b^(n+1) - b + b - 1 = b(b^n - 1) + (b - 1) First term divides by (b - 1), as b^n - 1 divides by (b - 1) Second term (b - 1) divides by (b - 1) Induction: True of first case, and second, and third, and so on...

MATT! I think there's a lovely geometric proof as well! Visualize 5^2 as a 5x5 grid of squares. Remove the southeast corner. You now have a row of 4 (n-1) to the west of the missing square. Remove it. You also have a column of 4 to the north of the missing square. Remove it. You're left with a 4x4 grid, which is just more rows of 4. This works for any n^2. It extrapolates to higher dimensions as well. If you make a 5x5x5 cube, then take out one corner, you can remove one entire face using the method above. Then, remove the strip of 4 that's aligned with the missing corner on the Z-axis -- just like you did with the "row" and "column" in the x^2 example -- which leaves you with a bunch of identical slices, each of which is identical to the 2-dimensional example after removing one corner piece.

0:05 b = 1 0:30 n = 0 0:41 oh... So it turns out you can divide by 0 after all

The two proofs are actually very closely related! In the first proof, you basically factor b^n - 1 into (b - 1) * (b^(n-1) + b^(n-2) + b^(n-3) + ... + b^0). And in the second proof, the reason aaa...a in base b is divisible by a is because aaa...a (base b) = a * b^(n-1) + a * b^(n-2) + a * b^(n-3) + ... + a * b^0 = a * (b^(n-1) + b^(n-2) + b^(n-3) + ... + b^0). Since a = b - 1, they are the same equation :)

I like how "complicating" the initial problem leads to a much more intuitive understanding of the proof. (And the dig at Amazon)

My first intuition when I heard "divisible by something" was to consider the whole situation modulo this something. There it also becomes quickly apparent, because modulo (b-1) we have: b ≡ 1 (mod b-1) and therefore b^n ≡ 1^n = 1 (mod b-1), hence b^n - 1 ≡ 0 (mod b-1), but the last equation is exactly synonymous to "(b^n - 1) is divisible by (b - 1)". Of course this than relates to the fact, that 1 is a zero of the polynomial (x^n - 1), because the calculation above is just evaluating this polynomial in the according ring of residual integers (Z/(b-1)Z).

I REALLY LOVE WHEN WE SWITCH NUMBER BASES AND IT BECOMES OBVIOUS IT IS MY FAVORITE GENRE OF MATH

The "base b" insight is wonderful, but it really doesn't answer how you would decide to do that. For me it's much more natural to switch to mod b-1, where b^n - 1 = 1^n - 1 = 0 mod b-1, since when you have to prove that x is divisible by y it's often useful to switch to proving that x = 0 mod y.

i love the orange circle in the top right, brings the whole thing together

If you use b-1=a you can rewrite the problem as (a+1)^n - 1 being divisible by a, and if you were to expand it you would get a lot of terms with some power of a, and then +1-1, which just cancels

I paused the video immediately after you said you picked 440, thought for a moment, decided on 17. I unpaused the video and the next sentence you said was someone else picked 17. I was reminded of Veritasium’s recent video on the human inability to create randomness.

To be honest, the first thing I thought of were geometric sums ( [b^n-1]/[b-1] = 1 + b + b² + ... + b^[n-1] ). But that's an admittedly more convoluted way of proving that [b^n-1]/[b-1] is an integer than proving that 1 is a root of x^n-1

"I don't think anybody's ever used base 440 before" Hmm... 440 Hz is what A440 (Stuttgart pitch) tuning is based on. I suppose it's more of a unit conversion than base though. I'm sure someone's played 440 Hz on a bass before though, and maybe that would be bass 440. A0 = 27.5 Hz A1 = 55 Hz A2 = 110 Hz A3 = 220 Hz *A4 = 440 Hz* A5 = 880 Hz A6 = 1760 Hz A7 = 3520 Hz A8 = 7040 Hz

instructions unclear, I picked "b" to be the big famous constant e and it didn't work :(

I thought of the cubes from grade school. Your n-hypercube can be decomposed into a bunch of sticks and slabs and cubes and hypercubes that have (b-1) side lengths.... and.... 1, but you have conveniently subtracted that out.

My b was 2. Yep, i was underwhelmed

I tried proving this myself without watching the rest of the video, and I made something like: 1. Base case: for n=1, b^n-1 is clearly divisible by b-1 (because they are equal) 2. Inductive case: Let's say b^n-1 is some x(b-1) + 1. Then: b^(n+1)-1 = b (b^n) - 1 = b(x(b-1)+1)-1 = bx(b-1) + b - 1 = bx(b-1) + 1(b-1) = (bx+1)(b-1) which is also divisible by b-1. QED

The naughty orange dot in the top right corner bugged me

I Love the shade thrown at Amazon!

The base change is sooo poggers

My mind was blown and I immediately understood when you said to use the base of the number, wonderful proof. I love the bigger videos with locations and large production values, but I love these simple "Here's a cool math(s) thing!" videos too, and I'm glad you're doing both.

I am also very stunned by the implications this could have on quickly determining if a number is divisible by another specific number. Powerful stuff

Not only is the second proof easy to follow, it also immediately tells you what the other factor is and why (1, b+1, b^2+b+1, etc, depending on n)

I think a pretty intuitive way of thinking about it is geometrically, If you make a b X b square (or cube or whatever) it can be seen to be a load of sets of (b - 1). In the case of a square b rows of b - 1 and one extra column of b - 1

Very nice! I love these kinds of insights. I'll never forget this little gem now.

I like it when Matt does a video on a topic I fully understand, it makes me feel much smarter than I actually am.

Pick any number but irrationals don’t work. He really Mat Parkered those instructions.

I like big exponents and I can not lie.

I asked myself this exact questions a few years ago during a calm shift, and came up with 3 solutions, two of them being those you present (but I cannot remember the third)! My favourite one was using base b. Love those kind of reflections, great video

That is GENIOUS! The base transformation is just so simple, I love it so much! I'm going to show everyone I know

I picked b=1. I feel like "a number" was not specific enough. Or is 0 divisible by 0? 🤔

I was obsessed with the Mersenne series in middle school. I discovered early that 2^(2n)-1 was divisible by 2^2-1 and 2^(3n)-1 was divisible by 2^3-1. That’s how i checked my work.

Matt releasing the video I didn't think I needed today. Thanks, helps a lot!

There is also a simple way to prove this by induction, for increasing n. (It's going to sound complicated in text but with pictures it's obvious) For n = 2, imagine the it as a square grid, now take one off the corner, now you have a rectangle of b*(b-1) plus a line of b-1, which are both divisible by b-1. For n = 3, imagine a cube, taking one off the corner leaves you with the same n = 2 square case on one face, plus a block of (b^2)*(b-1), this block is also divisible by b-1. This can be extended to arbitrary n, where the 'block' will always be (b^(n-1))*(b-1), divisible by b-1.

0:09 WTF I ALSO THOUGHT OF 17, why do people tend to pick prime numbers?!

If I remember correctly, putting maths in an unusual context because it tells you something about how the formula was derived, was exactly the sort of thing you were arguing _against_ in your tau vs pi smackdown with Steve Mould lol. I'd love to see a tau vs pi rematch with the two of you

the revelatory feeling of understanding I got out of this was so incredibly unique. Exactly the feeling that I always am seeking when working in math or programming.

Induction: b-1 divides (b^1) -1 = b-1 Let's assume b-1 divides (b^n)-1 = k b^(n+1) = b^n * b = (k+1) b = kb + b We need to prove b-1 divides b^(n+1)-1 = kb + b -1 And since b-1 divides k, b-1 divides kb, and b-1 divides b-1, we proved b-1 divides kb+ b+1 which equals to b^(n+1)-1

i picked b=900.1 it wasnt an integer, but it still worked

This my friends, is a classic old school standup maths. Well done, Matt!

love the jab at amazon right at the end!

This video is so cool. Need more of such short fun videos.

I feel so pleased I worked this out while the video was running! I paused the video as requested, and tried this with b=10, saw lots of 99999s and had to leap from the bathtub and run down the street shouting "BASES! BASES! BASES!!"

In the introductory logic course at my university, an exercise in the book is to prove 6^n-1 is divisible by 5, by induction on n. I discussed it with some other students and we realized it works for any base

Even better, (x^n - y^n) is divisible by x-y

I love how intuitive the 2nd proof is (as long as you understand bases)

Matt Parker: "Now, I don't think anyone's ever used base 440 before" Domotro: *exists*

I know everyone hates polynomial long division, but it's incredibly simple if you use that, because after the first round you get b^(n-1)-1, then b^(n-2)-1, and as you go on, you'll eventually get down to b^1-1,which is obviously divisible by b-1.

Both of these proofs are so infuriatingly simple, I love it.

Brilliant video - the first proof came to mind immediately but the second one blew me away! Just pre-ordered the book because trig is my favorite, and also because the UK cover is much better than the US cover. (That being said I do hope there's significant respect paid to our friend the unit circle!)

I had to pause at 3:47 to process just how patently obvious the result just became. That's so good.

I learned this in my number theory class, do I remember the proof without watching the video? No!

That's a great technique. Maybe it'll come handy for other stuff as well. Loving it.

My approach was to rewrite b^n as ((b-1)+1)^n and look at binomial expansion using Pascal's Triangle. Treat (b-1) and 1 as the two terms in a binomial. b^n = (b-1)^n*1^0 + ....[several terms with some power of (b-1) in them]....+(b-1)^0*1^n So the +1 at the end is the only term in the binomial expansion without (b-1) as a factor. Subtracting 1 leaves only numbers divisible by (b-1). From here you can generalize it to (b^n-a^n)/(b-a) is a whole number. I love Pascal's Triangle for approaching problems where you want a generalization for any power. It can be used to prove the power rule for derivatives (for positive powers at least). The derivative of x^n can be found in the second number in the nth row of Pascal's Triangle if you do a binomial expansion of the numerator of lim as h->-0 of [f(x+h)-f(x)]/h for f(x)=x^n and then cancel every remaining h.

I am so glad I stayed through this video. I was like yeah yeah yeah roots and stuff, then BAM! That was MAGNIFICENT❤

As others have pointed out, there are several other ways to prove this. One that I thought of is using modular arithmetic. If a=b-1, then b=a+1, which means that b is congruent to 1(mod a), and because you can multiply remainders this means that b^n is congruent to 1^n (mod a), or in other words b^n is 1 more than a multiple of a.

Woah, that's such a cool proof. So simple and approachable.

YEEEESSSS!!! Did you overhear my meeting with my academic supervisor a few months ago? This is so validating! I told him it’s so easy to see divisibility when you write the Mersenne number (2^mn)-1 in binary and then just look at the number! You can see so much by just looking at it! (The string of mn 1s is divisible by a string of n 1s, so the original is divisible by the smaller Mersenne number 2^n-1, and this is why a Mersenne number with a composite power can never be prime.) His reaction was that the difference of powers formula is an easier proof, and my immediate reaction was just 👀 Big lesson for me: translate concepts into what’s most familiar to my audience! And, in the academic community, that means translating my visuals into familiar formulas!

My thinking: You have a number b. This is of course 1 more than a multiple of b-1 (specifically 1 more than b-1 itself), which I will call A. If you multiply a number that is 1 more than a multiple of A by m, you get a number that is m more than a multiple of A, which if m is greater than A is also m mod A greater than a multiple of A. So if you multiply b by itself, you get a number b bigger than a multiple of A, so the resulting number must be b mod b-1 = 1 more than a multiple of A. If you multiple this by b you can go through the same logic as in the last step, and so on. So b^n is always 1 more than a multiple of b-1, or b^n-1 is divisible by b-1.

Two more proofs: 1. Work in mod (b-1). b is congruent to 1, so b^n is congruent to 1^n, which is also 1. Since b^n is congruent to 1, b^n - 1 is congruent to 0, so it's divisible by b-1. 2. By induction on n. If n = 0, then b^0 - 1 = 0, which is divisibly by absolutely anything. But if b^(n-1) - 1 is divisible by b-1, then there's some a where b^(n-1) - 1 = (b-1) a, so b^n - 1 = (b - 1) b^(n-1) + (b^(n-1) - 1) = (b-1) b^(n-1) + (b-1) a = (b - 1) (b^(n-1) + a).

Great work Jess! I’ve just run my first marathon and looking for inspiration for what to do next. I think you’ve inspired me to have another go at running a sub 45 minute 10k. I was 12 seconds short at last year’s Run Norwich… so have my goal for this September! 🤞

Oh wow, that second proof is incredible

b-1=a b^n-1=(a+1)^n-1 All terms in the polynomial have a as a factor therefore the number is divisible by a. I usually think of these problems using convenient bases but I found my method simpler

By induction: 1. for n=1 the equasion holds true as b-1=0(mod b-1). 2.We need to show that If b^n -1 = 0 (mod b-1) then b^(n+1)=0 (mod b-1) Here is the proof: b^n-1=0(mod b-1)b^(n+1)-b=0(mod b-1)b^(n+1)-1=0(mod b-1)

Very beautifull proof, easy to do and obvious proof, just what i like the most. But not so easy to think on it, without any external help.

what a neat way to look at the problem!

I thought about it before you started explaining and came up with this: a = b-1 b^n = a*b^(n-1) + b^(n-1) b^5 = a*b^4 + b^4 b^4 = a*b^3 + b^3 b^3 = a*b^2 + b^2 b^2 = a*b + b b^1 = a*b^0 + b^0 = 1 We see that the rest we get when dividing b^n with b-1 is ultimately 1. Therefore removing 1 from the original b^n will give us a number divisible by b-1. Hope this makes sense!

another interseting way you can prove it (It might be the same method and I just got confused) is to start with a^0+a^1+a^2+...+a^b=a^0+a^1+a^2+...+a^b then change the start to a 1 1+a^1+a^2+...+a^b=a^0+a^1+a^2+...+a^b then move it over and factorise (a^0+a^1+a^2+...+a^(b-1))a=a^0+a^1+a^2+...+a^b-1 (a^0+a^1+a^2+...+a^(b-1))a-1(a^0+a^1+a^2+...+a^(b-1))=a^b-1 (a^0+a^1+a^2+...+a^(b-1))(a-1)=a^b-1 a^0+a^1+a^2+...+a^(b-1)=(a^b-1)/(a-1) you get the original equation the cool thing about doing it this way is you can also do if you start with a^(0c)+a^c+a^(2c)+...+a^(bc)=a^(0c)+a^(c)+a^(2c)+...+a^(bc) and do the same process 1+a^c+a^(2c)+...+a^(bc)=a^(0c)+a^c+a^(2c)+...+a^(bc) (a^(0c)+a^c+a^(2c)+...+a^(bc-c))a^c=a^(0c)+a^c+a^(2c)+...+a^(bc)-1 (a^(0c)+a^c+a^(2c)+...+a^(bc-c))a^c-(a^(0c)+a^c+a^(2c)+...+abc-c)=a^(bc)-1 (a^(0c)+a^(c)+a^(2c)+...+a^(bc-c))(a^(c)-1)=a^(bc)-1 a^(0c)+a^(c)+a^(2c)+...+a^(bc-c)=(a^(bc)-1)/(a^(c)-1)

I love this. As soon as I heard base B, I knew where it was all going. Lovely

Love a short simple video like this that still contains a nice "aha" moment!

Surely if you consider b^(n-1) + b^(n-2) + ... + b^2 + b + 1, and multiply it by (b-1), you get (b^n + b^(n-1) + ... + b^3 + b^2 + b) - (b^(n-1) + b^(n-2) + ... + b^2 + b + 1). It should be pretty clear that the expression collapses to b^n - 1 since all the other terms are both added and subtracted. So (b-1)(b^(n-1) + b^(n-2) + ... + b^2 + b + 1) = b^n - 1. A rather trivial result, IMHO.

3:45 s'all about dat base 'bout dat base no treble

This is easy to visualize. Create a square, of b^2 dots, remove one dot, and you can reform that shape into a rectangle with one side of b - 1 dots. This works in all higher dimensions.

Wow I love that! The initial proof confirms to me that it works, but the second proof shows me how it works!

The n=2 & n=3 cases have a very satisfying visual proof for this.

Love it... That is beyond elegant

My favorite way is still rephrasing with a substitution a=b-1: b^n - 1 = 0 (mod b-1) (a+1)^n - 1 = 0 (mod a) At this point you either know modular arithmetics, replace by 1^n - 1 = 0 (mod a) - or you don't, and you expand that power into a^n + whatever a^(n-1) + ... + whatever a + 1 where all the whatevers are binomial coefficients, and you are done too.

The most standard way to test divisibility by m it to compute modulo m. And indeed working modulo b-1 we just get 1^n-1=0, which is even more trivial than your base b approach. Also you might recall the formula for the geometric series 1+b+b^2+...+b^{n-1} = (b^n-1)/(b-1) which implies this divisibility.

I went ahead and tried it myself geometrically before watching this video. Obviously I can't imagine more than 3 dimensions but I can take a length of boxes and make a square or cube out of them. Then I reframe b as a=b-1 and then the question becomes "Why does squaring or cubing a+1 then subtracting 1 leave a mass that is divisible by a?" That way, I can see the original square from a and then the extra bits at the ends from the a+1 and of course there is always an extra box in a corner that doesn't fit in the other sections. And with that understanding, I can easily prove this for higher dimensions too.

OK, I was surprised by the title, but the proof! That's very cool! I don't know any other example of using every number as a base for solving a problem, so that makes it much cooler. Might want to try giving this as an exercise in understanding the bases.

Awesome. 😃 Sharing it at once. 👍

I literally tried this problem yesterday from the Stanford Maths Problem book, and the next day BANG a video from the man himself.

My favorite proof that the (positive) rational numbers are countable also involves a change of base: Clearly the natural numbers map 1-1 to subset of the positive rationals (that subset being just themselves!), so we're done if we can prove that the rationals also map 1-1 to a subset of the natural numbers. Obtain that map as follows: By definition, every rational number can be written uniquely as p/q in lowest terms, with p and q being integers. So write the number that way on paper. Then re-imagine that string of symbols as a number in base 11, with the "slash" being the symbol for "10". Then that string represents a unique natural number to map the rational number to, which is exactly what we needed.

Love this!

Maybe there is another mathematics lesson to be had here. We used the fact that in any base b, there is a unique representation of any integer as a linear combination of powers of the base where the scalars can only be anything from 0 to b - 1. (Why aaaaaaa? What about 123a125a9 or any other notation? You can't just assume b^n - 1 can be written as aaaaaaa.) We do take it for granted all the time in base ten, but now we see why we may want to look at the fundamentals and be grounded in rigor. When base systems were first devised, they didn't know every integer had a unique representation until they proved it.

love the switch to base b. Elegant! Also, please tell us about the cool shirt you're wearing. There's gotta be some maths going on there, yes?

There's a geometric proof too. It's hard to describe in words because it's geometric, but I'll give it a go. If it sounds complex in the general case, picture it with n=3. Let's start by defining a "nibbled hypercube". Start with an n-dimensional hyper-cube with side length b. Take a little bite out of one corner - a hyper-cube with side length 1. The volume of this is just the volume of the original cube, minus the volume of the nibble, i.e. b^n - 1. Now, on a face which touches the nibbled bit, shave off a width 1 slice of the hyper-cube. Since it has width 1, the volume of this slice is the same as the (n-1)-dimensional volume of the "face" of the slice. And that face is an (n-1) dimensional nibbled hypercube. Its volume is b^(n-1) - 1, and by our inductive hypothesis, that is divisible by b-1. Having shaved a width-1 slice off our original nibbled cube, what we're left with is a hyper-rectangle. The side perpendicular to the slice has length b-1, so the volume of this is also divisible by b-1. Since we've shown that an n-dimensional nibbled hypercube can be broken into a two shapes whose volumes are both divisible by 1, we know that the it's total volume, i.e. b^n 1, is divisible by n-1.

I literally figured this out very recently when trying to fall asleep at night. Figuring out things like this is my version of counting sheep.

That second method was just beautiful. Beautiful. Wow.

wow, really cool proof! my first thought was that obviously it comes from how polynomials work but then the "base b" proof was so much nicer and made more intuitive sense

I thought of the partial sums of the geometric series: 1 + b + b^2 + ... + b^(n-1) = (b^n - 1) / (b - 1)

Not surprised by the fact, for a while I've been aware that b^n-1 expands to (b-1)(a0b^n-1 + a1b^n-2+...) where a0, a1 etc are numbers in the pascal triangle at nth row (or maybe n-1th, I'm a programmer, off by one, who cares) I did not see the "think of it in base b" solution though. That's really a simple yet beautiful piece of maths.

As a speedcuber and having solved 4d and 5d cubes, i very quickly understood it geometrically. Very closely related to the second proof. Helped that i picked 6 which is small and easy to visualise.

Excellent!

Here's a quick proof by induction: Assume b^n-1 is divisible by b-1, i.e. b^n-1 = x(b-1) for some integer x. Then b^(n+1)-1 = b ⋅ b^n - 1 = b ⋅ b^n - b + b - 1 = b(b^n-1) + (b-1) = bx(b-1) + (b-1) = (bx+1)(b-1), i.e. it's also divisible by b-1.