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

Printable View

- Apr 28th 2008, 07:49 AMmandy123primitive root
show that primitive root modulo 2^t where t is positive integer, does not exist for t>2

- Apr 28th 2008, 08:35 AMicemanfan
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}$?

- Apr 28th 2008, 08:36 AMThePerfectHacker
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.