Problem 1360

To prove that if $1 + 2^n + 4^n$ is prime, then $n = 3^k$ for some $k \in \mathbb{N}_0$, we will proceed as follows:

1. **Initial Check for Small Values of $n$**:
- If $n = 1$, then $1 + 2^1 + 4^1 = 1 + 2 + 4 = 7$, which is prime. Thus, $n = 1 = 3^0$ satisfies the condition.

2. **General Case for $n > 1$**:
- Assume $1 + 2^n + 4^n = p$ is a prime number and $p > 7$.
- We can rewrite the expression as $1 + 2^n + (2^n)^2 = p$.

3. Divisibility by 7:
- Consider the expression $2^{3n} - 1$. We can factorize it as:
$$2^{3n} - 1 = (2^n - 1)(2^{2n} + 2^n + 1)$$
- Notice that $2^{2n} + 2^n + 1 = 1 + 2^n + 4^n = p$. Therefore:
$$2^{3n} - 1 = (2^n - 1)p$$
- Since $2^{3n} - 1$ is divisible by 7 (as $2^3 \equiv 1 \mod 7$), it follows that $p$ must be divisible by 7 if $2^n - 1$ is not divisible by 7.

4. Divisibility by 3:
- For $2^{3n} - 1$ to be divisible by 7, $n$ must be divisible by 3. Let $n = 3k$ for some $k \in \mathbb{N}_0$.

5. Prime Divisors and Order:
- Consider the number $\frac{2^{3^{k+1}} - 1}{2^{3^k} - 1}$. This is a positive integer greater than 1.
- This fraction must have a prime divisor $q$. We need to show that $2^{3^k} - 1$ is not divisible by $q$.
- If $2^{3^k} \equiv 1 \mod q$, then $q$ divides $2^{3^{k+1}} - 1$ but not $2^{3^k} - 1$.

6. Contradiction and Conclusion:
- If $q = 3$, then $2^{3^k} \equiv 1 \mod 3$, which is a contradiction since $2 \not\equiv 1 \mod 3$.
- Therefore, there exists a prime $q$ such that $q$ divides $\frac{2^{3^{k+1}} - 1}{2^{3^k} - 1}$ and $\gcd(q, 2^{3^k} - 1) = 1$.
- This implies $q$ divides $p$, meaning $q = p$. Hence, $p$ divides $2^{3^{k+1}} - 1$, leading to $p < 2^{3^{k+1}}$.

7. Final Contradiction:
- Since $n$ is odd (otherwise $p$ would be divisible by 3), and if $n$ has prime divisors other than 3, then $p < 2^{3^{k+1}} < 2^n < p$, which is a contradiction.

Thus, the only possible values for $n$ are of the form $3^k$.

$\blacksquare$

The final answer is $\boxed{ n = 3^k }$ for some $k \in \mathbb{N}_0$.