Results 1 to 3 of 3

Math Help - primitive root

  1. #1
    Member
    Joined
    Feb 2008
    Posts
    125

    primitive root

    show that primitive root modulo 2^t where t is positive integer, does not exist for t>2
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by mandy123 View Post
    show that primitive root modulo 2^t where t is positive integer, does not exist for t>2
    Ok, I'll take a crack at this. A primitive root modulo 2^t is a number r: 1 < r < 2^t such that the numbers r, r^2, r^3, ... r^{2^t - 1} are all distinct numbers modulo 2^t. One way of disproving this would be to show that r^m is congruent to 1 for some m < 2^t - 1. Perhaps you could try induction on n, taking m = 2^{t-1}?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by mandy123 View Post
    show that primitive root modulo 2^t where t is positive integer, does not exist for t>2
    The proof depends on the fact that 5^{2^{t-3}} \equiv 1+2^{t-1}(\bmod 2^t) for t\geq 3. This shows that the order of 5 is 2^{t-2}.

    Once you established that prove that A=\{1,5,5^2,...,5^{2^{t-1}-1}\} = \{5^k| 0\leq k < 2^{t-2}\} are all incongruent with eachother. Then B=\{ -1,-5,-5^2,...,-5^{2^{t-1} - 1}\} = \{ -5^k|0\leq k < 2^{t-2}\} are all incrongruent with eachother. And finally each element in A is incongruenct with each element of B.

    With those two facts the proof is almost complete. Because there are a total of 2^{t-2} + 2^{t-2} = 2^{t-1} in A\cup B and \phi ( 2^t) = 2^{t-1}. Which means A\cup B is a reduced system of residues. And each element does not have order 2^{t-1}. Which means it has no primitive root.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: February 27th 2011, 05:59 PM
  2. primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 8th 2010, 08:49 AM
  3. primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 10th 2009, 05:53 PM
  4. Primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 29th 2008, 07:47 PM
  5. primitive root
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 30th 2006, 02:21 PM

Search Tags


/mathhelpforum @mathhelpforum