5

Find all positive integers satisfying $$\frac{2^n+1}{n^2} =k $$

where $k$ is a integer.

I can't just come up with a solution.

Avitus
  • 14,018
Apoorv Jain
  • 720
  • 1
    You should study the intersection of $y=2^n$ and $y=kn^2-1$, varying $k$ (and $n$). For example, if $k=3$, then you get the solution $n=1$. – Avitus Aug 18 '14 at 11:09
  • As I told I couldn't come up with any solution – Apoorv Jain Aug 18 '14 at 11:12
  • I suggest to draw $y=n^2-1$, $y=2n^2-1$ and $y=3n^2-1$ against $y=2^n$, for all $n>1$ (integers). What you are looking for is integer intersection points between the 2 curves. Can you find them in these cases? If $k>3$ then, looking at your diagram, you can infer that... – Avitus Aug 18 '14 at 11:16
  • Could you just post it in the answer with the graph – Apoorv Jain Aug 18 '14 at 11:17
  • Ok, I will write an answer. – Avitus Aug 18 '14 at 11:26

3 Answers3

2

This problem is extremely famous in world of Olympiad mathematics(It appeared in IMO 1990 , Problem-3) . This problem is famous, because it is also very easily solvable by use of Lifting the exponent lemma If you don't know about this lemma yet, then read this article, you will never regret.

Otherwise, see this.

Shivang jindal
  • 1,958
1

This is a special case of the Landau-Ostrowski Diophantine equation $$ ay^2+by+c=dx^n $$ with $x=2$, $y=n$, $c=-1$, $b=0$, $d=1$ and $a=k$, i.e., $kn^2-1=2^n$. It has the solutions $(n,k)=(1,3),(3,1)$. This follows, for example, from Theorem $L$ in the paper On the number of solutions of the generalized Ramanujan-Nagell equation by Y. Bugeaud.

In general, it has at most finitely many solutions $x,y$ $n\ge 3$, if $a,d\neq 0$ and $b^2-4ad\neq 0$, see Landau, Ostrowski: Proc. London Math. Soc. 19, no. 2, 276–280, (1920).

Dietrich Burde
  • 130,978
0

We want to find those $n\in\mathbb N$ (we exclude the $0$) s.t.

$$2^n=kn^2-1,$$

with integer $k$. To do so, we introduce the curves $y_1(n)=2^n$ and $y_k(n)=kn^2-1$, with real nonnegative variable $n$ and we study their intersections. We are interested in integer intersections. Let us do this.

  • $k = 0$

We are left to solve $2^n=-1$, which has no solution.

  • $k=1$

Let us study the integer solutions of $2^n=n^2-1$. It is easy to see that $n=3$ is the only solution. Uniqueness is proven geometrically; $y_1(n)=n^2-1$ is a monotone increasing continuous function, with $y_1(3)=2^3$, as claimed; it lies below $y(n)=2^n$ for all $n<3$, while for all $n>3$ we have $y_1(n)>2^n$ (draw a diagram to convince yourself).

  • $k=2$

Let us study the integer solutions of $2^n=2n^2-1$. To do so we notice that $y_2(1)=1$, while $y(1)=2$, and $y_2(2)=7$, while $y(2)=4$. As both functions are monotone increasing (and continuous), then their intersection point lies between $1$ and $2$: as it cannot be an integer, then we have no solution in this case.

  • $k=3$

This case is easier than the previous one, as $y_3(1)=2=y(1)$. So $n=1$ is an integer solution and it is the only one due to geometrical reasons as above (draw a picture).

  • $k>3$

We are left to solve $2^n=kn^2-1$ with $k>3$; as $y_k(1)=k-1>y(1)=2$ (we are considering $k>3$), then the intersection point between $y_k(n)$ and $y(n)$ lies between $0$ and $1$. It cannot be an integer and we have no solution in this case.

Avitus
  • 14,018