# Primitive root of 2^n + 1

• May 9th 2010, 11:46 AM
Primitive root of 2^n + 1
Show that, for n>1, 3 is a primitive root of any prime of the form $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.
• May 9th 2010, 12:01 PM
chiph588@
Quote:

Show that, for n>1, 3 is a primitive root of any prime of the form $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, $\phi(2^n+1) = 2^n$, so $\text{ord}(3) = 2^k$ for some $0.

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

$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 $(-1)^n+1\equiv 2\bmod{3}$ since if $(-1)^n+1\equiv 0\bmod{3}$ then $p$ would not be prime.

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

Thus $\text{ord}(3) = \phi(2^n+1)$ which makes $3$ a primitive root.
• May 9th 2010, 12:18 PM
Quote:

Originally Posted by chiph588@
So in summary we have $3^{2^{n-1}}\equiv -1\bmod{p}$ and I claim this forces $3^{2^k}\not\equiv1\bmod{p} \;\; \forall \; k . Can you see why?

Honestly, no.
• May 9th 2010, 12:30 PM
chiph588@
Quote:

Originally Posted by chiph588@
So in summary we have $3^{2^{n-1}}\equiv -1\bmod{p}$ and I claim this forces $3^{2^k}\not\equiv1\bmod{p} \;\; \forall \; k . Can you see why?

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

Let's prove the contrapositive:

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

Well $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.
• May 9th 2010, 12:34 PM
Quote:

Originally Posted by chiph588@
I'm saying if $3^{2^{n-1}}\equiv -1\bmod{p}$, then $3^{2^k}\not\equiv1\bmod{p} \;\; \forall \; k.

Let's prove the contrapositive:

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

Well $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 $\equiv$ to -1 or 1 for some reason. So hence we could have said that if...

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

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

Cheers!