TAOCP 1.3.3 Exercise 1
Let $f(x)=2x \bmod 7$ on ${0,1,2,3,4,5,6}$.
Section 1.3.3: Applications to Permutations
Exercise 1. [02] Consider the transformation of ${0, 1, 2, 3, 4, 5, 6}$ that replaces $x$ by $2x \bmod 7$. Show that this transformation is a permutation, and write it in cycle form.
Verified: yes
Solve time: 1m07s
Let $f(x)=2x \bmod 7$ on ${0,1,2,3,4,5,6}$. Since $\gcd(2,7)=1$, there exists $2^{-1}\equiv 4 \pmod 7$, so $x\mapsto 2x \bmod 7$ is invertible with inverse $x\mapsto 4x \bmod 7$; hence $f$ is a permutation of the set.
Compute successive images:
$$ 0 \mapsto 0,\quad 1 \mapsto 2,\quad 2 \mapsto 4,\quad 4 \mapsto 1, $$
giving the cycle $(1\ 2\ 4)$. Also,
$$ 3 \mapsto 6,\quad 6 \mapsto 5,\quad 5 \mapsto 3, $$
giving the cycle $(3\ 6\ 5)$. The element $0$ is fixed and does not appear in cycle notation.
The permutation in cycle form is
\boxed{(1\ 2\ 4)(3\ 6\ 5)}. $$∎