# 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$. Nov 12, 2020 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$. Nov 12, 2020 at 0:57
• Update: I've checked this for $k\leq120$. Nov 15, 2020 at 3:54
• Conjecture correct upto $k=150$ Nov 18, 2020 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}$$ Nov 19, 2020 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). Nov 21, 2020 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. Nov 21, 2020 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? Nov 21, 2020 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. Nov 21, 2020 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. Dec 11, 2020 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$. Nov 21, 2020 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. Nov 21, 2020 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$. Nov 21, 2020 at 11:48
• @TheSimpliFire , I thought only of the negative value of $k$ there... Nov 21, 2020 at 15:21
• @TheSimpliFire I have mentioned the rest. Nov 21, 2020 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$? Nov 21, 2020 at 18:12
• No. $4(n-1)y^2=4(4N+1-1)y^2=N(4y)^2$. Nov 21, 2020 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.... Nov 21, 2020 at 11:53
• Why this is true? $(2^k-x,2^k+x)=1$? any hint? Nov 21, 2020 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$. Nov 21, 2020 at 16:14
• At line 7, shouldn't "and" be "or"? Nov 21, 2020 at 17:36
• @Spectre sorry the answer is long, let me find a time to understand the details. Nov 21, 2020 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. Nov 20, 2020 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. Nov 21, 2020 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$. Nov 21, 2020 at 3:52
• @ThomasBrowning he has already mentioned it..... Nov 21, 2020 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? Nov 21, 2020 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$. Nov 17, 2020 at 19:37
• @ThomasBrowning , which means I'd have to elaborate on that in the answer ? Nov 18, 2020 at 3:05
• @ThomasBrowning I think that you'll see the experimental proof of it if you try substituting values there... Nov 18, 2020 at 3:06
• I believe that it's true, but there's a difference between "experimental proof" and "proof" Nov 18, 2020 at 3:11
• I don't think so, but that's the heart of the problem. Nov 18, 2020 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... Nov 20, 2020 at 10:58
• Also, it will be good if you help me determine if my answer is also ok... Nov 20, 2020 at 10:59
• Where $(x- 1)$ and $(x+ 1)$ come from? Nov 20, 2020 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. Nov 21, 2020 at 1:21
• @wendy.krieger , $(2^n - 1) - (2^n - x) = x + 1$, right ? Not $n - 1$, is it so ? Nov 21, 2020 at 6:15