# For every prime of the form $2^{4n}+1$, 7 is a primitive root.

What I want to show is the following statement.

For every prime of the form $2^{4n}+1$, 7 is a primitive root.

What I get is that

$$7^{2^{k}}\equiv1\pmod{p}$$ $$7^{2^{k-1}}\equiv-1\equiv2^{4n}\pmod{p}$$ $$7^{2^{k-2}}\equiv(2^{n})^2\pmod{p}$$ Thus $(\frac{2^n}{p})=(\frac{7^{2^{k-2}}}{p})=1$.

I think that $7$ is important because $7$ is a primitive root but I don't know how to use $7$.

-
For primality of $2^{4n}+1,n$ can not contain any odd factor $>1$ – lab bhattacharjee May 18 '13 at 17:43
– lab bhattacharjee May 18 '13 at 17:45

Assume that $p=2^{4n}+1$ is a prime. We know that the order of $7$ is a factor of $p-1$, so it is a power of two. The claim is equivalent to saying that the order is exactly $p-1$. Assume that this is not the case. Then the order is a factor of $(p-1)/2$ meaning that $$\left(\frac7p\right)\equiv 7^{(p-1)/2}\equiv 1\pmod p.$$ The case $n=0$ is easy, so we can assume that $n>0$. Then $p\equiv1\pmod4$, so the law of quadratic recpirocity tells that the claim is equivalent to $$\left(\frac{p}7\right)=1.$$ As $2^3\equiv1\pmod7$, $p\equiv 2^n+1\pmod7.$ The residue class of $2^n+1$ modulo $7$ can be either $2,3$ or $5$, when $n\equiv 0,1,2\pmod3$ respectively. Of these, only $2$ is a quadratic residue modulo $7$. This means that we must have $3\mid n$. I leave it to you to prove that in that case $p$ cannot be a prime unless $n=0$ and $p=2$.

-
Mind you, there are relatively few primes $p$ of this form known. Ask Fermat :-) – Jyrki Lahtonen May 18 '13 at 16:57
"Clearly $p\equiv 1\pmod 4$" - not really. The typical exeption is $n=0$, $p=2$ - but of course $7$ is a primitive root there as well. – Hagen von Eitzen May 18 '13 at 16:57
@Hagen, you're right, of course. I initially thought that the claim is false for $n=0$ as I calculated that $2^0+1=3$. Then I realised that error, but forgot that I actually used that assumption :-) Editing.... – Jyrki Lahtonen May 18 '13 at 16:59
What I missed is the connection between the primitive root and the Legendre symbol. I will keep in mind the key idea that $(\frac{7}{p})\equiv 7^{(p-1)/2} \equiv 1 \pmod{p}$. – Guillermo May 18 '13 at 17:00
@Guillermo: Except that (for primes of our form) $7^{(p-1)/2}\equiv -1\pmod{p}$. You may have misunderstood the proof by contradiction. – André Nicolas May 18 '13 at 17:54

Recall that any prime $p$ has $\varphi(p-1)$ primitive roots. In our case, $\varphi(p-1)=(p-1)/2$.

Any prime $p$ has $(p-1)/2$ quadratic non-residues. Any primitive root is a non-residue, so for primes $p$ of the form $2^w+1$, every NR is a primitive root.

It remains to show that $7$ is a NR of $p$. This is dealt with in the answer by Jyrki Lahtonen. Briefly, use Reciprocity.

-

Case $n=0$ is trivial and satisfies our assumption. So consider all possible outcomes when the natural number $n = 3k + t$ for some $k \in \mathbb{Z}$ and $t \in \{\, 0,1,2 \,\}$: \begin{align*} & p = 2^{4\cdot 3k} + 1 = 2^{12k}+1 = (2^{4k} + 1)(2^{8k} - 2^{4k} + 1) \not\in \mathbb{P} \quad (\text{prime}); \\ & p = 2^{4\cdot (3k+1)} + 1 = 8^{4k} \cdot 16^1 + 1 \equiv 1^{4k} \cdot 2^1 + 1 = 3 \mod{7}; \\ & p = 2^{4\cdot (3k+2)} + 1 = 8^{4k} \cdot 16^2 + 1 \equiv 1^{4k} \cdot 2^2 + 1 = 5 \mod{7}. \end{align*}

If $p \equiv 3 \mod{7}$ then we have $(p/7) = (3/7) = -(7/3) = -(1/3) = -1$.

If $p \equiv 5 \mod{7}$ then we have $(p/7) = (5/7) = (7/5) = (2/5) = -1$.

Since obviously $p \equiv 1 \mod{4}$, quadratic reciprocity law gives $(7/p) = (p/7)$ and \begin{equation*} -1 = (p/7) = (7/p) \equiv 7^{\frac{p-1}{2}} = 7^{2^{4n-1}} \mod{p}. \end{equation*} This means that $\operatorname{ord}_p(7) \nmid 2^{4n-1}$ while at the same time $\operatorname{ord}_p(7) \mid \varphi(p) = 2^{4n}$. Then the only possibility is that $\operatorname{ord}_p(7) = \varphi(p)$ and $7$ is a primitive root modulo $p$ by definition.

-