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.
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!