Checking understanding of Order, Primitive Roots

169 Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST 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$.