Solving Divisibility with Binomials.
Note: Please switch to dark mode for a more immersive experience.
1.1 Introduction
Most of us have learned about binomials and the binomial theorem in school courses or perhaps an excessively deep rabbit hole?
Anyhow, you must’ve seen its use in quickly finding values of larger powers like 99⁵ or using it for some approximations (especially the general form).
It even commands a strong presence in the fields of combinatorics and probability, with concepts like Bernoulli Trials, and in statistics, with the well-known Binomial Distribution.
Today, let's look at another one of its interesting uses, which may not be entirely unknown, but the different applications and the concepts around it are very interesting and worth discussing.
Specifically, we will be seeing a glimpse into how binomials help number theorists to solve some pretty interesting problems on divisibility and finding remainders!
1.2 Binomial Theorem
Before diving into the questions, let’s discuss the theorem itself and some critical concepts that we will be using for solving.
Note: We will be doing our discussions here today without invoking the power of modular arithmetic, to keep the concepts intuitive and simple.
As a start, here is the condensed formula of the general binomial theorem:
Nice and simple.
Next, to make the calculation simpler, I’d just like to consider the expansion (1+x)^n instead.
Which gives us the following:
This is helpful because the expansion just involves increasing powers of x terms along with some coefficients, which allows us to make the observations we are about to.
Firstly, if I said the following, you should be able to visualise it:
See, when you expand (1+x)^n, the terms look like this:
What you need to notice is that aside from the 1 term, every single term has at least a factor of x contained in it.
So when we remove the 1 to the other side, the remaining quantity is completely divisible by x.
In the same vein, statement 2 can be reasoned, as nC1 is simply n, so we take nx to the other side, leaving the smallest power of x in the remaining terms as x²
I.e., making the remaining quantity completely divisible by x²
And, of course! There is no need to stop here; by taking more terms to the LHS, we can show divisibility by higher powers of x as well.
These two statements, however, are the most commonly encountered.
As an example, consider a simple question asking you to show that the following expression is completely divisible by 8 for all natural n.:
By a simple application of the result, we can write 9 as 1 + 8 and prove it instantly.
This has to be divisible by 8 for all n, as we discussed earlier.
Similarly, try to reason out the following expression that you have to prove is divisible by 121 for all natural n:
This is part of homework!
Alright, next, I want to discuss a small extra concept that isn’t directly connected to this topic, but can help you solve some other cool questions:
First, let's consider the following question:
Our current tools will fail to handle that + 1 rather than the - 1 we were seeing earlier.
So need a new tool. Please give a thought about what it could be, because there are multiple methods.
One way to do it is to remember a very interesting algebraic identity:
You must’ve learnt the identity for the sum of two cubes, right? Just the general version of that.
It is derived by using the fact that if the LHS is considered to be a polynomial in x, then y = -x is a root of the polynomial! (because n is odd)
And that gives the (x + y) factor, with the second factor coming by long division.
The second factor also follows a very similar pattern to the binomial theorem, if all the coefficients were 1.
You basically take one less degree than you started with, k, and begin x from k -1 and y from 0, the same way you would for a binomial.
Also, don’t forget to alternate the signs between the terms.
This way it's very easy to remember as well!
Then, if we consider the question at hand, the 2n+1 is placed there very intentionally, because that gives us the exact “k has to be odd’ condition that we need!
Thus:
The second term is insignificant here so long as it remains an integer (which it will), as the 5 + 1 has already provided us the divisibility by 6 we were trying to prove.
Moreover, a very similar identity also exists when there’s a minus sign between the x and y:
This is the generalization of the fan-favorite difference of squares and cubes identity!
For this, since the minus sign does the heavy lifting in making y = x a root of the polynomial, allowing it to be valid for all natural n, unlike its brother we just saw.
The way to remember is pretty much the same as well, just notice the minus in (x-y) and how the signs do NOT alternate in the second factor.
So this aforementioned question can be looked at with another lens as well:
This proves the required condition yet again in one step.
Please try to remember these two identities I told you because they have immense use across multiple fields of math, not just here.
Another small thing before we move on to the example questions to really drill the concepts further.
If I say the following, does it make sense?
This is just a different way to say the concept we learnt all the way back in statement 1. Give it a few minutes and let it sink in.
Here, I is representing the remaining terms in the expansion after taking out the x.
All we care about is that it will be an integer for integer x, not its value.
Let's use this to great effect in the coming questions.
1.3 Questions
We will also now be moving on to finding more remainders rather than simple divisibility.
First, here's a nice question that will teach us many things in one:
Let’s make the following set-up:
Alright, here's another concept drop for all of you. In these kinds of remainder problems, it's very important to remember the most basic and effective path as:
Look for the power of the base that is at a difference of 1 from a multiple of the divisor.
Call this ‘star concept’ so we can refer to it later.
You should be able to figure out that this is just about creating the +1 term so we can use our trusty result from earlier.
We will understand this better after doing the problem.
So think. And you won't have to think for long, as 9² = 81 is exactly 1 away from 80, a multiple of 5.
So, we will try to use this by creating the (80+1) term in E.
But how do we do that? By using the laws of exponents, of course!
Follow suit:
Realize why we took the 9 out first? As 9² has 2, which is even, to create 81, we would need an even power initially.
Now only a simple rewriting step remains:
And directly applying our result from earlier gives us:
Then we just expand the terms to get:
I hope you haven't forgotten that we are trying to find the remainder of the number by 5.
So, our end goal would be to turn E into a form like 5n + k, where k is either 0, 1, 2, 3, or 4, and this value of k is precisely our sought-after remainder.
The common way to do that is creating terms to we can easily take 5 common from the terms.
And this leaves us with finally:
Here, 144I + 1 is just another integer, so I have replaced it with M.
Thus, E is fully in the aforementioned form, and hence we can say that the final answer for the remainder is: 4
Did that solution make sense? This is the quintessential variety when you talk about remainder questions involving binomials, so I hope you understood it well.
Well then, are you ready for the next challenge? It will be a bit more confusing than this one, but just remember what I’ve told you until now.
Here it is:
Please pause and attempt the question first because it is very interesting.
The first way is to use the star concept and proceed just like we did the last time. And I’ll tell you: It works.
Get OreoPlushie’s stories in your inbox
Join Medium for free to get updates from this writer.
Well, if you did go through it, you'd find that 3125 = 3124 + 1 ( 3125 = 5⁵, and 3124 is a multiple of 11), which perfectly fits our template from our previous problem, and we proceed like so:
Of course, once again, we have created 5⁹⁰, as our goal is to create 5⁵ inside the binomial term.
Next, we follow very similar steps to last time:
And using the result from earlier:
Now, you will find another interesting point:
Notice, E is split into two parts. The first part is a multiple of 11, and the other part is clearly not.
Now you tell me, will the remainder we are looking for come from the first term or the second?
Clearly, the second term, right! The first term is going to have a remainder of 0 anyway, so we only need to consider 5⁹.
I.e., we need to look at the remainder of 11 with 5⁹ only!
Note: To be more precise, since we are adding the terms, the remainder is the same and positive; however, if it had been — 5⁹, we would take the resulting remainder, whatever we get, as negative.
Then, to convert the negative remainder back to a positive and understandable one, we shall add the divisor to it until it becomes positive.
Example: If your remainder with this method comes out to be -2 and you divided by 11, your correct positive remainder is -2 + 11 = 9.
So, consider R as:
And we will actually continue the same method to ‘reduce’ the power of 5 we have to consider.
Thus, we again want to create 5⁵.
So these are the following steps that we take:
Now, can you see the end? By the same logic that we used to shift our focus to 5⁹, the math is now allowing us to shift our focus to 5⁴.
And now you shouldn't need any cool binomial expansion trick to find the answer, because the remainder of 5⁴ = 625 we can just calculate directly.
Thus, upon doing the long division:
The final answer to the problem is simply 9.
Beautiful? I think so too!
One more thing, though.
Say, without a calculator, you would be a bit hard-pressed and demotivated to work through the powers of 5.
Is there a faster — or at the very least less computational method that allows us to get the same result?
To be frank, the aforementioned method is not time-consuming enough that you couldn't do it — even in an exam. But this other method can be the difference between life and death for a question that isn’t so kind.
Alright, let's go back to our E originally:
Now, according to the star concept, we should look for that gap of 1 from a multiple of 11, right?
Sometimes in life, however, you may have to settle for something less than optimal; in this case, what if that gap was not 1?
Because then rewriting the 5 wouldn't be a problem at all!
For example, 25 = 22 + 3, let's use this and see what we end up with:
And then:
Alright, now keep your binomial theorem visualizations ready.
When we expand it, every term except 1 will have 22; can we agree on that?
So, if I write E this way, there should not be any argument:
Then, by the same logic that we’ve used twice already, let's consider only the second part of this E.
The remainder of this part with 11 is the remainder of the original number with 11.
So, we really just have to continue the chain now. We are not so lucky as to easily get a power with the 1 unit difference with 3, so let's just settle for 3² = 9 with the difference of 2 from 11.
Thus, we repeat the steps as follows:
Careful with the signs here. Since we have a negative between 11 and 2, we could have a negative constant term, but the even power handles that for us.
Maybe you are getting the idea of this method by now?
Let’s run it back!
Considering C as mentioned, we get:
One. More. Time
Then, 15 * 2⁴ is simply 240, the remainder with 11 of which can easily be found by long division:
And you have the same answer…
The crux of this method 2 is to reduce the power we have to work with.
We went from 99 to 49 to 24 to 8 to 4; halving the powers this way allows us to eventually bring the numbers into a calculable level, which makes the answer after that trivial.
Just make sure you are careful with the signs and the multiplications you are doing because they have a big effect on the remainder.
1.4 Boss Fight
Well, here we will be discussing the question in the thumbnail, and really, once you've managed to come all this way through the questions, it should not be hard at all.
This is a question from a past year Cambridge A2 Further Maths examination
Let's restate it properly:
The proof for this is going to be another very fun algebra exercise, so please try it.
This question has various ways to solve it (induction is one of my favorites), but I will use a purely algebraic approach.
Alright, let's call upon our trusty friend E again!
Now, I am going to do a step that might feel unprompted but will reward us heavily.
Yes, so I’ve created 1 + 4, and you know whats the thing I'll be doing next.
As for the motivation, it's simply because making more terms with a factor of 4 is good because we eventually want to prove divisibility by 8.
Also, I can foresee that the -1 chilling around will get cancelled when I expand the terms after this step:
Here is the 1 getting cut in 4k:
And that leaves just the question already half solved!
So we have shown by now that E is a multiple of 4. Alright, what shall we do next?
See, we have to prove the whole thing is a multiple of 8, and 4 is already out; we need to prove that the second factor is a multiple of 2, right?
Here’s a very nice observation for you: what is the exact value of M?
I know I said I wouldn't focus on that, but it's important here:
The nC0 term was the 1 we just cancelled, and the nC1 term is empty due to the 4 we took common earlier.
So, from this statement, we can write the following:
nC1 is simply n, and C here is just representing the remaining part of M after taking 4 common again.
Again, we don't care about its value so long as it's an integer, which it is.
Then just plug in this value of M into the value of E:
Simplifying this:
See it now? The second term is just an integer, so we can finally write E as:
And we have proved that E is a multiple of 8 !!!!
How does it feel? Nice? This is a very good question for this concept of divisibility and using it to prove things!
I do realize that this method may have been a bit more unintuitive, but I figured it was the best one for bringing full circle the methods we have learnt so far in our discussion!
Try to solve it in another way as well for exercise!
1.5 Conclusion
And there you have it!
We started with the humble binomial expansion, unlocked the “star concept,” and leveled up to defeat a Cambridge Further Maths Boss Fight!
You’ve now got very powerful new weapons in your math inventory. These strategies make massive exponents completely trivial.
Next time a divisibility problem stands in your way, break it down, let the binomial theorem do the heavy lifting, and watch the remainders fall into place.
See y’all next week!
