When Is (2ⁿ + 1) Divisible by n²? | Math Olympiad Problems

"Physics & Astronomy"
21 followers
We're looking for all integers n that make this expression, 2 to the power of n plus 1,
all divided by n squared, also an integer.
This seemingly simple problem will take us on a journey through the elegant world of number theory.
Like any good detective, we'll start by examining the scene.
Let's test a few small numbers and look for clues.
For n equals 1, we get 2 to the first plus 1, divided by 1 squared, which is 3.
This is an integer, so n equals 1 is our first solution.
For n equals 2, we have 5 fourths, not an integer.
Now for n equals 3, 2 cubed plus 1 is 9, and 3 squared is 9.
The result is 1. We've found a second solution.
What about negative integers?
Let's represent n as negative k, where k is a positive integer.
We evaluate the terms.
2 to the negative k becomes 1 over 2 to the k, and negative k squared becomes k squared.
Next, we find a common denominator in the numerator of the complex fraction.
Finally, simplifying the fraction gives us 1 plus 2 to the k, all over k, squared times 2 to the k.
This key insight simplifies our search.
We only need to consider positive integers.
Now, we dive into the deep.
We'll use a powerful strategy, analyzing the properties of the smallest prime factor of n.
We already have n equals 1, so let's assume n is a solution greater than 1.
Every integer greater than 1 has a prime factor.
Let's call the smallest one p.
From our problem's condition, if n squared divides 2 to the n plus 1,
then p, as a factor of n, must also divide it.
Stated differently, 2 to the n is congruent to negative 1, modulo p.
So, let's square both sides of the congruence.
This simplifies to 2 to the power of 2n is congruent to 1, modulo p.
This brings in a crucial concept from group theory.
The order of 2 modulo p, which we'll call d.
This is the smallest positive integer such that 2 to the power of d is 1, modulo p.
The order of a number, a modulo p, is the smallest positive integer d,
such that a to the d is congruent to 1, modulo p.
For example, the order of 2 modulo 7 is 3, since 2 cubed is 8, which is 1 mod 7.
From our previous step, the order d must divide 2n.
However, since 2 to the n is congruent to negative 1, and not 1, d cannot divide n.
And let's not forget Fermat's little theorem.
It tells us that d must also divide p minus 1.
Fermat's little theorem says that if p is a prime and does not divide a,
then a to the p minus 1 is congruent to 1 modulo p.
This means the order of a modulo p must divide p minus 1.
Because we found its smallest prime factor is 3,
n cannot be divisible by 2, and therefore must be odd.
An odd number has zero factors of 2.
Since d divides 2n, but not n, d must have exactly one factor of 2.
Thus, d has the form 2k, where k is an odd divisor of n.
Substituting this back into our inequality from Fermat's little theorem,
we get 2k is less than or equal to p minus 1.
If k were greater than 1, it would have to be greater than or equal to p.
Chaining these inequalities together, we'd have 2p is less than or equal to p minus 1.
This leads to the absurd conclusion that p is less than or equal to negative 1.
Impossible for a prime.
Our assumption that k is greater than 1 must be false.
The only possibility is that k equals 1.
If k is 1, then d must be 2.
If the order of 2 modulo p is 2, that means p must divide 2 squared minus 1.
This simplifies to p dividing 3.
Since p is a prime number, the only possibility is p equals 3.
This is a monumental breakthrough.
If any solution in greater than 1 exists, its smallest prime factor must be 3.
We know it is a multiple of 3, but how many factors of 3 can it have?
The expression n squared hints that we need to be precise.
Let's write n as 3 to the k times m, where m is not divisible by 3.
In the language of p-adic valuation, our condition means the number of factors of 3
in n squared is less than or equal to the number of factors of 3 in 2 to the n plus 1.
Here, V sub 3 of x means the highest power of 3 that divides x.
For example, V sub 3 of 27 is 3, since 27 equals 3 cubed.
The number of factors of 3 in n squared is simply 2 times k.
Now we use the lifting the exponent lemma, or LTE.
This lemma tells us how to count the number of times a prime divides expressions like
a to the n plus b to the n when the prime divides a plus b.
To find the number of factors on the other side,
the lifting the exponent lemma is our perfect tool.
It tells us that the number of factors of 3 in 2 to the n plus 1
is exactly 1 plus k.
The number of factors we found, 1 plus k,
must be greater than or equal to the number of factors required, 2k.
This gives us our critical inequality.
Solving this leaves us with k being less than or equal to 1.
Since k must also be at least 1, there's only one possibility.
k must be exactly 1.
This powerfully constrains our solution.
Any solution n greater than 1 must be 3 times some number m,
where m is not a multiple of 3.
We are at the endgame.
We have solutions n equals 1 and n equals 3, where m is 1.
Could m be greater than 1?
Let's find out.
Assume for the sake of contradiction that m is greater than 1.
Like before, let q be its smallest prime factor.
Our condition is that n squared divides 2 to the n plus 1.
With n equal to 3m, this becomes 3m all squared,
divides 2 to the power of 3m plus 1.
By transitivity of division, if q divides the smaller number,
it must also divide the larger one.
So q divides 2 to the power of 3m plus 1.
This uses the transitivity of divisibility.
If q divides a and a divides b, then q divides b.
This allows us to pass divisibility from factors to the whole expression.
We can rewrite 2 to the 3m as 8 to the m, making the relationship clearer.
q must divide 8 to the m plus 1.
This means 8 to the m is congruent to negative 1, modulo q.
Again, we'll use the order, this time of 8 modulo q,
and we'll call it d sub q.
Again, the order of a number, a modulo q is the smallest positive integer d,
such that a to the d is congruent to 1 modulo q.
Following the same logic as before, d sub q must divide 2m, but not m.
It must also divide q minus 1.
The greatest common divisor, or GCD, of two numbers is the largest integer that divides both.
Here, it tells us the largest possible order d sub q can have,
since it must divide both 2m and q minus 1.
Since q is the smallest prime factor of m,
any prime factor of q minus 1 is smaller than q, and therefore cannot be a factor of m.
This means m and q minus 1 share no common prime factors.
Their GCD is 1.
This collapses the GCD of 2m and q minus 1 down to at most 2.
So, d sub q must divide 2.
The only remaining possibility is that the order must be 2.
An order of 2 means q divides 8 squared minus 1, which is 63.
The prime factors of 63 are 3 and 7, so q must be 3 or 7.
However, we defined m to be not divisible by 3,
so its smallest prime factor q cannot be 3.
If we test q equals 7, we see that 8 is congruent to 1 modulo 7.
This means 8 to the power m would be congruent to 1 modulo 7.
This contradicts our requirement that 8 to the m is negative 1 mod q,
because it would mean 1 is congruent to negative 1, which is false.
Our entire house of cards built on the assumption that m is greater than 1 has collapsed.
That assumption must be false.
Let's assemble our findings into a final, undeniable conclusion.
We proved that any solution greater than 1 must take the form
n equals 3m, with m not divisible by 3.
Then, we proved through contradiction that m must be 1.
This gives us the solution n equals 3.
Combining this with the solution n equals 1 that we found at the very beginning,
we are left with just two integer solutions.
1 and 3.
Thank you for joining me on this mathematical journey.
If you enjoyed this video, please like and subscribe for more content.
Until next time, keep exploring the wonders of mathematics.
