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

  • $\begingroup$ 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$. $\endgroup$ – 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)$.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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