Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
@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

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
at the beggining, its a,m,n in naturals, not a,b,n, right? –  Integral Sep 12 '12 at 21:24
    
Thank you Hagen, your answer is very helpfull! –  Integral Sep 12 '12 at 21:31
    
@Integral: Oops, sure - thanks –  Hagen von Eitzen Sep 12 '12 at 21:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.