# Diophantine equation $3^n-1=2x^2$

How to solve a Diophantine equation like $$3^n-1=2x^2$$. One can easily see that the parity of $n$ and $x$ will be same and equation further can be seen taking if $$n\equiv0\pmod3\quad \text{then }x \equiv0\pmod{13}$$ but I don't know what to do further.

• This is equivalent to $\ 1+3+\ldots+3^{n-1} = x^2.\$ – Włodzimierz Holsztyński Sep 20 '16 at 11:05
• Right, so (decimal) $11^2$ is ternary $11111$. – Noam D. Elkies Sep 20 '16 at 15:39

This problem happens to have appeared on the Polish Mathematical Olympiad camp in 2015. Here is the official solution of the problem: (I use $m$ in place of $x$ because this is how the problem was stated there)

Suppose first $n$ is even, say $n=2k$. Then the equation is equivalent to $(3^k+1)(3^k-1)=2m^2$. Clearly $\gcd(3^k+1,3^k-1)=2$, so one of these numbers must be a perfect square (and the other one twice a perfect square). $3^k-1\equiv 2\pmod 3$, so it can't be a square, hence $3^k+1=t^2,3^k=(t-1)(t+1)$. Therefore, $t-1,t+1$ are powers of $3$. But they can't both be divisible by $3$, so $t-1=1,t=2$. This leads to solution $(m,n)=(2,2)$.

Now suppose $n$ is odd, say $n=2k+1$. Letting $t=3^k$ we get $3t^2-2m^2=1$. Setting $t=2v+u,m=3v+u$ (check $u,v$ are integers) we get the Pell's equation $u^2-6v^2=1$. Standard theory gives us that all its solutions are generated as follows: $$(u_0,v_0)=(5,2),(u_{i+1},v_{i+1})=(5u_i+12v_i,2u_i+5v_i).$$ From this we can get a recurrence for $t=t_i=2v_i+u_i$: $$t_{-1}=1,t_0=9,t_{i+2}=10t_{i+1}-t_i$$ Looking modulo $27$ and $17$, we find $$t_i\equiv 0\pmod{27}\Leftrightarrow i\equiv 3\pmod 9\Leftrightarrow t_i\equiv 0\pmod{17}$$ It follows that the only powers of $3$ in the sequence $t_i$ are $1,9$ which correspond to solutions $(1,1),(5,11)$.

So all the solutions are $(1,1),(2,2),(5,11)$.

Edit: This is a solution for positive integers. If we allow nonpositive integers, we also get $(0,0)$ and $(1,-1),(2,-2),(5,-11)$, but rather clearly no more.

A standard (although possibly not the most efficient) way to solve equations of this sort is to find all integer points on each of the elliptic curves $$E_1: X^3-1=2Y^2,\quad E_2:3X^3-1=2Y^2,\quad E_3:9X^3-1=2Y^2.$$ Next pick out the solutions that have $X$ equal to a power of $3$. These then give the solutions to your equation with $3^n=X$ and $x=Y$. Finding all integer solutions on elliptic curves with small coefficients is, these days, quite standard and is even built into many computer algebra systems.

• I agree. I fixed it. – Jeremy Rouse Sep 20 '16 at 12:46
• Magma gives that $E_{1}$, $E_{2}$ and $E_{3}$ have ranks $0$, $1$ and $2$ respectively. There is one integral point on $E_{1}$, giving $n = 0$. There is also one integral points on $E_{2}$, giving $n = 1$. Finally, there are two integral points on $E_{3}$, giving $n = 2$ and $n = 5$, respectively. – Jeremy Rouse Sep 20 '16 at 12:54
• On one hand this solution can be seen as somewhat... "lacking" (not sure what better word to choose), since it involves in a big part computer verification. On the other hand, I suppose this is how it is done these days :P – Wojowu Sep 20 '16 at 18:12
• By the way, not being an expert in elliptic curves, let alone computational aspects, how realistic is working these things out by hand? I know we have Nagell-Lutz which simplifies things a lot in rank zero case (assuming we know it's rank zero!), but how laborious would finding all the integer points be in general case? – Wojowu Sep 20 '16 at 18:15
• @Wojowu It wasn't meant to be a solution, per se, but to indicate (1) a possible of method of solution and (2) more importantly, to indicate to the OP that this equation fits into a general framework that has been much studied should one wish to pursue it further. So my answer was intended to aid the OP in doing research in this area, which I take to be an important function of MO. On the other hand, if the OP is really only interested in seeing a solution to this particular equation using elementary methods, which is also fine, then the solution that you posted is great. – Joe Silverman Sep 20 '16 at 18:43

This Diophantine equation arises naturally in coding theory, because $2x^2+1$ is the number of points in a ball of radius $2$ in the ternary Hamming space $\{0,1,2\}^x$. It is known that $3^5-1 = 2\cdot 11^2$ (which corresponds to the ternary Golay code) is the last solution.

A proof, using factorization in ${\bf Z}[\sqrt{-2}]$ (as suggested by Geoff Robinson) followed by Skolem's $p$-adic method, is given in the paper

Jungmin Ahn, Hyun Kwang Kim, Jung Soo Kim, Mina Kim: Classification of perfect linear codes with crown poset structure, Discrete Math. 268 (2003), 21-30.

• The equation is similar to the Ramanujan-Nagell equation $2^n-7=x^2$, which can be solved by factoring in $\mathbb{Z}[(1+\sqrt{-7})/2]$. This equation also arises naturally in coding theory, but I don't remember exactly how. – GH from MO Sep 20 '16 at 21:58
• Yes, in a very similar way: binary Hamming $2$-balls that contain $2^e$ points. But there the large solution (corresponding to the space of binary words of length $90$) does not actually come from a code. – Noam D. Elkies Sep 20 '16 at 23:17
• I ran many times into $\ 1+3+9+27+81 = 121\$ in the context of the multiperfect numbers (I call them baroque numbers). – Włodzimierz Holsztyński Sep 21 '16 at 2:07

W. Ljunggren proved in 1 that the Diophantine equation

$$\frac{x^{n}-1}{x-1} = y^{2}$$

doesn't admit solutions in integers $x>1, y>1, n>2$, except when $n=4, x=7$ and $n=5, x=3$. Since your equation can be rewritten as $$\frac{3^{n}-1}{3-1} = x^{2},$$ the aforementioned result of Ljunggren implies that its solutions in non-negative integers are $(n=0,x=0), (n=1,x=1), (n=2,x=2),$ and $(n=5,x=11)$.

Alternatively, you can find a solution to this problem via Pell equations on page 243 of the March issue of vol. 110 (2003) of the American Mathematical Monthly... After noticing that this problem made it sometime to the problems & solutions department of the AMM, I couldn't help but recall what Léo Sauvé, former editor of Crux Mathematicorum, said on one occasion: "it seems like all problems were published in the Monthly once..."

References

1. W. Ljunggren, Some theorems on indeterminate equations of the form $\frac{x^{n}-1}{x-1} = y^{q}$ (In Norwegian). Norsk. Mat. Tidsskr. 25 (1943), pp. 17--20.

2. On a result attributed to W. Ljunggren and T. Nagell, question 206645 in math-overflow.

Since $\mathbb{Z}[\sqrt{-2}]$ has unique factorization, I believe this is equivalent to proving that $( 1 + \sqrt{-2})^{n} = ( \pm 1 \pm x\sqrt{-2})$ for some integer $x$ . This happens if and only if $\sum_{k=1}^{\lfloor \frac{n}{2} \rfloor} (-2)^{k}\left( \begin{array}{clcr}n \\ 2k \end{array} \right) \in \{0,-2\}.$ I must admit that I do not see an easy resolution from this point.

Later edit: It suffices to consider the case $n > 2$, so we restrict to this case. We need $\sum_{k=1}^{\lfloor \frac{n}{2} \rfloor} (-2)^{k-1}\left( \begin{array}{clcr}n \\ 2k \end{array} \right) \in \{0,1\}.$ However, considering the parity of the left hand side, we need $\sum_{k=1}^{\lfloor \frac{n}{2} \rfloor} (-2)^{k-1}\left( \begin{array}{clcr}n \\ 2k \end{array} \right) =1$ if $n \equiv 2$ or $3$ (mod 4), or $\sum_{k=1}^{\lfloor \frac{n}{2} \rfloor} (-2)^{k-1}\left( \begin{array}{clcr}n \\ 2k \end{array} \right) =0$ if $n \equiv 0$ or $1$ (mod 4). Note that if $n > 2$ is prime, this forces the second possibility, and also $n \equiv 1$ (mod $4$).

I claim that $(n,x)=(0,0), (1,1), (2,2), (5,11)$ are the only solutions.

Let $f(n)=\sum_{k=0}^{\lfloor\frac{n}2\rfloor}(-2)^k\binom{n}{2k}$ and $g(n)=\sum_{k=0}^{\lfloor\frac{n-1}2\rfloor}(-2)^k\binom{n}{2k+1}$. Following up on Geoff Robinson's steps, we need to check $f(n)=\pm1$ for a solution $n$. Of course, this holds true if $n=0,1,2,5$ by direct calculations. From here on, we may assume $n\geq6$. On the other hand, $f(n)$ satisfies the recurrence $f(n+2)=2f(n+1)-3f(n)$. This offers the alternative formula $$f(n)=\frac{\lambda^n+\bar{\lambda}^n}2$$ where $\lambda=1+i\sqrt{2}$ and $\bar{\lambda}=1-i\sqrt{2}$ with $i=\sqrt{-1}$.

If $f(n)=-1$ then $\lambda^n+\bar{\lambda}^n=-2$. Since $\lambda\bar{\lambda}=3$, we get $\lambda^{2n}+2\lambda^n+3^n=0$ or that $(\lambda^n+1)^2+3^n-1=0$. Using $\lambda^n=f(n)+i\sqrt{2}g(n)$ and $f(n)=-1$, we arrive at $$g^2(n)=\frac{3^n-1}2.$$ From complex modulus, $\vert\lambda^n+\bar{\lambda}^n\vert=2$. Equivalently $\vert\bar{\lambda}\vert^n\vert \lambda^n\bar{\lambda}^{-n}+1\vert=2.$ Using $\lambda\bar{\lambda}=3$, we get $$\left\vert \frac{\lambda^{2n}+3^n}2\right\vert^2=3^n.$$ Now, let us look at the real and imaginary parts of the complex number \begin{align*} f(2n)+3^n= \Re(\lambda^{2n}+3^n)&=\Re((\lambda-1)(\lambda+1)+3^n+1) \\ &=\Re((-2+i\sqrt{2}g(n))(i\sqrt{2}g(n))+3^n+1) \\ &=-2g^2(n)+3^n+1=2, \end{align*} \begin{align*} \sqrt{2}g(2n)=\Im(\lambda^{2n}+3^n) &=\Im(\lambda^{2n})=\frac1{2i}(\lambda^{2n}-\bar{\lambda}^{2n}) \\ &=\frac1{2i}(\lambda^n-\bar{\lambda}^n)(\lambda^n+\bar{\lambda}^n) \\ &=-2\sqrt{2}g(n). \end{align*} Combining the above: $$\sum_{k\geq0}\binom{2n}{2k}(-2)^k=2-3^n, \qquad \sum_{k\geq0}\binom{2n}{2k+1}(-2)^k=-2\sum_{k\geq0}\binom{n}{2k+1}(-2)^k$$ leads to a contradiction. Therefore $f(n)\neq-1$.

A similar argument proves $f(n)\neq1$.

• Can you prove your claim – Subhash Chand Bhoria Sep 20 '16 at 11:24
• I need to think about it. – T. Amdeberhan Sep 20 '16 at 11:40
• Why is it much bigger? It is a sum of two numbers with the same absolute value, this could be small. – Fedor Petrov Sep 20 '16 at 14:32

http://arxiv.org/abs/1212.6306 of Granville talks about certain Lucas sequences in which every sufficiently large member has a primitive prime factor which occurs to an odd power. It may be possible to use this work to show that for $n \gt 6$ the equation $(3^n-1)/2 =x^2$ has no solutions.

Gerhard "Read It For Inspiration Anyway" Paseman, 2016.09.20.