Prima un po' di cose base.
Fatto 1. Per ogni intero positivo $m$, $f(m) > m$.
Dimostrazione. $n = 1$ nel testo.
Fatto 2. $f$ è iniettiva.
Dimostrazione. Supponiamo che per $a < b$ si abbia $f(a) = f(b)$. Sia $n = b - a + 1$. Allora $n \mid f^n(a) - a$ e $n \mid f^n(b) - b$, ma $f^n(a) = f^n(b)$ quindi $n \mid f^n(a) - a - (f^n(b) - b) = b - a$, evidentemente assurdo.
Fatto 3. Per ogni $m, \: n \in \mathbb{Z}^+$, vale $f(m) - m \equiv f^{n + 1}(m) - f^n(m) \pmod{n}$.
Dimostrazione. Abbiamo $m \equiv f^n(m)$ e $f(m) \equiv f^n(f(m)) = f^{n + 1}(m) \pmod{n}$, da cui $f(m) - m \equiv f^{n + 1}(m) - f^n(m) \pmod{n}$.
Ora le immancabili ***definizioni***!
Definizione 1. Fissato $a \in \mathbb{Z}^+ \setminus \text{Im} \: f$, chiamiamo catena di $a$ l'insieme $$C_a = \{f^n(a): \: n \in \mathbb{N}\}$$ (dove $f^0(m) = m$).
Corollari. Poiché le catene sono in ovvia bigezione con gli interi positivi che non stanno nell'immagine di $f$, le catene sono in numero finito. Inoltre, dal Fatto 2 segue banalmente che le catene sono a due a due disgiunte, ossia ogni intero positivo appartiene a una e una sola catena.
Definizione 2. Diciamo che la catena $C$ è limitata se l'insieme $\{f(m) - m: \: m \in C\}$ è limitato superiormente. Definiamo invece stabile una catena $C$ se esiste un intero positivo $r$ tale che $f(m) - m = r$ per ogni $m \in C$; in tal caso, chiameremo $r$ la ragione di $C$.
E adesso passiamo alle cose serie.
Lemma 1. $C$ è una catena. Se $C$ è limitata, allora è anche stabile.
Dimostrazione. Sia $\displaystyle D = \max_{m \in C} \{f(m) - m\}$ (esiste!) e $m_0 \in C$ tale che $f(m_0) - m_0 = D$. Ora, per ogni $n \ge D$, per il Fatto 3 vale $$f^{n + 1}(m_0) - f^n(m_0) \equiv f(m_0) - m_0 = D \pmod{n}$$ e quindi, dato che $n \ge D$, $f^{n + 1}(m_0) - f^n(m_0) \ge D \implies f^{n + 1}(m_0) - f^n(m_0) = D$. Dunque $C$ è definitivamente stabile.
Ora sia $m_1$ tale che $f(m) - m = D$ per ogni $m_1 \le m \in C$, e supponiamo esista $m' \in C$ per cui $f(m') - m' < D$. Allora scegliamo $n \ge D$ tale che $f^n(m') \ge m_1$. Allora sempre per il Fatto 3 $f(m') - m' \equiv f^{n + 1}(m') - f^n(m')$, ma per quanto appena dimostrato $f^{n + 1}(m') - f^n(m') = D$, quindi $n \mid D - (f(m') - m')$ e questo è assurdo perché $n \ge D > D - (f(m') - m')$.
Lemma 2. Tutte le catene sono limitate (e quindi, per il Lemma 1, anche stabili).
Dimostrazione. Sia $s$ il numero di catene e supponiamo, per assurdo, che $k < s$ di queste siano limitate/stabili e le restanti $s - k$ no. Dette $r_1, \: r_2, \: \dots, \: r_k$ le ragioni delle $k$ catene stabili, poniamo $t = r_1r_2\cdots r_k$. Allora abbiamo una "periodicità parziale" di periodo $t$, cioè: se $m$ appartiene a una delle $k$ catene stabili (diciamo la $j$-esima), allora $f(m) - m = f(m + t) - (m + t) = r_j$ (questo perché, essendo $t$ multiplo di $r_j$, anche $m + t$ appartiene a tale catena). Adesso si dimostra (ma in realtà è circa ovvio, quindi non lo sto a giustificare) che esiste un intero positivo $h$ tale che, per infiniti interi positivi $a$, tra i numeri $a + 1, \: a + 2, \: \dots, \: a + ht$ ce ne sono almeno $s - k + 1$ che appartengono a una delle catene non limitate (non necessariamente la stessa per tutti). Ma allora, tra questi numeri, ce ne sono almeno $2$ che appartengono alla stessa catena non limitata, e quindi possiamo trovare interi $m$ grandi a piacere tali che $m$ appartiene a una catena non limitata e $f(m) - m < ht$.
D'altra parte, se $C$ è una catena non limitata, allora esiste un $m_2 \in C$ tale che $f(m_2) - m_2 = d \ge ht$. Per ogni $n \ge d$ abbiamo $$d = f(m_2) - m_2 \equiv f^{n + 1}(m_2) - f^n(m_2) \pmod{n}$$ e, poiché $n \ge d$, questo implica $f^{n + 1}(m_2) - f^n(m_2) \ge d$. Dunque esiste un $m_3$ tale che, per ogni catena non limitata $C$ e per ogni $m_3 \le m \in C$, $f(m) - m \ge d \ge ht$, e questo contraddice quanto detto sopra.
A questo punto abbiamo praticamente finito, perché abbiamo dimostrato che le $s$ catene sono tutte stabili. Dette quindi $r_1, \: r_2, \: \dots, \: r_s$ le loro ragioni e posto $T = r_1r_2\cdots r_s$, la successione $f(1) - 1, \: f(2) - 2, \: \dots$ è periodica di periodo $T$. Questo perché, se $m$ è un intero positivo che appartiene alla catena $j$-esima, vale $$m + T = f(m) + (T - r_j) = f^2(m) + (T - 2r_j) = \cdots = f^{T/r_j}(m)$$ quindi anche $m + T$ appartiene a quella stessa catena, e quindi banalmente $$f(m + T) - (m + T) = f(m) - m = r_j$$
