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 \pmod{b}\). For the sum to produce a carry at the first digit, we would necessarily have \(nk_0 = b - 1 \pmod{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 \pmod{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 = \lfloor mk'/b^{j-1} \rfloor\) and \(y = \lfloor nk'/b^{j-1} \rfloor\). 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 \pmod{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,\ldots,b - 1\}\) such that \(z = D(z) \pmod{b}\), i.e. the first digit of \(z\) in base \(b\).
Consider the mapping from \(B\) to \(B \times B\) given by \(w \to (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,\ldots,q - 1\}\) and \(d\) in \(\{0,1,\ldots,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] \times [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\).