# How many rationals of the form $\large \frac{2^n+1}{n^2}$ are integers?

This was Problem 3 (first day) of the 1990 IMO. A full solution can be found here.

How many rationals of the form $\large \frac{2^n+1}{n^2},$ $(n \in \mathbb{N} )$ are integers?

The possible values of $n$ that i am able to find is $n=1$ and $n=3$, so there are two solutions and this seems to be the answer to this problem.

But now we have to prove that no more of such $n$ exists, and thus the proof reduces to: Proving that $n^2$ does not divides $2^n+1$ for any $n \gt 3$.

Does anybody know how to prove this?

• If 2|n then 2|2^n+1, therefore n is odd. – user16697 Jan 7 '12 at 20:05
• @QED:Yes, I have noticed that. – Quixotic Jan 7 '12 at 20:07
• It's useful to add it then. – user16697 Jan 7 '12 at 20:07
• @Geoff: Click here, scroll to bottom. – cardinal Jan 7 '12 at 21:36
• You tagged this contest math, what contest or preparation book are you talking about? – Will Jagy Jan 7 '12 at 21:43

This was Problem 3 (first day) of the 1990 IMO. A full solution can be found here.

• All that I find there today is "The network path was not found." archive.org doesn't have it cached either. – Peter Taylor Jan 11 '12 at 12:24
• I find the same here.The problem can be seen here – Quixotic Jan 11 '12 at 13:23
• The cached version, seem to be accessible as of now. – Quixotic Jan 11 '12 at 13:41
• The question asks for an integer, not a prime. Most of the calculations suppose that $n$ behaves like a prime. See my post, where $171 \mid 2^{171}+1$, and its square divides the third multiple of the second number. – wendy.krieger Jun 29 '13 at 11:13
• The argument I linked to (on the web site maintained by Scholes) is right. – André Nicolas Jun 29 '13 at 12:40

It's a bit late to post this answer. But I found this question can be solved using the Lifting the exponent lemma with so much ease.

Theorem: Let $x$ and $y$ be two integers and $n$ is an odd integer. Let $p$ be an od prime such that $p|x+y$ and none of $x$ and $y$ are divisible by $p$. Then we have,

$v_p(x^n+y^n)=v_p(x+y)+v_p(n)$

$v_p(N)$ denotes the highest power of $p$ which divides $N$.

Solution:

Claim: If $n$ divides $2^n+1$ then $n$ is a perfect power of $3$.

Proof:

Let $p$ be a smallest prime factor of $n$,

That means $2^n \equiv -1 \pmod p \implies 2^{2n} \equiv 1 \pmod p$. And also $2^{p-1} \equiv 1 \pmod p \implies 2^{\gcd(2n,p-1)} \equiv 1 \pmod p$

Now, since $p$ is the smallest divisor of $n$ the $\gcd(2n,p-1)=2 \implies 2^2 \equiv 1 \pmod p \implies p=3$, therefore, $n=3^m \cdot k \text { and } 3 \nmid k$, if $k$ is greater than $1$, the similar argument would show $3 |k$. Contradiction.

So we have $3^{\alpha} || n \implies 3^{\alpha+1} \nmid n$

$v_3(2^n+1) \ge v_3(n^2)$

$v_3(2+1)+v_(n) \ge v_3(n^2)$

$1+ \alpha \ge 2\alpha \implies \alpha =1,0$

$\implies v_3(n)=1,0$

$n=1 \text{ or } 3$

• The logic here is flawed. It relies on $p$ being prime. The question asks for any integer. The examples i give with $55$ and $171$ are pointing in the right direction. – wendy.krieger Jun 29 '13 at 10:09
• @wendy.krieger: $171^2 \nmid 2^{171}+1$ and also $55^2 \nmid 2^{55}+1$. I didn't consider $n$ as a prime. I considered a prime which divides $n$ which turns to be only $3$. – Inceptio Jun 29 '13 at 14:00
• There is the condition $p|x+y$ in your lemma, which means $p|2 + 1 = 3$ in this case when you use the lemma. Doesn't seem to cover many $p$ I think. – user27126 Jun 29 '13 at 18:12
• The case where you go from $2^n+1$ to $2+1$ is where the proof is flawed. $55$ requires $2^5+1$, and $171$ requires $2^9+1$. – wendy.krieger Jun 30 '13 at 5:20
• Wait! Sanchez is right. The LTE lemma requires $p|x+y$, which is not usually the case here. :( – Potato Jun 30 '13 at 7:58

I've translated the handling of the problem into a certain notation, which I find very useful for formal algebraic manipulation of exponential diophantine problems, and provide a solution in that formalism. The Woeginger-solution was already linked by André Nicolas so my proposed way of solving this is now only for that reader who might be interested into that -hopefully: much general- formalism. Here is the link so far. (I'm a bit lazy to recode the text into latex/mathjax here after the original fiddling with word/word-to-pdf. Maybe I can put it into mathjax after the weekend, if there is any interest at all)

• Of course, the link is flawed too. It does not prevent one from writing a product of several primes, ending in 3 or 1, base 8, the periods of which divide the product. Were such a set to exist, then their product would satisfy the relation. – wendy.krieger Jun 29 '13 at 10:32
• @wendy: what do you mean with "link is flawed"? I can access it immediately... – Gottfried Helms Jun 29 '13 at 11:24
• @Wendy: Didn't you read, that I did three steps: a) n is prime or power of a prime, b) n has two primefactors (or powers of two primefactors) c) n has three or more primefactors. In b) there was one possibility having n=3*7, but was excluded by one argument, and then case c) was also excluded for a solution.I don't know what the idea of your critics is? – Gottfried Helms Jun 29 '13 at 13:21
• The proof is overly complex, and applies to base=2 only. A more general and shorter proof is in my post in this thread. – wendy.krieger Jun 30 '13 at 7:45
• @Wendy, I find it a bit rude, to write first "the proof is flawed" and after being asked "it is overly complex" - and even more, not to beg for pardon for or not to delete the wrong comment. This is not the site for such unconstructive attitude. – Gottfried Helms Jun 30 '13 at 8:17

Andre's modification of a wrong answer :)

If $n=3^k$, then

$$2^n+1=2^{3^k}+1=2^{3 \cdot 3^{k-1}}+1= (2^{3^{k-1}}+1)( 2^{2 \cdot 3^{k-1}}-2^{ \cdot 3^{k-1}}+1)$$

The second bracket is never divisible by $9$, thus by induction one can prove that $3^{2k-1}$ doesn't divide $2^n+1$.

Note: Since Geoff's answer was wrong, and this post doesn't make too much sense anymore, a simple observation:

If $n \neq 1$, then $3|n$.

Indeed let $p$ be the smallest prime divisor of $n$.

Then $2^{p-1} \equiv 1 \mod p$ and $2^{2n} \equiv (-1)^2 \equiv 1 \mod p$.

Thus $2^d \equiv 1 \mod p$ where $d=gcd(p-1,2n)$. But no prime factor of $p-1$ can divide $n$, since $p$ is the smallest one, thus $gcd(p-1,n)=1$. Hence $d |2$.

$2^d \equiv 1 \mod p$ implies now that $p=3$.

This proves that $n=3^km$ for some $k \geq 1$ and $m$ relatively prime to $3$. I wonder if the first argument can be modified for this case:

$$2^n+1=2^{3^km}+1=2^{3 \cdot 3^{k-1}m}+1= (2^{3^{k-1}m}+1)( 2^{2 \cdot 3^{k-1}m}-2^{ \cdot 3^{k-1}m}+1)$$

Since $9$ doesn't divide the second bracket we get that $3^{2k-1}$ must divide $(2^{3^{k-1}m}+1)$ and repeating I think we get $3^{k}$ divides $2^m+1$...

It is easy to prove that $2^m \equiv -1 \mod 9$ implies $3 |m$ (this follows from $2^3 \equiv -1 mod 9$ and $ord(2)=6$).

Hence $k=1$, and we must have $n=3 m$ with $gcd(3,m)=1$...

Now, lets try the same again.

Suppose by contradiction $m \neq 1$. Let $q$ be the smallest prime factor of $m$.

Then

$2^d \equiv 1 \mod q$ where $d=gcd(q-1,2n)$. But no prime factor of $p-1$ can divide $n$, excepting $3$, Hence $d |6$.

This implies that

$$2^6 \cong 1 \mod q \,.$$

Thus, the only possible values of $q$ is $q=7$.

But this is not possible since $2^{3m}+1 \equiv 1+1 \mod 7$, thus $7$ cannot divide $2^n+1$.

• Hmm. Did you try $k=2$? – cardinal Jan 7 '12 at 20:32
• Let $k=2$. We have $2^9+1=(27)(19)$. This is not divisible by $3^4$. – André Nicolas Jan 7 '12 at 20:33
• @N.S.: Your argument, turned around a bit, will work to show there is nothing beyond $3$. We need only verify that $x^2-x+1$ is never congruent to $0$ modulo $9$. – André Nicolas Jan 7 '12 at 20:36
• @N.S.: Only a detail was wrong, the factoring idea was a good one. So modification, to show $2^{3^k}+1$ is not even divisible by $3^{k+2}$, sounds better to me than deletion. – André Nicolas Jan 7 '12 at 20:47
• @N.S.: My comment said that $x^2-x+1$ is not divisible by $9$. It can be divisible by $3$, and indeed is when $x$ is an odd power of $2$. Can you change things? – André Nicolas Jan 7 '12 at 21:35

Since the links referenced in the question and answers are now mostly dead, I thought it would be worthwhile to cite the solution from the book The IMO Compendium, A Collection of Problems Suggested for The International Mathematical Olympiads: 1959 - 2009):

Let us assume $n>1$. Obviously $n$ is odd. Let $p \geq 3$ be the smallest prime divisor of $n$. In this case $(p-1,n)=1$. Since $2^n+1 \mid 2^{2n}-1$, we have that $p\mid 2^{2n}-1$. Thus it follows from Fermat's little theorem and elementary number theory that $p\mid (2^{2n}-1,2^{p-1}-1)=2^{(2n,p-1)}-1$. Since $(2n,p-1)\leq 2$, it follows that $p \mid 3$ and hence $p=3$.

Let us assume now that $n$ is of the form $n=3^kd$, where $2,3 \nmid d$. We first prove that $k=1$.

Lemma. If $2^m-1$ is divisible by $3^r$, then $m$ is divisible by $3^{r-1}$.

Proof. This is the lemma from (SL$97$-$14$) with $p=3, a=2^2, k=m, \alpha=1$, and $\beta=r$.

Since $3^{2k}$ divides $n^2 \mid 2^{2n}-1$, we can apply the lemma to $m=2n$ and $r=2k$ to conclude that $3^{2k-1}\mid n=3^kd$. Hence $k=1$.

Finally, let us assume $d>1$ and let $q$ be the smallest prime factor of $d$. Obviously $q$ is odd, $q\geq 5$, and $(n,q-1)\in \{1,3\}$. We then have $q \mid 2^{2n}-1$ and $q \mid 2^{q-1}-1$. Consequently, $q \mid 2^{(2n,q-1)}-1=2^{2(n,q-1)}-1$, which divides $2^6-1=63=3^2\cdot 7$, so we must have $q=7$. However, in that case we obtain $7 \mid n \mid 2^n+1$, which is a contradiction, since powers of two can only be congruent to $1,2$ and $4$ modulo $7$. It thus follows that $d=1$ and $n=3$. Hence $n>1 \Rightarrow n=3$.

It is easily verified that $n=1$ and $n=3$ are indeed solutions. Hence these are the only solutions.

And here is the lemma referenced from SL$97$-$14$, again it can be found in the same book:

Lemma. Let $a,k$ be positive integers $p$ an odd prime. If $\alpha \geq 1$ and $\beta \geq 0$ are such that $p^\alpha \mid a-1$ and $p^\beta \mid k$, then $p^{\alpha + \beta} \mid a^k-1$.

Proof. We use induction on $\beta$. If $\beta = 0$, then $\frac{a^k-1}{a-1}=a^{k-1}+\dots+a+1\equiv k \pmod{p}$ (because $a \equiv 1$), and it is not divisible by $p$.

Suppose that the lemma is true for some $\beta \geq 0$, and let $k=p^{\beta+1}t$ where $p\nmid t$. By the induction hypothesis, $a^{k/p}=a^{p^\beta t}=mp^{\alpha+\beta}+1$ for some $m$ not divisible by $p$. Furthermore, \begin{align} a^k-1&=(mp^{\alpha+\beta}+1)^p-1\\ &=(mp^{\alpha+\beta})^p+\dots+\binom{p}{2}(mp^{\alpha+\beta})^2+mp^{\alpha+\beta+1}. \end{align} Since $p \mid \binom{p}{2}=\frac{p(p-1)}{2}$, all summands except for the last one are divisible by $p^{\alpha+\beta+2}$. Hence $p^{\alpha+\beta+1}\mid a^k-1$, completing the induction.

It is interesting that everyone is considering that $n$ must be prime. $2^{55}+1$ and $55^2$ share a common factor of $121$, since when $n$ is composite, there is no need for the period to divide $n-1$.

One can see that $n$ can not be even, because the first number would be odd, and the divisor even. So, the numbers that divide some $2^e+1$, leave a remainder of '3' or '1', when divided by 8. In the example above, $121$ is $11^2$, and 11 is 3 modulo 8.

So, for example, $171$ divides $2^{171}+1$, and $171^2$ divides $3 \cdot(2^{171}+1)$.

There could exist several primes, of the form $p=1,3 \mod 8$, where the period divides the product, and thus would completely satisfy this relation. The proof of 'raising the powers' does not prevent the case of 2, as shown in the examples of $55$ and $171$ above, where one comes from the multiple of $11$, and $19$, and the other comes from the basic period.

# General Proof of $n^2 \mid b^n+1$

$1$. $n$ is odd for all $b$

Suppose $n$ is even, say $n=2e$, then we have $4 \mid 4e^2 \mid b^{2e}+1$. However, the last term is never a multiple of $4$, so $n$ must be odd.

$2$. Rule of descent.

Suppose that $p \mid n$ and $p \mid b^q+1$, then $q \mid n$.

This is because $p \not\mid b^x+1$ unless $q \mid x$. q either is 1, or has prime divisors. Put $p'$, $q'$ for each divisor of $q$, and repeat.

$2a$ The rule of ascent.

If for some $p \not\mid n$, that its $q \mid n$, then $pn$ is a further solution.

This is used to ascend from instances where $q=1$, ie $p \mid b+1$, as a general construction where allowed.

$3$ Rule of sevenites and repeaters.

If $p^m \mid n$, then $p^m \mid (b^n+1) /(b^q+1)$, and for $p^{2m} \mid b^n+1$, then $p^m \mid b^q+1$.

If $p \mid b^x+1$ then $p \mid (b^{px}+1 )/(b^x+1)$. This and $b^g+1 \mid b^{gh}+1$ for odd $g, h$, means that if $p^m \mid n$ then $p^n \mid (b^n+1)/(b^q+1)$.

$p \mid (b^{px}+1)/(p^x+1)$ repeats some $p$ before it. It is easy to show that $p^2$ won't work here except in one case of $p=2$. This means that if $p^m \mid n$, then it is needed that $p^m \mid b^q-1$. Repeaters are why $p^m$ can have periods. For example, 3 has a 2-digit period in base 2, and 9 has a 6-digit period, and 27 has an 18 digit period.

A sevenite is where if $p \mid b^n-1$, then so does $p^2$. See link below for sevenites to bases to $2112$ and $p<144000$.

http://z13.invisionfree.com/DozensOnline/index.php?showtopic=737

## Discussion

We see that the rule of descent means that it is only necessary to start from the divisors of $b+1$, which give $q=1$. Then we consider the divisors of $b^x+1$, where $x$ is an odd divisor of $b+1$. This means that $3, 7, 15, 31, \cdots$ have no further action, because there are no odd divisors > 1.

For $b=10$, we see that $b+1=11$, and that $10^{11}$ has divisors $11^2 \cdot 23 \cdot 4093 \cdot 8779$. The product of $11$ and any of these primes >11, will satisfy this relation. We also see that by the rule of descent, if $47$ works, then $23$ must also divide $n$. In fact, 23 brings in $47, 139, 2531$. $139$ in turn brings in $557$ and $2503$. The rule of descent applies here. So if $2531$ divides $n$ in $n^2 \mid 10^n+1$, then so must 23, 11. So $640343$ is a solution. It can be further multiplied by $139$ or $47$ or $4093$ or $8779$, because the descent paths are already there.

   1    11
11    23   4093  8779
23    47   139   2531
47   6299
139    557 2503


When $b+1$ is composite, as in $b=14$, one can descend to any of the divisors of $b+1$. This is the table of descent for $b=14$. As before, the numbers to the right are $p$ having the first as their $q$.

   1    3   5
3    61
5    71  101
15    811
61    90281
71    569  3620291
183    733  9151
213    1287799


The marker example here is $80$, where $80+1=3^4$. amd $80^3+1 = 3^5\cdot 7^2 \cdot 43$. One of the three's in $80^3+1$ is a repeater, but this means that any prime whose $q$ comes to a divisor of $3^4 7^2 43$ can be immediately multiplied to give an additional solution. Specifically $127 (q=21)$, $163 (q=81)$ and $883 (q=441)$ all work, as does any numner $3 | n | 3^4 7^2 43$. These, and several very large primes, all work in base $80$, with the usual rule of descent.

    1    3  3 3 3
3    7  7  43
7    29  4789 ..
21    127  ...
43    1721
81    163


## The rule of descent fails in $b=2$

When we start off with $2$, we have $2+1=3$, which allows us to consider the factors of $2^3+1$, other than $3$. But there are not any factors.

We could try to follow the rule of descent, noting that if $n$ is odd, then any prime that divides $n$ must be $1, 3$, mod $8$. The list starts $3$, $11$, $17$, $19$, $41$, $43$, $67$. If either $p$ or its derived $q$ is not factorised to this list, we can strike it out.

We see here the significance of the test for $55$ and $171$ in the previous posts. Both of these work for the larger prime, but fail on descent. This is the magic here. Their paths are broken, but they open the way for possible unbroken paths.

$11$ fails, since $q=5$ is not in the list. $19$ has $q=3*3$, both in the list, but we see by the rule of power, that if $3^2 \mid n$, then $3^2 \mid 2^1 +1$, which it doesn't. $17$ and $41$ yield even $q=4, q=10$. $67$ yields $33 = 3* 11$, but we see that $11$ implies $5$. $43$ yields $7$, not in the list.

Larger primes have a period larger than 10, so these $p$ can not divide, because $q$ has been disallowed.

There is no path of descent, so $3$ is the sole example.

• What are you trying to show by having $171^2| 3 \cdot 2^{171}+1$? Do you see that highest power of $3$ in $2^{171}+1$ is only $1$, but you have highest power of $2$ dividing $171$. – Inceptio Jun 29 '13 at 14:06
• @inceptio Actually, it's 3. We have $27 \mid 2^9+1 \mid 2^{171}+1$. We also have $19 \mid 2^9+1$ implies 19^2 \mid $2^{19 \cdot 9}+1$. So the statement i made was true. The proof fails $253^2 \mid 10^{253}+1$ which actully works. – wendy.krieger Jun 30 '13 at 2:28