If $2^{2k}-x^2\bigm|2^{2k}-1$ then $x=1$ [duplicate]

I continue from Thomas Browning's (the author of the question) answer. We desire to show that

$$nx^2-4(n-1)y^2=1$$

has no solutions. Note that any solution must satisfy $\gcd(nx,y)=1$. We can rewrite the equation as

$$(nx)^2-4n(n-1)y^2=n,$$

so if

$$x^2-4n(n-1)y^2=n$$

has no solutions with $\gcd(x,y)=1$ then we're done. I'm going to prove that using the fact that

$$\frac xy\approx \sqrt{4n(n-1)}\approx 2n$$

and then squeezing the inequalities together and proving that they're too tight to hold. This corner of number theory is called Diophantine Approximation, and I happen to know about it. Start with

$$\sqrt{4n(n-1)}=[2(n-1);\overline{1,4(n-1)}]$$

This is easier to prove backwards. Let

$$t=2(n-1)+\frac 1{1+\frac 1{t+2(n-1)}}$$

and then it's easy to find that the positive solution is $t=\sqrt{4n(n-1)}$.

Also if

$$x^2-dy^2=n$$

then

$$\frac xy=\sqrt{d+\frac n{y^2}}=\sqrt{d}\sqrt{1+\frac n{dy^2}}$$

$$\frac xy-\sqrt{d}<\frac n{2\sqrt{d}y^2}$$

In our case $n>0$ and $d=4n(n-1)$ so

$$0<\frac xy-\sqrt{4n(n-1)}<\frac 1{4y^2\sqrt{1-1/n}}$$

Now from Hardy and Wright intro to number theory page 153:

Theorem 184. If

$$\left|\frac pq -x\right|<\frac 1{2q^2}$$

then $p/q$ is a convergent.

Note that when H&W say convergent they require it to be in lowest terms. Which is true of our previous expression, so $x/y$ is a convergent of $\sqrt{4n(n-1)}$. But the residues $x^2-dy^2$ left by a convergent $\frac xy$ to the continued fraction of $\sqrt d$ are periodic with the same period as the continued fraction itself. You can verify that when $d=4n(n-1)$ the residues are $1$ and $-4(n-1)$.

\begin{align*} [2(n-1)]&=\frac{2(n-1)}1 &(2(n-1))^2-4n(n-1)1^2&=-4(n-1)\\ [2(n-1);1]&=\frac{2n-1}1 &(2n-1)^2-4n(n-1)1^2&=1\\ [2(n-1);1,4(n-1)]&=\frac{8n^2-10n+2}{4n-3} &(8n^2-10n+2)^2-4n(n-1)(4n-3)^2&=-4(n-1)\\ [2(n-1);1,4(n-1),1]&=\frac{8n^2-8n+1}{4n-2}&(8n^2-8n+1)^2-4n(n-1)(4n-2)^2&=1\\ [2(n-1);1,4(n-1),1,4(n-1)]&=\frac{32n^3-56n^2+26n-2}{16n^2-20n+5}&(\dots)^2-4n(n-1)(\dots)^2&=-4(n-1) \end{align*}

So $n$ can never be a residue, therefore our equation has no solution.


I can reduce the problem to an infinite family of generalized Pell equations, which explains why the problem is hard. Maybe someone who is familiar with this corner of number theory can finish it off?

Let $y=2^k$. Then $y^2-x^2\bigm|y^2-1$. In other words, $$y^2-1=n(y^2-x^2)$$ for some $n\geq1$. Rearranging terms gives $$nx^2-(n-1)y^2=1.$$ It suffices to show that this equation has no solutions for $y$ even and $n\geq2$. Equivalently, it suffices to show that the equation $$nx^2-4(n-1)y^2=1$$ has no solutions for $n\geq2$.

For each $n\geq2$, this is a generalized Pell equation.

I plugged this generalized Pell equation into this solver for all $n\leq30$, and in each case there are no solutions.


Following from the OP's self-answer, the quadratic Diophantine equation $$nx^2-4(n-1)y^2=1\tag1$$ means that $nx^2\equiv1\pmod4$ which forces $n=4N+1$ as $x^2\equiv0,1\pmod4$. Thus $$(4N+1)x^2-NY^2=1$$ where $Y=4y$ so $Y^2\equiv4\pmod{4N+1}$ and $x^2\equiv1\pmod N$.

Suppose that $Y\equiv\pm2\pmod{4N+1}$. Then $y=(rn\pm1)/2$ and substituting into $(1)$ gives $$nx^2-(n-1)(rn\pm1)^2=1\implies x^2=r^2n^2-(r^2\mp2r)n\mp2r+1.$$ Let $x=rn-a$ so $$n=\frac{a^2\pm2r-1}{2ra-r^2\pm2r}=\frac1{4r^2}\left(2ra+r^2\mp2r+\frac{r^2(r\pm4)}{2a-r\pm2}\right)$$ which reduces to $$2^{k+3}=m+2r+\frac{r(r\pm4)}m$$ since $rn\pm1=2y$ and $y=2^k$.

Notice that this formulation is quite similar to your equivalency statement. The latter is derived from the system $sx=ty=4^k-1$ and $x+y=2^{k+1}$, which in turn is equivalent to solving $st=c(4^k-1)$ and $s+t=c\cdot2^{k+1}$. In the formulation above, we are looking for integers $s,t$ such that $st=r(r\pm4)$ and $s+t=2^K-2r$.