Prove that the equation $3^k = m^2 + n^2 + 1$ has infinitely many solutions in positive integers.

Prove that the equation $3^k = m^2 + n^2 + 1$ has infinitely many solutions in positive integers.

I have found that this is true for the first $k$'s from 1 to 7 except 3 and 6.

I have tried algebraic manipulation and induction too and it doesn't seem to work. I believe induction won't work since there are exceptions.

If I am correct, the numbers $m^2$ and $n^2$ can only be of the form $3a+1$.

Do you have any ideas about how I should proceed with this? I would love a few hints. Thanks.

• Hint: proof that there is infinitely Pythagorean Triples, $z^2=m^2+n^2$ and $z^2=3^k-1$. – AsdrubalBeltran Mar 29 '16 at 14:15

EDIT(ELABORATION)

Note that $$(a^2+b^2)(c^2+d^2)=(ad+bc)^2+(ac-bd)^2 \tag{1}$$ Thus a product of two numbers that are a sum of $2$ squares is als0 a sum of two squares.

CLAIM

For all $t \in \mathbb{N}$, we have that $3^{2^{t}}-1$ is a sum of two squares.

PROOF

It is true when $t=1$ since $$3^{2}-1=2^2+2^2$$ Assume it is true when $t=a$. Note that for $t=a+1$, $$3^{2^{a+1}}-1=\left(3^{2^a} -1 \right) \left(3^{2^a}+1 \right)$$ By the inductive hypothesis, $3^{2^a} -1$ is a sum of two squares. Also, $3^{2^a}+1$ is a sum of two squares from . Thus, the inductive hypothesis is true when $t=a+1$ from $(1)$. We are done. The result follows, as $k=2^{t}$.

• $$3^{2^{n+1}} = 3^{2^n} \cdot 3^2$$ So? – TheRandomGuy Mar 29 '16 at 14:06
• No, $3^{2^{n+1}}=\left(3^{2^n}\right)^2$ @Dhruv – Thomas Andrews Mar 29 '16 at 14:07
• @ThomasAndrews That's equal to $$3^{2^n} \cdot 3^{2^n}$$ None of these is a sum of two perfect squares. I'm confused. – TheRandomGuy Mar 29 '16 at 14:11
• But you won't want $3^{2^{n+1}}$ to be the sum of two squares, you want $3^{2^{n+1}}-1$ to be the sum of two perfect squares, given that $3^{2^n}-1$ is. @Dhruv – Thomas Andrews Mar 29 '16 at 14:13
• Hint for the hint: what is $\Big(3^{2^{n+1}}\Big)^2 - 1$? – shardulc Mar 29 '16 at 14:13

Hint: Prove that if $a^2-1$ is a sum of two square, then $a^{4}-1$ is a sum of two squares.

Thus if $3^{2k}-1$ is the sum of two squares for some $k$, then so is $3^{2^nk}-1$ for any $n$. (You can also prove if $3^{2k}-1$ is the sum of two squares, then so is $3^{k}-1$.)

The hint given by MXYMXY is just the case $k=1$.

The case $k=5$ also has this property, because $$3^{10}-1=(3^5-1)(3^5+1)=8 \cdot 11^2\cdot 61=(11\cdot 22)^2 + 22^2$$ is the sum of two squares. So $3^{5\cdot 2^n}-1$ is always the sum of two squares.

• We also have $3^{26} = 253118^2 + 1574102^2 + 1$ and $3^{26} = 455002^2 + 1528018^2 + 1$. Solutions exist for many odd exponents of 3 as well, like 9, 13, 15, 19, 21, and 27. – shardulc Mar 29 '16 at 14:40
• They have to exist if they exist for even. For example, $3^{k}-1$ follows from $3^{2k}-1$, but not visa-versa when $k$ is odd. You need the even case to get the induction for an infinite class, but there are cases when $k$ is odd. – Thomas Andrews Mar 29 '16 at 14:46