"For instance there are no primitive roots modulo 8. To see this note that the only integers less than 8 and relatively prime to 8 are 1, 3, 5, and 7..."
The author then proceeds to show that the order of these numbers with $n=8$ is less than $\phi(n)$. I apologize if this seems basic - (maybe it arises from a definition), but why must primitive roots be less than and relatively prime to $n$? What is to say that $16^\phi(8)$ is not the smallest power congruent to $1 \mod 8$?