Primitive root:
If $a^{h}\equiv 1\pmod{n}$ is not possible for $ 1\le h \lt \phi(n)$, then $a$ is a primitive root of $n$.
Does this mean if $n$ has a primitive root, then a group of order $n$ is cyclic ?
Because we can use the primitive root to generate the entire group.
If my understanding so far is accurate, here is where I'm stuck at:
1) I read that if a group has order $pq$, where $p\gt q$ are primes and if $q\nmid p-1$, then the group is cyclic.
2) But I also know that a number of form $pq$ can not have a primitive root.
Aren't above two statements contradicting?
Best Answer
$\varphi (pq)=(p-1)(q-1)\lt pq$.
The existence of a primitive element $\pmod n$ doesn't mean a group of size $n$ is cyclic. It means the group of units $U_n$ (of size $\phi(n)$) is cyclic.
So there is no contradiction. $U_{pq}$, the group of units of $\Bbb Z_{pq}$, is never cyclic. But a group of order $pq$ can be cyclic (and is when $q\not\mid p-1$).