1
$\begingroup$

This problem showed up when I was doing some recreative math, but the problem was interesting itself and I found very difficult to solve.

Given $n\in\mathbb{N}$ and $m\in\mathbb{Z}$, the question is: There is a method to know if $2^n + m$ is a perfect square?

Thank you very much.

  • 0
    Thank you very much Erick.2012-09-12

1 Answers 1

4

Assume $2^n+m=a^2$ with $a,m,n\in\mathbb N$, $0.

If $n=2k$ is even, then $(2^k)^2=2^n and $(2^k+1)^2=2^n+2\cdot 2^k+1>2^n+m$, contradiction.

If $n=2k+1$ is odd, then $\left(\frac a{2^k}\right)^2=2+\frac m{2^{2k}}$, i.e. $\frac a{2^k}$ is a relatively good approximation for $\sqrt 2$. In fact with $\frac a{2^k}>\sqrt 2$ we find that $\frac m{2^{2k}}=\left(\frac a{2^k}\right)^2-2=\left(\frac a{2^k}+\sqrt2\right)\left(\frac a{2^k}-\sqrt2\right)>2\sqrt 2 \cdot\left(\frac a{2^k}-\sqrt2\right),$ hence $0<\frac a{2^k}-\sqrt2<\frac{m}{2^n\sqrt 2}\le \frac{\sqrt{2^n}}{2^n\sqrt 2}=\frac1{2^{k+1}}.$ Letting $a=\lceil2^k\sqrt 2\rceil$ will therefore lead to an instance of $2^n+m=a^2$ about 50% of the time. If we relax the restriction on $m$ to $m\le 2\cdot\sqrt{ 2^n}$, this rate will go up to 100%. For example $2^{59}+9092137 = 759250125^2$.

  • 0
    @Integral: Oops, sure - thanks2012-09-12