Generalization of, and proof of, m_turner's postulate.
Let A and B be any positive integers. Let N =
((A * B) + 1). Let D0 to
D(N - 1) be N distinct digits, the value
of Di
(v(Di)) 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]) *
Ni)). 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]) *
Nx)) = (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.