# Is my proof correct? $2^n=x^2+23$ has an infinite number of (integer) solutions.

This is how I tried to prove it. Is it correct? Thanks!!

$2^n = x^2+23$

$x^2$ must be odd, therefore $x^2 = 4k+1$, where $k \in \mathbb{N}$.

$2^n=4k+24$

$k=2(2^{n-3}-3)$

Since $x^2=4k+1$,$\ \ \ \$ $k_1 = \frac{x_1^2-1}{4}$

and $k_2=\frac{(x_1+2)^2-1}{4}=\frac{x_1^2+4x_1+3}{4}$

If we substitute $x_1^2=4k_1 + 1$, we end up with:

$k_2=k_1 + \sqrt{4k_1+1} + 1$

Therefore, finding solutions of $k=2(2^{n-3} - 3)$ is comparable to

finding the solutions of $k+\sqrt{4k+1}+1=2(2^{n-3}-3)$

Let $p=2(2^{n-3}-3)$

Therefore, $(\sqrt{4k+1})^2=(p-k-1)^2$, so

$(p-k)^2 = 2(p+k)$

Since $p$ has an infinite number of solutions $(p-k)^2=2(p+k)$ also has an infinite number of solutions, which implies the the original does also.

• Why a downvote? – Ovi Jun 9 '13 at 3:21
• I don't know, maybe because someone wants you type all this stuff here – user42912 Jun 9 '13 at 4:33
• I believe the set of solutions is finite and rather small. Why do you think there are infinitely many? – Will Jagy Jun 9 '13 at 5:53
• @CameronWilliams Squares are all 0 or 1 mod 4. – Zach L. Jun 9 '13 at 6:27
• See Will Jagy's answer. If you prove this statement, you'd have disproved Pillai's conjecture, and thereby the abc conjecture, two big open conjectures in number theory. So not only is your proof wrong, even the statement you're trying to prove is (very probably) false. – ShreevatsaR Jun 9 '13 at 8:47

It can be seen by elementary means that the number of solutions is finite. Then we need only find the possible solutions. I give a heuristic first.
Consider the primefactorization of some expression $$f(b,n) = b^n - 1 = 2^{e_2} \cdot 3^{e_3} \cdot 5 ^{e_5} \cdots =\prod_{q \in \mathbb P} q^{e_q}$$ then we know by Fermat/Euler, that the occurence of the primefactors $q$ cycles when $b$ is fixed and $n$ is increasing. To make the actual value of the exponents explicite I've made myself used to the following notation:
Let's introduce the notations

• $[n:p]$ meaning $[n:p]=1$ if p divides n, and $[n:p]=0$ if not
• $\{n,p\}$ meaning the highest exponent, to which $p$ occurs in $n$

then any primefactor $q$ (where of course $[b:q]=0$ is assumed) occur in $f(b,n)$ at a smallest $n=\kappa_q$ first time and then cyclically with cyclelength $\lambda_q$. Here the "first time" and the cycle-length are identical, we'll see in the next step, where we use this for our actual problem, that they shall differ - but this does not spoil the power of the logic of the arguments.

Also, we denote the exponent, to which the primefactor $q$ occurs in $f(b,\kappa)$ as $\alpha$ such that

• $\{f(b,\kappa),q\}=\alpha_q$

getting now for instance for the primefactor $q=2$
$$f(b,n) = b^n - 1 = 2^{e_2} \cdot r$$ $\qquad \qquad$ (where $r$ is some possible remainder)

and $$e_2 = [n:\lambda_2](\alpha_2 + \{n,2\} )$$ We can then rewrite the complete expression $$f(b,n) =\prod_{q \in \mathbb P \\\ [b:q]=0} q^{ [n:\lambda_q](\alpha_q + \{n,q\})}$$

The key-observation is here the "valuation-brace" in the exponent, $$e_q = \ldots \{n,q \}$$ varies with n itself; so the multiplicity of some primefactor in $b^n-1$ occurs in the same variation as in $n$ only, so roughly $q^{e_q}$ grows with $n$ and not with $b^n$. The consequence of this is then, that increasing $n$ requires more and more additional primefactors and after a first solution, where $b^n-1$ may have only the single primefactor $q$ (to some power) this shall never happen again when $n$ increases. (This might be also related to the theorem of Szygmondi (correct spelling?).)

Now we turn back to our original question.
We can restate the same function, only fix $n=2$ and let $b$ vary and use another constant, so that we have $$g(x,2) = x^2 + 23 = 2^{e_2} \cdot 3^{e_3} \cdot 5^{e_5} \cdots = \prod_{q \in \mathbb P} q^{e_q}$$
The arguments about cyclicitiness and level of exponents of the primefactors $q$ are assentially the same, only that we have, that in general $\kappa \ne \lambda$ and also have $2$ disjunct cycles. Your question concerns the primefactor $q=2$ only, so we may look at the level of its exponents heuristically. We get for the first few $x$ the following table, where it is made in $4$ columns each consisting $g=g(x,2)$ and $e_2 =\{ g(x,2),2 \}$ to see the two "cycles". We read the table rowwise from left to right and then downwards for $x=1,2,3,4,5,...$ : $$\small \small \begin{array} {rr|rr|rr|rr} g & e_2 &g & e_2 &g & e_2 &g & e_2 &\\ \hline 24 & 3 & 27 & 0 & 32 & 5 & 39 & 0 \\ 48 & 4 & 59 & 0 & 72 & 3 & 87 & 0 \\ 104 & 3 & 123 & 0 & 144 & 4 & 167 & 0 \\ 192 & 6 & 219 & 0 & 248 & 3 & 279 & 0 \\ 312 & 3 & 347 & 0 & 384 & 7 & 423 & 0 \\ 464 & 4 & 507 & 0 & 552 & 3 & 599 & 0 \\ 648 & 3 & 699 & 0 & 752 & 4 & 807 & 0 \\ 864 & 5 & 923 & 0 & 984 & 3 & 1047 & 0 \\ 1112 & 3 & 1179 & 0 & 1248 & 5 & 1319 & 0 \\ 1392 & 4 & 1467 & 0 & 1544 & 3 & 1623 & 0 \\ 1704 & 3 & 1787 & 0 & 1872 & 4 & 1959 & 0 \\ 2048 & 11 & 2139 & 0 & 2232 & 3 & 2327 & 0 \\ \ldots \end{array}$$ Although the left part of each column increase dominated by g's quadratic term $x^2$, the right part, which contains the exponent of the primefactor $2$, follows only the pattern which is identical to that of increasing $x^1$ only. We can also identify the shifts; after we find the high exponent $e_2=11$ and see also, that this consumes the whole number $g=2048$ (which occurs at $x=45$) and constitute thus a solution for your question the previous and the next exponents vary as if $g$ would grow only linearly in steps of $8$ (=$2^3$) and thus $g(x,2)$ needs further primefactors besides $2^{e_2}$ to multiply up to its actual value, except for that finite number of (possible) exceptions (at most 2 because a parabola and a line can meet at most 2 times).

The same is true for the third column; here we have a solution for $g(x,2)=32$ where $e_2=5$ and no other primefactor is needed (which means actually $x=3$) , but again the growth of the g-values in the column is dominated by its quadratic term $x^2$ while the exponents of the primefactor $2$ grow only according to the linear term $x$, besides the offset and the scaling of the stepwith to $8=2^3$.

This is so far heuristic/observation. I cannot yet make the formal proof for the finiteness of the number of solutions; if it is possible I'll append it here - perhaps this is also the line of arguments of Pillai who was linked to in Will @Jagy's answer.

There are only finitely many solutions. Pillai's conjecture is overkill because it allows for all possible exponents simultaneously, whereas the solutions of $2^n = x^2 + 23$ must lie on one of the three curves $y^3 = x^2+23$, $2y^3 = x^2+23$, $4y^3= x^2+23$, each of which has finitely many integer points.

• Thanks, and I think I found out why my proof was wrong, I posted an answer myself. – Ovi Jun 9 '13 at 12:13
• Erick, I knew Pillai was overkill, but I have never been very clear about elliptic curves. – Will Jagy Jun 9 '13 at 18:29
• @WillJagy I confess I too could be more familiar with this area, but I was sufficiently confident that $cy^3-23$ has distinct roots, making it an elliptic curve. Alternatively, multiplying by an appropriate power of $2$ should turn these into good ol' Mordell curves (which $y^3 = x^2 + 23$ is already). – Erick Wong Jun 9 '13 at 20:00

I get $x=\pm 3$ and $x = \pm 45$ and that's it. It is likely that the set of solutions is finite, see PILLAI'S CONJECTURE There is a fine description of how Pillai's conjecture would be written by @ShreevatsR in comment below:

that "for fixed positive integers A,B,C the equation $Ax^n−By^m=C$ has only finitely many solutions $(x,y,m,n)$ with $(m,n) \neq (2,2).$" Here with $(A,B,C)=(1,1,23)$ it says that $x^n−y^m=23$ has finitely many integer solutions $(x,y,m,n).$ The OP's claim is that it has infinitely many integer solutions of the form $(2,x,2,n).$ This is probably false

Meanwhile, I can describe how to rapidly exhaust possible solutions, by my methods. We know that $n$ must be odd in $x^2 - 2^n = -23.$ So, take $n= 2t+1$ and make a new variable, $y= 2^t.$ The result is $$x^2 - 2 y^2 = -23.$$ The seed values are $(x,y) = (3,4)$ and $(x,y) = (-3,4).$ We want all solutions such that $y$ turns out to be a power of 2. Now, given a solution $(x,y),$ we get all possible solutions by repeatedly taking the result of applying an element of the automorphism group/isometry group/orthogonal group of $x^2 - 2 y^2,$ namely $$(3x-4y,-2x+3y).$$

Now, $y=4$ is a power of 2, so that is a start, with $x=\pm 3$

The first string is $$(3,4), (-7,6), (-45,32),(-263,186),(-1533,1084),(-8935,6318), \ldots$$ So this one gives $$(x = \pm 3, y = 4), \; \; \; (x = \pm 45, y = 32)$$ as successes

The other string is $$(-3,4),(-25,18),(-147,104), (-857,606),(-4995,3532),(-29113,20586), \ldots$$

So you can see how I became skeptical about there being any more solutions with $y$ a power of 2.

Note that Erick Wong has pointed out a proof as a simple application of elliptic curves.

Meanwhile, I am now awake, see KATY PERRY.

• Making this answer self-contained against linkrot: Pillai's conjecture is that "for fixed positive integers A,B,C the equation $Ax^n−By^m=C$ has only finitely many solutions $(x,y,m,n)$ with $(m,n)\ne(2,2)$." Here with $(A,B,C)=(1,1,23)$ it says that $x^n-y^m=23$ has finitely many integer solutions $(x,y,m,n)$. The OP's claim is that it has infinitely many integer solutions of the form $(2,x,2,n)$. This is probably false, as the more general Pillai's conjecture is still open; moreover it's said to follow from the even stronger ABC conjecture which is also still open / not definitively proved. – ShreevatsaR Jun 9 '13 at 8:31
• @WillJagy: please consider including some of ShreevatsaR's comment so that your answer is more self-contained. – robjohn Jun 9 '13 at 11:44
• @robjohn, I just quoted from the comment, which seems well worded to me – Will Jagy Jun 9 '13 at 18:30
• @ShreevatsaR, a fine summary. i quoted it in my answer, at robjohn's suggestion. Note that I had never heard of Pillai before last night, the thing reminded me of Catalan's cojecture so i looked that up on wikipedia. – Will Jagy Jun 9 '13 at 18:43

This seems wrong to me.

You went from $k_1 = \frac{x_1^2-1}{4}$ to $x_1^2 = 4 k_1^2+1$. Somehow the $k_1$ got squared.

This is not a correct proof.

Please learn how to enter math in $\LaTeX$.

• Even i think there is some mistake in this solution. If i had to take x as someting i will take it 2k+1. Here k cannot even be a fraction else x will be even. – Rohinb97 Jun 9 '13 at 7:25
• Thanks, but that was not the problem because the next line continues as if I've performed the substitution correctly. I posted an answer myself to why I think the proof was actually wrong. – Ovi Jun 9 '13 at 12:10

Here is another heuristic argument along probabilistic lines that there are finitely many solutions.

The distance between primes near $n$ is approximately $2\sqrt{n}$. Thus, the probability of a given integer $n$ to be a perfect square is approximately $\frac1{2\sqrt{n}}$. Summing the probability that $2^n-23$ is a perfect square gives \begin{align} \sum_{n=5}^\infty\frac1{2\sqrt{2^n-23}} &\le\frac16+\sum_{n=6}^\infty\frac1{2\sqrt{2^{n-1}}}\\ &=\frac16+\frac{\sqrt2+1}8 \end{align} According to the Borel-Cantelli Lemma, this indicates that the probability that there are finitely mny solutions is $1$.

Of course, this really proves nothing, because the same argument suggests that there are finitely many perfect squares of the form $2^n$, when in fact $2^n$ is a perfect square whenever $n$ is even. However, in the absence of proof to the contrary, this provides a decent guess.

• Revised my answer, great one. – Will Jagy Jun 9 '13 at 18:42

The substitution $x^2=4k^2+1$ was wrong because $x^2=4k+1$, but nevertheless the next line is correct as if I've substituted the correct thing. The actual problem of the proof comes from when I said "$p$ has infinitely many solutions". I was thinking that $p$ is just an integer, and clearly $2(2^{n-3}-3)$ outputs a positive integer when $n$ is at least $5$. That's why I said that $p$ has an infinite number of solutions. However, I did not realize that since $p=k+\sqrt{4k+a}+1$, I'm already assuming that $2(2^{n-3}-3)=k+\sqrt{4k+a}+1$ has an infinite number of solutions, which would be implied if I was actually correct.Therefore this is a circular argument. But I do have one question about a certain step. Was it correct when I said that finding solutions of $k=2(2^{n-3} - 3)$ is comparable to finding the solutions of $k+\sqrt{4k+1}+1=2(2^{n-3}-3)$?

• This should be included as an addendum to your question. It is not really an answer. – robjohn Jun 9 '13 at 12:48