primitive root

**mandy123** · April 28th 2008, 07:49 AM

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

**icemanfan** · April 28th 2008, 08:35 AM

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}$ ?

**ThePerfectHacker** · April 28th 2008, 08:36 AM

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.

Thread: primitive root

LinkBack

Thread Tools

Display

primitive root

Similar Math Help Forum Discussions

Prove if a is a primitive root mod p^2, then it is a primitive root mod p

primitive root

primitive root

Primitive root

primitive root

Search Tags