How is $3$ not a primitive root mod 8? 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.
 A: $\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. 
A: 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$.
A: For starters,


*

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

*$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
A: 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$.
