"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$?
The have to be relatively prime to $n$ because if $x$ is a primitive root, then $x^n \equiv 1$ for some $n$, and therefore $x^{n-1}$ must be the multiplicative inverse of $x$. But only numbers relatively prime to $n$ have a multiplicative inverse.
They don't strictly speaking have to be smaller than $n$, but any number larger than $n$ is equivalent modulo $n$ to some number smaller than $n$. Remember that $$ a \equiv b \mod n \quad\Leftrightarrow\quad \exists k \in \mathbb{Z} \,:\, a - b = kn \text{.} $$ So if $a \geq n$, we can substract $n$ until we reach an integer $b$ within $[0,n-1]$. If we had to subtract $k$ times, we have $b = a - kn$, i.e. $a - b = kn$, so $a \equiv b \mod n$.