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 kj to denote the j'th digit of k, with k0 being the least significant digit.
The first digit of k
If gcd(m,b) = 1, we can choose k0 such that mk0 = 1 (mod b). For the sum to produce a carry at the first digit, we would necessarily have nk0 = b - 1 (mod b). In this case b must divide the sum, and since k0 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 k0 = b / d. Since mk0 = 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'/bj-1) and y = floor(nk'/bj-1). We want to determine kj such that the sum of mkj + x and nkj + y does not produce a carry at the first position.First assume gcd(m,b) = 1. In this case we can choose kj such that mkj + 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 kj = w, the sum D(mkj + x) + D(nkj + 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.