# Finding all natural $n$ such that $2^n+2^{2n} +2^{3n}$ has only $2$ prime factors.

Find all natural $n$ such that $2^n+2^{2n} +2^{3n}$ has only $2$ prime factors.

I've tried checking the first 6-7 $n$'s on wolframalpha, but I don't see any patterns for even nor odd $n$'s. At first I thought for all odd $n$'s it was divisible by $2,3,7$, but $n=5$ doesn't work ($n=1,3,7$ do work). How are these $n$ found?

• The only solutions with $n<10000$ are $n=1,3,9$. – lhf Oct 17 '14 at 13:06

$2^n + 2^{2n}+2^{3n} = 2^n(1+2^n + 2^{2n}) = 2^n p^a$ for some prime $p$ and positive integer $a$. Then, $p^a = 1+2^n + 2^{2n}$.

Suppose $a>1$.

If $a$ is even, $a = 2b$, meaning $p^a - 1 = (p^b - 1)(p^b+1) = 2^n(1+2^n)$, which is impossible (you can see that easily). Then $a$ must be odd.

Then, $2^n + 2^{2n}= (p-1)(p^{a-1} + \dots +1)$. $(p^{a-1} + \dots +1)$ must be odd (it is the sum of an odd number of odd numbers), then $2^n | p-1$. But since $p-1 < p^2 + p +1$, you must have $2^n = p-1$, which means $p= 2^n +1= (p^{a-1} + \dots +1)$, an absurd.

So, $a=1$.

• for $n=3$ you have $2^3+2^6=72=73-1$, so a solution with $p=73$, $a=1$, but $p\neq 2^n+1$... – wisefool Oct 17 '14 at 14:04
• I'm sorry, I can't get your point. If $a=1$, you must have $p = 1+ 2^n + 2^{2n}$. $p = 2^n+1$ only if $a > 1$. Am I wrong? – Leo163 Oct 17 '14 at 14:15
• If $a$ is even why we arrive at a contradiction?Maybe is easy to see why, but I can't see this now immediately. – Konstantinos Gaitanas Oct 17 '14 at 15:25
• @Leo163: yes, sorry, you edited the post after I had written the comment … – wisefool Oct 17 '14 at 15:31

Hint: It can be written as $$2^n\frac{2^{3n}-1}{2^n-1}$$

So you need $n$ so that $\dfrac{2^{3n}-1}{2^n-1}$ is a power of a single prime.

If $n$ is not divisible by $3$, then $7$ is a factor, so you'd need this to be a power of $7$. Not sure what you can do beyond that, however.

If $n$ is a multiple of $3$, it gets even harder.

This is just a sketch of a partial answer...

$$2^n+2^{2n}+2^{3n}=2^n(1+2^n+2^{2n})$$ so you need to check if $1+2^n+2^{2n}$ is of the form $p^k$. First note that, if $n$ is even $$1+2^n+2^{2n}\equiv 1 + 1 + 1\equiv 0\bmod 3$$ so, if $n$ is even, you need $$2^n+2^{2n}=3^a-1$$ if $a$ is odd, then $3^a-1\equiv -1-1\equiv -2\bmod 4$, so $a$ is even. Then, by LTE $$v_2(3^a-1)=v_2(3+1)+v_2(3-1)+v_2(a)-1=2+v_2(a)$$ but also $v_2(2^n+2^{2n})=n$ so $n=2+v_2(a)$, hence $2^{n-2}\vert a$, but then $$2^n+2^{2n}\leq 3^{2n+1} < 3^{2^{n-2}}$$ for $n\geq 5$. So no solutions for $n$ even greater than $5$.

Moreover, if $3\not\vert n$, then $2^n\equiv 2,4\bmod 7$, so $1+2^n+2^{2n}\equiv 0\bmod 7$. The same reasoning as before says that $1+2^n+2^{2n}$ is not a power of $7$ if $n\geq 5$ and coprime with $3$.

We are left with odd multiples of $3$. We see that for $n=3$ we get $73$, which is prime; repeating the previous reasoning, we exclude the numbers of the form $9k+3$ and $9k+6$, but we have still to check odd multiples of $9$. This strategy doesn't seem promising, because $9$ is a solution, $27$ is not but in the factorization of the number we obtain with $n=27$ other primes ($4$-digit primes!) show up...