# Why must a primitive root be less than and relatively prime to n?

"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$.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}