Show that there exist a positive integer $M>1$

Question

Let $f$ be a bijective (one-one and onto) function from the set $$A=\{1,2,3,…,n\}$$ to itself. Show that there is a positive integer $M>1$ such that $$f^M(i)=f(i)$$ for each $i\in A$

[$f^M$ denotes the composite function $f\times f \times f \times \dotsb \times f$, repeated $M$ times.]

Please help me!!!

Answer 1

Consider the set $S$ to be the set of all bijective functions on $A$. Then check that $|S| = n!$. In fact, all you need is that $|S| < \infty$.

Now consider the set $T:= \{f, f^2, f^3, \ldots\} \subset S$. Since $T$ is finite, $\exists n,m\in \mathbb{N}$ such that $n\neq m$ and $$ f^n = f^m $$ as functions (ie. $f^n(i) = f^m(i)$ for all $1\leq i\leq m$).

Can you use this to construct the number $M$ you need?

Answer 2

Hint: Look at $1,f(1),f^2(1),\ldots$. This is a repeating sequence of some length. Look at all other such sequences and their lengths. Let $N$ be the product of all those lengths. What is $f^N(i)$? What is $f^{N+1}(i)$?

Answer 3

Obviously $f \in S_n$, the symmetric group on sets of $n$ elements, which is finite. Then there must be a positive integer $M$ with $f^M = e$, where $e$ is the (multiplicative) identity, otherwise $f$ would generate an infinite set.

In other words at some finite $j$ we must have a repetition of some prior element at $i$, $i < j$: $$ f^j = f^i \iff f^{j-i} = e $$ so $M = j - i > 0$.