How is $3$ not a primitive root mod 8?

Question

Sources are telling me that there are no primitive roots $\mod 8$, yet $\phi (8) = 4$ and $3^{\phi(8)} = 1 \mod 8$. Thus $1, 3$ form a reduced residue system.

Answer 1

A primitive root $a$ modulo $n$ achieves all of the numbers relatively prime to $n$ through taking successive powers. Thus we could define a sort of logarithm using $a$ as a base.

In the case of numbers modulo $8$, every element relatively prime to $8$ has order $2$ (except of course $1$). This includes $3$,$5$, and $7$.

This means that $3^2 \equiv 5^2 \equiv 7^2 \equiv 1 \mod 8$, and there is no power of $3$ that will equal $5$ or $7$.

Answer 2

For starters,

1. $\Bbb Z_8^*$ has no primitive roots because it is not cyclic.

2. $3^2$ = $1$ mod 8. So, $order_8 (3) = 2$. Thus, because $order_8 (3) \not= \phi(8)$, $3$ is not a primitive root mod $8$ Intuitively, there is no power we can raise $3$ to that will give us any elements in $\Bbb Z_8^*$ other than $3$ and $1$.

Not all $\Bbb Z_n^*$ have generators. However, All $\Bbb Z_p^*$ for prime p

Answer 3

You have a primitive root $a$, mod $m$ when $\phi(m)$ is the smallest integer $n$ such that $a^m \equiv 1 \mod m$. In this case, $3^2\equiv 9 \equiv 1 \mod 8$ and $2 \neq \phi(8) = 4$.

Answer 4

$\phi(8) = 4$ because there are $4$ numbers less than $8$ and coprime to it - the totatives of $8$ - $\{1,3,5,7\}$.

In order for a number to be a primitive root $\bmod n$, its powers $\bmod n$ must cycle through all the totatives of $n$ with of course $1$ being the last because that restarts the cycle.

However, for $8$,
$3^2 =9 \equiv 1 \bmod 8, \\ 5^2 =25 \equiv 1 \bmod 8, \\ 7^2 =49 \equiv 1 \bmod 8,$
so there is no primitive root among the totatives.

Any time the Carmichael function of a number is less than Euler's totient, there are no primitive roots.