How many primitive roots does $334$ have?

Question

Clearly $334 = 2 \times 167$. So it is of the form $2p^k$ which implies primitive roots $\bmod 334$ exits but the question is how many?

The formula $\phi(\phi(n))$ requires $n$ to be prime. If we use it for $334$ which is composite, we get $\phi(\phi(334)) = 82$.

So can we conclude that there are $82$ primitive roots $\bmod 334$?

Answer 1

The formula $\phi(\phi(n))$ does not require $n$ to be prime:

• the primitive roots mod $n$ are exactly the generators of the group $U(n)$ when $U(n)$ is cyclic

• a cyclic group of order $m$ has $\phi(m)$ generators

• the group $U(n)$ has order $m=\phi(n)$

Answer 2

Yes, you can. The formula $\varphi(\varphi(n))$ is valid even if $n$ is not prime, as soon as the group $\mathbf Z/\mathbf Z^\times$ is cyclic since a cyclic group of order $r$ has $\varphi(r)$ generators.