$2$ cannot be a primitive root of a prime $F_n = 2^{2^n} + 1$ where $n\ge 2$

I've understood that the fact that $F_n \equiv 1 \pmod{8}$ for $n\ge 2$ might be helpful here, but I don't see how (Though I'm open to other suggestions of course)

I have seen in class that there's a primitive root modulo $m$ iff:

  1. $m=2,4$
  2. $m=p^k$, $p$ an odd prime and $k\ge 1$
  3. $m=2p^k$, $p$ an odd prime and $k\ge 1$

In particular, for $m=8$ there's no primitive root modulo $m$.

  • $\begingroup$ If $p\equiv 1\pmod{8}$, then $2$ is a quadratic residue modulo $p$, hence not a primitive root. $\endgroup$ – pisco Dec 14 '17 at 14:20
  • $\begingroup$ @pisco125, Could you please elaborate on that? $\endgroup$ – Elimination Dec 14 '17 at 14:22
  • $\begingroup$ @BarryCipra, you're right - $n\ge 2$ (I'll add that) $\endgroup$ – Elimination Dec 14 '17 at 14:32

$$2^{2^n}\equiv -1\pmod {F_n}$$ Then $$2^{2^{n+1}}\equiv 1\pmod{F_n}$$ And clearly $2^{n+1}<F_n-1$ for $n\ge 2$

  • $\begingroup$ Oh wow, nice solution! Thank you! $\endgroup$ – Elimination Dec 14 '17 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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