Find all positive integers $n$ such that $4^n+6^n+9^n$ is a square. David Yang, Alex Zhu.
Problem
Source: ELMO Shortlist 2012, N1
Tags: modular arithmetic, quadratics, algorithm, number theory, number theory proposed
02.07.2012 07:19
math154 wrote: Find all positive integers $n$ such that $4^n+6^n+9^n$ is a square. David Yang, Alex Zhu. Solution: $(a)$ If $n=1$ False! $(b)$ If $n\geq 2$ We rewrite the equation as follow: $6^n+9^n=k^2-(2^n)^2=(k-2^n)(k+2^n)$ $\Leftrightarrow 3^n(3^n+2^n)=(k-2^n)(k+2^n)$ Since $4^n+6^n+9^n=k^2 \Rightarrow k$ is odd thus $k-2^n,k+2^n$ are both odd On the other hand $gcd(k-2^n,k+2^n)=gcd(k-2^n,2.2^n)=1$ (because $k-2^n$ is odd) But $3^n(3^n+2^n) \Rightarrow 3|LHS \Rightarrow 3|RHS$ therefore only one of $k-2^n,k+2^n$ which is divisible by $3$ (because from $(1)$ we have proven that $gcd(k-2^n,k+2^n)=1$ Case 1: $3|k-2^n \Rightarrow$ $k+2^n$ is not divisible by $3$ Therefore $3^n \mid k-2^n$ or $k-2^n\geq 3^n$ $(2)$ (because $3^n(3^n+2^n)>0 \Rightarrow k-2^n>0$) Because $k-2^n\geq 3^n$ and $3^n(3^n+2^n)=(k-2^n)(k+2^n) \Rightarrow 3^n+2^n\geq k+2^n \Rightarrow 3^n\geq k \Rightarrow 3^n>k-2^n$ which is contrary to $(2)$ Case 2: $3|k+2^n \Rightarrow$ $k-2^n$ is not divisible by $3$ Therefore $3^n \mid k+2^n \Rightarrow k+2^n=3^n.t$ ($t\geq 1$) And this implies $k-2^n=\dfrac{3^n+2^n}{t} \Rightarrow k-2^n+2.2^n=\dfrac{3^n+2^n}{t}+2.2^n$ $\Rightarrow k+2^n=\dfrac{3^n+2^n}{t}+2^{n+1}=\dfrac{3^n+2^n+2^{n+1}.t}{t}$ On the other hand. $k+2^n=3^n.t$ Thus $\dfrac{3^n+2^n+2^{n+1}.t}{t}=3^n.t \Rightarrow 3^n+2^n+2^{n+1}.t=3^n.t^2$ $\Leftrightarrow 2^{n+1}.t+2^{n+1}-2^n=3^n(t-1)(t+1)$ $\Leftrightarrow 2^{n+1}.(t+1)-2^n=3^n(t-1)(t+1)$ $\Leftrightarrow (t+1)(2^{n+1}-3^n(t-1))=2^n$ Since $2^n>0$ and $t\geq 1$ thus $2^{n+1}-3^n(t-1)>0 \Rightarrow 2^{n+1}>3^n(t-1)$ If $t=1 \Rightarrow (t+1)(2^{n+1}-3^n(t-1))=2^{n+2}>2^n$ FALSE! If $t>1 \Rightarrow 2^{n+1}>3^n(t-1)\geq 3^n \Rightarrow 2^{n+1}>3^n$ $(3)$ But we are considering $n\geq 2 \Rightarrow 2^{n+1}<3^n$ for all $n$ such that $n\geq 2$ and this is contrary to $(3)$ then we eliminate this case Answer: No solution
02.07.2012 10:00
Taking $\pmod5$ it is clear that $n$ is odd. Now take $\pmod{13}$. By Fermat's little theorem $6^{13}\equiv6\pmod{13}$. As $13|4^n+9^n$, we just check if $6^{2k+1}$ is a quadratic residue $\pmod{13}$ for $k=0,1,2,3,4,5$ We get remainder $6, 8, 2, 7, 5, 11$, none of which is a quadratic residue $\pmod{13}$, and so there are no solutions.
05.07.2012 05:43
$6^{2k+1} = (6^k)^2 \cdot 6$, so to check that $6^{2k+1}$ is never a residue, it's enough to check that 6 isn't a residue.
06.07.2012 03:04
Pretty simple: Take it $\mod 5$ and it's clear that $n=2k+1$ for some $k$. Therefore, $(3^{2k+1}+2^{2k+1})^2-3^{2k+1}2^{2k+1}=x^2$ for some odd $x$, so $(3^{2k+1}+2^{2k+1}+x)(3^{2k+1}+2^{2k+1}-x)=3^{2k+1}2^{2k+1}$. The division algorithm yields $gcd(3^{2k+1}+2^{2k+1}+x, 3^{2k+1}+2^{2k+1}-x)=2$, so $3^{2k+1}+2^{2k+1}+x=2(3^{2k+1})$, $3^{2k+1}+2^{2k+1}-x=2^{2k}$ or $3^{2k+1}+2^{2k+1}+x=2^{2k-1}3^{2k+1}$, $3^{2k+1}+2^{2k+1}-x=2$(no other arrangement is possible). Either way, different values of $x$ are attained from each of the expressions in each case. Hence there are no solutions.
06.07.2012 08:32
My solution. Checking modulo 5 we get $n$ is odd. Now, $4^n+6^n+9^n\equiv 4^n+6^n-4^n\equiv 6^n\pmod{13}$ $\begin{cases}6 ^1 \equiv 6\pmod{13}\\ 6^3\equiv 8\pmod{13}\\ 6^5\equiv 2\pmod{13}\\ 6^7\equiv 7\pmod{13}\\ 6^9\equiv 5\pmod{13}\\ 6^{11}\equiv 11\pmod{13}\end{cases}$ Check that $6^{12}\equiv 1\pmod{13}$ and that and the set of Quadratic Residues modulo $13$ is $\{0,1,3,4,9,10,12\}$. Hence done.
26.01.2019 22:05
without checking mods... Let expression equal $k^2$. Clearly $k$ is odd. Write $(3^n + 2^n)^2 - 3^n \cdot 2^n = k^2$, so that $\gcd(k, 3^n + 2^n)$ can only have $2$ or $3$ as prime factors. But $2, 3 \nmid 2^n + 3^n$ so $\gcd(k, 3^n + 2^n)=1$. Now write $(3^n + 2^n + k)(3^n + 2^n - k) = 3^n \cdot 2^n$. Check that $\gcd(3^n + 2^n + k, 3^n + 2^n - k) = 2$. In particular this forces $3^n + 2^n + k = 2 \cdot 3^n$ and $3^n + 2^n - k = 2^{n-1}$, for which no $k$ exists. $\Box$
07.09.2021 21:20
The quantity is not a square for $n=1,2,3,4$ so assume $n \geq 5$. Let the quantity equal $v^2$ and rewrite the problem as \[(2^n+3^n-v)(2^n+3^n+v)=2^n \cdot 3^n\]Now if we let $a=(2^n+3^n-v),b=(2^n+3^n+v)$ we have $ab=2^n \cdot 3^n$ and $a+b=2(2^n+3^n)$. Now note that from the second equation, $3$ does not divide $\gcd(a,b)$ so WLOG let $b=3^n \cdot x$. Now by induction, we can prove that $a+b=2(2^n+3^n)<3 \cdot 3^n$ so $x=1$ or $x=2$. Plugging both of these in shows that neither works, so no $n$ works, so we are done.
27.03.2022 04:47
Taking modulo $5,$ we see $(-1)^n+1^n+(-1)^n\equiv -1,3\pmod{5}.$ Only the former value on the RHS is a quadratic residue, so $n$ is odd. Taking modulo $13,$ we see $4^n+6^n+(-4)^n\equiv 6^n\equiv 6,8,2,7,5,11$ by FLT. The quadratic residues for modulo $13$ are $0,1,4,9,3,12,10$ so there are no solutions. $\square$
23.04.2022 21:52
$4^n+6^n+9^n=x^2$ If $n=2k$: $4^{2k}+6^{2k}+9^{2k} \equiv 6+6+1 \equiv 3$ (mod 10) If $n=2k+1$: $(2^{2k+1}+3^{2k+1}-1)^2<4^{2k+1}+6^{2k+1}+9^{2k+1}<(2^{2k+1}+3^{2k+1})^2$, Absurd that it is between two consecutive perfect squares. So there are no solutions
27.01.2023 21:08
By taking mod 5, we have $$(-1)^n + 1 +(-1)^n\equiv 0,1,4\pmod 5.$$Therefore, $n$ must be odd. Let $n=2m+1$. Note that the sum of odd powers $4^{2k+1}+9^{2k+1}$ is divisible by 13, so we must have $$6^n\equiv 0,1,3,4,9,10,12 \pmod{13}.$$However, listing out odd powers of 6 mod 13 until we reach 6^13, none of these appear, so there are no solutions and we are done. edit: took way too long because i kept trying to use $$(27^n-8^n)=k^2(3^n-2^n)$$to no avail
18.01.2025 22:20
We will prove that there are no solutions. For the sake of contradiction, suppose $4^n+6^n+9^n = k^2$. By rearranging the terms one might easily obtain $(k - 2^n)(k + 2^n) = 3^n(2^n + 3^n)$. Observe that $\gcd(k-2^n, k+2^n) = \gcd(k-2^n, 2^{n+1}) = 1$ as $k$ is clearly odd. Therefore, either $3^n\mid (k-2^n)$ or $3^n\mid (k+2^n)$. We treat these two cases separately. Case 1. $3^n \mid (k-2^n)$ Notice that $(k - 2^n)(k + 2^n) = 3^n(2^n + 3^n)$ implies $k\leq 3^n$. By combining this with $k-2^n\geq 3^n$, we indeed get a contradiction. Case 2. $3^n \mid (k+2^n)$ Check that $\frac{k+2^n}{3^n}\neq 1$ as $k^2>9^n> (3^n-2^n)^2$. Thus, we obtain $k+2^n\geq 2\cdot 3^n \implies k\geq 2\cdot 3^n - 2^n$. But then $$4^n+6^n+9^n\geq (2\cdot 3^n-2^n)^2 = 4\cdot 9^n -4\cdot 6^n + 4^n \implies 5\cdot 6^n \geq 3\cdot 9^n$$And now a simple size argument gives that this is only true for $n=1$, which after checking manually gives no solution. We have now exhausted all possible cases, so we are done by contradiction.