Solving a Diophantine Equation dealing with powers of 2

Question

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

Answer 1

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.

Answer 2

This is an incomplete answer...

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

Answer 3

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

Answer 4

Given $x^2-y^2=2^k\implies x^2=y^2+2^k\quad$ we have the Pythagorean theorem $A^2+B^2=C^2\quad $where

$A=m^2-n^2\quad B=2mn\quad C=m^2+n^2\\\implies A=y, B=2^k, C=x$

Side-B can be any multiple of $4$ such as in the triples $$(3,4,5)\qquad (15,8,17)\qquad (5,12,13), (35,12,37)\\ (12,16,20), (63,16,65)$$

$B=2^k\land 1\le n \le 2019\implies n\in\{2,3,4,\cdots,2019\}$ and $2^2\le B \le 2^{2019}.$ Notice that $B\not\in\{12,20,24,28,36...\}$ but this is not a problem.

Now we can find the triples for these values of $B$ by solving $B=2mn$ for $n$ and testing a defined range of $m$-values to find which yield integers. For example

\begin{equation} B=2mn\implies n=\frac{B}{2m}\qquad\text{for}\qquad \bigg\lfloor \frac{1+\sqrt{2B+1}}{2}\bigg\rfloor \le m \le \frac{B}{2}\ \end{equation} The lower limit ensures $m>n$ and the upper limit ensures $m\ge 2$ $$B=64\implies\qquad \bigg\lfloor \frac{1+\sqrt{128+1}}{2}\bigg\rfloor =6 \le m \le \frac{64}{2}=32\quad \\ \land \quad m\in\{8,16,32\}\implies n\in\{4,2,1\}$$ $$f(8,4)=(48,64,80)\qquad f(16,2)=(252,64,260)\qquad f(32,1)=(1023,64,1025)$$ Here we have $(x,y,k)=(80,48,6),(260,252,6),(1025,1023,6)$

The only problem here is the restriction on prime factors greater than $5$. For the example given only $(80,48,6)$ works. The larger the value of k, the harder it will be to find triples that meet this criteria, expecially since $2^{2019}$ contains over $600$ digits.

A little more testing shows that the following Pythagorean triples meet the criteria

$(3,4,5)\quad (12,16,20)\quad (48,64,60)\quad (192,256,320)\quad (768,1024,1280)\quad (3072,4096,5120)\quad (12288,16384,20480)$

It looks like a pattern where each B-value is 4-times the one before it but it does not hold up with $B=65536$ so testing is required for each triple.