Nel corso della dimostrazione il fatto j verrà spesso abbreviato Fj.
Fatto 1: $f\left(x\right)>1\ \ \forall x>1$.
Dimostrazione: se per assurdo esistesse $x>1$ tale che $f\left(x\right)=1$ allora per l'ipotesi del problema dovremmo avere che $f\left(x-1\right)+f\left(1\right)$ non è divisibile per nessun primo, quindi è uguale a $1$, assurdo perché $f$ va in $\mathbb{Z}^+$.
Fatto 2: per ogni primo $p$ sia $A_p\subseteq\mathbb{Z}^+:\ \ p\mid f\left(x\right)\Leftrightarrow x\in A_p$. Allora, detto $a_p$ il più piccolo elemento di $A_p$ (esiste per la suriettività!), si ha che gli elementi di $A_p$ sono in progressione aritmetica di ragione $a_p$.
Dimostrazione: sfruttando l'ipotesi del problema, con una semplice induzione si riesce a far vedere che $p\mid f\left(ka_p\right)\ \ \forall\ k\in\mathbb{Z}^+$. Adesso supponiamo per assurdo che esistano $h,\ 1\le j<a_p$ tali che $p\mid f\left(ha_p+j\right)$. Ma allora per l'ipotesi del problema, poiché $p\mid f\left(ha_p\right)\wedge\ p\mid f\left(ha_p+j\right)$, si ha che $p\mid f\left(j\right)$ che va contro l'ipotesi che $a_p$ fosse il minimo di $A_p$.
Un corollario di F2 è che $f\left(1\right)=1$, altrimenti se $f\left(1\right)$ fosse divisibile per almeno un primo $q$ allora tutti gli elementi dell'immagine di $f$ lo sarebbero, e addio suriettività.
Fatto 3: per ogni primo $p$ si ha che $a_p$ è primo.
Dimostrazione: ragioniamo come al solito per assurdo, quindi supponiamo esistano due primi distinti $p_1$ e $p_2$ tali che divide $p_2\mid a_{p_1},\ p_2<a_{p_1}$. Allora, poiché $f\left(p_2\right)>1$ per F1, esiste un primo $q$ che divide $f\left(p_2\right)$, quindi $a_q\stackrel{F2}{\mid}p_2\mid a_{p_1}\Rightarrow a_q\mid a_{p_1}$. Per come abbiamo definito $p_1$ e $p_2$ sappiamo inoltre che $a_q\le p_2<a_{p_1}$, quindi $q\ne p_1$. A questo punto se $a_q\mid a_{p_1}$ ciò significa che nell'immagine di $f$ tutti i multipli di $p_1$ saranno anche multipli di $q$, ciao ciao suriettività.
Un corollario di F3 è che $f\left(p\right)$ è una potenza di un primo (non necessariamente uguale a $p$) per ogni $p$ primo.
Fatto 4: per ogni primo $p$ si ha che $a_p=p$.
Dimostrazione: facendo attenzione a non confondere con la notazione della dimostrazione per assurdo di F3, definiamo $p_n$ l'$n$-esimo numero primo in ordine crescente.
Dimostriamo F4 per induzione su $n$. Passo base: $f\left(1\right)+f\left(1\right)=2\Rightarrow 2\mid f\left(2\right)$.
Veniamo al passo induttivo. Supponiamo F4 vero per $p_n$ con $n$ che va da $1$ a $k-1$. Supponiamo per assurdo che $a_{p_k}=p_l$ con $l\ne k$ (grazie all'ipotesi induttiva estesa e grazie al corollario di F3 sicuramente $l>k$). Ma allora se $p_k\mid f\left(p_l\right)$ per l'ipotesi del problema abbiamo che per ogni $0<s<p_k$ si ha che $p_k\mid f\left(s\right)+f\left(p_l-s\right)$. Inoltre $p_k\not\mid f\left(s\right)$ altrimenti contraddiremmo che $a_{p_k}=p_l$. Ma allora sfruttando il fatto che $p_l>p_k$, abbiamo che per un semplice pigeonhole esisteranno $0<s_1<s_2<p_l$ con $s_1\ne p_l-s_2$ tali che $p_k\mid f\left(s_1\right)+f\left(s_2\right)$. Quindi $p_k\mid f\left(s_1+s_2\right)$, ma d'altronde $p_l\ne s_1+s_2<2p_l$, quindi non $s_1+s_2$ non è multiplo di $p_l$, il che va a contraddire il fatto che $a_{p_k}=p_l$.
Fatto 5: per ogni $n\in\mathbb{Z}^+$ l'insieme dei primi che dividono $n$ coincide con l'insieme dei primi che dividono $f\left(n\right)$.
Dimostrazione: conseguenza di F2 e F4.
Fatto 6: $f\left(p^t\right)=p^t$ per ogni $\left(p,t\right)\in\mathbb{P}\times\mathbb{Z}^+$.
Dimostrazione: verrebbe più veloce con Zsigmondy, ma facciamo le brave persone e accontentiamoci di un'induzione + lemma del guadagno di un primo (LGP). Passo base: $t=1$. Poniamo per assurdo $f\left(p\right)=p^{d>1}$. Ma allora $f\left(1\right)+f\left(p\right)=1+p^d$. Ma essendo $d>1$, per LGP esisterà quindi un primo che divide $1+p^d$ ma che non divide $1+p$, quindi per F5 che non divide $f\left(1+p\right)$, assurdo.
Passo induttivo: F6 vero per ogni $t<k$. Allora supponiamo per assurdo che $f\left(p^k\right)=p^{e\ne k}$.
Caso 1: $e<k$. Allora $f\left(p^{e-1}\right)+f\left(p^k\right)=p^{e-1}\left(p+1\right)$ il che significa che quest'ultima quantità ha gli stessi fattori primi di $f\left(p^{e-1}+p^k\right)$, quindi per F5 ha gli stessi fattori primi di $p^{e-1}+p^k=p^{e-1}\left(p^{k+1-e}+1\right)$. Ma allora $p-1$ ha gli stessi fattori primi di $p^{k+1-e}+1$, assurdo per LGP, infatti $k+1-e\ge 2$.
Caso 2: $e>k$. Allora $f\left(p^{k-1}\right)+f\left(p^k\right)=p^{k-1}+p^e=p^{k-1}\left(p^{e+1-k}+1\right)$, quindi quest'ultima quantità ha gli stessi fattori primi di $f\left(p^{k-1}+p^k\right)$, quindi per F5 ha gli stessi fattori primi di $p^{k-1}+p^k=p^{k-1}\left(p-1\right)$. Analogamente al caso 1 quindi $p-1$ ha gli stessi fattori primi di $p^{e+1-k}+1$, assurdo per LGP, infatti $e+1-k\ge 2$.
Fatto 7: $f\left(n\right)=n\ \ \forall n\in\mathbb{Z}^+$.
Dimostrazione: supponiamo per assurdo che per un certo $m$ si abbia $f\left(m\right)=m_1\ne m$. Allora sia $q$ un primo maggiore sia di $m_1$ che di $m$, in modo che quindi $m_1\not\equiv m\pmod{q}$. Sia $g$ un generatore modulo $q$. Sia $q_1$ un primo congruo $g$ modulo $q$ (esiste per Dirichlet). Quindi per un opportuno intero $v$ si avrà $q_1^v\equiv -m_1\pmod{q}$. Ma allora $f\left(m\right)+f\left(q_1^v\right)\stackrel{F6}{=}m_1+q_1^v$ è multiplo di $q$.
D'altronde per F5 $q\mid f\left(m+q^v\right)\Leftrightarrow q\mid m+q^v$, il che non può accadere in quanto $m\not\equiv m_1\pmod{q}$.
