It can be quite easily shown that $5$ is a divisor of $2^q+2^{(q+1)/2}+1$ iff ($q=8k+1$ or $q=8k+7$) and that $5$ is a divisor of $2^q-2^{(q+1)/2}+1$ iff ($q=8k+3$ or $q=8k+5$).
Now, it seems that for $2^q\pm2^{(q+1)/2}+1$ to be prime, it is necessary that $q$ be prime. Is this true? If yes, is there an elementary proof? I have hard time to find one.
On
Here is a proposal for a proof of the statement that $Q_p^{\pm}$ is prime implies that $p$ is prime.
It is based of the relationship :
$Q_p=((1+i)^p-1)((1-i)^p-1)=2^p+e(p)2^{(p+1)/2}+1$
where $p$ is an odd positive integer, $e(p)=-1$ when $p=8k\pm1$ and $e(p)=+1$ when $p=8k\pm3$.
This is easily derived, if you write $1\pm{i}= \sqrt2.exp(\pm{i}\pi/4$).
Then $Q_p=Q_p^-$ when $p=8k\pm1$ and $Q_p=Q_p^+$ when $p=8k\pm3$. (Note that when $p=8k\pm1$, $Q_p^+$ is divisible by $5$, and therefore composite, and when $p=8k\pm3$, $Q_p^-$ is divisible by $5$, and therefore composite, too.)
Now suppose that $p$ is composite and let $q$ be a proper divisor of $p$. Then $((1+i)^p-1)((1-i)^p-1) = [((1+i)^q-1)R((1+i)^q)][((1-i)^q-1)R((1-i)^q)]$, where R is a polynomial of degree $p/q-1$.
That is $Q_p=Q_q.R((1+i)^q)R((1-i)^q)$ which says that $Q_q$ is a proper divisor of $Q_p$. (Note that $e(p)$ and $e(q)$ may differ in sign).
Conversely, if $Q_p$ is prime, then $p$ is prime. Q.E.D.
PS: From the research I have done, these primes $Q_p$ have a name: they are the "Gaussian Mersenne primes". In 2006, 37 were known, the largest one is $2^{1203793} - 2^{601897} +1$.
Beginnings: the product of the two expressions is $4^q + 1,$ with $q$ odd. If $q = r s,$ we know that $4^{rs} + 1$ is divisible by both $4^r + 1$ and $4^s + 1.$
More to come.
Well, what I suspect: let's make $s$ prime, it may be important. If $s \equiv \pm 3 \pmod 8,$ then it appears that $$ \gcd \left( 2^r + 2^{(r+1)/2} + 1, 2^{rs} + 2^{(rs+1)/2} + 1 \right) = 1, $$ and $$ \gcd \left( 2^r - 2^{(r+1)/2} + 1, 2^{rs} - 2^{(rs+1)/2} + 1 \right) = 1. $$
If $s \equiv \pm 1 \pmod 8,$ then it appears that $$ \gcd \left( 2^r + 2^{(r+1)/2} + 1, 2^{rs} - 2^{(rs+1)/2} + 1 \right) = 1, $$ and $$ \gcd \left( 2^r - 2^{(r+1)/2} + 1, 2^{rs} + 2^{(rs+1)/2} + 1 \right) = 1. $$
If these work out, they give the whole package, using the initial observation about $4^q + 1.$ The outcome is that each piece is divisible by either the same or the opposite piece for any smaller $q$ value that divides the current, composite, $q.$ Worth checking these patterns for larger $q.$ It is not necessary to factor the numbers to confirm the gcd pattern, so large $q$ is acceptable.
For what it's worth, i did the gcd tests I described for $q \leq 149.$ Whenever $q$ was composite, i took gcd's of the two $\pm$ factors with those of any factor $k.$ Results as i expected. Results go by the ratio modulo 8. So, somewhere there is a Jacobi symbol $(2 | q)$ hiding. Oh, I did not print out the gcd if larger than 1, I just said to write the word "big." We know what the gcd is when the other on the same line is 1.