Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
This is the $y=2^k$ case of this question.
Suppose that $k\geq1$ and $0<x<2^k$ and $2^{2k}-x^2\bigm|2^{2k}-1$. Is it necessarily the case that $x=1$?
Equivalently: Suppose that there are two positive divisors of $2^{2k}-1$ which average to $2^k$. Is it necessarily the case that these two divisors are $2^k-1$ and $2^k+1$?
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$.
This is just a hint, which may be useful, not a full answer.
$$(2^k-1)(2^k+1)=(2^k-x)(2^k+x)t$$
From this we see that $x$ should be odd. And easy to prove that the $$(2^k-x,2^k+x)=1 $$ As the $2^k+x > 2^k-1$ and $2^k+x > 2^k+1$ for the $x>1$ then $$(2^k+x,2^k-1)=a > 1$$ and $$(2^k+x,2^k+1)=b > 1$$ and $(a,b)=1$ and $ab=2^k+x$.
Let assume that $$(2^k-1,2^k-x)=c$$ and $$(2^k+1,2^k-x)=d$$ then obviously $(a,c)=1$, $(a,d)=1$, $(b,c)=1$, $(b,d)=1$, $(d,c)=1$ and $cd=2^k-x$. And $a,b,c,d$ are odd. $$ac | 2^k-1$$ $$bd | 2^k+1$$ $$ab+cd=2^{k+1}$$ $$ab-cd=2x$$
From this it seems that there should be some solution, but probably for the $k$-s for which the $2^k-1$ and $2^k+1$ has enough divisors. In this scope it is also interesting to consider the Bang's theorem
For $k\ge 1$ and $0<x<2^k$, suppose$$(2^{2k}-x^2) | (2^{2k}-1)$$for some $x>1$, and hence that $2^{2k}-x^2$ is composed only of the prime factors of $2^{2k}-1$ but lacks one or more of them (or perhaps contains all of the distinct factors but with one or more of them to a lesser power).
Thus let$$2^{2k}-1=(2^k-1)(2^k+1)=pqr\cdot stu$$and suppose, for some $x>1$, that$$2^{2k}-x^2=pq\cdot stu$$and hence divides $2^{2k}-1$.
Then since for $x\ge1$,$$2^{2k}-x^2=(2^k-x)(2^k+x)$$and hence the sum$$(2^k-x)+(2^k+x)=2^{k+1}$$then$$pqr+stu=pq+stu=2^{k+1}$$which is impossible.
Hence it is clear that removing one or more prime factors from either $2^k-1$ or $2^k+1$, while leaving the other addend intact, must make their sum less than $2^{k+1}$. Still less can their sum be $2^{k+1}$ if one or more prime factors are removed from both $2^k-1$ and $2^k+1$.
The remaining possibility is that removing one or more prime factors from both $2^k-1$ and $2^k+1$ and re-arranging the remaining prime factors, might yield a sum $=2^{k+1}$.
E.g. for $k=6$, $(2^k-1)(2^k+1)=63\cdot65=3^2\cdot7\cdot5\cdot13$, and$$3^2\cdot7+5\cdot13=2^{k+1}=2^7$$Removing one $3$-factor and re-arranging the four remaining distinct prime factors in the seven possible ways we get$$3\cdot7+5\cdot13=86$$$$3\cdot5+7\cdot13=106$$$$3\cdot13+5\cdot13=74$$$$3+7\cdot5\cdot13=458$$$$5+3\cdot7\cdot13=278$$$$7+3\cdot5\cdot13=202$$$$13+3\cdot5\cdot7=118$$Noteworthy here is that all sums are odd multiples of $2^1$.
For $k=10$, removing one of the $5$-factors from $2^{2k}-1=1023\cdot1025=3\cdot11\cdot31\cdot5^2\cdot41$, I find the fifteen possible sums of two addends containing the remaining five distinct primes are all odd multiples of $2^2$.
If it could be shown, then, that all such sums dividing $2^{2k}-1$ are odd multiples of some power of $2$, and hence not equal to $2^{k+1}$, it would follow that, for $k\ge1$ and $x>1$, $2^{2k}-x^2$ does not divide $2^{2k}-1$.
This of course is not a full answer, but it lays out a possible approach.
If you'd love to, you may take it as a comment. I am just putting up a a try, so sorry if I were wrong.
$\because 0 < x < 2^k , x = 2^k - m$
$2^{2k} - x^2 \mid 2^{2k} - 1 \implies \dfrac {2^{2k} - 1}{2^{2k} - x^2} \in \mathbb{N}$ for now. You may place $\mathbb{Z}$ insteasd of $\mathbb{N}$ as well.
If $m$ is even(i.e., $m = 2n$):
$2^{2k} - x^2 = 2^{2k} - (2^k - 2n)^2 = 2^{2k} - 2^{2k} + 4 \times 2^k n - 4n^2 = 4n(2^k - n)$
$2^{2k} - 1$ is obviously odd, so its factors are odd and none of its factors are divisible by $4$, so we can easily reject the case that $m$ is even.
If $m$ is odd (i.e., $m = 2n - 1$):
$2^{2k} - x^2 = 2^{2k} - (2^k - (2n - 1))^2 = 2^{2k} - 2^{2k} + 2 \times 2^k (2n - 1) - (2n - 1)^2 = (2n - 1)(2^{k+1} - (2n - 1)) \longrightarrow(1)$
Let's put back the $m$ :
$(1) = m(2^{k + 1} - m)$
Let's take $u = 2^k, \implies (1) = m(2u - m)$ and the fraction becomes $\dfrac {u^2 - 1}{m(2u - m)} = \dfrac{(u + 1)(u - 1)}{m(2u - m)}$.
Obviously, for $(2u - m) \nmid (u \pm 1)$,$(2u - m) > (u \pm 1)$ ($\because x = 2^k - m = u - m, m \in [0,2^k)$ ; $m$ can never be $0$ so as to avoid the denominator from becoming $0$. Plus, the opposite [$(2u - m) < (u \pm 1)$] needn't always be true as $m = u + 1$ is a solution in that case)$\forall m : m \in [0, 2^k]$ even if $m \mid (u \pm 1)$ and hence, our objective here must be to find an $m$ that reverses or breaks the inequality. Since the denominator must be small enough (or even equal to the factors of the expression in the numerator) we can conclude from the inequality that $m(2u - m)\nmid (u^2 - 1) \space \forall m : m < u \pm 1$. Also, if $m > u \pm 1$, we get to see that $x \leq 0$ and that goes against our constraints that $0 < x < 2^k$. This simplifies things a bit and thus tells us that if we put $m = u \pm 1$, you'll get an integer quotient and out of the values we have for $m$, we can only take $m = u - 1$ since $0 < x < 2^k$ and $x = 2^k - m$. Thus we end up with $x = 1$ as the only solution.
This is not like a common approach of factoring $2^{2k} - 1$ into $2^k + 1$ and $2^k - 1$, and the denominator into $2^k + x$ and $2^k - x$ and matching corresponding parts (or using the fact that $(x -y)\mid (x^n - y^n)$. Here, we assume that we want more $x$'s and see if we can find them.
Note : I haven't mentioned about the variables I had to use here for substitution, so I'd like to mention it. The least significant variable is $n$, and I lay more of an emphasis is on $m$, since its value can directly affect that of $x$. The only thing : $m \in \mathbb{Z}$ while $n \in \mathbb{R}$.
I admit that this is not a perfect solution, but a weak indication to the fact that it is hard to find whether there exists other $x$ for which the divisibility holds for all $k$.
The condition I am referring to is the condition for which $(2u - m) \nmid (u \pm 1)$ if $m \mid (u \pm 1)$, as mentioned in the second case (i.e., $m$ is odd).
Since $(2u - m) \nmid (u \pm 1)$, we can consider two cases : $(2u - m) > (u \pm 1)$ and $(2u - m) < (u \pm 1)$ (I didn't take $(2u - m ) = u \pm 1$ since that gives only a straightforward answer $m = u \pm 1$).
To simplify these conditions, let's suppose that $m \mid (u + 1)$. Here, if $(2u - m)\nmid (u - 1)$ , let's take the two cases :
From 1. , we can see that the fraction can be simplified to $\dfrac{y(u + 1)}{(u + x)}$ (since $m \mid (u - 1)$, let $y = \dfrac{u - 1}m$; but $\because m = u - x,\dfrac{u - 1}{u - x}$ is only possible if $x = 1$ $\implies y = 1$) $ = \dfrac{u + 1}{u + x}$ which is possible only if $x = 1$.
Now , to prove why $x = 1$ is the only feasible value here :
Let $\exists k : k \in \mathbb{Z}, \space u + 1 \equiv 0 (\mod{u + k})$ and let's set $x = k$
If $k < 0$ (according to the fact that the factor of a number is lesser than or equal to itself) , $$u - k = u - (-|k|) = u + |k| > u - 1 \space \forall k$$ and thus the factor in the denominator gets bigger than the factor in the numerator.
If it is $u - 1 \equiv 0 (\mod{u + k})$ ($x = k$ as usual), $$u - k = u - (-|k|) = u + |k| \geq u + 1 \space \text{for} \space |k| \geq 1$$
Now since $u + |k| > u + 1$ for $|k| > 1$, the only value we can choose for $|k|$ is $1$.
The same thing can be applied by assuming $k > 0$:
If $k > 0$ and $u + 1 \equiv 0 (\mod{u + k})$, $$u - k \leq u - 1 \space \forall k \geq 1$$
If $k > 0$ and $u - 1 \equiv 0 (\mod{u + k})$, $$u - k < u + 1 \forall k$$
An experimental approach : suppose that $x$ has a value greater than $1$ for which $(u - x)\mid(u - 1)$. Since our $x > 1$, $(u + 1) < (u + x)$ thus making division impossible. Also, if $(u - x) \mid (u + 1)$, $(u + x) > (u - 1)$ for all $x > 1$ , again making division impossible.
From this point, we can say that only $x = 1$ is the only possible solution.
The equation resolves to $(2^k+x)(2^k-x) \mid (2^k+1)(2^k-1)$. Since we have the first factor larger than the rest, we would look for a common factor in $(x- 1)$ and $(2^k-1)$ or $(x+1)$ and $2^k+1$,
We could suppose that the first is a product of say $(ab)(cd)$, and that the second is a product of $(ac)(bd)e$, where $ac$ divides $2^k+1$ and $bd$ divides $2^k-1$. The common divisor between the first two and the last two factors, is $x+1$, and between the second and third, and the first and fourth, $x-1$.
But this common factor must also divide $2^k+1$ and $2^k-1$, and so must divide $2$.
So there is no other number which divides pairs of divisors (ie $2^k \pm 1$ and $2^k\pm x$).
