Is this group cyclic?

Decide whether Z_n*, Z_n or a product of cyclic groups is cyclic, and write it as a product of cyclic groups.

How it works

A group is cyclic when one element, a generator, produces every element by repeating the operation. The additive group $\mathbb Z_n$ always is (take $1$). The multiplicative group $\mathbb Z_n^*$ of the numbers coprime to $n$ is cyclic only sometimes: Gauss proved that this happens exactly for $n = 1, 2, 4, p^k$ and $2p^k$ with $p$ an odd prime. So $\mathbb Z_7^*$ and $\mathbb Z_{18}^*$ are cyclic, $\mathbb Z_8^*$ and $\mathbb Z_{15}^*$ are not.

The test without the rule: the largest order of an element is the Carmichael function $\lambda(n)$, and the group is cyclic exactly when $\lambda(n) = \varphi(n)$. To see the structure, split $\mathbb Z_n^*$ with the Chinese remainder theorem into one group per prime power: $\mathbb Z_{p^k}^*$ is cyclic of order $p^{k-1}(p-1)$ for odd $p$, and $\mathbb Z_{2^k}^* \cong \mathbb Z_2 \times \mathbb Z_{2^{k-2}}$ for $k \ge 3$. For example $\mathbb Z_{15}^* \cong \mathbb Z_3^* \times \mathbb Z_5^* \cong \mathbb Z_2 \times \mathbb Z_4$.

A product $\mathbb Z_a \times \mathbb Z_b$ is cyclic exactly when $\gcd(a, b) = 1$, and then it is $\mathbb Z_{ab}$. Collecting the prime powers this way writes every finite abelian group uniquely as $\mathbb Z_{n_1} \times \dots \times \mathbb Z_{n_k}$ with $n_1 \mid n_2 \mid \dots \mid n_k$, the invariant factors. Cryptography wants cyclic groups (or cyclic subgroups of prime order) so that one generator $g$ reaches every key $g^x$; the points of an elliptic curve form a group of the same kind.

Everything is calculated in your browser. Nothing you type leaves your device.