X hits on this document

# StupidDivisibilityTricks.pdf - page 6 / 15

58 views

0 shares

6 / 15

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 10n 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

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 10n ≡ 1 (mod d), and we wish to see if d

divides the number a = [a

a0]. Assuming k n, we get

a = [a

a0] = 10n[a

an] + [an 1

a0]

[a

an] + [an 1

a0]

(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

a0]

[a

an] + [an 1

a0]

.

[a

.

.

[a

a2n] + [a2n 1

atn] + [atn 1

(mod d)

an] + [an 1

a0]

a

t 1)n] + · · · + [a2n 1

an] + [an 1

a0]

6

 Document views 58 Page views 62 Page last viewed Tue Jan 17 00:53:11 UTC 2017 Pages 15 Paragraphs 695 Words 3760