3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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)$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.