somma cifre in base b

[Febo]

Siano a,b,n interi positivi tali che: $ b^n-1|a $

Poniamo $ a=\displaystyle\sum_{i=0}^k a_ib^i $ dove $ 0\le a_i<b $

Dimostrare che: $ \displaystyle\sum_{i=0}^k a_i \ge n(b-1) $

Buona fortuna...

[Marco]

Io l'ho fatto cosi':

Notazione: Dato un intero non negativo $ n $, indico con $ s(n) $ la somma delle cifre in base $ b $ di $ n $.

Lemma: Siano $ x $, $ y $, $ z $ interi positivi t.c. $ z = x - y $. Allora

$ $s(z) = s(x) - s(y) + (b-1)r $,

dove $ r $ e' il numero di riporti che si effettuano nel calcolare la sottrazione $ x - y $ .

Dim.: Ovvia, dall'algoritmo di sottrazione in colonna. []

Soluzione
Sappiamo che $ a $ e' un multiplo di $ b^n - 1 $, ossia che esiste un intero positivo $ k $ t.c. $ a = k \left( b^n - 1 \right) $.

Wlog, posso supporre $ b \nmid k $, dato che eliminare gli zeri in coda da $ a $ non cambia la somma delle cifre.

Applico il Lemma con $ x = k b^n $, $ y = k $, $ z = a $. Se dimostro che questa sottrazione ha almeno $ n $ riporti, ho vinto. Ma questo e' abbastanza ovvio, dato che le ultime $ n $ cifre di $ x $ sono zeri, e la cifra delle unita' di $ y $ e' diversa da zero. []