# Thread: Primitive root of 2^n + 1

1. ## 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.

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.

3. Originally Posted by chiph588@
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.

4. Originally Posted by chiph588@
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.

5. Originally Posted by chiph588@
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!