# Primitive root of 2^n + 1

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.

#### chiph588@

MHF Hall of Honor
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.

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?
Honestly, no.

#### chiph588@

MHF Hall of Honor
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?
I'm saying if $$\displaystyle 3^{2^{n-1}}\equiv -1\bmod{p}$$, then $$\displaystyle 3^{2^k}\not\equiv1\bmod{p} \;\; \forall \; k<n$$.

Let's prove the contrapositive:

If $$\displaystyle 3^{2^k}\equiv1\bmod{p}$$ for some $$\displaystyle k<n$$, then $$\displaystyle 3^{2^{n-1}}\not\equiv -1\bmod{p}$$.

Well $$\displaystyle 3^{2^{n-1}} = \left(3^{2^k}\right)^{2^{n-1-k}}\equiv 1^{2^{n-1-k}}\equiv 1\not\equiv-1\bmod{p}$$. Thus our original claim is true.

I'm saying if $$\displaystyle 3^{2^{n-1}}\equiv -1\bmod{p}$$, then $$\displaystyle 3^{2^k}\not\equiv1\bmod{p} \;\; \forall \; k<n$$.

Let's prove the contrapositive:

If $$\displaystyle 3^{2^k}\equiv1\bmod{p}$$ for some $$\displaystyle k<n$$, then $$\displaystyle 3^{2^{n-1}}\not\equiv -1\bmod{p}$$.

Well $$\displaystyle 3^{2^{n-1}} = \left(3^{2^k}\right)^{2^{n-1-k}}\equiv 1^{2^{n-1-k}}\equiv 1\not\equiv-1\bmod{p}$$. Thus our original claim is true.
Oh ok I see! I was wrongly thinking that it was either going to be $$\displaystyle \equiv$$ to -1 or 1 for some reason. So hence we could have said that if...

$$\displaystyle 3^{\tfrac{2^{n-1}}{2}}$$$$\displaystyle \equiv -1$$ mod p

Then we can square both sides and get a contradiction. But of course $$\displaystyle 3^{2^k}$$ can be congruent to more than 1 or -1...

Cheers!