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.

Printable View

- May 9th 2010, 11:46 AMDeadstarPrimitive 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. - May 9th 2010, 12:01 PMchiph588@
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. - May 9th 2010, 12:18 PMDeadstar
- May 9th 2010, 12:30 PMchiph588@
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. - May 9th 2010, 12:34 PMDeadstar
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!