Peter wrote: Suppose that $4^{n}+2^{n}+1$ is prime for some positive integer $n$. Show that $n$ must be a power of $3$. Copying my proof from MathLinks: Consider the polynomial $\Phi_3\left(x\right)=x^2+x+1$. We will first show: Lemma 1. If k is a positive integer not divisible by 3, then $\Phi_3\left(x^k\right)$, written as a polynomial of x, is divisible by the polynomial $\Phi_3\left(x\right)$ over $\mathbb{Z}\left[x\right]$; in other words, there exists a polynomial u with integer coefficients such that $\Phi_3\left(x^k\right)=u\left(x\right)\cdot \Phi_3\left(x\right)$. Proof of Lemma 1. The complex zeroes of the polynomial $\Phi_3\left(x\right)=x^2+x+1$ are the two primitive 3rd roots of unity, i. e. the two complex numbers z such that $z^3=1$ but $z\neq 1$ (each being a zero with multiplicity 1). Let u be one of these two zeros. Then, $u^3=1$ but $u\neq 1$. Now, since k is an integer, $\left(u^k\right)^3=u^{3k}=\left(u^3\right)^k=1^k=1$. On the other hand, since k is not divisible by 3, it is coprime with 3, so we can find integers $\alpha$ and $\beta$ such that $\alpha\cdot k+\beta\cdot 3=1$. Hence, if we had $u^k=1$, then we would have $u=u^1=u^{\alpha\cdot k+\beta\cdot 3}=u^{\alpha\cdot k}\cdot u^{\beta\cdot 3}=\left(u^k\right)^\alpha\cdot\left(u^3\right)^\beta=1^{\alpha}\cdot 1^{\beta}=1$, contradicting $u\neq 1$. Thus, we must have $u^k\neq 1$. [Well, I know this argumentation was overkill, but it's generalizable.] Thus, the number $u^k$ satisfies $\left(u^k\right)^3=1$ but $u^k\neq 1$. Hence, $u^k$ is also a primitive 3rd root of unity, i. e. a root of the polynomial $\Phi_3\left(x\right)$. In other words, $\Phi_3\left(u^k\right)=0$. But this can also be interpreted as follows: The number u is a root of the polynomial $\Phi_3\left(x^k\right)$. Hence, we have showed that, if u is a root of the polynomial $\Phi_3\left(x\right)$, then u is also a root of the polynomial $\Phi_3\left(x^k\right)$. Thus, the polynomial $\Phi_3\left(x^k\right)$ must be divisible by the polynomial $\Phi_3\left(x\right)$. Since both polynomials have integer coefficients and the leading coefficients are both 1, it follows that the quotient is a polynomial with integer coefficients, i. e. there exists a polynomial u with integer coefficients such that $\Phi_3\left(x^k\right)=u\left(x\right)\cdot \Phi_3\left(x\right)$. Lemma 1 is proven. As a consequence of Lemma 1, if x and k are positive integers and k is not divisible by 3 and satisfies k > 1, then the number $\Phi_3\left(x\right)$ is a proper divisor of $\Phi_3\left(x^k\right)$. In fact, since x is an integer and $\Phi_3$ and u are polynomials with integer coefficients, the equation $\Phi_3\left(x^k\right)=u\left(x\right)\cdot \Phi_3\left(x\right)$ yields that the number $\Phi_3\left(x\right)$ divides the number $\Phi_3\left(x^k\right)$, and in fact it is a proper divisor since it is not equal to 1 (in fact, $\Phi_3\left(x\right)=x^2+x+1>1$) and not equal to $\Phi_3\left(x^k\right)$ (since $\Phi_3\left(x\right)=x^2+x+1<\left(x^k\right)^2+x^k+1=\Phi_3\left(x^k\right)$). Now, if the number n is not a power of 3, then it has a prime divisor $\neq 3$. Let q be this prime divisor. Then, q is a positive integer, q > 1 (since q is a prime), and q is not divisible by 3 (since q is a prime $\neq 3$), and also, the number n can be written in the form n = qr, where r is some positive integer. Hence, by the above, the number $\Phi_3\left(2^r\right)$ is a proper divisor of $\Phi_3\left(\left(2^r\right)^q\right)$. Thus, $\Phi_3\left(\left(2^r\right)^q\right)$ cannot be a prime. But $\Phi_3\left(\left(2^r\right)^q\right)=\Phi_3\left(2^{qr}\right)=\Phi_3\left(2^n\right)=\left(2^n\right)^2+2^n+1=1^n+2^n+4^n$ must be a prime by the condition of the problem. Hence, n must be a power of 3. That's all. darij

Here's my generalisation from MathLinks: Let $\Phi_{n}(x)$ denote the $n$-th cyclotomic polynomial, defined on any way you like, e.g. by $x^{n}-1= \prod_{d|n}\Phi_{d}(x)$ for all $n$ or by $\Phi_{n}(x) = \prod_{m \in (\mathbb{Z}/n \mathbb{Z})^{*}}(x-\zeta_{n}^{m})$, with $\zeta_{n}= e^{\frac{2 \pi i}{n}}$ a $n$-th primitive root of unity. Generalisation: Theorem 1 Let $a \geq 2$ be an integer and $p$ be prime. Then $a^{(p-1)m}+a^{(p-2)m}+...+a^{2m}+a^{m}+1$ can only be prime if $m=p^{k}$ for some $k$. Proof: This is the case $n$ prime of theorem 2. Remark: this still holds for composite $n$, but then the term is never prime. Generalisation of generalisation: Theorem 2 Let $a \geq 2$ and $n \geq 1$ be integers. Then for $\Phi_{n}(a^{m})$ to be prime, it is necessary that $m$ has only prime divisors also dividing $n$, except of the case $a=2, n=1$ where it is only necessary for $m$ to be prime. Proof: The case $n=1$ is well know stuff from elementary results on Mersenne numbers. So let $n \geq 2$. When $m$ is not of the desired type, see theorem 3 for a factorisation of $\Phi_{n}(a^{m})$. It's enough to show that $\Phi_{mn}(a)>1$ and $\Phi_{kn}(a)>1$ now, since then $\Phi_{n}(a^{m})$ will surely not be prime. For this it suffices to show that $\Phi_{w}(b)$ is greater than one for all $w,b \geq 2$. This is easy when looking at the roots of $\Phi_{w}(x)$: they all are on the unit circle and $\neq 1$ (the latter by $n \neq 1$), so their distance to $b$ is $>1$, so also the product of those distances, giving what we wanted. Generalisation of generalisation of generalisation: Theorem 3 Let $a \geq 2$ and $n \geq 1$ be integers. Then the polynomial $\Phi_{n}(x^{m})$ is irreducible iff $m$ is only divisible by prime divisors also dividing $n$; when $q|m=q^{v}k$ with $q\nmid k,n$, two nontrivial factors are explicitely given as $\Phi_{mn}(x)$ and $\Phi_{kn}(x)$. Proof: If $q$ is some prime dividing $m=q^{v}k$ ($q \nmid k$) but not $n$, we see that the two factors proposed have only roots $\Phi_{n}(x^{m})$ has, and they have no common roots (all this may be hard to see at first). Thus these are indeed different factors. Another way to get these factors is by using the following Lemma sometimes. You can stop reading all that generalisations, since only the already proven part is needed for the proofs of theorem 1 and 2. But here goes the other direction: We need a important property of cyclotomic polynomials (only the first part is needed but the other is good to know): Lemma: Let $n$ be any positive integer and $q$ be prime. Then: - $\Phi_{n}(x^{q}) = \Phi_{nq}(x)$ iff $q|n$ - $\Phi_{n}(x^{q}) = \Phi_{nq}(x) \cdot \Phi_{n}(x)$ iff $q \nmid n$ This is essentially done by comparing the roots of both sides using that $\Phi_{w}(x) = \prod_{a \in (\mathbb{Z}/w \mathbb{Z})^{*}}(x-\zeta_{w}^{a})$. Back to the problem: If $m$ has only such prime factors, by repeated use of the Lemma, part 1, we get that $\Phi_{n}(x^{m})=\Phi_{mn}(x)$. And the cyclotomic polynomials are irreducible as was shown in http://www.problem-solving.be/pen/viewtopic.php?t=585 .

Let $ 3^k || n$, write $ n = 3^k(3q+r)$ where $ r = 1,2$ It's easy to see that $ x^2+x+1 | x^{6q+2r}+x^{3q+r}+1$ for all $ q \in N_0 ,r \in \{1,2\}$ thus $ (2^{3^k})^2 +2^{3^k}+1 | 4^n+2^n+1 = (2^{3^k})^{6q+2r}+(2^{3^k})^{3q+r}+1$ since $ 4^n+2^n+1$ is prime and $ (2^{3^k})^2 +2^{3^k}+1>1$ Hence, $ 3q+r=1$ so $ r=1$ and $ q=0$. thus $ n=3^k$ , a power of $ 3$