Published Monday 22. March 2010

Assume gcd(m,n) = 1 and that b does not divide m + n.
We want to determine a number k > 0, such that mk and nk adds without carry in base b. The following algorithm tries to do this by determining one digit at a time.
Notice that the j'th digit of k does not affect the first j - 1 digits of the sum, so we can actually determine the digits one at a time, without affecting the digits we've already determined.

We write k

_{j}to denote the j'th digit of k, with k

_{0}being the least significant digit.

### The first digit of k

If gcd(m,b) = 1, we can choose k_{0}such that mk

_{0}= 1 (mod b). For the sum to produce a carry at the first digit, we would necessarily have nk

_{0}= b - 1 (mod b). In this case b must divide the sum, and since k

_{0}is coprime to b, b must actually divide m + n. But this is exactly what we assumed not to be the case.

If d = gcd(m,b) is greater than 1, take k

_{0}= b / d. Since mk

_{0}= 0 (mod b), we get no carry.

### The rest of the digits

Now we assume that we have determined the first j - 1 digits of k. Let k' be the first j - 1 digits of k, and let x = floor(mk'/b^{j-1}) and y = floor(nk'/b

^{j-1}). We want to determine k

_{j}such that the sum of mk

_{j}+ x and nk

_{j}+ y does not produce a carry at the first position.

First assume gcd(m,b) = 1. In this case we can choose k

_{j}such that mk

_{j}+ x = 0 (mod b), and so no carry is produced.

Now we can assume that p = gcd(m,b) > 1, and by the same reasoning we can assume q = gcd(n,b) > 1.Let D(z) denote the number in B = {0,1,...,b - 1} such that z = D(z) (mod b), i.e. the first digit of z in base b.

Consider the mapping from B to B × B given by w → (D(mw), D(nw)).

We want to prove that the image contains all values of the form (cb/q, db/p) for c in {0,1,...,q - 1} and d in {0,1,...,p - 1}.

If we can prove this, then we can find a w such that D(mw + x) < b/q and D(nw + y) < b/p; even if the grid spanned by (b/q, 0) and (0, b/p) is translated by an arbitrary vector (x, y), it will always have a point in common with the rectangle [0..b/q-1] × [0..b/p-1]. This is exactly what we want: If we take k

_{j}= w, the sum D(mk

_{j}+ x) + D(nk

_{j}+ y) is less than b/q + b/p which is less than b/2 + b/2 = b, so no carry occurs.

It is enough to prove that the image contains (b/q, 0) and (0, b/p), since the mapping is additive modulo b, and by symmetry it is enough to prove that it contains (b/q, 0).

From gcd(m, q) = 1 we see that gcd(mb/q, b) = b/q. Therefore we can find integers u and v such that (mb/q)u + bv = b/q. Now take w = bu/q, and we see that D(mw) = D(mbu/q) = b/q and D(nw) = D(nbu/q) = 0.