117. $2^k\mid n^n-m$

[nobu]

Dati $k$ ed $m$ interi positivi con $m$ dispari, dimostrare che esiste $n$ tale che $2^k\mid n^n-m$.

P.S. spero vada bene

[jordan]

Lavorando in $S_n:= (\mathbb{Z}/2^n\mathbb{Z})^*$ (l'insieme dei residui mod $2^n$ e coprimi con esso), e' sufficiente dimostrare che la funzione $f_n(x):= x^x$ e' bigettiva in $S_n$. $f_1(x)$ e' chiaramente bigettiva in $S_1$, e supponiamo lo sia anche in $S_n$. Se in $S_n$ fosse $f_n(x)=y$, allora in $S_{n+1}$ sarà $f_{n+1}(x):=z \in \{y,y+2^n\}$ e $f_{n+1}(x+2^n)=(x+2^n)^{x+2^n}=\displaystyle \sum_{0\le i\le x+2^n}{\binom{x+2^n}{i}2^{ni}x^{x+2^n-i}}$ $=x^{x+2^n}+2^n\left((x+2^n)(x^{x+2^n-1})\right)=x^x\cdot x^{2^n}+2^n=z+2^n \in \{y,y+2^n\}$. Allora $f_{n+1}(x)$ e' bigettiva in $S_{n+1}$. []

Ps. Bel problema! Il prossimo qui