Primitive root of 2^n + 1

**Deadstar** · May 9th 2010, 11:46 AM

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.

**chiph588@** · May 9th 2010, 12:01 PM

Originally Posted by Deadstar

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<k\leq n$ .

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<n$ . Can you see why?

Thus $\text{ord}(3) = \phi(2^n+1)$ which makes $3$ a primitive root.

**Deadstar** · May 9th 2010, 12:18 PM

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<n$ . Can you see why?

Honestly, no.

**chiph588@** · May 9th 2010, 12:30 PM

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<n$ . 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<n$ .

Let's prove the contrapositive:

If $3^{2^k}\equiv1\bmod{p}$ for some $k<n$ , 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.

**Deadstar** · May 9th 2010, 12:34 PM

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<n$ .

Let's prove the contrapositive:

If $3^{2^k}\equiv1\bmod{p}$ for some $k<n$ , 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!

Thread: Primitive root of 2^n + 1

LinkBack

Thread Tools

Display

Primitive root of 2^n + 1

Similar Math Help Forum Discussions

Prove if a is a primitive root mod p^2, then it is a primitive root mod p

primitive root

Primitive root

primitive root

primitive root

Search Tags