Results 1 to 3 of 3

Thread: 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 $\displaystyle 2^t$ is a number $\displaystyle r: 1 < r < 2^t$ such that the numbers $\displaystyle r, r^2, r^3, ... r^{2^t - 1}$ are all distinct numbers modulo $\displaystyle 2^t$. One way of disproving this would be to show that $\displaystyle r^m$ is congruent to 1 for some $\displaystyle m < 2^t - 1$. Perhaps you could try induction on n, taking $\displaystyle 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
    10
    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 $\displaystyle 5^{2^{t-3}} \equiv 1+2^{t-1}(\bmod 2^t)$ for $\displaystyle t\geq 3$. This shows that the order of $\displaystyle 5$ is $\displaystyle 2^{t-2}$.

    Once you established that prove that $\displaystyle A=\{1,5,5^2,...,5^{2^{t-1}-1}\} = \{5^k| 0\leq k < 2^{t-2}\}$ are all incongruent with eachother. Then $\displaystyle 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 $\displaystyle A$ is incongruenct with each element of $\displaystyle B$.

    With those two facts the proof is almost complete. Because there are a total of $\displaystyle 2^{t-2} + 2^{t-2} = 2^{t-1}$ in $\displaystyle A\cup B$ and $\displaystyle \phi ( 2^t) = 2^{t-1}$. Which means $\displaystyle A\cup B$ is a reduced system of residues. And each element does not have order $\displaystyle 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: Feb 27th 2011, 05:59 PM
  2. primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 8th 2010, 08:49 AM
  3. primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 10th 2009, 05:53 PM
  4. Primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 29th 2008, 07:47 PM
  5. primitive root
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 30th 2006, 02:21 PM

Search Tags


/mathhelpforum @mathhelpforum