Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
For primality of $2^{4n}+1,n$ can not contain any odd factor $>1$ – lab bhattacharjee May 18 '13 at 17:43
up vote 4 down vote accepted

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$.

share|cite|improve this answer
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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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