Siccome nessuno ha più provato a risolvere il quesito, posto le soluzioni che ho trovato
1)
Testo nascosto, fai click qui per vederlo
Dimostriamo che l'unica funzione che soddisfa le condizioni i) e ii) contemporaneamente è l'identità.
Sia \( f \) una funzione che soddisfa le condizioni del problema 1) dalla condizione ii) deduciamo che siccome per ogni \( p \) primo abbiamo che \( p \not\mid 1 \) segue che \( p \not\mid f(1) \) per ogni \( p \) primo e dunque \(f(1) =1 \).
Sia \( N > 1 \) supponiamo che per ogni \( n < N \) abbiamo che \(f(n)=n \). Siccome \(N>1\) abbiamo che esiste \( p \) primo tale che \( p \mid N \) e dunque \( p \mid f(N) \).
Supponiamo per assurdo che \( f(N) > N \), abbiamo allora che esiste un numero primo \(q\) tale che \( q \mid f(N) - N +1 \) poiché \( f(N)-N+1 >1\) pertanto segue che \( f(N) \equiv N-1 \mod q \).
Per ipotesi d'induzione abbiamo che \( N-1=f(N-1) \equiv f(N) \mod q \). Per la condizione i) abbiamo dunque che \(N-1 \equiv N \mod q \) che è assurdo!
Supponiamo dunque per assurdo che \( f(N) < N \), per ipotesi d'induzione abbiamo che \( f(f(N)-1) = f(N)-1\). Inoltre analogamente a prima abbiamo che esiste un numero primo \( q \) tale che \(q \mid N-f(N)+1 \) e segue che \( N \equiv f(N)-1 \mod q \). Grazie alla condizione i) segue che \( f(N)\equiv f(f(N)-1) = f(N)- 1 \mod q \) che è assurdo.
Pertanto \( f(N) = N \) è l'unica scelta possibile.
Chiaramente l'identità soddisfa le condizioni i) e ii)
\(\square \)
2)
Testo nascosto, fai click qui per vederlo
La dimostrazione del punto 2) passa attraverso tre piccoli lemmi.
Sia \( p \) un numero primo arbitrario, ed \(f \) come nel problema 2), poniamo \[ m_p = \min \{ n \in \mathbb{N} : p \mid f(n) \} \]
\( m_p \) è ben definito poiché \(f \) è suriettiva. D'ora in poi siccome la scelta di \(p \) è arbitraria per alleggerire la notazione scriverò \(m \) per indicare \(m_p \).
Lemmi: Sia \( f \) come nel problema 2), \(p \) un primo arbitrario ed \(m \) definito qui sopra allora segue che:
a) \(p \mid f(n) \) se e solo se \( m \mid n \)
b) Dati \(x,y \in \mathbb{N} \) abbiamo che \( x \equiv y \mod m \) se e solo se \( f(x) \equiv f(y) \mod p \)
c) \( p = m \).
Dimostriamo b) grazie ad a) e dimostriamo c) grazie a b) infine dimostriamo 2) grazie ad c) e dunque ad 1).
Dimostrazione di a)
\( \Leftarrow \):
Se \( k = 1 \) abbiamo per definizione di \(m \) che \( p \mid f(m) \). Supponiamo vero che per \( k=n \) abbiamo che \( p \mid f(n m) \), abbiamo che \( p \mid f(nm) + f(m) \) e grazie alla proprietà della \(f \) abbiamo che \( p \mid f(nm+n)=f(m(n+1)) \)
\( \Rightarrow \):
Supponiamo per assurdo che esiste \( n \in \mathbb{N} \) tale che \( m \not\mid n \) e \( p \mid f(n) \)
Poniamo \( x = \min \{ n \in \mathbb{N} : m \not\mid n, p \mid f(n) \} \). Per definizione di \(m \) abbiamo chiaramente \( x > m \) e dunque \(x > x-m >0 \) e non è divisibile per \( m\) altrimenti \( x \) è divisbile per \(m\).
Per definizione di \(x \) abbiamo che \( p \not\mid f(x-m) \) ma al contempo abbiamo che \( p \mid f(m) \) e \( p \mid f(x)=f(m+x-m) \) e dunque per la proprietà di \( f \) abbiamo che \( p \mid f(x-m) \) contraddizione.
Dimostrazione di b):
\( \Rightarrow \):
Siano \(x,y \in \mathbb{N} \) tale che \( x \equiv y \mod m \).
Abbiamo grazie ad a) che \( p \mid f(2xm)=f(x+2xm-x) \), inoltre \( m \mid y + 2xm -x \) pertanto sempre grazie ad a) risulta che \( p \mid f(y+2xm-x) \)
Dunque grazie alla proprietà di \(f \) otteniamo che \( p \mid f(x) + f(2xm-x) \) e \( p \mid f(y) + f(2xm-y) \) pertanto segue che \( f(x) \equiv -f(2xm-x) \mod p \) e \( f(y) \equiv -f(2xm-x) \mod p \) e concludiamo che \( f(x) \equiv f(y) \mod p \).
\( \Leftarrow \):
Siano \( x,y \in \mathbb{N} \) tale che \( f(x) \equiv f(y) \mod p \).
Analogamente a prima otteniamo che \( p \mid f(x) + f(2xm-x) \). Deduciamo dunque grazie alla proprietà della funzione \(f \) che \(p \mid f(x) + f(2xm-x) + f(y)-f(x) = f(y) + f(2xm-x) \)
E dunque ancora otteniamo che \( p \mid f(y+ 2xm-x) \)
Grazie ad a) abbiamo che \( 0 \equiv y+ 2xm-x \equiv y-x \mod m \)
Dimostrazione di c)
Abbiamo che i numeri \( 1,2,3,\ldots,m \) appartengono due a due a classi di resto modulo \( m \) distinti. Grazie al lemma b) deduciamo che \( f(1), f(2),f(3),\ldots,f(m) \) appartengono due a due a classi di resto modulo \(p \) distinti, pertanto vi sono almeno \(m \) resti distinti e dunque \( p \geq m \).
Per suriettività di \(f \) abbiamo che esistono \(n_1,\ldots,n_p \) interi positivi tale che \( f(n_k)=k \) per ogni \( k =1,\ldots ,p \). Grazie al lemma b) abbiamo che gli interi \( n_k \) appartengono due a due a classi di resto modulo \(m \) distinti e pertanto siccome gli \(f(n_k) \) appartengono due a due a classi di resto modulo \(p \) distinti vi sono almeno \( p \) resti distinti e dunque \( m \geq p \).
Segue che \( m = p\).
Dimostrazione di 2)
Per la scelta arbitraria di \(p \) primo concludiamo dunque che una funzione \(f \) come nel problema 2) soddisfa contemporaneamente le condizioni i) e ii) del problema 1) per ogni primo \(p \) e dunque grazie ad 1) abbiamo che l'identità è l'unica funzione che possiede la proprietà del punto 2).
\(\square \)