a = [a

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

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

≡ [a

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

number a = [a

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

a_{0}]

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_{n}]) + [a_{n }_{1 }

a_{0}]

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

a_{0}]

[a_{tn 1 }

a

_{t 1)n}] + · · ·

[a_{2n 1 }

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

≡

[a

≡

( [a

= [a

≡ ( 1)^{t}[a

(mod d)

a_{tn}] + ( 1)^{t 1 }

a = [a

. . .

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

a_{2n}]

[a_{2n }

1

a_{0}]

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

a_{0}]

Running total: We now have divisibility tests for 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 16, 20, 27, 25, 32, 33, 37, 40, 50, 64, 73, 77, 80, 91, 99, 100, 101.

3.4

# Trim from the Right

A basic result from elementary number theory tells us that if the greatest common divisor of d and 10 is 1, then there exists a number u such that 10u ≡ 1 (mod d). Such a number u is called an inverse of 10 modulo d and

we write u ≡ 10 ^{1 }(mod d). For instance, 10(4) = 40 ≡ 1 (mod 13) so 4 ≡ 10

^{1}, mod 13. In fact, any

number congruent to 4 mod 13 (e.g.

9), is also an inverse of 10, mod 13.

8

a_{0}]