Condition for primeness of a degree 2 Solinas Prime

Question

Given $2^{2k+1}+2^{k+1}+1$ is prime, this necessarily imply $2k+1$ is a prime. This result is assumed true in Primality tests for $2^p \pm 2^{(p+1)/2}+1$ using elliptic curves by YU TSUMURA in Proceedings of the American mathematical society vol. 139 num. 8 August 2011 Pages 2697-2703 and also considered easy to prove in that paper, but I didnt find anything in the web and the only fact I found that may help to prove this is $(2^{2k+1}+2^{k+1}+1)(2^{2k+1}-2^{k+1}+1)=2^{2(2k+1)}+1$.

Answer 1

We begin with the following identity applied on $x=2^k$.

$$4x^4+1=(2x^2+2x+1)(2x^2-2x+1).$$

This gives that

$$\left(2^{2k+1}+2^{k+1}+1\right)\left(2^{2k+1}-2^{k+1}+1\right)=2^{4k+2}+1.$$

Assume for contradiction that $2k+1$ is not prime, but our first factor is prime. Let $p$ be a prime dividing $2k+1$. We have that, as $\frac{2k+1}{p}$ is odd,

$$x^p+1\big| x^{2k+1}+1,$$

which applied at $x=4$ gives

$$2^{2p}+1\big | 2^{4k+2}+1.$$

However, as $p$ is a proper divisor of $2k+1$, $2p\leq 2k+1$, so

$$2^{2p}+1\leq 2^{2k+1}+1 < 2^{2k+1}+2^{k+1}+1,$$

so $2^{2p}+1$ is not our first factor, and, as our first factor is prime, it cannot share any common factors with $2^{2p}+1$. This means that

$$2^{2p}+1 \big|2^{2k+1}-2^{k+1}+1.$$

As $2k+1=mp$ for some odd $m=2n+1$, we have that

$$2^{2k+1} = 2^{mp} \equiv 2^{2np+p}\equiv (-1)^n2^p\bmod \left(2^{2p}+1\right),$$

and similarly

$$2^{k+1} = 2^{\frac{(2n+1)p+1}{2}} = 2^{np+\left(\frac{p+1}{2}\right)}\equiv 2^{\frac{p+1}{2}}K\bmod \left(2^{2p}+1\right),$$

where $K$ is in the orbit of $2^p\bmod \left(2^{2p}+1\right)$; in particular, we may choose

$$K\in\left\{1,2^p,-1,-2^p\right\}.$$

Thus, we have

$$2^{2p}+1\bigg|(-1)^n 2^p - 2^{\frac{p+1}{2}}K+1.$$

As $p\geq 1$, both of the first two terms of the right side are clearly even, while $1$ is odd, which implies that the right side is odd and thus nonzero. As a result, its magnitude is $\geq 2^{2p}+1$, which implies that

$$2^{2p}+1\leq \left|(-1)^n 2^p - 2^{\frac{p+1}{2}}K+1\right|\leq 2^p\left(1+2^{\frac{p+1}{2}}\right)+1$$

$$2^p\leq 1+2^{\frac{p+1}{2}}.$$

$$x^2\leq 2+2x$$

for $x=2^{\frac{p+1}{2}}$. This is clearly false for $x\geq 3$, and as $p$ is odd, $2^{\frac{p+1}{2}}\geq 4$, and we have a contradiction.