If r is a primitive root mod m, then r is a primitive root $\pmod{\phi(m)}$?

92 Views Asked by At

Gerstein's Introduction to Mathematical Structures and Proofs offers the following proposition and corollary:

Suppose r is a primitive root mod m:

Prop 6.80: $log_r xy \equiv log_r x + log_r y$

Corollary: Suppose $gcd(x_i,m)=1$ $ \forall i <\phi$ Then

$log_r \Pi x_i = \Sigma log_r x_i \pmod{\phi(m)}$

I can see easily why the corollary would be true if the modulus were m, but the modulus is $\phi(m)$. We can establish this if it is true that r being a primitive root mod m implies r is also a primitive root $\pmod{\phi(m)}$. Is this true?

3

There are 3 best solutions below

0
On BEST ANSWER

No, $2$ is a primitive root for $3$ but not for $\phi(3)=2$. Similarly, $2$ is a primitive root for $5$ but not for $\phi(5)=4$. In fact $2$ is a primitive root for many odd prime numbers $p$ but never for $\phi(p)=p-1$.

0
On

If $m = p^k$ for $p$ a prime $> 3$ and $k > 1$, $\phi(m) = p^{k-1} (p-1)$ so $m$ has a primitive root but $\phi(m)$ does not.

0
On

The statement I made, "I can see easily why the corollary would be true if the modulus were m", was mistaken. $\phi(m)$, not m, is the correct modulus.