m_turner's postulate

postulate:
For any integer base B greater than 2, the multiples of the number B-1, when represented in base B will always have the sum of the digits be a multiple of B-1. If B-1 is a square number (4,9,16,...) then the square root of B-1 will also have this property.

---

What you say? Huh?
Most everyone knows of the 'if the number is divisible by 9, the digits will add up to nine' rule. 81 (9 * 9) is has this property, as does 47115 (9 * 5235). It may take multiple steps to get to the final 9, but its always there:

4 + 7 + 1 + 1 + 5 = 18
1 + 8 = 9

9 also happens to be a square number (3² = 9), and thus 3 has this property too (see How to determine whether a number is divisible by 3 for a proof).

While this is all well and good, the question of in base 5, does this work with the number 4? The number 48₁₀ is represented as 121₅, and 1 + 2 + 1 = 4. This appears to hold true for all bases.

The primary 'use' for this is in the optimization of the search space in self-describing numbers (such as 2100010006) in which the number has an equal number of digits as the base it is in, and the sum of the digits is equal to the base. Thus, the number must be 1 + n(B-1).

Generalization of, and proof of, m_turner's postulate.

Let A and B be any positive integers. Let N = ((A * B) + 1). Let D₀ to D_{(N - 1)} be N distinct digits, the value of D_i (v(D_i)) being i. Let L be any positive integer and let S be a string of L digits. Let V be the standard base-N value associated with S (i.e., in Eindhoven notation, (+ i : (i ∈ Z) ∧ (i ≥ 0) ∧ (i < L) : v(S[i]) * Nⁱ)). Let W be the sum of all the digits in S (i.e., (+ i : (i ∈ Z) ∧ (i ≥ 0) ∧ (i < L) : v(S[i]))).
Prove V mod A = W mod A.

Proof is by induction on L.

L = 1 ; trivial.

For x ≥ 1, given that the proposition true for L = x, prove the proposition for L = (x + 1):

Let S′ be the least significant x digits of S, let V′ be the standard base-N value associated with S′, let W′ be the sum of all the digits of S′, we have V′ = W′ (mod A). Now, V = (V′ + (v(S[x]) * N^x)) = (V′ + (v(S[x]) * ((A * B) + 1)^x)) = (working modulo A) (V′ + (v(S[x]) * ((0 * B) + 1)^x)) = (V′ + (v(S[x]) * 1)) = (V′ + v(S[x])). Also, W = (W′ + v(S[x])). Given V′ = W′ (mod A), (V′ + v(S[x])) = (W′ + v(S[x])), so V = W.
QED.

In particular, if B = 1, then N = (A + 1). m_turner's postulate follows. Other interesting cases include: A = 3, B = 3, N = 10 (How to determine whether a number is divisible by 3), A = 5, B = 3, N = 16. This makes it (relatively) easy to check if a number is divisible by 5, and divisibility by 2 is easy in hexadecimal so there's a quick check for divisibility by 10. Reversing A and B, there's also a quick check for divisibility by 3 in hexadecimal.