7
$\begingroup$

If $n\in\mathbb N$ and $4^n+2^n+1$ is prime, prove that there exists an $m\in\mathbb N\cup\{0\}$ such that $n=3^m$.

I.e. if $4^n+2^n+1$ is prime, prove that $n=3^m$, where $m\in\mathbb N\cup\{0\}$.

I don't know how I could solve this, I don't have any ideas. I know that $4^n+2^n+1$ is obviously odd. Assume $m=0$, i.e. $n=1$. Then $3$ is prime. So that doesn't disprove what we're trying to show.

So assume $m>0$. Then $4^n+2^n+1>3$, so $4^n+2^n+1$ is either $3k+1$ or $3k+2$, where $k\in\mathbb N$. So either $4^n+2^n$ or $4^n+2^n-1$ is divisible by 3. I think it's not something that could help out at solving this. Just a little observation. I don't have any ideas.

$\endgroup$
  • 4
    $\begingroup$ Try to relate it to $2^{3n}-1$. $\endgroup$ – Gerry Myerson Dec 28 '13 at 0:55
  • $\begingroup$ Do you mean to relate $4^n+2^n+1$ to $2^{3n}-1$? How could they be related? I don't quite understand. $\endgroup$ – user26486 Dec 28 '13 at 1:00
  • $\begingroup$ @mathh $4^n=(2^n)^2$. $\endgroup$ – Matemáticos Chibchas Dec 28 '13 at 1:05
  • $\begingroup$ Do you know a formula for factoring the difference of two cubes? $\endgroup$ – Gerry Myerson Dec 28 '13 at 1:06
  • $\begingroup$ I do know it. $2^{3n}-1=(2^n-1)(2^{2n}+2^n+1)$. $\endgroup$ – user26486 Dec 28 '13 at 1:11
4
$\begingroup$

If $n$ is not $3^m$, then $n=3^mr$ for some integer $r$, $r\gt1$, $\gcd(r,3)=1$.

$$(2^n-1)(4^n+2^n+1)=2^{3n}-1=2^{3^{m+1}r}-1=(2^{3^{m+1}}-1)q$$ for some integer $q\gt1$. Now $$\gcd(2^a-1,2^b-1)=2^c-1$$ where $c=\gcd(a,b)$, so $$\gcd(2^n-1,2^{3^{m+1}}-1)=2^{3^m}-1$$ Hence, $$\gcd(2^{3^{m+1}}-1,4^n+2^n+1)\gt1$$ But $2^{3^{m+1}}-1\lt4^n+2^n+1$, so $$\gcd(2^{3^{m+1}}-1,4^n+2^n+1)\lt4^n+2^n+1$$ Therefore, $4^n+2^n+1$ can't be prime.

| cite | improve this answer | |
$\endgroup$
8
$\begingroup$

Hint. For prime $p\not=3$ we have $$(x^2+x+1)\mid (x^{2p}+x^p+1)$$ Proof.

\begin{align}x^{2p}+x^p+1&=\frac{x^{3p}-1}{x^p-1}\\&=\frac{(x^3-1)\left(\sum\limits_{k=0}^{p-1}x^{3k}\right)}{x^p-1}\\&=\frac{(x^2+x+1)\left(\sum\limits_{k=0}^{p-1}x^{3k}\right)}{(x^p-1)/(x-1)}\end{align} Now it suffices to prove \begin{align}\frac{x^p-1}{x-1}\big|\sum_{k=0}^{p-1}x^{3k}\end{align} Since $x^p\equiv 1\pmod{x^p-1}$, we see $x^{np+j}\equiv x^j\pmod{\frac{x^p-1}{x-1}}$. Now note that since $3\not\mid p$, for $k=0,1,\cdots,p-1$ the sequence $3k$ form a complete residue system of $p$. So \begin{align}\sum_{k=0}^{p-1}x^{3k}&\equiv\sum_{j=0}^{p-1}x^j\pmod{\frac{x^p-1}{x-1}}\\ & \equiv\frac{x^p-1}{x-1}\equiv 0\pmod{\frac{x^p-1}{x-1}}\end{align}

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ it is enough that, if $p$ is not divisible by $3,$ prime or not, $\omega = \frac{-1 + i \sqrt 3}{2}$ and $\omega^2 = \bar{\omega}$ are roots of $x^{2p} + x^p + 1,$ since $p \equiv 1 \pmod 3$ and $2p \equiv 2 \pmod 3,$ or else $p \equiv 2 \pmod 3$ and $2p \equiv 1 \pmod 3.$ $\endgroup$ – Will Jagy Oct 15 '16 at 17:57
  • $\begingroup$ This is a brilliant answer. Could you potentially prove that $3 \not\vert p$ implies that the sequence $3k$ for $k \in [0, p-1]$ forms a complete residue system? I think I'm being stupid but that doesn't come immediately to me. $\endgroup$ – gowrath Oct 16 '16 at 0:10
  • $\begingroup$ @WillJagy Thanks for your neat approach! $p$ is taken as prime just for convenient. In fact I never used its primeness in the proof. Anyway, your method is very elegant. $\endgroup$ – Cave Johnson Oct 16 '16 at 3:22
  • $\begingroup$ @gowrath The sequence $3k~(k\in[0,p-1])$ are pairwise distinct mod $p$. To see this, check that $p\not|3(i-j)$ for $i,j\in[0,p-1],i\not=j$ since $\gcd(3,p)=1$ and $|i-j|<p$. Now, for $k\in[0,p-1]$ there are $p$ distinct numbers mod $p$, they must form a complete residue system. $\endgroup$ – Cave Johnson Oct 16 '16 at 3:26
  • $\begingroup$ One last question. This proves that p must be a multiple of 3, but not that it must also be a power of 3. Or does that entail and I'm just not seeing it? (sorry I'm very very green in number theory). $\endgroup$ – gowrath Oct 16 '16 at 5:19
4
$\begingroup$

The case $n=1$ is trivial. Let $n\ge2$

By contradiction assume that $n=3^km$ where $3\not|m$, $m\ge2$ and let $$P_q(x)=x^{2q}+x^q+1\in\mathbb Z[x]$$ so $$P_n(x)=(x^{3^k})^{2m}+(x^{3^k})^{m}+1=P_m(x^{3^k})$$ We have $$P_m(j)=P_m(j^2)=j^{2m}+j^m+1=\frac{j^{3m}-1}{j^m-1}=0$$ hence $P_1(x)|P_m(x)$ in $\mathbb Z[x]$ so $$P_1(2^{3^k})|P_m(2^{3^k})=P_n(2)=4^n+2^n+1$$ and $$1<P_1(2^{3^k})<4^n+2^n+1$$ so $4^n+2^n+1$ isn't prime. Contradiction.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $j=e^{2i\pi/3}$ is a cubic root of $1$ and this notation is standard. We have $j^2+j+1=0$. $\endgroup$ – user63181 Dec 28 '13 at 2:42
  • $\begingroup$ This is simple just we have: $$j^3=\left(e^{2i\pi/3}\right)^3=e^{2i\pi}=1$$ $\endgroup$ – user63181 Dec 28 '13 at 2:50
0
$\begingroup$

Lemma: $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$

Proof: Several proofs can be found here


$4^n+2^n+1 = \frac{8^n-1}{2^n-1}$. Let $n=3^t \times k$, where $k$ is not divisible by $3$. The numerator becomes $8^{3^t \times k}-1 = \left( {8^{3^t}} \right) ^k-1$, which has a factor $\left(8^{3^t}-1 \right)$.

The denominator becomes $2^{3^t \times k}-1$. By our lemma, $\gcd(8^{3^t}-1, 2^{3^t \times k}-1)$ $= \gcd(8^{3^t}-1, 8^{3^{t-1} \times k}-1)$ $ = 8^{\gcd(3^t, {3^{t-1} \times k})} - 1 = 8^{3^{t-1}}-1 = 2^{3^{t}}-1$, since $3 \nmid k$.

We now rewrite the fraction $\frac{8^n-1}{2^n-1}$as follows:

$$\frac{ \left( 2^{3^{t}}-1 \right) \left( {\left(2^{3^{t}}\right)}^2 + 2^{3^{t}} +1\right) \left( {\left(8^{3^{t}}\right)}^{k-1} + {\left(8^{3^{t}}\right)}^{k-2} + ... +1\right)}{\left( 2^{3^{t}}-1 \right) \left( {\left(2^{3^{t}}\right)}^{k-1} + {\left(2^{3^{t}}\right)}^{k-2} + ... +1\right)}$$

$\gcd\left( \left( {\left(2^{3^{t}}\right)}^2 + 2^{3^{t}} +1\right),\left( {\left(2^{3^{t}}\right)}^{k-1} + {\left(2^{3^{t}}\right)}^{k-2} + ... +1\right) \right) = 1$, so the only way the fraction cancels to a prime is when $\left( {\left(8^{3^{t}}\right)}^{k-1} + {\left(8^{3^{t}}\right)}^{k-2} + ... +1\right)$ $=\left( {\left(2^{3^{t}}\right)}^{k-1} + {\left(2^{3^{t}}\right)}^{k-2} + ... +1\right)$. This only occurs when $k=1$. Hence, $n$ is of the form $3^t$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.