# Elementary Diophantine equation

Solve $(x+y)(xy+1)=2^z$ in positive integres. My attempts is to use $x+y=2^a$, $xy=2^b-1$ and therefore $x,y$ are the roots of the quadratic equation $w^2-2^aw+2^b-1=0$. I try to analyze its dicriminant but it seems to be a dead end...

• As I understand it, this question is equivalent to asking when $2^{2(a-1)} - 2^b + 1$ is a perfect square, with $a,b \in \mathbb{N}$. Commented Apr 16, 2013 at 13:57
• Jyrki's comment under their answer has basically demonstrated the way to translate the language of abstract algebra into a purely elementary one. This bounty is rather meaningless. Commented Dec 24, 2021 at 3:48
• @Saad : right ! and how come Jyrki's solution has never been accepted :-( ? Commented Dec 25, 2021 at 1:38

You have a good start in using uniqueness of factorization.

Because $xy+1\ge x+y$, we have $b\ge a$. Therefore $xy\equiv-1\pmod{2^a}$. As we also have $x\equiv-y\pmod{2^a}$, we can conclude that $$x^2\equiv-xy\equiv1\pmod{2^a}.$$

Assume that $a\ge3$. Then we know that the group $\mathbb{Z}_{2^a}^{\times}$ of units of this residue class ring is isomorphic to $C_2\times C_{2^{a-2}}$. Therefore there are exactly four elements of order two in this group, and they are easily seen to be the residue classes of $\pm1$ and $\pm1+2^{a-1}$. The same reasoning applies to $y$. As we know that $0<x,y<2^a=x+y$, the remaining possibilities are $\{x,y\}=\{1,2^a-1\}$ and $\{x,y\}=\{2^{a-1}-1,2^{a-1}+1\}$. Both of these work, the first choice leads to $b=a$ the latter to $b=2a-2$.

I leave the cases $a<3$ to you.

• If you want to avoid the use of that bit of group theory, then you can simply verify that if $2^\ell$ is the highest power of two dividing either $x-1$ or $x+1$, then $2^{\ell+1}$ is the highest power of two dividing $x^2-1$. Commented Apr 16, 2013 at 13:41
• In your hint $b$ hardly appears whereas you reduce mod $2^a$. Is $b$ uniquely determined by $a$ and the condition that $x$ and $y$ are integers? Commented Apr 16, 2013 at 14:04
• @Douglas: To each $a$ there are two possibilities for $b$ - corresponding to the two $\{x,y\}$ pairs. I edited the answer to make this clearer. Commented Apr 16, 2013 at 14:06

Hint: Your idea will work. The discriminant is $2^{2a} -4(2^b-1)$. For simplicity divide by $4$. We get $2^{2c}-4\cdot 2^b+1$. Now an analysis of size will bring the problem down to small cases. A useful fact is that there is no perfect square strictly between $x^2$ and $(x+1)^2$.

ETA: Jyrki's answer and comments already says this it turns out, and so he really should get the bounty.

Let $$x$$ and $$y$$ be positive integers satisfying $$x+y\ge 16$$. Then $$x+y$$ must be a power of $$2$$. Write then, $$x+y=2^a$$ for some $$a \ge 4$$. Then $$xy+1$$ must also be a power of $$2$$, and as the strict inequality $$xy+1 \ge x+y$$ for all such $$x,y$$, it follows that $$xy+1=(2^a-y)y+1 =2^b$$ $$= 2^ay -y^2+1,$$ where $$b$$ is an integer satisfying $$b>a$$. And so $$2^a| (y^2-1)$$. So from this it follows that $$2^{a-1}$$ divides one of $$y+1, y-1$$ [because $$4$$ can only divide one of $$y+1,y-1$$]. Likewise, $$2^{a-1}$$ divides one of $$x-1,x+1$$. So from this one can deduce WLOG that $$2^{a-1}$$ divides $$y+1$$ and $$2^{a-1}$$ divides $$x-1$$, as this is the only way $$x$$ and $$y$$ can sum to something that is $$0$$ mod $$2^a$$. As $$x+y=2^a$$ and both $$x$$ and $$y$$ are nonnegative integers, it follows that $$x$$ and $$y$$ must respectively satisfy either the equations $$x=2^{a-1}+1$$ and $$y=2^{a-1}-1$$, or $$y=2^a-1$$ and $$x=1$$.

However, for each positive integer $$a \ge 4$$, note that if on the one hand either $$x$$ and $$y$$ satisfy the respective equations $$x=2^{a-1}+1$$ and $$y=2^{a-1}-1$$, then $$(x,y,z)$$, with $$z=3a-2$$, is a solution: $$(x+y)(xy+1)=2^a((2^{2a-2}-1)+1) = 2^{3a-2}.$$ If on the other hand $$x=1$$ and $$y=2^a-1$$ then $$(x,y,z)$$, with $$z=2a$$ is also a solution: $$(x+y)(xy+1)=(1+y)(1+y)$$ $$=2^a×2^a =2^{2a}.$$

• Actually $x+y \le xy+1$ for any positive integers $x,y$. This can be readily checked; assume WLOG $x\ge y$. Then if $y=1$ then $xy+1=x+1=x+y$, and if $y\ge 2$ then $xy +1 \ge 2x +1 =x+x+1 > x+y$.
– Mike
Commented Dec 24, 2021 at 5:02
• Thanks for the not so academic solution: I will give Jyrki the bounty as you suggest. Have a nice day Commented Dec 24, 2021 at 14:13
• you reason for $x+y>=16$ and $a>=4$, but, does same reasoning not hold for $x+y>=8$ and $a>=3$ as well (i.e.: to find (3,5,7)) [where $x<=y$]? Finally if one considers positive to mean greater or equal to $0$ there are solutions (0,2^n,n) too. Current aswers seem to consider positive to mean strictly greater than $0$, which is fine. Commented Dec 24, 2021 at 17:11
• @FirstNameLastName, yeah, my condition $x+y \le 16$ is not really needed, I just put it in to be safe. But yes, $(x,y)=(1,1)$ works, as does $(x,y)=(1,3)$, and $(x,y)=(1,7), (3,5)$ works.
– Mike
Commented Dec 24, 2021 at 17:21

The idea of discriminant works nicely, as @Jyrki, @Andre and @Mike answered. Yet, I think of another (perhaps more "number theory"ish :) way.

First, the equation is symmetric in $$x$$ and $$y$$, hence without loss of generality, we assume $$x\ge y$$.

Since $$xy+1$$ divides $$2^z$$ and is not equal to $$1$$, then it should be even, meaning that $$x$$ and $$y$$ should both be odd. Let $$x=2a+1$$ and $$y=2b+1$$. A replacement yields $$4(a+b+1)(2ab+a+b+1)=2^z.$$ Since $$a+b+1$$ is a power of $$2$$, $$2ab+a+b+1$$ will too be another power of $$2$$ only if $$2ab=a+b+1$$ or $$2ab=0$$ (a simple proof follows from assuming contrary). The latter case yields $$b=0$$ (or $$a=0$$) which means $$y=1$$ and $$(x+1)^2=2^z$$. Therefore, a set of solutions is found among $$(x,y,z)=(2^u-1,1,2u)$$ (and obviously $$(x,y,z)=(1,2^u-1,2u)$$). The former case yields $${2ab=a+b+1\implies \\(2a-1)(2b-1)=3\implies \\(x-2)(y-2)=3\implies \\x=5,y=3\implies z=7 \\\text{ or } \\x=3,y=5\implies z=7 }.$$

In conclusion, all the solutions are $$(x,y,z){\in \left\{(2^u-1,1,2u):u\in\Bbb N\right\} \\\cup \left\{(1,2^u-1,2u):u\in\Bbb N\right\} \\\cup \left\{(3,5,7),(5,3,7)\right\} }$$

• Actually : any $(x,y)=(2^n-1,2^n+1)$ gives a solution where $z=3*n+1$. Proving these are only ones for $1<x<=y$ in a simple way is the harder part. Commented Dec 24, 2021 at 14:01
• You are right. The part saying "...only if $2ab=a+b+1$ or $2ab=0$ ..." gives a subset of solutions. I don't currently know whether or not it's possible the solve for the general case as easily, so I'll spend some time later to find it out. Anyway, thanks for the nice comment on my reply. Commented Dec 24, 2021 at 15:15