# Prime number

What have you tried so far? My gut is telling me to use the division algorithm $n = 3^k q + r$. Then since the order of 2 in the multiplicative group of $\mathbb{Z} / 3^{k+1}\mathbb{Z}$ is known to be $(3-1)\cdot 3^{k+1-1} = 2\cdot 3^k$, you can further use the division algorithm on $4^{3^kq+r} = 4^r\left(4^{3^k}\right)^q = 4^r\left(1+3^{k+1} x\right)^q$ for some $x \in \mathbb{Z}$. Maybe an induction argument will arise that will yield that if $n \neq 3^k$ then 3 divides $1+2^n + 4^n$.