Is There a Strategy for Finding Primitive Roots of 2p^n If There is One for p^n?

[Poirot1]

let p be an odd prime. Show that if there is a primitive root of p^n, then there is a primitive root of 2p^n. Strategy?

 

[caffeinemachine]

Re: primitive root

let p be an odd prime. Show that if there is a primitive root of p^n, then there is a primitive root of 2p^n. Strategy?

Let $r$ be a primitive root of $p^n$. If $r$ is odd then we can show that $r$ is a primitive root of $2p^n$. If $r$ ain't odd then it can be shown that $r+p^n$ is a primitive root of $2p^n$.

 

[Poirot1]

Re: primitive root

Let $r$ be a primitive root of $p^n$. If $r$ is odd then we can show that $r$ is a primitive root of $2p^n$. If $r$ ain't odd then it can be shown that $r+p^n$ is a primitive root of $2p^n$.

Ok let's first assume r is odd. Then if d divides g(p^n), we have r^d=1 (mod p^n) iff
d = g(p^n). But g(p^n)=g(2p^n). r is odd so r^d=1 (mod 2). Can we somehow combine moduli?

 

[caffeinemachine]

Re: primitive root

Can we somehow combine moduli?

Under certain conditions yes.

Say $x\equiv a\pmod{m}, x\equiv a\pmod{n}$ and gcd$(m,n)=1$. Then $x\equiv a\pmod{mn}$

 

[CellCoree]

Yes, there is a strategy for finding primitive roots of 2p^n if there is one for p^n. First, let's clarify the definition of a primitive root. A primitive root of a prime number p is an integer a such that a^k ≡ 1 (mod p) for all positive integers k less than p-1. In other words, a is a generator of the multiplicative group of integers modulo p.

Now, let's consider the case where p is an odd prime and there exists a primitive root of p^n, denoted as a. This means that a is a generator of the multiplicative group of integers modulo p^n. We can then use this fact to show that there is also a primitive root of 2p^n.

First, note that 2p^n is also a prime number, since p is an odd prime. We can then use the following theorem: if a is a primitive root of p, then a is also a primitive root of p^n for any positive integer n. This means that a is a generator of the multiplicative group of integers modulo p^n.

Next, we can use the fact that 2 is a primitive root of 2p (since 2 is a primitive root of any prime number). This means that 2 is also a primitive root of 2p^n, since 2 is a generator of the multiplicative group of integers modulo 2p^n.

Therefore, we have shown that if there exists a primitive root of p^n, then there is also a primitive root of 2p^n. This means that the strategy for finding primitive roots of 2p^n is to first find a primitive root of p^n and then use the theorem mentioned above to find a primitive root of 2p^n.

In conclusion, the strategy for finding primitive roots of 2p^n if there is one for p^n is to first find a primitive root of p^n and then use the theorem mentioned above to find a primitive root of 2p^n. This is a useful strategy for finding primitive roots of 2p^n efficiently, as it builds upon the fact that we already know a primitive root of p^n.