Prove that if $n$ is a natural number such that $1 + 2^n + 4^n$ is prime then $n = 3^k$ for some $k \in N_0$.
Problem
Source: Croatia TST 2002 p3
Tags: number theory, prime
08.12.2020 17:39
If $1+2^n+4^n=7$, then $n=1$ and condition holds. Otherwise $1+2^n+4^n=p>7$. So, $2^{3n}-1=(2^n-1)p$ Since left part is divisible by $7$, $n$ is divisible by $3$. Suppose that $|n|_3=k$. Consider the number $\frac{2^{3^{k+1}}-1}{2^{3^k}-1}$. Obviously that it’s positive integer more than one. Then this fraction has prime divisor $q$. I am going to show that $2^{3^k}-1$ isn’t divisible by $q$ — otherwise $2^{3^k}\equiv 1$ mod $q$, so $| (2^{3^k})^3-1|_q= | 2^{3^k}-1|_q+|3|_q> | 2^{3^k}-1|_q$ (since $q|\frac{2^{3^{k+1}}-1}{2^{3^k}-1}$). Therefore, $q=3$ and $2^{3^k}\equiv 1$ mod $3$, contradiction. Hence, there exists $q| \frac{2^{3^{k+1}}-1}{2^{3^k}-1}$ and $gcd(q, 2^{3^k}-1)=1$. Then $q$ divides $2^{3n}-1$ and doesn’t divide $2^{n}-1$, since $ord_q(2)=3^{k+1}$ as was shown above, but $|n|_3=k$. So, $q$ divides $p$, it means that $q=p$. That is, $p|2^{3^{k+1}}-1$ $=>$ $p<2^{3^{k+1}}$. But, since $n$ is odd (otherwise $p$ is divisible by $3$), and if $n$ has prime divisors differing 3 (that is more than 3), then $p<2^{3^{k+1}}<2^n<p$ — contradiction.
03.02.2024 00:01
the polynomial $Q(x)=x^{2p}+x^p+1$ is always divisible by the polynomial $R(x) = x^2+x+1$ where $p$ is a prime other than 3.
13.12.2024 19:02
Let $n=3^k\cdot m$ where $3\nmid m$. Our goal is to show $m=1$. Let $x=2^{3^k}$. Suppose $x^{2} + x + 1 \equiv0\pmod{p}$ for some prime $p$. $x\equiv 1\pmod{p}\implies p=3$. Hence $3\mid 1+2^{n}+2^{2n}$ so it should be equal to $3$, but it is always greater than $3$. Hence $x\not\equiv 1\pmod{p}$. In particular, \[\frac{x^3-1}{x-1}\equiv 0\pmod{p}\implies x^3\equiv 1\pmod{p}\implies \mathrm{ord}_p(x)=3\]In particular, we may take the exponents of $x^k$ $\mod 3$ without changing the residue class $\mod p$. Hence, because multiplication is a bijection in $\mathbb{F}_3$, we have \[x^{2m}+x^{m}+1\equiv x^2+x+1\equiv 0\pmod{p}\]In particular, if $x^{2m}+x^m+1>x^2+x+1$, we have a contradiction. Hence $m=1$, as desired. $\square$