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

4 Answers 4

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$ Commented Jul 3, 2019 at 18:04
  • $\begingroup$ @Thomas Browning : Nice, your way looks much easier. $\endgroup$
    – mathlove
    Commented Jul 4, 2019 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$ Commented Jul 4, 2019 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$ Commented Jul 2, 2019 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$ Commented Jul 2, 2019 at 4:47
  • $\begingroup$ Yes, you right, $j\mid (2^k-1)(2^ki+1)$. $\endgroup$ Commented Jul 2, 2019 at 15:30
  • $\begingroup$ Why does $i$ only go up to $k$ in your code? $\endgroup$ Commented Jul 2, 2019 at 16:41
  • $\begingroup$ Those six equations all look correct. Why do you call the fourth equation a Pell equation? $\endgroup$ Commented Jul 2, 2019 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .