Scrivere un numero in base p, significa scriverlo come

a_n*p^n+...+a_1*p+a_0 con ciascun coefficiente a_i che sia < p (così come le cifre dei numeri in notazione decimale sono i coefficienti della scrittura a_n*10^n+...+a_2*100+a_1*10+a_0).

In particolare, se vuoi scrivere il tuo numero x in base 2, prendi la più alta potenza n di 2 tale che 2^n<=x e fai la divisione con resto di x per 2^n, cioè trovi due numeri a_n e r_n (il resto) tali che

x = a_n*2^n + r_n

Questo a_n è il tuo coefficiente n-esimo (che può assumere i soli valori 1 o 0, per come è definito... in realtà il primo sarà sempre 1). Poi prendi il resto r_n e continui ad applicare questo algoritmo su di lui, ottenendo il coefficiente successivo e il resto successivo.

L’unica cosa da dimostrare è che il procedimento termini. Il fatto che produca una scrittura come quella che ho scritto all’inizio, è abbastanza ovvio (e comunque lo si può far vedere per induzione su n). Forse si potrebbe, per completezza, dimostrare l’unicità della scrittura ma, anche questo, è abbastanza facile da vedere (l’unicità segue dal fatto che i coefficienti sono più piccoli di p).