Solving a Diophantine Equation dealing with powers of 2

Let x and y be positive integers with no prime factors larger than 5. Find all such $$x$$ and $$y$$ which satisfy $$x^2-y^2=2^k$$ where the range of k is $$1\leq k\leq2019$$.

I managed to solve the equation for general solutions where $$(x, y)=(3 \times 2^z, 2^z)$$ and $$(x, y)=(5 \times 2^z, 3 \times 2^z)$$ for non-negative integers for $$z$$. However, I still have trouble finding the range of values for $$z$$ that fit the given range of $$k$$.

• For $(x,y)=(3\cdot 2^z,2^z)$, we have $2^k=x^2-y^2=(3\cdot 2^z)^2-(2^z)^2=2^{2z+3}$ which implies $k=2z+3$. – mathlove Dec 29 '18 at 6:41

Given (a,b) such that $$a^2-b^2=2^m$$, we just simply multiple by $$2^z$$ to get $$2^{m+z}$$. Any (x,y) can be represented as $$2^z \cdot (a,b)$$, so we need only consider this form.

To find all the unique tuples (a, b) that fit your requirements, note that they must be coprime. Also, a two cannot divide a or b, since if (a,b) is coprime, you’d get an odd difference. I’ll leave it to you to do the work from there.

edit: using Tob Ernack’s work with the idea of (a,b) tuples, we get the additional facts that $$a-2=b=2^i-1$$ for some integer i. Combining this constraint upon the others, solving and proving all valid tuples should be easy, I’ll finish working that out later.

First, we have the equation: $$x^2 - y^2 = 2^k$$ We define $$\nu_2(n)$$ to be the power of $$2$$ that divides $$n$$.

Now, assume that $$\nu_2(x) \neq \nu_2(y)$$. We divide our equation by $$2^{2\min(\nu_2(x),\nu_2(y))}$$. Then, we will have the LHS as an odd value, as one term would be even, and the other would be odd. Thus, we would have an odd power of $$2$$, that is, $$2^{k-2\min(\nu_2(x),\nu_2(y))} = 1$$. This would mean that the difference of two positive perfect squares is $$1$$. Contradiction.

Let $$\nu_2(x) = \nu_2(y) = t$$. Then, let $$x = 2^t \cdot p$$ and $$y = 2^t \cdot q$$. Here, $$p$$ and $$q$$ are odd. Let $$l = k-2t$$. By dividing by $$2^{2t}$$ : $$p^2-q^2 = 2^l \implies (p-q)(p+q) = 2^l \implies p-q = 2^{l_1} \space , \space p+q = 2^{l_2}$$ Again, we can note that if $$4 \mid p-q$$ and $$4 \mid p+q$$, then $$4 \mid (p-q) + (p+q) \implies 4 \mid 2p \implies 2 \mid p$$. However, this is wrong as $$p$$ is odd. Thus, it is not possible for both of $$p+q$$ and $$p-q$$ to be divisible by $$4$$. Since they are both even and powers of $$2$$, and $$p-q < p+q$$, we have $$p-q = 2$$.

Solving $$p-q = 2$$ and $$p+q = 2^{l-1}$$, we get $$p = 2^{l-2}+1$$ and $$q = 2^{l-2}+1$$. We are given the condition that $$x$$ and $$y$$ have no prime factors greater than $$5$$. Then, we can note that the only prime factors of $$p$$ and $$q$$ are $$3$$ and $$5$$. Moreover, as $$p-q = 2$$, we can have $$3$$ and $$5$$ only dividing one of $$p$$ and $$q$$. Thus, one of $$p$$ and $$q$$ is a power of $$3$$ and the other is a power of $$5$$.

Case 1: Power of $$5$$ is equal to $$1$$

Here, we have $$p > q$$ and as the power of $$5$$ is equal to $$1$$, we have $$q=1$$ which would give us $$p=3$$. Then, we would have the solution: $$(x,y,k) = (3 \cdot 2^t , 2^t , 2t+3)$$

Case 2: Power of $$5$$ is more than $$1$$

Here, we can note that $$p=2^{l-2}+1$$ and $$q = 2^{l-2}-1$$. We have: $$5 \mid 2^n \pm 1 \implies 2 \mid n$$ Thus, we have $$2 \mid l-2$$. Then, $$3 \mid 2^{l-2}-1$$.

Now, we get $$p= 2^{l-2}+1 = 5^m \implies 2^{l-2} = 5^m-1$$. By lifting the exponent lemma: $$\nu_2(5^m-1) = \nu_2(5-1) + \nu_2(m) = \nu_2(m) + 2 \implies 2^{l-4} \mid m$$ This shows that $$m \geqslant 2^{l-4}$$. Hence: $$2^{l-2} = 5^m-1 \geqslant 5^{2^{l-4}}-1$$ which is true only when $$l=4$$. In that case, we get $$p=5$$ and $$q=3$$, which shows: $$(x,y,k) = (5 \cdot 2^t , 3 \cdot 2^t , 2t+4)$$

Therefore, the only solutions are $$(x,y,k) = (3 \cdot 2^t , 2^t , 2t+3)$$ and $$(x,y,k) = (5 \cdot 2^t , 3 \cdot 2^t , 2t+4)$$.

We have the factorization $$x^2 - y^2 = (x+y)(x-y)$$ which allows rewriting the equation as $$(x+y)(x-y) = 2^k$$

Since $$\mathbb{Z}$$ satisfies the unique factorization property, both factors are powers of $$2$$ (note also that $$x \gt y$$ since this follows from the original equation).

So write $$x - y = 2^i$$ and $$x + y = 2^{k-i}$$ for some integer $$i$$.

We can solve the system of equations to find $$x = 2^{k-i-1} + 2^{i-1}$$ and $$y = 2^{k-i-1} - 2^{i-1}$$.

Now the only thing left is finding which values of $$i$$ work. It is easy to see that in order for $$x$$ and $$y$$ to be positive integers, we need $$k - i - 1 \gt i - 1$$ and also $$i \geq 1$$.

Therefore the set of solutions is parametrized by $$(x, y) = \left(2^{k-i-1} + 2^{i-1}, 2^{k-i-1}-2^{i-1}\right)$$ for $$1 \leq i \leq \lceil k/2 \rceil - 1$$.

You would now need to eliminate those which have prime factors larger than $$5$$.