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
Same, I saw the thumbnail and so knew I'd be raising it to an exponent, and so picked a number I knew would be easy to do that to without getting out a calculator. And yeah definitely gave away the trick on the second proof XD
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...
@@broskey4041 You mean *in* the set of natural numbers. And that's really a matter of conventions : if you use n as a value name for something else than a (natural) integer without precisions, you're an heretical monster in the mathematical community. Similarly, because we're discussing divisibility without more details, you can infer that b should be an integer too. Of course if you're writing a math paper or in your exam, you should **really** details all of this!
@@chaddaifouche536 thank you for the correction and clarification. I didn't even know that divisibility implies working with integers that's kinda cool
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.
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.
@@ShongoStick It's easier to understand (at least if you can write it out properly instead of trying to force it into a TH-cam comment), if you look at like this: first set a=1, since we don't need the more general version, so we have (b-1)(b^n-1 + b^n-2 + ... b + 1) If you expand that out, you get (b^n + b^n-1 + ... b^2 + b) - (b^n-1 + b^n-2 + ... + b + 1). If you compare the positive terms with the ones being subtracted off, you'll notice that all of them cancel out except for the first and last, b^n-1.
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 :)
@samueldeandrade8535 That's a stupid argument. According to your analogy, videos that explain a topic at a fundamental level should simply NOT exist. Afterall, it's obvious. Plus, it's certainly not like there are people out there that don't understand the subject you're so profoundly good at! If you'd already inferred what the comment was suggesting, you could've simply ignored it and moved on. There was simply no need to leave a discrediting reply. Nothing like a good old TH-cam comment section argument.
@@Mitchpott0/0 is considered undefined. Imagine a function (or graph it in Desmos) where it's some number divided by x, like y=1/x. If you start at x=1 and move towards x=0, you're dividing by a smaller number which means you're actually multiplying by a larger number, i.e. 1÷½=1×2. So as x approaches 0 from the positive side, the number races off to infinity. Now what happens if you start from x=-1? Well, the exact same thing, but the number is now negative. As x gets infinitely close to 0, the 'limit' (basically what we've just done) is different depending on how you look at it. So the limit is said to not exist. Lastly, imagine the age-old 0.99999... = 1. You might know it works because it's an infinitely long string of O's, but if you try to decide what its limit is (the number it gets infinitely close to), it approaches 1. There are some great proofs here for you to find. But in this respect of limits, we arrive at the conclusion that they are actually equivalent. So, because the limit does not exist, it is impossible to divide by 0. In actual calculus, it is said that if your result is 0/0, you've taken the wrong approach.
Factors aren't defined by division but by multiplication into a product. Given h × k = j, then h and k are factors of j. Likewise, since 3 × 0 = 0, both 3 and 0 are factors of 0. Nothing in there about division.
From the point of view of the definition of divisibility, 0 is actually divisible by 0, since there exists a number (any number in fact) that you can multiply by zero to get zero. The funny thing is, this still doesn't imply you can divide by zero, it's just the one single case where the terms "divisibility" and "division" collide and contradict each other. But for any non-zero number, divisibility for sure implies that you can divide by that number and get a single unambiguous result.
@@nickpro8116 The terms "divisibility" and "division" do not contradict each other. Division is defined as multiplication (one of the defining operation in a ring) by the multiplicative inverse (which exists for any nonzero element in a field). By definition, "division" excludes dividing by zero already.
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).
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
This is how I went about it as well. Let F(b, n) = (b^(n) - 1) / (b - 1). Now evaluate at F(b + 1, n) = ((1 + b)^(n) - 1) / (b). Now expand the binomial and note that C(n ,n) b^0 = 1, which cancels the one in the numerator. Now we have a polynomial expression in terms of b multiplied by 1/b, which we can negate by subtracting one in all of our terms. Now evaluate this expression at b - 1 to show that F(b, n) = (b^(n) - 1) / (b - 1) = sum(k = 0, n - 1, C(n, k) * (b - 1)^(n-k-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
@@BigDBrian Then if you multiply the pitch by the paper size, you get a very strange way to express kinematic viscosity: A4 × A4 = 440 Hz × 1/16 m² = 27.5 m²/s = 275 kilostokes (kSt)
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
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.
The base b approach is natural when one is in school and one hasn't done modular arithmetic yet, but one _has_ encountered things like how to test in base 10 for divisibility by 9.
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
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.
I have changed my strategy for picking random numbers under 100 since I watched that. 30 and 90 are preferred random numbers, now. But, of course, there's the question of how many other people in the world have thought the same. (-:
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.
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.
Yes, this is my favorite proof. You can also mix it with a bit of induction to make it simpler: b^n -1 is the volume of a n-cube with side lenght b, which has a small (n-cube)-shaped hole with side length 1 at one of its corners. Take a slice off of it from the top: you’re left with a n-parallelepid with one side lenght (b-1) and all other sides b, and the extra slice you cut off. You can “flat” this extra slice by looking at it from the front, suppressing the dimension along its side of lenght 1. Then, you’ve got the same shape as you started with, but which lives in 1 dimension lower: a (n-1)-cube with a unit corner missing. Repeat n times and you get all shapes with at least a side lenght of (b-1)
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.
The first thing I did is divide (b^n-1) by (b-1), just like you are taught at school. Since it divides with no remainder, you know it is divisible. Then the obvious thing is just to write down how b^n-1 factorises as two polynomials, one of which is b-1. I quite like the geometric and base approaches as well.
I think 1 has to divide into your "b". I imagine if you picked b = ½, you could say b ^ n - ¼ is divisible by b - ¼. (I picked ¼ because it divides into ½). Therefore it makes sense that b has to be an integer for the video's equation to work. p.s. this could all be wrong, I've not actually checked the maths
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
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.
The second proof implies to me that this can be extended to b^n - k, as long as 1 < k < b. Using base 10, 8888 is obviously divisible by 8, 7777 is divisible by 7, etc.
I decided to look into doing a proof by induction to prove this: The way I did it used two base cases: b^n - 1 | b - 1. When n = 1, this is trivial, and when n = 2, this is covered in the video Moving on to the inductive step: Assume b^k - 1 | b - 1 and also assume b^(k-1) - 1 | b - 1 Prove b^(k+1) - 1 | b - 1 b^(k+1) - 1 = (b^k - 1)(b + 1) - (b^k - b) = (b^k - 1)(b + 1) - b(b^(k-1) - 1) Since (b^k - 1)(b + 1) has a factor of (b^k - 1), that is divisible by b - 1 and b(b^(k-1) - 1) has a factor of b^(k-1) - 1, that is divisible by b - 1 Therefore b^(k+1) - 1 | b - 1 Thus b^n - 1 | b - 1 for all n in N QED
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.
PS I didn't start by thinking in n-dimensions, I'm not a genius! I started in 2-d, then thought about 3-d, and fortunately that was enough to see how the generalisation would work :)
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
Doesn't the extra column have b elements? E.g if b = 4 and we square it: Say these asterisks represent b, so here is a 4x4 grid: * * * * * * * * * * * * * * * * I see b (4) rows of b-1(3) * * * * * * * * * * * * But this remaining extra column you refer to has b, not b-1 elements * * * * I just realised why this makes sense - because we are dividing by (b^n) - 1, so if you subtract this extra one off, then yes it is divisible by (b - 1) * * * But the way you described it was incorrect and confusing for me lol.
@@JavedAlam-ce4mu sorry if I was unclear but yes we ended up at the same solution, if b = 4, you end up with: b rows of b - 1 (4 rows of 3) and one extra column of b - 1 (3) ###| ###|# ###|# ###|#
two other ways of thinking about it that don't require different bases: 1. synthetic division/polynomial division: if we write out our problem as a synthetic division problem it will always be a 1 followed by n 0s followed by -1, then our root is 1. Drop the first 1, multiply add to the next value and on and on until we get to the end (basic synthetic division obviously), because we are never multiplying by anything but the mutliplicative identity or adding anything but the additive identity, when we finally add the -1, we get a remainder of 0, proving that 1 is a root and (b-1) is a factor. 2.if we take the quotient of that synthetic division and think about the process in reverse, we are multiplying some n-degree polynomial with no skipped terms with only coefficients of 1 (e.g. b^7 + b^6 + b^5 + b^4 + b^3 + b^2 + b + 1) by (b-1), which we can re-frame as (b^1 - b^0), then through distribution we get b^1(b^n + b^[n-1] +...+ 1) -1*b^0((b^n + b^[n-1] +...+ 1), then by distributing again and through our exponent rules, every term multiplied by b^1 will have it's degree raised by 1, (b^n + b^[n-1] +...+ 1) -> (b^[n+1] + b^n +...+ b^1) , and every term of the other part will become negative, (b^n + b^[n-1] +...+ 1) -> (-b^n - b^[n-1] -...- 1), those two resultant polynomials' values all obviously cancel out, b^n - b^n = 0 and so on, except for b^[n+1] and -1. Therefore (b-1) must always be a factor of (b^n - 1)
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)
More generally x - y divides x^n - y^n for all nonnegative x, y, n. In fact, this is all just a special case of the (very nice) lemma that a - b divides P(a) - P(b) for ANY integer polynomials P and nonnegative integers a, b.
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.
Actually, irrationals DO work, depending on your definition of divisibility. No matter the number, b^n - 1 can always be factorized as (b^(n-1) + b^(n-2) + ... + b + 1) * (b - 1). If you divide by b-1, you're left with just the b^(n-1) + ... + 1 term, whose representation in base b is always just 111...111. Thus, in base b, the resulting number is always an "integer" even if b itself is irrational.
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
You can just take the term b^n-1 and add and subtract all powers of b from (n-1) down to 1. Then group all additions together and all subtractions together so you'll get b^n+b^(n-1)+b^(n-2)+...+b-b^(n-1)-b^(n-2)-...-1. Next put some braces and pull out a common factor: b(b^(n-1)+b^(n-2)+...+1)-1*(b^(n-1)+b^(n-2)+...+1) Since the terms inside the braces are equal we can pull their factors together: (b-1)*(b^(n-1)+b^(n-2)+...+1) And we can see that it indeed is divisible by (b-1).
Zero is indeed divisible by zero. Since there exists a whole number k such that kx0=0 (this is true for all k, but we can take k=0 as an example, 0x0=0). Generally speaking "a is divisible by b" and "a is a multiple of b" are the same statement. This trips a lot of people up because there's no answer to "zero divided by zero", which sounds like it should mean the same thing, but it doesn't.
@@chemicalbrother5743 unfortunately, the mathematical definition of "a is divisible by b" is in general not the same as "you can divide b by a". this is because the concept of divisibility is very useful even in situations where you don't have a concept of division at all. in general, "a divides b" is defined as "there's some k such that k*a=b", which is obviously satisfied for 0 and 0, because 0*k=0 for all k.
The problem I generally face while studying in the field of STEM is that, there is always that one person with something different that challenges how you see a certain thing. And it's beautiful. This beauty will save the world.
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
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! 🤞
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.
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
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.
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!
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).
i did it by induction. idk how to do it this way formally, but like you can see roughly what i was thinking (haven't learnt it in school yet, it's like 2 years above my grade level) so please tell me if there's some inconsistencies. let n = 1. LHS = b^1 - 1 = (b - 1)(1) = 0(1) mod (b - 1) = 0 mod (b - 1) therefore LHS = RHS for n = 1 assume this is true for any n. => b^k - 1 = 0 mod b - 1. let n = k + 1. LHS = b^(k + 1) - 1 = b(b^k) - 1 = (b^k)(b - 1 + 1) - 1 = (b - 1)(b^k) + b^k - 1 = 0 + 0 mod b - 1 = 0 mod b - 1 = RHS therefore LHS = RHS for n = k + 1 therefore by mathematical induction, LHS = RHS for all n.
About to watch the second proof, but recording my guess about what it is. To illustrate, consider the n=2 case. Imagine a square grid of size b by b. Knock off the bottom corner, and you get two lines of b-1 and a square of b-1. This is clearly divisible by b-1. (b-1)²+2(b-1), which simplifies to the famous (b+1)(b-1). Next to get a sense of what happens for different n, consider the cube for n=3. Knock off a corner and you get 3 squares of b-1 and one cube of b-1. (b-1)³+3(b-1)², which simplifies to (b-1)²(b+2). It's not so easy to visualize the hypercube, but I think this will lead to a proof after finding the right generalization. Essentially, for an n-dimensional hypercube, you can count the number of cubes b^n by starting from the b-1 hypercube of that dimension, adding n-1 hypercubes of dimension n-1 to each face sharing a particular vertex, which is n-1 faces, and adding a 1 by 1 hypercube to that corner.
You want to know if it's divisible?... The most direct way to find out would be to straight-up divide, and see that there's no remainder! The standard long division paper-and-pencil algorithm works (if you abstract cleverly)! Write b-1 to the left of the long division symbol. Write b^n under the 'roof', on the left... then include a few zero terms like +0b^(n-1) +0b^(n-2) ... +0b, then finish up with -1. The most 'significant' part of your answer will be b^(n-1), you'll subtract b^n-b^(n-1) from the numerator, and get b^(n-1) on the next line (with the implicit +0b^(n-2) + ... +b -1). Next significant part of your answer will be b^(n-2), then the numerator left to be processed will be b^(n-2)-1. The pattern continues, yes this is like doing the second step of induction first, and you'll get a point of having b^(n-1) +b^(n-2) ... +b above the line, and b-1 below the line. This is simple: that's +1 to the answer, and no remainder (the base case of the induction). Long division shows you there's no remainder: one divides into the other.
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)
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.
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.
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
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!)
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!
As for the first technique, I once took a seminar on Riemannian Manifolds and in my paper that I had to hand in, I gave an unusual proof for the Fundamental Theorem of Algebra by using holomorphic functions between the 2-spheres interpreted as Riemannian Surfaces. During the discussion I was asked why I added this part to the paper and I said "because we need more obscure proofs for basic mathematics".
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.
That's a pretty neat way to solve it, certainly more intuitive than what I did. I started with b^2 - 1 = (b+1)(b-1) as you mentioned, then looked at what happened as n grows, and how you could factor that number in terms of b-1: b^3 - 1 = b^2(b-1) + b^2 - 1 Would you look at that. One of the terms has b-1 as a factor, and we've already proved that b^2 - 1 is divisible by b-1. b^4 - 1 = b^3(b-1) + b^3 - 1 Same thing here, except this time the term on the right is b^3 - 1, which we proved in the previous step is divisible by b-1. This works recursively for any natural n. Working back to find a lower bound for n: b^1 - 1 = b - 1, clearly divisible by b-1. b^0 - 1 = 1 - 1 = 0, which is (b-1)*0. For negative n, this breaks down as the exponent just keeps growing towards negative infinity. For non-integer n, this also doesn't work because you never hit an initial condition like the n=0 case. So generally, for any real b and any non-negative integer n: b^n - 1 = b^(n-1)(b-1) + b(n-1)-1
Thank you for the proof and here is the next step if b^n - 1 then b^n-1=(b^n!2)^2-(1)^2 =>(b^n/2-1)(bn/2+1) so the two factors of this type are integers if n is even
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.
This is neat, and you can continue this pattern further! You can subtract any exponential number from any other number of the same factor, and the result will be divisible by the root of the number you subtracted! Let's take 8 as our base because I like 8. And let's use the second power because I don't want this becoming a mess of huge numbers. 64-1=63, 8-1=7, 63/7=9 64-4=60, 8-2=6, 60/6=10 64-9=55, 8-3=5, 55/5=11 this pattern continues all the way down to 64-64=0, 8-8=0, 0/0=ERR We can try it with the third power as well just to prove this isn't only a squares thing. (8 cubed is 512.) 512-1=511, 8-1=7, 511/7=73 512-8=504, 8-2=6, 504/6=84 512-27=485, 8-3=5, 485/5=97 There has to be a real math name for this already but I have no idea what it is.
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.
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.
Semi-related: When you want to check (in a program) if an unsigned integer 'n' is a power of two, you can either do a popcnt (i.e check for only one set bit), or you check that 'n' is non-zero and 'n & (n-1)' is false. Iff 'n' is a power of two, subtracting one creates a bitmask that when bitwise and'ed with the input results in zero.
Awesome video Matt! I found it was easiest to build intuition for this problem by visualizing the n = 2 and n = 3 cases. If we draw a b x b grid and remove the top right corner, it's pretty easy to see that the remaining cells are a b-1 x b-1 square starting in the bottom left, a b-1 row at the top, and a b-1 column on the right. And the 3-d version just scales each of these pieces up - there's a b-1 x b-1 x b-1 cube, 3 b-1 x b-1 squares, and some b-1 columns and rows. (that said, I'm pretty sure this is entirely analogous to your base-b approach)
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.
Haven't watched the video yet, but since I use different bases often enough I notice that in base n any exponent of n would always be a 1 followed by a given number of zeros and subtracting 1 from any of those numbers would give you a series of (n-1) and thus be factored easily into (n-1)(1111...) so yeah that makes a lot of sense that (b^n)-1 would be divisible by b-1
Before watching the full video I went through that in my head and had the idea: When we take b=440 as the example and n=3, b^n = 85,184,000 1 less than 440 is 439 and if we do 439*440*440 = 84,990,400 which is 440² less than 440³ If we now do 439*440 = 193,160 and do 193,160+84,990,400 = 85,183,56 which is 440 less than 440³ And if we add 439 to that it's 1 less than 440³ This would also aply for all natural numbers Also (b-1) * (b^(n-1) + b^(n-2) ... b^0) = b^n - 1 And here we come back to the base b thing. Because this is basically 11111... (n times) in base b times b-1 which will get you to that aaaaa... (n times) which is 1 less than 10000... (n times 0)
also b^n - b^m is divisible by b-1 for any m not equal to n. In your proof this would be like taking 10 to any power and subtracting a smaller power of 10 resulting in 9999...0000... which is also clearly divisible by 9. another interesting one is b^(2n+1) + b^(2m) is divisible by b+1. in terms of modular arithmetic: b = -1 (mod b + 1) b ^ (2n+1) = -1 (mod b +1) b^(2m) = 1 (mod b +1) b ^ (2n+1) + b^(2m) = 0 (mod b +1) which implies that b ^ (2n+1) + b^(2m) is divisible by b+1 if you look at it in terms of number bases, you get b to any odd power ends is a 9 (in base b+1) b to any even power ends in a 1 ( in base b +1) adding the two results in a string of digits ending in a 0 (in base b+1) which is divisible by b+1
If you look at b^n-1 as an integer polynomial in b, it's factors have a really interesting structure. Each positive integer has a corresponding polynomial (call it p_i), and b^n-1 is the product of p_i(b) for each factor i of n (and a minus sign). For example, b^4-1=-(1-b)(1+b)(1+b^2)=-p_1(b)*p_2(b)*p_4(b) and b^6-1=-(1-b)(1+b)(1+b+b^2)(1-b+b^2)=-p_1(b)*p_2(b)*p_3(b)*p_6(b) .
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.
Redefine b-1 to x, and b^n - 1 becomes (x + 1)^n - 1. When you expand the parenthesis, only part that does not have an x in it is the 1^n = 1, which gets removed by subtracting with 1. Thus, you can factor out x, QED.
Love this. I’m a carpenter, and for the type of carpentry I do I have to use a lot of geometry. But I still love playing with maths and finding and learning new insights like this. Even at 45 (that’s my age, not degrees, unfortunately - though my posture is slowly reaching 45 degrees with age). Cheers 👍
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.
2) difference of squares b^2-1^2=(b-1)(b+1) 3) difference of cubes b^3-1^3=(b-1)(b^2+b+1) 4) Difference of 4th orders is factored as difference of squares 5) b^5-1^5 = (b-1)(b^4+b^3+b^2+b^1+1) 6) b^6-1^6= difference of squares, where one factor is a difference of cubes Long division shows any odd n will be factored (b-1)(b^(n-1)+b^(n-2)+….b^(n-n)), and any even n can be factored as difference of squares, until one factor is b to an odd exponent, minus 1, which is factored as above.
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.
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.
I did it via induction. b-1 obviously divides b-1, so all we need to do is check that n implies n+1. b^(n+1) -1 = b*b^n -1 = b * b^n -b+b-1 = b(b^n -1) + b-1. b^n -1 is divisible by b-1 as per our assumption, and b-1 is the obvious case from before => b-1 | b^(n+1) - 1 => b-1 | b^n - 1 for all n.
This reminds me of a way to square a number. You take the number you wanna square, in this case 'b'. And subtract 1. Then you find it's triangular number. (Like a factorial, but instead of multiplication it's addition.) Now you take that number, multiply it by 2 and add b. (b-1)T×2+b=b²
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!!"
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 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
That version of it may be obvious but it's a bit in-tens for me.
Same, I saw the thumbnail and so knew I'd be raising it to an exponent, and so picked a number I knew would be easy to do that to without getting out a calculator. And yeah definitely gave away the trick on the second proof XD
Once they've followed the step of converting to base b, technically everyone is using 10 as their starting number
I’m not convinced you are not.
I picked 2. Which, yes, is divisible by 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...
I did that too!
I thought of this as well
was it specified that n is a set of natural numbers?
@@broskey4041 You mean *in* the set of natural numbers. And that's really a matter of conventions : if you use n as a value name for something else than a (natural) integer without precisions, you're an heretical monster in the mathematical community. Similarly, because we're discussing divisibility without more details, you can infer that b should be an integer too.
Of course if you're writing a math paper or in your exam, you should **really** details all of this!
@@chaddaifouche536 thank you for the correction and clarification. I didn't even know that divisibility implies working with integers that's kinda cool
I raised to the power of 1. Made a load of sense.
Now prove for case n+1 and you've got your inductive proof.
me too
I raised it to the power of 0, and it made no sense at all
@@soberhippiei mean 0/(b-1) is an integrr for b!=1
I chose 1 as my starting number "b", which I promptly regretted
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.
I like your idea! When a problem is visualised it makes it much more simple for me.
This. I visualised exactly the same almost straight away.
...and going up in dimensions by one always adds (b-1) copies of the currently existing cubelets prior to the removal from the very first strip.
This is beautiful!
This should get more upvotes
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.
ah yes, this complicated string of math that i don't understand....yes, i understood that perfectly
And now in the vein of the second proof, in (b^n)-1=(b-1)(b^n-1+b^n-2+...+b+1), if you write the second number in base b you get 111..1 (b ones)
@@mathieuaurousseau100 Whoa
This was my first thought.
@@ShongoStick It's easier to understand (at least if you can write it out properly instead of trying to force it into a TH-cam comment), if you look at like this: first set a=1, since we don't need the more general version, so we have (b-1)(b^n-1 + b^n-2 + ... b + 1) If you expand that out, you get (b^n + b^n-1 + ... b^2 + b) - (b^n-1 + b^n-2 + ... + b + 1). If you compare the positive terms with the ones being subtracted off, you'll notice that all of them cancel out except for the first and last, b^n-1.
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 :)
No sh1t, Sherlock.
@@samueldeandrade8535 You must be pretty smart wow
@@novamc7945 thanks, but no. No one needs to be smart to NOT like obvious comments.
@samueldeandrade8535 That's a stupid argument. According to your analogy, videos that explain a topic at a fundamental level should simply NOT exist. Afterall, it's obvious. Plus, it's certainly not like there are people out there that don't understand the subject you're so profoundly good at!
If you'd already inferred what the comment was suggesting, you could've simply ignored it and moved on. There was simply no need to leave a discrediting reply.
Nothing like a good old TH-cam comment section argument.
@@novamc7945 "According to your analogy ..."
Wtf are talking about? What analogy? I made no analogy ...
I thought of b=1
Me too!
Try b=pi, or root 2
same here
Zero divided by zero
That's a bbbase case.
"Wait it's all 9s"
"Always has been"
0:05 b = 1
0:30 n = 0
0:41 oh...
So it turns out you can divide by 0 after all
Does 0/0 = 1 or undefined or infinity
@@Mitchpott0/0 is considered undefined.
Imagine a function (or graph it in Desmos) where it's some number divided by x, like y=1/x. If you start at x=1 and move towards x=0, you're dividing by a smaller number which means you're actually multiplying by a larger number, i.e. 1÷½=1×2. So as x approaches 0 from the positive side, the number races off to infinity.
Now what happens if you start from x=-1? Well, the exact same thing, but the number is now negative. As x gets infinitely close to 0, the 'limit' (basically what we've just done) is different depending on how you look at it. So the limit is said to not exist.
Lastly, imagine the age-old 0.99999... = 1. You might know it works because it's an infinitely long string of O's, but if you try to decide what its limit is (the number it gets infinitely close to), it approaches 1. There are some great proofs here for you to find. But in this respect of limits, we arrive at the conclusion that they are actually equivalent.
So, because the limit does not exist, it is impossible to divide by 0. In actual calculus, it is said that if your result is 0/0, you've taken the wrong approach.
Factors aren't defined by division but by multiplication into a product. Given h × k = j, then h and k are factors of j. Likewise, since 3 × 0 = 0, both 3 and 0 are factors of 0. Nothing in there about division.
From the point of view of the definition of divisibility, 0 is actually divisible by 0, since there exists a number (any number in fact) that you can multiply by zero to get zero. The funny thing is, this still doesn't imply you can divide by zero, it's just the one single case where the terms "divisibility" and "division" collide and contradict each other.
But for any non-zero number, divisibility for sure implies that you can divide by that number and get a single unambiguous result.
@@nickpro8116 The terms "divisibility" and "division" do not contradict each other. Division is defined as multiplication (one of the defining operation in a ring) by the multiplicative inverse (which exists for any nonzero element in a field). By definition, "division" excludes dividing by zero already.
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).
Nice one. Really clean. It does have the downside of not knowing the resulting alternate factor, though. Still a good proof, though.
Just got that answer too🤪🤪🤪
I like how "complicating" the initial problem leads to a much more intuitive understanding of the proof. (And the dig at Amazon)
I REALLY LOVE WHEN WE SWITCH NUMBER BASES AND IT BECOMES OBVIOUS
IT IS MY FAVORITE GENRE OF MATH
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 believe that coincides with how synthetic division works, which was how I went about thinking through the problem
I really like this one.
This is how I went about it as well. Let F(b, n) = (b^(n) - 1) / (b - 1). Now evaluate at F(b + 1, n) = ((1 + b)^(n) - 1) / (b). Now expand the binomial and note that C(n ,n) b^0 = 1, which cancels the one in the numerator. Now we have a polynomial expression in terms of b multiplied by 1/b, which we can negate by subtracting one in all of our terms. Now evaluate this expression at b - 1 to show that F(b, n) = (b^(n) - 1) / (b - 1) = sum(k = 0, n - 1, C(n, k) * (b - 1)^(n-k-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
I'm sure the 440Hz playing bassist also had some sheets of paper:
A0 = 1 m²
A1 = 1/2 m²
A2 = 1/4 m²
A3 = 1/8 m²
A4 = 1/16 m²
...
@@BigDBrian Then if you multiply the pitch by the paper size, you get a very strange way to express kinematic viscosity:
A4 × A4 = 440 Hz × 1/16 m² = 27.5 m²/s = 275 kilostokes (kSt)
A440 isn't a bass note, it's the very definition of mid-range.
@@AlRoderick it's not a bass note, but that doesn't mean it can't be played on a bass.
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
That's probably the original proof of this fact.
well you can do your way without proving that for any a satisfying a polynomial f(x), (x-a) divides f(x). So I think its nicer
I mean you would have to show after dividing it out, the polynomial has integer coeffs? If rationals then, we can't guarantee?
@@Schpeeedy exactly.
@@TechToppers no
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.
Base B is just mod B with a carry 😊
But then when you need to divide by b-1 mod b-1, it would be like dividing by zero, or perhaps I didn’t understand you?
The base b approach is natural when one is in school and one hasn't done modular arithmetic yet, but one _has_ encountered things like how to test in base 10 for divisibility by 9.
@@gideonk123 if a number is 0 mod b-1, that means its divisible by b-1
A way to find it would’ve been if you tried b=10 at some point in your tests
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
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.
well. technically he didnt say to pick a "fully random" number, but just a number we like, thus reducing the numbers chosen by a LOT.
17 is just a decently likable number.
I picked 17, but only because it used to be my favourite football player's number when I was a kid, and now it's my favourite number xD
I picked 7 and i think there's something to it why is 7 a number people often pick
I have changed my strategy for picking random numbers under 100 since I watched that. 30 and 90 are preferred random numbers, now. But, of course, there's the question of how many other people in the world have thought the same. (-:
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.
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.
Yeah, I found it fairly easy to visualise a proof for n=2 and n=3 just by chopping up shapes, but I wasn't sure how to visualise n=4 lmao
My thoughts exactly! Sad it wasn't original, happy people think in hypercubes!
Yes, this is my favorite proof. You can also mix it with a bit of induction to make it simpler: b^n -1 is the volume of a n-cube with side lenght b, which has a small (n-cube)-shaped hole with side length 1 at one of its corners. Take a slice off of it from the top: you’re left with a n-parallelepid with one side lenght (b-1) and all other sides b, and the extra slice you cut off. You can “flat” this extra slice by looking at it from the front, suppressing the dimension along its side of lenght 1. Then, you’ve got the same shape as you started with, but which lives in 1 dimension lower: a (n-1)-cube with a unit corner missing. Repeat n times and you get all shapes with at least a side lenght of (b-1)
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.
The first thing I did is divide (b^n-1) by (b-1), just like you are taught at school. Since it divides with no remainder, you know it is divisible. Then the obvious thing is just to write down how b^n-1 factorises as two polynomials, one of which is b-1. I quite like the geometric and base approaches as well.
instructions unclear, I picked "b" to be the big famous constant e and it didn't work :(
Similarly, I picked pi. Fairly sure that's not working either.
I think 1 has to divide into your "b". I imagine if you picked b = ½, you could say b ^ n - ¼ is divisible by b - ¼. (I picked ¼ because it divides into ½).
Therefore it makes sense that b has to be an integer for the video's equation to work.
p.s. this could all be wrong, I've not actually checked the maths
No it definitely works
it only applies to integers. He should have said that
I picked -1/4. Can you believe that didn't work?
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
Discrete Math ftw.
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.
My b was 2. Yep, i was underwhelmed
That's odd
I think it’s prime time to retry with another number.
@@charstringetje No, 2 is definitely even.
@@Centauris-ty8wn 2 is my favourite number. I would never forsake it.
@@helsing7423Two forever!
The second proof implies to me that this can be extended to b^n - k, as long as 1 < k < b. Using base 10, 8888 is obviously divisible by 8, 7777 is divisible by 7, etc.
I Love the shade thrown at Amazon!
I decided to look into doing a proof by induction to prove this:
The way I did it used two base cases: b^n - 1 | b - 1. When n = 1, this is trivial, and when n = 2, this is covered in the video
Moving on to the inductive step: Assume b^k - 1 | b - 1 and also assume b^(k-1) - 1 | b - 1
Prove b^(k+1) - 1 | b - 1
b^(k+1) - 1 = (b^k - 1)(b + 1) - (b^k - b) = (b^k - 1)(b + 1) - b(b^(k-1) - 1)
Since (b^k - 1)(b + 1) has a factor of (b^k - 1), that is divisible by b - 1
and b(b^(k-1) - 1) has a factor of b^(k-1) - 1, that is divisible by b - 1
Therefore b^(k+1) - 1 | b - 1
Thus b^n - 1 | b - 1 for all n in N
QED
I immediately thought of doing it by induction too!
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)
What is the second proof?
The base B proof.
Also I wasn't expecting to see MrCheese while scrolling through the comments. Neat.
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.
PS I didn't start by thinking in n-dimensions, I'm not a genius! I started in 2-d, then thought about 3-d, and fortunately that was enough to see how the generalisation would work :)
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
This is how I visualized it as well
Doesn't the extra column have b elements? E.g if b = 4 and we square it:
Say these asterisks represent b, so here is a 4x4 grid:
* * * *
* * * *
* * * *
* * * *
I see b (4) rows of b-1(3)
* * *
* * *
* * *
* * *
But this remaining extra column you refer to has b, not b-1 elements
*
*
*
*
I just realised why this makes sense - because we are dividing by (b^n) - 1, so if you subtract this extra one off, then yes it is divisible by (b - 1)
*
*
*
But the way you described it was incorrect and confusing for me lol.
@@JavedAlam-ce4mu sorry if I was unclear but yes we ended up at the same solution, if b = 4, you end up with: b rows of b - 1 (4 rows of 3) and one extra column of b - 1 (3)
###|
###|#
###|#
###|#
@@JavedAlam-ce4mu if you remove the corner square then yeah, youll have a square of (b-1)^2 plus 2(b-1) sides
two other ways of thinking about it that don't require different bases:
1. synthetic division/polynomial division: if we write out our problem as a synthetic division problem it will always be a 1 followed by n 0s followed by -1, then our root is 1. Drop the first 1, multiply add to the next value and on and on until we get to the end (basic synthetic division obviously), because we are never multiplying by anything but the mutliplicative identity or adding anything but the additive identity, when we finally add the -1, we get a remainder of 0, proving that 1 is a root and (b-1) is a factor.
2.if we take the quotient of that synthetic division and think about the process in reverse, we are multiplying some n-degree polynomial with no skipped terms with only coefficients of 1 (e.g. b^7 + b^6 + b^5 + b^4 + b^3 + b^2 + b + 1) by (b-1), which we can re-frame as (b^1 - b^0), then through distribution we get b^1(b^n + b^[n-1] +...+ 1) -1*b^0((b^n + b^[n-1] +...+ 1), then by distributing again and through our exponent rules, every term multiplied by b^1 will have it's degree raised by 1, (b^n + b^[n-1] +...+ 1) -> (b^[n+1] + b^n +...+ b^1) , and every term of the other part will become negative, (b^n + b^[n-1] +...+ 1) -> (-b^n - b^[n-1] -...- 1), those two resultant polynomials' values all obviously cancel out, b^n - b^n = 0 and so on, except for b^[n+1] and -1. Therefore (b-1) must always be a factor of (b^n - 1)
The naughty orange dot in the top right corner bugged me
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)
The base change is sooo poggers
very skibidi indeed.
Spoiler alert!
More generally x - y divides x^n - y^n for all nonnegative x, y, n. In fact, this is all just a special case of the (very nice) lemma that a - b divides P(a) - P(b) for ANY integer polynomials P and nonnegative integers a, b.
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.
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
Pick any number but irrationals don’t work. He really Mat Parkered those instructions.
Actually, irrationals DO work, depending on your definition of divisibility. No matter the number, b^n - 1 can always be factorized as (b^(n-1) + b^(n-2) + ... + b + 1) * (b - 1). If you divide by b-1, you're left with just the b^(n-1) + ... + 1 term, whose representation in base b is always just 111...111. Thus, in base b, the resulting number is always an "integer" even if b itself is irrational.
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
I like big exponents and I can not lie.
You can just take the term b^n-1 and add and subtract all powers of b from (n-1) down to 1. Then group all additions together and all subtractions together so you'll get b^n+b^(n-1)+b^(n-2)+...+b-b^(n-1)-b^(n-2)-...-1. Next put some braces and pull out a common factor:
b(b^(n-1)+b^(n-2)+...+1)-1*(b^(n-1)+b^(n-2)+...+1)
Since the terms inside the braces are equal we can pull their factors together:
(b-1)*(b^(n-1)+b^(n-2)+...+1)
And we can see that it indeed is divisible by (b-1).
I picked b=1. I feel like "a number" was not specific enough. Or is 0 divisible by 0? 🤔
Sure 0 is divisible by 0, 0 = k*0 for some k
@@galoomba5559 That would make 0 / 0 = k. Which is not a unique value, so u can't divide 0 by 0.
Zero is indeed divisible by zero. Since there exists a whole number k such that kx0=0 (this is true for all k, but we can take k=0 as an example, 0x0=0). Generally speaking "a is divisible by b" and "a is a multiple of b" are the same statement. This trips a lot of people up because there's no answer to "zero divided by zero", which sounds like it should mean the same thing, but it doesn't.
@@mudkip_074 Ah, right, hadn't considered that you can define divisibility by multiplication
@@chemicalbrother5743 unfortunately, the mathematical definition of "a is divisible by b" is in general not the same as "you can divide b by a". this is because the concept of divisibility is very useful even in situations where you don't have a concept of division at all. in general, "a divides b" is defined as "there's some k such that k*a=b", which is obviously satisfied for 0 and 0, because 0*k=0 for all k.
The problem I generally face while studying in the field of STEM is that, there is always that one person with something different that challenges how you see a certain thing. And it's beautiful. This beauty will save the world.
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
W pfp
Oh my Euler, you are ins4ne.
It's on Numberphile
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! 🤞
This. *This* is my favourite comment on a maths video. 😁
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.
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
Even better, (x^n - y^n) is divisible by x-y
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.
Actually same idea as the second proof, we even both reframed as a too.
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!
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).
Such a brilliant way to re-frame things (to base b)! made the proof so transparent, loved it!
i did it by induction. idk how to do it this way formally, but like you can see roughly what i was thinking (haven't learnt it in school yet, it's like 2 years above my grade level) so please tell me if there's some inconsistencies.
let n = 1.
LHS = b^1 - 1
= (b - 1)(1)
= 0(1) mod (b - 1)
= 0 mod (b - 1)
therefore LHS = RHS for n = 1
assume this is true for any n.
=> b^k - 1 = 0 mod b - 1.
let n = k + 1.
LHS = b^(k + 1) - 1
= b(b^k) - 1
= (b^k)(b - 1 + 1) - 1
= (b - 1)(b^k) + b^k - 1
= 0 + 0 mod b - 1
= 0 mod b - 1
= RHS
therefore LHS = RHS for n = k + 1
therefore by mathematical induction, LHS = RHS for all n.
About to watch the second proof, but recording my guess about what it is.
To illustrate, consider the n=2 case. Imagine a square grid of size b by b. Knock off the bottom corner, and you get two lines of b-1 and a square of b-1. This is clearly divisible by b-1. (b-1)²+2(b-1), which simplifies to the famous (b+1)(b-1).
Next to get a sense of what happens for different n, consider the cube for n=3. Knock off a corner and you get 3 squares of b-1 and one cube of b-1. (b-1)³+3(b-1)², which simplifies to (b-1)²(b+2).
It's not so easy to visualize the hypercube, but I think this will lead to a proof after finding the right generalization. Essentially, for an n-dimensional hypercube, you can count the number of cubes b^n by starting from the b-1 hypercube of that dimension, adding n-1 hypercubes of dimension n-1 to each face sharing a particular vertex, which is n-1 faces, and adding a 1 by 1 hypercube to that corner.
You want to know if it's divisible?... The most direct way to find out would be to straight-up divide, and see that there's no remainder! The standard long division paper-and-pencil algorithm works (if you abstract cleverly)!
Write b-1 to the left of the long division symbol. Write b^n under the 'roof', on the left... then include a few zero terms like +0b^(n-1) +0b^(n-2) ... +0b, then finish up with -1. The most 'significant' part of your answer will be b^(n-1), you'll subtract b^n-b^(n-1) from the numerator, and get b^(n-1) on the next line (with the implicit +0b^(n-2) + ... +b -1). Next significant part of your answer will be b^(n-2), then the numerator left to be processed will be b^(n-2)-1. The pattern continues, yes this is like doing the second step of induction first, and you'll get a point of having b^(n-1) +b^(n-2) ... +b above the line, and b-1 below the line. This is simple: that's +1 to the answer, and no remainder (the base case of the induction). Long division shows you there's no remainder: one divides into the other.
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)
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.
I literally tried this problem yesterday from the Stanford Maths Problem book, and the next day BANG a video from the man himself.
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.
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
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!)
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!
Consider A=b^0+b^1+b^2+...b^(n-1), for integers b,n A is an integer. But A*b=A+b^n-1. So A = (b^n-1) / (b-1) is an integer. So b-1 divides b^n-1.
As for the first technique, I once took a seminar on Riemannian Manifolds and in my paper that I had to hand in, I gave an unusual proof for the Fundamental Theorem of Algebra by using holomorphic functions between the 2-spheres interpreted as Riemannian Surfaces.
During the discussion I was asked why I added this part to the paper and I said "because we need more obscure proofs for basic mathematics".
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.
That's a pretty neat way to solve it, certainly more intuitive than what I did.
I started with b^2 - 1 = (b+1)(b-1) as you mentioned, then looked at what happened as n grows, and how you could factor that number in terms of b-1:
b^3 - 1 = b^2(b-1) + b^2 - 1
Would you look at that. One of the terms has b-1 as a factor, and we've already proved that b^2 - 1 is divisible by b-1.
b^4 - 1 = b^3(b-1) + b^3 - 1
Same thing here, except this time the term on the right is b^3 - 1, which we proved in the previous step is divisible by b-1.
This works recursively for any natural n.
Working back to find a lower bound for n:
b^1 - 1 = b - 1, clearly divisible by b-1.
b^0 - 1 = 1 - 1 = 0, which is (b-1)*0.
For negative n, this breaks down as the exponent just keeps growing towards negative infinity.
For non-integer n, this also doesn't work because you never hit an initial condition like the n=0 case.
So generally, for any real b and any non-negative integer n: b^n - 1 = b^(n-1)(b-1) + b(n-1)-1
Thank you for the proof and here is the next step if b^n - 1 then b^n-1=(b^n!2)^2-(1)^2
=>(b^n/2-1)(bn/2+1) so the two factors of this type are integers if n is even
Before the videos started, i just came up with that since 1^n = 1 then b^n - 1^n = (b - 1)^n which is obviously divisible by b - 1
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.
This is neat, and you can continue this pattern further! You can subtract any exponential number from any other number of the same factor, and the result will be divisible by the root of the number you subtracted!
Let's take 8 as our base because I like 8. And let's use the second power because I don't want this becoming a mess of huge numbers.
64-1=63, 8-1=7, 63/7=9
64-4=60, 8-2=6, 60/6=10
64-9=55, 8-3=5, 55/5=11
this pattern continues all the way down to
64-64=0, 8-8=0, 0/0=ERR
We can try it with the third power as well just to prove this isn't only a squares thing. (8 cubed is 512.)
512-1=511, 8-1=7, 511/7=73
512-8=504, 8-2=6, 504/6=84
512-27=485, 8-3=5, 485/5=97
There has to be a real math name for this already but I have no idea what it is.
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.
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.
Semi-related: When you want to check (in a program) if an unsigned integer 'n' is a power of two, you can either do a popcnt (i.e check for only one set bit), or you check that 'n' is non-zero and 'n & (n-1)' is false. Iff 'n' is a power of two, subtracting one creates a bitmask that when bitwise and'ed with the input results in zero.
Awesome video Matt! I found it was easiest to build intuition for this problem by visualizing the n = 2 and n = 3 cases. If we draw a b x b grid and remove the top right corner, it's pretty easy to see that the remaining cells are a b-1 x b-1 square starting in the bottom left, a b-1 row at the top, and a b-1 column on the right. And the 3-d version just scales each of these pieces up - there's a b-1 x b-1 x b-1 cube, 3 b-1 x b-1 squares, and some b-1 columns and rows.
(that said, I'm pretty sure this is entirely analogous to your base-b approach)
love the jab at amazon right at the end!
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.
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.
Haven't watched the video yet, but since I use different bases often enough I notice that in base n any exponent of n would always be a 1 followed by a given number of zeros and subtracting 1 from any of those numbers would give you a series of (n-1) and thus be factored easily into (n-1)(1111...) so yeah that makes a lot of sense that (b^n)-1 would be divisible by b-1
Before watching the full video I went through that in my head and had the idea:
When we take b=440 as the example and n=3, b^n = 85,184,000
1 less than 440 is 439 and if we do 439*440*440 = 84,990,400 which is 440² less than 440³
If we now do 439*440 = 193,160 and do 193,160+84,990,400 = 85,183,56 which is 440 less than 440³
And if we add 439 to that it's 1 less than 440³
This would also aply for all natural numbers
Also (b-1) * (b^(n-1) + b^(n-2) ... b^0) = b^n - 1
And here we come back to the base b thing.
Because this is basically 11111... (n times) in base b times b-1 which will get you to that aaaaa... (n times) which is 1 less than 10000... (n times 0)
also b^n - b^m is divisible by b-1 for any m not equal to n. In your proof this would be like taking 10 to any power and subtracting a smaller power of 10 resulting in 9999...0000... which is also clearly divisible by 9.
another interesting one is b^(2n+1) + b^(2m) is divisible by b+1. in terms of modular arithmetic:
b = -1 (mod b + 1)
b ^ (2n+1) = -1 (mod b +1)
b^(2m) = 1 (mod b +1)
b ^ (2n+1) + b^(2m) = 0 (mod b +1)
which implies that b ^ (2n+1) + b^(2m) is divisible by b+1
if you look at it in terms of number bases, you get
b to any odd power ends is a 9 (in base b+1)
b to any even power ends in a 1 ( in base b +1)
adding the two results in a string of digits ending in a 0 (in base b+1)
which is divisible by b+1
If you look at b^n-1 as an integer polynomial in b, it's factors have a really interesting structure. Each positive integer has a corresponding polynomial (call it p_i), and b^n-1 is the product of p_i(b) for each factor i of n (and a minus sign). For example,
b^4-1=-(1-b)(1+b)(1+b^2)=-p_1(b)*p_2(b)*p_4(b) and
b^6-1=-(1-b)(1+b)(1+b+b^2)(1-b+b^2)=-p_1(b)*p_2(b)*p_3(b)*p_6(b) .
Always blows my mind how a small change in perspective can makes things totally obvious.
Shutout to my fam p-addics the real one!
I like it when Matt does a video on a topic I fully understand, it makes me feel much smarter than I actually am.
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.
Redefine b-1 to x, and b^n - 1 becomes (x + 1)^n - 1. When you expand the parenthesis, only part that does not have an x in it is the 1^n = 1, which gets removed by subtracting with 1. Thus, you can factor out x, QED.
Love this.
I’m a carpenter, and for the type of carpentry I do I have to use a lot of geometry.
But I still love playing with maths and finding and learning new insights like this.
Even at 45 (that’s my age, not degrees, unfortunately - though my posture is slowly reaching 45 degrees with age).
Cheers 👍
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.
I love how intuitive the 2nd proof is (as long as you understand bases)
2) difference of squares b^2-1^2=(b-1)(b+1)
3) difference of cubes b^3-1^3=(b-1)(b^2+b+1)
4) Difference of 4th orders is factored as difference of squares
5) b^5-1^5 = (b-1)(b^4+b^3+b^2+b^1+1)
6) b^6-1^6= difference of squares, where one factor is a difference of cubes
Long division shows any odd n will be factored (b-1)(b^(n-1)+b^(n-2)+….b^(n-n)), and any even n can be factored as difference of squares, until one factor is b to an odd exponent, minus 1, which is factored as above.
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.
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.
I did it via induction.
b-1 obviously divides b-1, so all we need to do is check that n implies n+1.
b^(n+1) -1 = b*b^n -1 = b * b^n -b+b-1 = b(b^n -1) + b-1.
b^n -1 is divisible by b-1 as per our assumption, and b-1 is the obvious case from before
=> b-1 | b^(n+1) - 1 => b-1 | b^n - 1 for all n.
I've always thought about the factors of consecutive numbers, but only now after you said it did it become obvious to me why they wouldn't have any.
This reminds me of a way to square a number. You take the number you wanna square, in this case 'b'. And subtract 1. Then you find it's triangular number. (Like a factorial, but instead of multiplication it's addition.) Now you take that number, multiply it by 2 and add b. (b-1)T×2+b=b²
That is GENIOUS!
The base transformation is just so simple, I love it so much! I'm going to show everyone I know
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!!"
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 figured this out for squares back in high school via x² = (x-1)² + 2x +1. Neat to see it holds true for other exponents too! :D