OliForum Matematico

Chiamiamo $ r(k) $ la somma dei resti della divisione di k per: 1,....k-1.Mostrare che esistono infiniti k tali che $ r(k)=r(k-1) $
E' un esercizio carino... Dalla gara Kurschak.

EDIT: Mi sono accorto ieri notte che ho fatto una domanda stupida.

perchè sempre le potenze di due???

Chiamo $ a_w $ i resti della divisione tra $ k $ e i numeri tra $ 1 $ e $ k-1 $.
$ k=a_{k-1} \hspace{0.2cm}(mod \hspace{0.2cm}k-1) $
$ k=a_{k-2} \hspace{0.2cm}(mod \hspace{0.2cm}k-2) $
$ \cdots $
Si ha quindi che $ r(k)=a_1+\dots+a_{k-1} $.
Analizziamo $ r(k-1) $: per tutti gli $ a_i>0 $ si ha $ k-1=a_i-1(mod \hspace{0.2cm}i) $. Per gli $ a_j=0 $ il resto della divisione per $ k-1 $ sara $ j-1 $. Notiamo inoltre che se un resto e' nullo allora allora $ j_z $ e' un divisore di $ k $ diverso da $ k $.
Abbiamo quindi, con $ i $ che non divide $ k $ e $ j_z $ divisore di $ k $ e chiamando $ C $ il numero dei divisori di $ k $ diversi da $ k $:
$ r(k-1)=\sum{(a_i-1)}+\sum{(j_z-1)} $
$ r(k-1)=\sum{a_i}-((k-1)-C)+\sum{j_z}-C $
$ r(k-1)=\sum{a_i}+\sum{j_z}-k+1 $
Se $ r(k-1)=r(k) $ allora si avrebbe
$ \sum{a_i}+\sum{j_z}-k+1=\sum{a_i} $
$ \sum{j_z}=k-1 $
Dobbiamo trovare i numeri la cui somma dei divisori sia uguale al numero stesso meno uno. Le potenze di due soddisfano queste condizioni. La somma dei divisori per $ 2^x $:
$ 1+2+4+\cdots+2^{x-1}=\frac{2^x-1}{2-1}=2^x-1 $
EDIT: a posto ora. grazie Carlein

Ok stessa soluzione. Manca solo l'uno tra i divisori nella somma
Ciao!

durante questo fine settimana mi è venuto in mente come (forse) risolvere questo problema, ora provo a buttare giù la mia soluzione.

consideriamo le potenze di 2. Queste sono congrue a 0 modulo uno e tutte le potenze di due minori di esse. Per qualsiasi altro modulo compreso tra 1 e $ $k-1 $, tali potenze sono congrue a "qualcosa" diverso da 0, e quindi $ $k-1 $ per questi moduli è congruo al residuo corrispondente di $ $k $ meno 1. Inoltre sappiamo che $ $k-1 $ è congruo a $ $-1=2^a-1 (mod 2^a) $ con $ $2^a < k $ . Dunque la somma dei residui mod (variabile) di k-1 sarà uguale alla somma dei residui mod (variabile) di k meno k-x-1 (che sarebbe il numero di moduli non potenze di 2 minori di k e diverse da 1, poichè tutti i numeri sono congrui mod 1) più la somma di tutte le potenze di 2 minori di k diminuite di 1. Se $ $r(k)=r(k-1) $ , allora ponendo $ $r(k)=h $ abbiamo $ $h=h-(k-x-1)+(2+4+8+...+2^{x-1})-(x-1) $ con $ $2^{x-1} $ la più piccola potenza di 2 minore di k. Allora $ $k=2^x $ e, sostituendo, otteniamo $ $(2+4+8+...+2^{x-1})=2^x-2 $ . E' fatto noto che la somma di tutte le potenze di 2 minori o uguali a $ $2^{x-1} $ con esponente naturale è effettivamente uguale a $ $2^x-2 $ , per cui l'uguaglianza è sempre verificata. Dunque $ $r(k)=r(k-1) $ con k=qualsiasi potenza di 2.


Per favore mi potete dire se è giusta? Grazie mille

Ma è la stessa cosa che ha scritto leonim.Cioè l'unica differenza sostanziale è che quello che lui ha scritto algebricamente tu l'hai detto a parole .

me ne sono accorto dopo