2
$\begingroup$

On this OEIS page, it is claimed that the number $2^n+3^n$ can never be a perfect square for positive integer $n$. Can you prove not only this claim, but also the following stronger statement?

$2^n+3^n$ can never be the square of a rational number for any (not necessarily positive) integer value of $n$.

The proof should be simple, involving only basic modular arithmetic and not more abstract concepts such as quadratic residues.

$\endgroup$
  • $\begingroup$ Both solutions below use quadratic residues, are you sure there is a solution that doesn't use them? (Note that saying "no square is 3 mod 4" is exactly the same as saying "3 is a quadratic nonresidue mod 4"). $\endgroup$ – ffao Sep 30 '16 at 4:05
  • $\begingroup$ @ffao Ah, but saying "no square is 3 mod 4" is likely to be comprehensible to a layman, whereas discussing the abstract concept of a quadratic residue needs more advanced/specialised knowledge. The point of my endnote was that this question is doable with basic modular arithmetic and you don't need to know what quadratic residues are (even if you use them implicitly). $\endgroup$ – Rand al'Thor Sep 30 '16 at 14:42
6
$\begingroup$

For $n=0$, we have $2^n + 3^n = 2$, which is not a square of any rational number.

For positive n:

We have $2^n + 3^n = p^2$.

Taking the equation mod 4, we have that the right-hand side is either 0 or 1, and the left-hand side is 1 or 3.

So to have equality $p^2 \equiv 2^n + 3^n \equiv 1 \pmod{4}$, which implies $n$ is even. Letting $s = \frac{n}{2}$ we get

$$(2^s)^2 + (3^s)^2 = p^2 \\ (3^s)^2 = p^2 - (2^s)^2 \\ (3^s)^2 = (p - 2^s)(p + 2^s)$$

In the right-hand side both factors must be powers of 3. If none of them is 1, both are multiples of 3 and then their difference, $2 \times 2^s$, is a multiple of 3 as well. But $2 \times 2^s$ is not a multiple of 3, so one of the factors is 1.

From $p - 2^s = 1$ and $p + 2^s = 3^{2s}$, subtracting both equations we get $$(3^s - 1)(3^s + 1) = 2^{s+1}$$ But the only two powers of 2 two units apart are 2 and 4, from where we must have $s = 1$. We can check that this value of $s$ does not satisfy our original equation, so there are no solutions.

For negative n:

We have $2^{-n} + 3^{-n} = \frac{p^2}{q^2}$, with $p$ and $q$ coprime. This implies

$$q^2\frac{2^n + 3^n}{2^n3^n} = p^2$$

The right-hand side is an integer, so the left one must be as well. Furthermore, $2^n + 3^n$ and $2^n3^n$ are coprime, so we must have $q^2 = k 2^n3^n$, where $gcd(k,p)=1$. Substituting back:

$$k(2^n+3^n) = p^2$$

$k$ and $p$ are coprime and $k$ is a factor of $p^2$, so $k=1$ and we have $2^n+3^n = p^2$, which we already showed is impossible.

Bonus: What if we had $2^x + 3^y$ instead of $2^n + 3^n$?

x or y is zero

If x is zero, then $3^y + 1 = p^2 \Rightarrow 3^y = (p-1)(p+1)$. As the only powers of 3 two units apart are 1 and 3, $p=2$ and we have $\boxed{2^0 + 3^1 = 2^2}$.

If y is zero, then $2^x = (p-1)(p+1)$. As the only powers of 2 two units apart are 2 and 4, $p=3$, and we have $\boxed{2^3 + 3^0 = 3^2}$

x and y have the same sign

If x and y are positive, then by the same reasoning as earlier we can set $x = 2s$ and $y = 2t$ to get $3^{2t} = (p-2^s)(p+2^s) \Rightarrow (3^t-1)(3^t+1) = 2^{s+1}$ and because the only powers of 2 differing by 2 are 2 and 4, we have that the only solution is $s=2, t=1$. From this we get $\boxed{2^4 + 3^2 = 5^2}$.

From our earlier deduction, we know that the case in which both are negative is deeply intertwined with the case in which both are positive, and $-x,-y$ can only be a solution if $x,y$ is a solution. And in fact, our only positive solution also works for the negative case: $\boxed{2^{-4} + 3^{-2} = \left(\frac{5}{12}\right)^2}$

x is positive and y is negative

Assuming $x$ is positive and $y$ is negative, we have:
$$\frac{2^x3^y + 1}{3^y} = \frac{p^2}{q^2} \\ 2^x9^t + 1 = p^2 \\2^x9^t = (p-1)(p+1)$$ From this, either $p-1=2^s$ or $p+1=2^s$.

  • $p-1 = 2^s$:
    $$2^s(2^s+2) = 2^x9^t \\ 2^{s-1} + 1 = 9^t \\ 2^{s-1} = (3^t-1)(3^t+1)$$ The only powers of two 2 units apart are 2 and 4, from where $s=4, t=1$ or $\boxed{2^5 + 3^{-2} = \left(\frac{17}{3}\right)^2}$.

  • $p+1 = 2^s$:
    $$2^s(2^s+2) = 2^x9^t \\ 2^{s-1} - 1 = 9^t$$ $2^{s-1}$ is 1 mod 3, from which $s-1$ is even. Say $s-1=2a$, then we have $$(2^a-1)(2^a+1) = 9^t$$ The only powers of three 2 units apart are 1 and 3, but then their product is not a power of 9. So this case is impossible.

x is negative and y is positive

Doing the same thing for $x$ negative and $y$ positive, we arrive at $$4^t3^y + 1 = p^2 \\ 4^t3^y = (p-1)(p+1)$$ and analyzing the same two cases we find the final solution $\boxed{2^{-4} + 3^1 = \left(\frac{7}{4}\right)^2}$. Those six are the only solutions possible.

$\endgroup$
  • $\begingroup$ don't we have 2^4+3^2? $\endgroup$ – JonMark Perry Sep 30 '16 at 5:22
  • $\begingroup$ your first proof is wrong too - we can have the first factor =1 $\endgroup$ – JonMark Perry Sep 30 '16 at 5:58
  • $\begingroup$ @JonMarkPerry yep, I saw that, should be ok now $\endgroup$ – ffao Sep 30 '16 at 6:07
  • $\begingroup$ another bonus you could try, for which a,b, a^n+b^n=p^2 is this impossible $\endgroup$ – JonMark Perry Sep 30 '16 at 6:56
  • 1
    $\begingroup$ I'd rather not go down that rabbit hole... $\endgroup$ – ffao Sep 30 '16 at 7:15
4
$\begingroup$

Consider the sequence:

$$ a_n=x^n+y^n $$

We can write this as a recurrence relation:

$$ \begin{align} a_n&=(x+y)\ a_{n-1}-xy\ a_{n-2} \\ a_n&=(x+y)\left(x^{n-1}+y^{n-1}\right)-xy\left(x^{n-2}+y^{n-2}\right) \\ a_n&=x^n+xy^{n-1}+x^{n-1}y+y^n-x^{n-1}y-xy^{n-1} \\ a_n&=x^n+y^n \end{align} $$

We are given $x=2,\ y=3$, so:

$$ \begin{align} a_n&=5a_{n-1}-6a_{n-2} \\ a_0&=2 \\ a_1&=5 \end{align} $$

Now consider the sequence modulo $15$:

$$ \begin{align} a_0&=2 \\ a_1&=5 \\ a_2&=13 \\ a_3&\equiv 5 \\ a_4&\equiv 7 \\ a_5&\equiv 5 \\ a_6&\equiv 13 \end{align} $$

Since the recurrence relation depends only on the two previous terms, and the two terms $a_5$ and $a_6$ are the same as $a_1$ and $a_2$, the sequence (modulo $15$) must repeat the four terms $5,13,5,7$ infinitely.


Now consider the sequence of squares,

$$ b_n=n^2 $$

Again we write this as a recurrence relation:

$$ \begin{align} b_n&=3b_{n-1}-3b_{n-2}+b_{n-3} \\ b_n&=3(n-1)^2-3(n-2)^2+(n-3)^2 \\ b_n&=3n^2-6n+3-3n^2+12n-12+n^2-6n+9 \\ b_n&=n^2 \end{align} $$

...and consider the sequence modulo $15$. This time it goes for quite a bit longer before repeating:

$$ b_n=0,1,4,9,1,10,6,4,4,6,10,1,9,4,1,0,1,4\ldots $$

But like before, once the initial three terms come up again it must repeat the same sequence infinitely.


Now notice that all elements of $a_n\bmod 15$ are in $\{2,5,7,13\}$; and all elements of $b_n\bmod 15$ are in $\{0,1,4,6,9,10\}$. Since these two sets are disjoint, no member of $a_n$ can be a member of $b_n$; or, no number of the form $a_n=2^n+3^n$ can be a square (for nonnegative $n$).


(Work in progress; negative powers to come later)

$\endgroup$
1
$\begingroup$

Given that the statement holds true for integers and that $2^n + 3^n$ always results in an integer the question can be answered by proving this stronger claim:

The square root of an integer is never a non-integer rational number

For the proof of that I like to quote this answer here https://math.stackexchange.com/q/4468:


Theorem: If $a$ and $b$ are positive integers, then $a^{1/b}$ is either irrational or an integer.

If $a^{1/b}=x/y$ where $y$ does not divide $x$, then $a=(a^{1/b})^b=x^b/y^b$ is not an integer (since $y^b$ does not divide $x^b$), giving a contradiction.

I subsequently found a variant of this proof on Wikipedia, under Proof by unique factorization.

The bracketed claim is proved below.

Lemma: If $y$ does not divide $x$, then $y^b$ does not divide $x^b$.

Unique prime factorisation implies that there exists a prime $p$ and positive integer $t$ such that $p^t$ divides $y$ while $p^t$ does not divide $x$. Therefore $p^{bt}$ divides $y^b$ while $p^{bt}$ does not divide $x^b$ (since otherwise $p^t$ would divide $x$). Hence $y^b$ does not divide $x^b$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.