Fact 1: Let d be a positive integer, then S(m, n; b) is true if and only if S(md, nd; b) is true.

Proof.  Note that we can assume d  to be a prime. Assume S(m, n; b) is true. This means that a k exists such that mk and nk adds without carry. If d divides b, take k' = kb/d. Obviously, the addition of mdk' = mkb and ndk' = nkb will not produce any carries. If d is coprime to b, we can find a positive integer r such that b^r = 1 (mod d) and b^r > max(mk, nk). Consider the number

s = 1 + b^r + ... + b^r(d-1).

Since each of the d  terms in the sum is 1 (mod d), s is divisible by d. Now take k' = ks/d. The numbers mdk' = mks and ndk' = nks represented in base b are just the numbers mk and nk concatenated with themselves d  times (possibly with a number of zeroes between each occurance), and so the addition of the numbers produce no carries.

Now assume S(md, nd; b) is true. This means that a k exists such that mdk and ndk adds without carry. In this case we can just take k' = dk to make mk' and nk' add without carry. This finishes the proof.

Fact 2: If gcd(m+n, b) = 1, then S(m, n; b) is true.

Proof. If gcd(m+n, b) = 1, we can find a positive integer r, such that b^r = 1 (mod m+n). In other words, we can find a k, such that (m+n)k = b^r - 1. Represented in base b, the number b^r - 1 is the digit (b-1) repeated r times. Notice that the sum of two digits in base b can never be greater than b + (b-2), so if the last digit of a sum is (b-1), there was no carry at that place. Using this fact repeatedly, we see that the sum mk + nk produces no carry. This finishes the proof.

Fact 3: If gcd(m, n) = 1 and b divides m+n, then S(m, n; b) is false.

Proof. If a k existed such that mk and nk added without carry, we could assume that b did not divide k; shifting the base b representation of the numbers one place does not change the number of carries in the sum. Since gcd(m, n) = 1, b can not divide mk and nk both. Therefore the last digits of mk and nk in base b can not both be zero. However, because b divides m+n, the last digit of mk+nk is zero, and that can only happen if the sum of the last digits is b, i.e. a carry is produced. This finishes the proof.