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?
This was Problem 3 (first day) of the 1990 IMO. A full solution can be found here.
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&lt;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.