# If $y^2-x^2\bigm|2^ky-1$ and $2^k-1\bigm|y-1$ then $y=2^k$ and $x=1$

Suppose that $$k\geq2$$ and $$0 and $$y^2-x^2\bigm|2^ky-1$$ and $$2^k-1\bigm|y-1$$. Is it necessarily the case that $$x=1$$ and $$y=2^k$$?

Equivalently (I prove equivalence at the end): Suppose that $$k\geq2$$ and $$m\geq1$$ and suppose that there are two positive divisors of $$(2^k-1)(2^km+1)$$ which average to $$m(2^k-1)+1$$. Is it necessarily the case that $$m=1$$ and that these two divisors are $$2^k-1$$ and $$2^k+1$$?

I've tested this up to $$y\leq10^{10}$$ but I haven't been able to make much progress with standard number theoretic techniques.

If $$k=1$$ then there are infinitely many solutions of the form $$x=y-1$$.

Let $$(1)$$ be the initial version of the problem and let $$(2)$$ be the supposedly equivalent version of the problem.

$$(2)\implies(1)$$: Suppose that $$k\geq2$$ and $$0 and $$y^2-x^2\bigm|2^ky-1$$ and $$2^k-1\bigm|y-1$$. We can write $$y=m(2^k-1)+1$$ for some $$m\geq1$$. Then $$2^ky-1=2^k(m(2^k-1)+1)-1=(2^k-1)(2^km+1)$$ so $$y-x$$ and $$y+x$$ are two positive divisors of $$(2^k-1)(2^km+1)$$ which average to $$y=m(2^k-1)+1$$. By $$(2)$$, $$y-x=2^k-1$$ and $$y+x=2^k+1$$. Then $$x=1$$ and $$y=2^k$$.

$$(1)\implies(2)$$: Suppose that $$k\geq2$$ and $$m\geq1$$ and suppose that there are two positive divisors of $$(2^k-1)(2^km+1)$$ which average to $$m(2^k-1)+1$$. Let $$y=m(2^k-1)+1$$. We can write the two divisors as $$y-x$$ and $$y+x$$ for some $$0. Thus, \begin{align*} y-x&\bigm|2^ky-1,\\ y+x&\bigm|2^ky-1, \end{align*} since $$2^ky-1=(2^k-1)(2^km+1)$$. Manipulating these divisibility relations shows that \begin{align*} y-x&\bigm|2^kx-1,\\ y+x&\bigm|2^kx+1, \end{align*} where $$\gcd(2^kx-1,2^kx+1)=1$$. Then $$\gcd(y-x,y+x)=1$$ so $$y^2-x^2\bigm|2^ky-1$$. We clearly have $$2^k-1\bigm|y-1$$. By $$(1)$$, $$x=1$$ and $$y=2^k$$. Then $$m=1$$ and the two positive divisors were $$2^k-1$$ and $$2^k+1$$.

• One note: $y-x\bigm|2^ky-1$ and $y+x\bigm|2^ky-1$ so $y-x\bigm|2^kx-1$ and $y+x\bigm|2^kx+1$. Since $2^kx-1$ and $2^kx+1$ are coprime, so are $y-x$ and $y+x$. – Thomas Browning Jun 17 '19 at 15:29
• Another note: If $y=m(2^k-1)+1$ then $2^ky-1=(2^k-1)(2^km+1)$. – Thomas Browning Jul 1 '19 at 21:28
• For $k=1$ the integer $2^k-1$ divides all integer. – Piquito Jul 2 '19 at 16:47
• @Piquito yes, if $k=1$ then the second divisibility is always true, so it reduces to the divisibility $y^2-x^2\bigm|2y-1$. – Thomas Browning Jul 2 '19 at 16:50
• I'm not sure if this helps, but one can prove that it is necessary that $y=\left\lfloor 1+\frac{x-1}{2^k-1}\right\rfloor(2^k-1)+1$. – mathlove Jul 3 '19 at 16:42

Too long to comment:

It is necessary that $$y=\left\lfloor 1+\frac{x-1}{2^k-1}\right\rfloor(2^k-1)+1$$

Proof :

We can write $$y-1=m(2^k-1)\tag1$$ where $$m$$ is a positive integer.

Also, $$y^2-x^2\mid 2^ky-1$$ implies $$2^ky-1-(y^2-x^2)\ge 0\tag2$$ From $$(1)(2)$$, we get $$2^k(m2^k-m+1)-1-(m2^k-m+1)^2+x^2\ge 0,$$ i.e. $$(2^k-1)^2m^2-2(2^k-1)(2^{k-1}-1)m-(2^k-2+x^2)\color{red}{\le} 0,$$ i.e. $$\small\frac{2^{k-1}-1-\sqrt{(2^{k-1}-1)^2+2^k-2+x^2}}{2^k-1}\le m\le \frac{2^{k-1}-1+\sqrt{(2^{k-1}-1)^2+2^k-2+x^2}}{2^k-1}\tag3$$

Since we have

$$\frac{2^{k-1}-1+\sqrt{(2^{k-1}-1)^2+2^k-2+x^2}}{2^k-1}\le \frac{2^{k-1}-1+(2^{k-1}-1+x)}{2^k-1}\tag4$$ and $$x\lt y=m2^k-m+1\implies \frac{x-1}{2^k-1}\lt m\tag5$$ it follows from $$(3)(4)(5)$$ that $$\frac{x-1}{2^k-1}\lt m\le 1+\frac{x-1}{2^k-1}$$ from which $$m=\left\lfloor 1+\frac{x-1}{2^k-1}\right\rfloor$$ follows.$$\quad\blacksquare$$

• Very nice! There is an easier way to get this, I think. Starting with $2^ky-1\geq y^2-x^2$, we get $y\leq2^{k-1}+\sqrt{2^{2(k-1)}+(x^2-1)}\leq2^k+x-1$. Also, $x<y$. Thus, $x<(2^k-1)m+1\leq2^k+x-1$. Your result follows. – Thomas Browning Jul 3 '19 at 18:04
• @Thomas Browning : Nice, your way looks much easier. – mathlove Jul 4 '19 at 7:24
• If $y>x>2^k$ then $\left\lfloor 1+\frac{x-1}{2^k-1}\right\rfloor>1$. And then we need proof $x<2^k$. – Dmitry Ezhov Jul 4 '19 at 9:47

Let $$y = 1 + (2^k - 1) i$$ and $$2^k y = 1 + (y^2 - x^2) j$$.

Then

1) $$2^k y - 1 = (2^k-1) (2^k i+1) = (y^2 - x^2) j$$,

2) $$(y-1) (y+i) = i j (y^2 - x^2)$$,

3) $$(-(2^k-1) + j (y^2 - x^2)) ((2^k i+1) + j (y^2 - x^2)) = i j (y^2 - x^2) 2^{2k}$$,

4) $$(2y(i j-1)-(i-1))^2 - (i j-1) i j (2x)^2 = (i - 1)^2 - 4 (i j-1) i$$,$$\quad$$ aka Pell equation,

5) $$(j (y - x) - 2^{k - 1}) (j (y + x) - 2^{k - 1}) = 2^{2 (k - 1)} - j$$,

6) $$(2^k-1) (-(2^k i+1) + (2 + (2^k-1) i) i j) = (x^2 - 1) j$$.

gp-code for verifing 5) (actually computable for $$2\le k<48)$$ :

ijk()=
{
for(k=2,1000, for(i=1,k,
m=2^k-1;
yo=1+m*i;
J=divisors(m*(2^k*i+1));
for(q=2,#J-1,
j=J[q];
z=2^(2*(k-1))-j;
D=divisors(z);
for(l=2,#D-1,
u=D[l]; v=z/u;
s=u+2^(k-1); t=v+2^(k-1);
if(s!=t,
if(s%j==0&&t%j==0,
y=(s+t)/2; x=abs(s-t)/2;
if(y==yo,
print(yo"    "k"    "i"    "j"    "s"    "t"    "x,"    "y)
)
)
)
)
)
))
};

Code for 4) (evaluate over numbers $$d=ij-1$$):

ijd()=
{
for(d=3, 10^6,
IJ= divisors(d+1);
for(l=1, #IJ,
i= IJ[l]; j= (d+1)/i;
D= d*i*j;
if(!issquare(D),
C= (i-1)^2-4*d*i;
Q= bnfinit('X^2-D, 1);
if(bnfcertify(Q),
fu= Q.fu[1]; \\print(fu);
N= bnfisintnorm(Q, C);
for(v=1, #N, n= N[v];
for(u=0, 100,
s= lift(n*fu^u);
X= abs(polcoeff(s, 0)); Y= abs(polcoeff(s, 1));
if(Y, if(X^2-D*Y^2==C, if(X==floor(X)&&Y==floor(Y), \\print("(X,Y) = ("X", "Y")");
if(Y%2==0,
x= Y/2;
if((X+i-1)%(2*d)==0,
y= (X+i-1)/(2*d); \\print("(x,y) = ("x", "y")");
if((y-1)%i==0,
k= ispower((y-1)/i+1, , &t),
if(k&&t==2,
if(2^k*y==1+(y^2-x^2)*j,
print("    i= "i"    j= "j"    k= "k"    (x,y)= ("x", "y")")
)
)
)
)
)
)))
)
)
)
)
)
)
};
• Why does $j$ divide $2^ki+1$? – Thomas Browning Jul 2 '19 at 4:19
• We have $(y^2-x^2)j=2^ky-1=2^k(1+(2^k-1)i)-1=(2^k-1)(2^ki+1)$ so $j\bigm|2^ki+1$ if and only if $2^k-1\bigm|y^2-x^2$ but I don't see why $2^k-1\bigm|y^2-x^2$. – Thomas Browning Jul 2 '19 at 4:47
• Yes, you right, $j\mid (2^k-1)(2^ki+1)$. – Dmitry Ezhov Jul 2 '19 at 15:30
• Why does $i$ only go up to $k$ in your code? – Thomas Browning Jul 2 '19 at 16:41
• Those six equations all look correct. Why do you call the fourth equation a Pell equation? – Thomas Browning Jul 2 '19 at 20:12

COMMENT.-We have $$2^ky-1=a(y^2-x^2)\\y-1=b(2^k-1)$$ where the given solution gives the identities $$2^{2k}=2^{2k}$$ and the equivalent $$2^k=2^k$$, not properly a system of two independent equations.

Suppose now a true (independent) system

The first equation gives a quadratic in $$y$$ $$ay^2+(-2^k)y+(-ax^2+1)=0$$ and the difference of the two equations gives another quadratic $$ay^2+(2^k-1)y+(b-ax^2-b2^k)=0$$ Assuming these two quadratics have both roots $$y$$ equal we finish because the coefficients should be proportional and the first ones are equal ($$a=a$$) so the absurde with the seconds coefficients. Then there are not a true system.

Missing the case in which the two quadratics have only one common root. A known necessary condition of compatibility for this is

$$(ac'-a'c)^2=(ab'-a'b)(bc'-b'c)$$ when the quadratics are $$ax^2+bx+c=0\\a'x^2+b'x+c'=0$$

I've finally solved it!

My solution to this question proves a generalized version.

To deduce this special case, set $$z=2^k$$, note that $$z$$ is divisible by $$4$$, and use Theorem 9 to conclude that $$y=z$$ and $$yz-1=y^2-x^2$$. Then $$y=2^k$$ and $$x=1$$ as desired.