1
$\begingroup$

"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$?

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.