I dont seem to understand how primitive roots work. I've outlined what I think, if anyone can tell me what I'm misunderstanding I'd really appreciate it!
To calculate the order of 5 modulo 18, our objective is to figure out $a$ when $5^{a} \equiv 1 (18)$ right?
Then the definition of a primitive root is a number $a$ such that
$a^{\varphi(18)} \equiv 1 (18)$ correct?
Answer
The order of $5$ modulo $18$ is the smallest positive value of $a$ such that $5^a \equiv 1 (18)$.
Since the powers of $5$ modulo $18$ are:
$$ 5^1 \equiv 5, \ \ \ 5^2 \equiv 7, \ \ \ 5^3 \equiv 17, \ \ \ 5^4 \equiv 13, \ \ 5^5 \equiv 11, \ \ \ 5^6 \equiv 1,$$
the order of $5$ modulo $18$ is $6$.
We need to be very careful when stating this definition. It's true that $5^{12} \equiv 1 (18)$ and $5^{18} \equiv 1 (18)$ etc, but it would be incorrect to say that the order of $5$ modulo $18$ is $12$ or $18$ etc.
A primitive root modulo $18$ is an element of the group of units modulo $18$ whose order is equal to $\varphi(18)$. In other words, a primitive root modulo $18$ is an element that generates the group of units.
Since $\varphi(18) = 6$, and since the order of $5$ is $6$, it is true that $5$ is a primitive root modulo $18$.
Again, we need to be very careful when we state the definition. We can't say that a primitive root is any $x$ in the group of units such that $x^{\varphi(18)} \equiv 1 (18)$, because, in fact, every $x$ in the group of units obeys the property $x^{\varphi(18)} \equiv 1 (18)$, by Lagrange's theorem!
Instead, $x$ is a primitive root modulo $18$ iff $\varphi(18)$ is the smallest power of $x$ that is equal to $1$ modulo $18$.
No comments:
Post a Comment