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

This is the $$y=2^k$$ case of this question.

Suppose that $$k\geq1$$ and $$0 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$$?

• If my calculations are correct, this is true for $k\leq30$. – Thomas Browning Nov 12 '20 at 0:02
• I should point out that in the divisor formulation, the two divisors are necessarily coprime (proof in the original question), but their product might be smaller than $2^{2k}-1$. – Thomas Browning Nov 12 '20 at 0:57
• Update: I've checked this for $k\leq120$. – Thomas Browning Nov 15 '20 at 3:54
• Conjecture correct upto $k=150$ – Peter Nov 18 '20 at 13:29
• This is not very useful, but one can prove that if $x\gt 1$, then $x$ is odd satisfying $$\frac{\sqrt{2^{2k+3}+1}}{3}\le x\le \frac{2^{k+1}-\sqrt{2^{k+3}+17}+1}{2}$$ – mathlove Nov 19 '20 at 16:01

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.

• This looks promising. Unfortunately, the equation $x^2-4n(n-1)y^2=n$ could have solutions (e.g., $n=9$ or $n=25$, although it might just be when $n$ is an odd square). – Thomas Browning Nov 21 '20 at 18:53
• @ThomasBrowning You're totally right. I dropped an assumption about $\gcd(x,y)=1$ and then you get these solutions when $n$ is a square. In this case multiplying a solution of $x^2-4n(n-1)y^2=1$ by 9 on both sides. I was in a bit of a hurry because the bounty time ended a couple minutes ago. – Sophie Nov 21 '20 at 18:56
• Can't you use Theorem 5.1 from kconrad.math.uconn.edu/blurbs/ugradnumthy/pelleqn2.pdf to immediately deduce that $x/y$ is a convergent? – Thomas Browning Nov 21 '20 at 19:10
• @ThomasBrowning yes but that follows from theorem 184 immediately when $n>0$ and the one I used is also a lot more general. I just used the one I managed to recall when writing. I only had to look up that the constant you have to multiply $1/q^2$ by is $1/2$. I wondered if it was $1/\sqrt{5}$ but that's another theorem. – Sophie Nov 21 '20 at 20:14
• Sophie, there is a method due to Gauss and Lagrange that deals directly with the cycle of a "reduced" indefinite form $ax^2 + b xy + c y^2$ and finds, among other things, the numbers of smallest absolute value represented by the form. The form $\langle n,0,4-4n \rangle \approx \langle n,2n,4-3n \rangle$ which then has "digits" $-1,n,-1,2$ and minimum $4$ rather than $1$ In two books I know, Dickson's Introduction (1929) and Buell's Binary Quadratic Forms. – Will Jagy Dec 11 '20 at 3:01

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.

• Correct me if I'm wrong, but if this equation has a solution, then $n \equiv 1 \mod 4$. – Derek Luna Nov 21 '20 at 10:39
• If $n \equiv 1 \pmod 4$, then $y^2-1=n(y^2-x^2) \implies y^{2} \equiv y^{2}-x^{2} \pmod 4$ so that $x^{2} \equiv 0 \pmod 4$ and using your last equation this means that $0\equiv 1 \pmod 4$. So then modulo $4$ there are no solutions, and there are no solutions in general. I am wondering if I am making a silly mistake. Assuming this reduction of the problem is logically equivalent to what you wanted to prove in the first place. – Derek Luna Nov 21 '20 at 10:58
• 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\tag2$$ where $Y=4y$ so $Y^2\equiv4\pmod{4N+1}$ and $x^2\equiv1\pmod N$. – TheSimpliFire Nov 21 '20 at 11:48
• @TheSimpliFire , I thought only of the negative value of $k$ there... – Spectre Nov 21 '20 at 15:21
• @TheSimpliFire I have mentioned the rest. – Spectre Nov 21 '20 at 15:21

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

• Do you mean $Y=2y$? – Thomas Browning Nov 21 '20 at 18:12
• No. $4(n-1)y^2=4(4N+1-1)y^2=N(4y)^2$. – TheSimpliFire Nov 21 '20 at 20:25

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

• nice hint.... but is my answer also worth of being called a hint ? I am a bad beginner at number theory, but I have done the best of what I can.... – Spectre Nov 21 '20 at 11:53
• Why this is true? $(2^k-x,2^k+x)=1$? any hint? – C.F.G Nov 21 '20 at 16:10
• Assume $2^k-x=uv$ and $2^k+x=ut$ then $2^{k+1}=u(v+t)$ as the $x$ is odd then $u$, $v$ and $t$ are odd. So the $u$ should be $1$. – Gevorg Hmayakyan Nov 21 '20 at 16:14
• At line 7, shouldn't "and" be "or"? – C.F.G Nov 21 '20 at 17:36
• @Spectre sorry the answer is long, let me find a time to understand the details. – Gevorg Hmayakyan Nov 21 '20 at 17:45

For $$k\ge 1$$ and $$0, 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.

• I don't believe your answer is correct. $2^{2k}-x^2=pq\cdot stu$ is not the only possibility. it could be $2^{2k}-x^2=ps\cdot tu$ or $pst\cdot u$ or any other combinations. – C.F.G Nov 20 '20 at 19:23
• @C.F.G.--I agree, there are many possibilities. I was only ruling out a few of them to start with, namely cases where the prime factors remain unchanged in one of the addends but the other addend lacks one or more of the prime factors found in $2^{2k}-1$. I go on to make some observations about the remaining possibilities. – Edward Porcella Nov 21 '20 at 0:07
• @EdwardPorcella I think that there are still more possibilities than what you have considered. For example, you could remove some factors from $2^k-1$ and multiply some of those onto $2^k+1$. – Thomas Browning Nov 21 '20 at 3:52
• @ThomasBrowning he has already mentioned it..... – Spectre Nov 21 '20 at 4:24
• I tried to consider that. For $k=6$ I removed a $3$-factor from $2^k-1$, and then in the fourth permutation removed $7$ from $2^k-1$ and multiplied it onto $2^k+1$, and in the sixth permutation removed $3$ from $2^k-1$ and multiplied it onto $2^k+1$. Or is that not what you meant? – Edward Porcella Nov 21 '20 at 4:25

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.

1. 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.

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

## Edit : A Better Way to Deal With the Indivisibility Condition

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 :

1. $$(2u - m) > u - 1 \implies (u + x) > (u - 1) [\because m = u - x] \implies x > -1$$ - perfectly in line with our constraints.
2. $$(2u - m)< u - 1 \implies (u + x) < (u - 1) \implies x < -1$$, which is against our constraints.

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.

• It's not obvious that the fraction $\frac{(u+1)(u-1)}{m(2u-m)}$ is not an integer for all $m=1,3,5,\ldots,u-3$. – Thomas Browning Nov 17 '20 at 19:37
• @ThomasBrowning , which means I'd have to elaborate on that in the answer ? – Spectre Nov 18 '20 at 3:05
• @ThomasBrowning I think that you'll see the experimental proof of it if you try substituting values there... – Spectre Nov 18 '20 at 3:06
• I believe that it's true, but there's a difference between "experimental proof" and "proof" – Thomas Browning Nov 18 '20 at 3:11
• I don't think so, but that's the heart of the problem. – Thomas Browning Nov 18 '20 at 3:30

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

• I didn't understand your solution.. I am not a good beginner at number theory , so please help me understand... – Spectre Nov 20 '20 at 10:58
• Also, it will be good if you help me determine if my answer is also ok... – Spectre Nov 20 '20 at 10:59
• Where $(x- 1)$ and $(x+ 1)$ come from? – C.F.G Nov 20 '20 at 11:16
• The two products have no common divisors, so there would be common factors in their differences. $(2^n-1)-(2^n-x)$ gives n-1. – wendy.krieger Nov 21 '20 at 1:21
• @wendy.krieger , $(2^n - 1) - (2^n - x) = x + 1$, right ? Not $n - 1$, is it so ? – Spectre Nov 21 '20 at 6:15