Results 1 to 5 of 5

Thread: Primitive root of 2^n + 1

  1. #1
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722

    Primitive 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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Deadstar View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by chiph588@ View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by chiph588@ View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by chiph588@ View Post
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Feb 27th 2011, 05:59 PM
  2. primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 10th 2009, 05:53 PM
  3. Primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 29th 2008, 07:47 PM
  4. primitive root
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 28th 2008, 08:36 AM
  5. primitive root
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 30th 2006, 02:21 PM

Search Tags


/mathhelpforum @mathhelpforum