test divisibility by some numbers by adding together blocks of digits, starting from the right. For example, to test divisibility of a by 33, we add the digits of a in blocks of 2. Using this rule, we see that 5210832 is divisible by 33 since 32 + 08 + 21 + 5 = 66 is clearly divisible by 33.

Sum of Digits Trick: Let d be given, and suppose that 10^{n }≡ 1 (mod d) for some n. Add the digits of a in blocks of n starting from the right, and call the result s. Now a and s leave the same remainder upon division by d; in particular, a is divisible by d if and only if s is divisible by d.

d

3

9

11

27

33

37

99

101

block size to add

1

1

2

3

2

3

2

4

# Below are the values of d (2 ≤ d ≤ 102) for which the trick works and

the block size is fairly small (at most 4).

# Why it works: Suppose that 10^{n }≡ 1 (mod d), and we wish to see if d

divides the number a = [a

a_{0}]. Assuming k ≥ n, we get

a = [a

a_{0}] = 10^{n}[a

a_{n}] + [a_{n }_{1 }

a_{0}]

≡ [a

a_{n}] + [a_{n }_{1 }

a_{0}]

(mod d)

Now letting t be the greatest integer such that k ≥ tn, and repeating this process on the leftmost term we find

a = [a

a_{0}]

≡ [a

a_{n}] + [a_{n }_{1 }

a_{0}]

.

≡ [a

.

.

≡ [a

a_{2n}] + [a_{2n }_{1 }

a_{tn}] + [a_{tn }_{1 }

(mod d)

a_{n}] + [a_{n }_{1 }

a_{0}]

a

_{t 1)n}] + · · · + [a^{2n }^{1 }

a_{n}] + [a_{n }_{1 }

a_{0}]

6