11
$\begingroup$

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?

  • 0
    @Will Jagy:It's from my GRE/CAT preparation module which was prepared by someone I know, obviously the question didn't want to me to proof they only want the right answer.2012-01-08

6 Answers 6

12

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

  • 2
    The argument I linked to (on the web site maintained by Scholes) is right.2013-06-29
3

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$

  • 0
    @Inceptio This time, I take $p$ as the least prime divisor of $k$, and I reached $\gcd (2.3^m.k,p-1)=2.3^t$, where $t\leq m$. So,....?2017-08-22
2

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$.

  • 0
    I think i fixed it.. :)2012-01-19
2

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)

  • 0
    That the proof gives the correct result and theory, does not suppose that the process is flawed. One is reminded of the discussion between Bentley and Knuth, on the latter's writing of a program using literate programming. It proves the result, but it's a one-trick pony, and one takes little from it apart from that solution. It is of no help solving the same problem for say $n^2 \mid b^n-1$ in general, and supposes that in particular, that the rule of descent *must* apply, ie that a solution in $n$ primes must include $3$ also. You feel that a swifty has been pulled: that's its flaw.2013-07-01
0

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.

-2

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.

  • 0
    @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.2013-06-30