An unfortunate truth about converting a number from base $a$ to base $b$
is that unless there are integers $m > 0$ and $n > 0$ such that $a^m = b^n$,
you need to use an arbitrarily large amount of memory in order
to convert arbitrarily large numbers from base $a$ to base $b$ -- not necessarily all the digits all the time, but a lot of the digits a lot of the time.
When $a^m = b^n$ (such as the conversion between $a=2^8$ and $b=2^5,$ which was mentioned in the question, where $a^5 = b^8$), you are able to "chunk" the input string of digits into groups of $m$ digits that can be converted into groups of $n$ digits, one group at a time with no kind of "carry" or interaction between the groups other than simply concatenating the digits to the output, exactly as described in the question; but that is a special case.
Suppose there are no such numbers $m$ and $n$.
There are various ways this can happen, classified by the prime
factorizations of $a$ and $b$:
- At least one of the bases $a$ or $b$ has a prime factor the other does not have, for example base $8 = 2^3$ and base $10 = 2\cdot5$.
- The bases $a$ and $b$ have the same prime factors, but not in the same ratio of powers, for example base $10 = 2\cdot5$ and base $20 = 2^2\cdot5$,
or base $60 = 2^2\cdot3\cdot5$ and base $90 = 2\cdot3^2\cdot5$.
Note that in the case where $a$ and $b$ are both powers of the same prime,
there is always a way to read and convert one block of digits at a time, provided that you either start with the least significant digit or you know how many digits each number contains.
In the case where $b$ has a prime factor that $a$ does not have,
there is no power of $a$ that will ever be divisible by $b$,
so if we take an arbitrarily large $m$, we can make $a^m$ have as
many significant digits in base $b$ as we want.
So when converting an arbitrarily large number from base $a$ to base $b$,
there is no limit on the size of the block of digits of the output
that could be affected by whether some high-place-value digit of input
happens to be $0$ or $1$.
Conversely, when converting from base $b$ to base $a$,
there is no limit on the size of the block of digits of the input
that we would have to examine in order to know for sure
what the value of some high-place-value digit of the output is.
So both conversion directions take unbounded memory if one base
has a factor the other does not have.
In the case where the two bases have the same prime factors, but the
powers of the prime factors are not in the same ratio, for any
large-enough integer $m$, $a^m$ will be divisible by $b^n$ for some
integer $n > 0$. But the quotient $a^m/b^n$will always contain
some number of "uncancelled" prime factors, and we can show that the
number of these factors grows without bound as $m$ grows arbitrarily large.
At this point I want to introduce some mathematical notation:
for $p$ a prime, $\nu_p(x)$ is the number of factors of $p$
in a prime factorization of $x$; for example, $\nu_2(60) = 2$
because $60 = 2^2\cdot3\cdot5$.
Now for each prime factor $p$ of $a$ and $b$, evaluate $\nu_p(a)/\nu_p(b)$;
let $q$ be the prime factor of $a$ and $b$ that minimizes this ratio, $r$ the prime factor that maximizes it.
Then $\nu_q(a^{\nu_q(b)}) = \nu_q(b^{\nu_q(a)})$; in fact, $a^{\nu_q(b)}$
is divisible by $b^{\nu_q(a)}$, because for every other prime factor $p$,
$\nu_p(a^{\nu_q(b)}) \geq \nu_p(b^{\nu_q(a)})$.
But the quotient $a^{\nu_q(b)}/b^{\nu_q(a)}$ is not divisible by $b$;
it has at least one prime factor of $r$ and no prime factor $q$.
That is, $a^{\nu_q(b)}$ has at least one "uncancelled" factor of $r$
when we take the greatest power of $b$ that divides $a^{\nu_q(b)}$.
If we next consider $a^{2\nu_q(b)}$,
the highest power of $b$ that divides it is $b^{2\nu_q(a)}$,
and after that division there are at least two "uncancelled"
factors of $r$.
In general, $a^{k\nu_q(b)}$ has at least $k$ "uncancelled" factors of $r$;
to write $a^{k\nu_q(b)}$ in base $b$, we would have to write some multiple
of $r^k$ not divisible by $b$ followed by some zeros.
This base-$b$ numeral could have as many significant digits as we want,
depending on how large $k$ is.
So once again, an arbitrarily large number of digits of the base-$b$
output can depend on the value of a single high-place-value digit of
the base-$a$ input, and there is no bound on how much memory we might
require to convert an arbitrarily large number.
The conversions where we can convert blocks of digits one at a time in
bounded memory are just the ones where the two bases have exactly the same
prime factors, and the powers of those prime factors are in the same proportions. This implies both bases are powers of the same integer.
For example, every three digits in base $36 = 2^2\cdot3^2 = 6^2$
can be converted to two digits of base $216 = 2^3\cdot3^3 = 6^3$.
Note that base-85 encoding of a string of (for example)
$1024$ binary digits does not produce a number written in base $85$.
Instead, it produces something like a mixed-radix number, but
with more complex rules for "carryover" than more well-known
mixed-radix systems (such as the time of day) typically have.
Reading from right to left, the place values of a base-85 encoding
of a $1024$-bit integer would be $1$, $85$, $85^2$, $85^3$, $85^4$,
$2^{32}$, $85\cdot2^{32}$, $85^2\cdot2^{32}$,
$85^3\cdot2^{32}$, $85^4\cdot2^{32}$,
$2^{64}$, $85\cdot2^{64}$, and so forth.
You might say that the so-called "base-85" encoding really encodes
a string of bits as a base-$2^{32}$ numeral, except that rather than
define a sequence of $2^{32}$ unique glyphs for the digits
$0$ to $2^{32}-1$, we write each base-$2^{32}$ digit as a
five-digit base-$85$ integer in that range, left-padded with zeros as needed.
By the way, for a conversion from base $a$ to base $b$ where the bases are not powers of the same integer and therefore there is no simple $n$-digit-to-$m$-digit conversion, it is still not ever necessary to use a division algorithm. You just have to work out how to multiple a base-$b$ number by $a$ in base $b$. For example, $723_{10}$ to base $16$:
First represent base $a=10$ in base $b=16$. In base $16$, the number $10_{10}$ is written $\mathrm a_{16}$.
Take the leftmost digit, $7.$ The intermediate result is $7_{16}.$
Multiply by $\mathrm a_{16}$. Result:
$7_{16} \times \mathrm a_{16} = 46_{16}.$
Add the next digit from the input, $2.$ Result: $48_{16}.$
Multiply by $\mathrm a_{16}$. Result:
$40_{16} \times\mathrm a_{16} + 8_{16} \times\mathrm a_{16}
= 280_{16} + 50_{16} = 2\mathrm{d}0_{16}.$
Add the next digit from the input, $3.$ Result: $2\mathrm{d}3_{16}.$
Since that is the last digit of input, the final result is $2\mathrm{d}3_{16}.$
When base $b$ is smaller than base $a,$ the individual digits of the base-$a$ number will sometimes come out to multiple digits in base $b,$ but the idea is the same; just add them to the intermediate results.
You've done pretty well in your proof, which requires just one extra step.
If $\ m+n \le g-1\ $, then $$\ 2G>2g\ge 2g-n-m \ge g+1= G .$$
Thus, since $\ 2G>2g-n-m\ge G\ $ in this case, you have $\ \lfloor\frac{2g-n-m}{G}\rfloor=1\ $, $\ \lfloor\frac{n+m}{G}\rfloor=0\ $, and
$\lfloor\frac{2g-n-m}{G}\rfloor+\lfloor\frac{n+m}{G}\rfloor=1\ .$
On the other hand, if $\ m+n>g-1\ $, then (because $\ m,n < g\ $):
$$0<2g-n-m<g+1=G\ ,$$
and so $\ \lfloor\frac{2g-n-m}{G}\rfloor=0\ $, $\ \lfloor\frac{n+m}{G}\rfloor=1\ $, and
$\lfloor\frac{2g-n-m}{G}\rfloor+\lfloor\frac{n+m}{G}\rfloor=1\ .$
One thing you should be made aware of, however, is that when writing out proofs, you should avoid just writing down the equation you're trying to prove and manipulating it into something which is purportedly equivalent. The main reason why this is inadvisable is the that the flow of logic is wrong:
$$\
\left[\matrix{\mbox{Proposition}\\ \mbox{to be proved}}\right]\implies P_2\implies P_3\implies \dots \implies\left[\matrix{\mbox{True}\\ \mbox{Proposition}}\right]\ ,$$
and the final proposition will be equivalent to the original only if every step in your manipulation is reversible. If that does happen to be true, then you will be able to reverse the implications in the above chain of propositions to obtain a valid proof:
$$\
\left[\matrix{\mbox{True}\\ \mbox{propostion}}\right]\implies \dots \implies P_3\implies P_2 \implies\left[\matrix{\mbox{Proposition}\\ \mbox{to be proved}}\right]\ ,$$
and this is the form which any proof you give should take.
As it turns out, your addition, $\ "➕"\ $, is essentially the same thing as addition modulo $\ b^r-1\ $:
$$ a➕c \equiv a+c \pmod{b^r-1}\ .$$
Your negation is also the same as negation modulo $\ b^r-1\ $:
$$ m'\equiv -m \pmod{b^r-1}\ .$$
So your observation that $\ n➕m= (n'➕m')'\ $ is equivalent to the equation:
$$ m+n\equiv -\left(\left(-m\right)+\left(-n\right)\right) \pmod{b^r-1}\ ,$$
which is not difficult to prove using modular arithmetic.
Best Answer
We prove by induction that the maximum carry is $1$ in any base $b$. This is clearly true when carrying over units to the $b^1$ place, because the maximum is $(b-1)+(b-1)=1(b-2)_b$. Suppose by induction that we are adding the digits in the $b^k$ place, say $x$ and $y$ with $x,y<b$, and let $c$ be the carry from $b^{k-1}$, which by the inductive hypothesis is at most $1$. Then the result is $x+y+c\leq (b-1)+(b-1)+1=1(b-1)_b$, so the maximum carry to the $b^{k+1}$ place is a $1$, and the result follows by induction.
Looking at the base $10$ case, that means the largest digit sum you can get is $19$, which is what happens when you carry over a $1$ and have a $9$ for each digit. The max in general is $2b-1$, which has a $1$ in the $b^1$ place.