Show that, for n>1, 3 is a primitive root of any prime of the form \(\displaystyle 2^n + 1\).

Thoughts,

Need conditions such that if 3 is NOT a primitive root then such and such. But I don't know what the such and such should be.

In this case, \(\displaystyle \phi(2^n+1) = 2^n \), so \(\displaystyle \text{ord}(3) = 2^k \) for some \(\displaystyle 0<k\leq n \).

Let \(\displaystyle p=2^n+1 \) and look at \(\displaystyle 3^{(p-1)/2} \):

\(\displaystyle 3^{(p-1)/2}\equiv \left(\frac3p\right) = \left(\frac p3\right) = \left(\frac{(-1)^n+1}{3}\right) = \left(\frac23\right) = -1\bmod{p}\).

Note that I'm saying \(\displaystyle (-1)^n+1\equiv 2\bmod{3} \) since if \(\displaystyle (-1)^n+1\equiv 0\bmod{3} \) then \(\displaystyle p \) would not be prime.

So in summary we have \(\displaystyle 3^{2^{n-1}}\equiv -1\bmod{p} \) and I claim this forces \(\displaystyle 3^{2^k}\not\equiv1\bmod{p} \;\; \forall \; k<n \) . Can you see why?

Thus \(\displaystyle \text{ord}(3) = \phi(2^n+1) \) which makes \(\displaystyle 3 \) a primitive root.