# When $2^n + m$ is a perfect square

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.

-
Is $p$ just an integer, or a prime? The symbol $p$ is usually reserved for primes. – trb456 Sep 12 '12 at 15:40
You are right, im going to change this, p is not necessarily a prime. – Integral Sep 12 '12 at 15:45
What is special about this? You can test if a natural is square, and all squares $a^2$ can be written in this form in $\lfloor \log_2 a^2 +1 \rfloor$ ways (assuming $0 \in \mathbb N$). – Ross Millikan Sep 12 '12 at 15:49
@Ross Millikan is right: unless $p$ IS a prime, this isn't very interesting. – trb456 Sep 12 '12 at 15:54
@Integral For very large $m$, $n$ this will be an exceedingly rare event (assuming a reasonably uniform distribution). In this case you may want to use a probabilistic method to rule out cases quickly: for instance compute $2^n+m$ modulo products of small primes and check that the result is a quadratic residue. – Erick Wong Sep 12 '12 at 17:18

Assume $2^n+m=a^2$ with $a,m,n\in\mathbb N$, $0<m\le\sqrt{2^n}$.
If $n=2k$ is even, then $(2^k)^2=2^n<a$ 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$.