Cyclic groups

You've seen cyclics groups before, they were just disguised as ``clock arithmetic''.

Example 5.1.1   Let $C_{12}$ be the group whose elements are $\{0,1,...,11\}$ and for which the group operation is simply ``addition mod $12$", just as one adds time on a clock (except that we call ``12 o'clock" ``0 o'clock"). Thus $5+8=1$, $1+11=0$, and so on. Questions: What is the element (the ``inverse of $5$'') of $C_{12}$ which, when added to $5$, gives 0? What is the inverse of $1$? This group is called the (additive) cyclic group of order 12.

Definition 5.1.2   Let $n>1$ be an integer and let $C_{n}$ be the group whose elements are $\{0,1,...,n-1\}$ (more precisely, $\{\overline{0},\overline{1},..., \overline{n-1}\}$, where $\overline{i}$ is the residue class mod $n$ of $i$) and for which the group operation is simply ``addition modulo $n$''. This group is called the (additive) cyclic group of order $n$.

We've encountered cyclic groups before in this book - when discussing the discrete log problem in §1.8.5 as as $\mathbb{Z}/n\mathbb{Z}$ chapter 1. In the additive case, the problem boiled down to the following: given $a,b\in C_n$, find $x\in C_n$ (if it exists) such that $ax=b$. As we know, $x$ exists if $gcd(a,n)=1$ and, in that case, $x=a^{-1}b$. Here $a^{-1}\in C_n$ is the (multiplicative) inverse of $a$ mod $n$. The multiplicitive case of the discrete log problem is of course much harder.

Exercise 5.1.3   Solve the following problems for $x$ (or state $DNE$ if $x$ does not exist). (a) $5x=7$ in $C_{12}$, (b) $5x=6$ in $C_{12}$, (c) $4x=7$ in $C_{12}$ (hint: what happens when you multiply each side by 3?), (d) $8x=12$ in $C_{12}$ (see hint above), (e) $x^5=7$ in $C_{12}$, (f) $5^x=7$ in $C_{12}$.