Interi e basi

[G.D.5]

Mi pare carino, facile e non troppo complicato (e per quest'ultimo motivo lo posto in questa sezione).

Sia $b$ un intero positivo. Dimostrare che per ogni intero positivo $a$ esistono unici degli interi $a_0, a_1, a_2, \ldots, a_n, \ldots$ tali che $a=a_0 + a_1 b + a_2 b^2 + \ldots + a_n b^n + \ldots$ e $0<=a_i=0$.


In pratica si tratta di provare che ogni intero positivo è rappresentabile in una qualsivoglia base in un certo modo e solo in quello.
Io l'ho risolto in modo molto maccheronico, mi piacerebbe vedere come procedete voi.
Se qualche mod ritiene che vada spostato, faccia pure.

[Steven11]

La butto lì.

Sia appunto
$a=a_0 + a_1 b + a_2 b^2 + \ldots + a_n b^n$
Supponiamo per assurdo che esistano $c_0, c_1, c_2, ...,c_n$ tali che
$a=c_0 + c_1 b + c_2 b^2 + \ldots + c_n b^n$
e per almeno un intero $k<=n$ si ha $a_k !=c_k$.

Possiamo dunque scrivere
$a_0 + a_1 b + a_2 b^2 + \ldots + a_n b^n=c_0 + c_1 b + c_2 b^2 + \ldots + c_n b^n$
I due membro possiamo vederli come polinomi di grado $n$, quindi per il principio di identità dei polinomi dovrà aversi
$a_0=c_0$
$a_1=c_1$
...
$a_n=c_n$
contro l'ipotesi che esiste almeno un $k$ per cui $a_k != c_k$, assurdo.

Fammi sapere.
Ciao.

[G.D.5]

Sono d'accordo. Questo prova l'unicità. Credo resti da provare l'esistenza degli interi e il loro ordine rispetto allo $0$ e alla base $b$.

[_Tipper]

L'esistenza si prova abbastanza facilmente. Se $a \le b$ è banale, consideriamo dunque il caso $a > b$. Facciamo le seguenti divisioni

$a = q_1 \cdot b + a_0$

$q_1 = q_2 \cdot b + a_1$

$\vdots$

$q_{n-2} = q_{n-1} \cdot b + a_{n-2}$

$q_{n-1} = q_{n} \cdot b + a_{n-1}$

$q_{n} = 0 \cdot b + a_n$

fino a trovare un quoziente nullo (prima o poi si trovera un quoziente nullo, dato che $a > q_1 > q_2 > \ldots > q_{n+1} = 0$). Sostituendo l'ultima nella penultima si ottiene

$q_{n-1} = a_n \cdot b + a_{n-1}$

sostituendo questa nella terzultima si ottiene invece

$q_{n-2} = a_n \cdot b^2 + a_{n-1} \cdot b + a_{n-2}$

e così via, ottenendo

$a = \sum_{k=0}^n a_k \cdot b^k$

[Steven11]

"WiZaRd":Credo resti da provare l'esistenza degli interi e il loro ordine rispetto allo $0$ e alla base $b$.

Vero..
Gentilmente Tipper ha finito il lavoro al posto mio.

La tua dimostrazione cui alludevi coincide con queste qui postate?

[G.D.5]

La mia dimostrazione sfrutta le divisioni successive, come quella di Tipper. Io però ho usato le divisioni successive anche con $a<=b$: si arresta il procedimento delle divisioni al primo passo anzicché proseguire.
In pratica l'esistenza è assicurata dall'algotmo per la conversione della base di numerazione.
Usando questo metodo, l'unicità è provata dall'algoritmo stesso: infatti l'algoritmo sfrutta l'algoritmo per la divisione euclidea, la quale fornisce resti e quozienti unici. Inoltre, semper la divisione euclidea giustifica l'ordine degli $a_i$ rispetto a $0$ e $b$.