0

Let $n \geq 4$ be an even integer and let $S= \{1,2,\ldots,n\}$. Fix an element $r \in \{1,2,\ldots, \frac{n}{2}-1\}$. Define a map $f: S \longrightarrow S$ by $f(t)=s$, for all $t \in S$, where $s$ is the remainder when $t+r$ is divided by $n$.

(1) Show that $f$ is a bijection (i.e. $f$ is a permutation on $\{1,2,\ldots,n\}$).

(2) Show that $f$ can be written as a product of $k$ disjoint cycles, where $k=gcd~(n,r)$.

(3) What is the length of each of these cycles ?

I guess that the length of each cycle is $m$, where $n=mk$; But couldn't achieve the proofs. Any suggestions in this regard will be useful.

RKR
  • 547

1 Answers1

0

Note that $f^{k}(t) \equiv t + k\cdot r \pmod n.$ So the first $k$ such that $f^k(t)\equiv t$ for any $t\in S$ is the smallest integer $k$ such that $k\cdot r$ is a multiple of $n.$ Everything you need to show follows from this.

In particular, $f^n$ is the identity map and $f^{n-1}$ is the inverse of $f.$ So, $f$ is bijective.

Reiner Martin
  • 4,097