Primitive root of 2^n + 1

Oct 2007
722
168
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
Sep 2008
1,163
429
Champaign, Illinois
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.
 
  • Like
Reactions: Deadstar
Oct 2007
722
168
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
Sep 2008
1,163
429
Champaign, Illinois
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.
 
Oct 2007
722
168
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!