# Math Help - primitive root

1. ## primitive root

show that primitive root modulo 2^t where t is positive integer, does not exist for t>2

2. Originally Posted by mandy123
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}$?

3. Originally Posted by mandy123
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.