10
$\begingroup$

Suppose that $k\geq2$ and $0<x<y$ 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<x<y$ 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<x<y$. 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$.

$\endgroup$
8
  • $\begingroup$ 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$. $\endgroup$ – Thomas Browning Jun 17 '19 at 15:29
  • $\begingroup$ Another note: If $y=m(2^k-1)+1$ then $2^ky-1=(2^k-1)(2^km+1)$. $\endgroup$ – Thomas Browning Jul 1 '19 at 21:28
  • $\begingroup$ For $k=1$ the integer $2^k-1$ divides all integer. $\endgroup$ – Piquito Jul 2 '19 at 16:47
  • $\begingroup$ @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$. $\endgroup$ – Thomas Browning Jul 2 '19 at 16:50
  • 1
    $\begingroup$ 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$. $\endgroup$ – mathlove Jul 3 '19 at 16:42
3
+50
$\begingroup$

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$

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Browning Jul 3 '19 at 18:04
  • $\begingroup$ @Thomas Browning : Nice, your way looks much easier. $\endgroup$ – mathlove Jul 4 '19 at 7:24
  • $\begingroup$ 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$. $\endgroup$ – Dmitry Ezhov Jul 4 '19 at 9:47
1
$\begingroup$

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")")
            )
           )
          )
         )
        )
       )))
      )
     )
    )
   )
  )
 )
};
$\endgroup$
6
  • $\begingroup$ Why does $j$ divide $2^ki+1$? $\endgroup$ – Thomas Browning Jul 2 '19 at 4:19
  • $\begingroup$ 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$. $\endgroup$ – Thomas Browning Jul 2 '19 at 4:47
  • $\begingroup$ Yes, you right, $j\mid (2^k-1)(2^ki+1)$. $\endgroup$ – Dmitry Ezhov Jul 2 '19 at 15:30
  • $\begingroup$ Why does $i$ only go up to $k$ in your code? $\endgroup$ – Thomas Browning Jul 2 '19 at 16:41
  • $\begingroup$ Those six equations all look correct. Why do you call the fourth equation a Pell equation? $\endgroup$ – Thomas Browning Jul 2 '19 at 20:12
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.