Question:
Suppose that $a\geq 1$ and $b\geq 2$. Show that there exist $a_0,a_1,...,a_d \in [0,b-1]$, such that
$a=a_d b^d+a_{d-1}b^{d-1}+....+a_0$
I tried to approach the problem using the Euclidean algorithm.
Suppose I take any integer $b$ greater than $2$. Then, if for a given $a\geq 1$, if $1 \leq a\leq b-1$, then we can write a=(0)b+a and the whole thing gets done.
The case $a \geq b$ has gotten very complicated for me.
By Euclidean Algorithm, we can write $a$ as, $a=bq_1+r_1$ where $0 \leq r_1\leq b-1<a$.Thus, $a-r$ is positive, and consequently, $q_1$ is positive. If $q_1 \in [0,b-1]$, our job is done. If $q_1\geq b$, then by perceiving $a=q_1$ as repeating the same thing we did with $a$, we go on obtaining $q_i$ such that, $q_i=q_{i+1}b+r_{i+1}$, where $r_{i+1} \in [0,b-1]$ unless at some point $q_i$ becomes less than $b$ for some $i$. Also,$q_{i+1}<bq_{i+1}+r_{i+1}=q_i$. So, this process will end in finite number of steps.
My approach is rather intuitive and I am struggling to write this formally.Can somebody help me prove case 2 more formally by using only the Euclidean Algorithm?
It's much easier to start from the top and go down than to start from the bottom and go up.
We can do it your way and end up with a bunch of equations
$a= q_1b + r_1; a_0 = r_1$
$q_1 = q_2b + r_2; a_1 = r_2$ $q_2 = q_3b + r_3;a_2=r_3$ ..... until it ends ..... $q_{d-1}= q_db + r_d;a_{d-1}=r_3$ (but $q_d < b$ for the first time and so)
$q_d = 0\cdot b + q_d = 0\cdot b + r_{d+1}$ and $a_d=q_d = r_{d+1}$.
but then you have to show that:
$a = q_1b + a_0 =$
$(q_2b + a_1)b + a_0 =$
$....$
$(((((((((((a_db + a_{d-1})b + a_{d-2})b + ..... +a_2)b+a_1)b + a_0=$
$adb^d + a_{d-1}b^{d-1} + ..... + a_2b^2 + a_1b + a_0$.
... but that requires a lot of inductive faith and hand waving.
Better to determine that as $1 < b < b^2 < b^3 < .....$ is unbounded then if we assume $a\ge b$ (if we assume $a < b$ then we just let $a_0 = a$ and we are done) then there is a unique $d$ so that $b^d \le a < b^{d+1}$.
And therefore we can find unique
$a = a_db^d + r_d$ where $0 \le r_d < b^d$ and $1 \le a_d \le b-1$. Then as $a = a_db^d + r_d < b^{d+1}$ we have unique values where
$r_d = a_{d-1}b^{d-1} + r_{d-1}$ where $0 \le r_d < b^{d-1}$ and $0 \le a_{d-1}\le b-1$. And we repeat.
As each step reduces our our case to $r_{d-k}$ where $0\le r_{d-k} < b^{d-k-1}$ we will after $d$ steps reach:
$r_3 = a_2b^2 + r_2$ where $0\le r_d < b^2$ and $0 \le a_2 \le b-1$
$r_2 = a_1b + r_1$ where $0\le r_1 < b$ and $0 \le a_1 \le b-1$
$r_1 = 0\cdot b + r_0$ where $r_0 = r_1 = a_0$ and as $0 \le a_0 < b$ we have $0 \le a_0\le b-1$.