X hits on this document

# StupidDivisibilityTricks.pdf - page 8 / 15

62 views

0 shares

8 / 15

a = [a

a0] = 10n[a

an] + [an 1

[a

an] + [an 1

number a = [a

a0]. Assuming k n, we get

a0]

a0]

(mod d)

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

an]) + [an 1

a0]

an] + [an 1

a0]

[atn 1

a

t 1)n] + · · ·

[a2n 1

an] + [an 1

[a

( [a

= [a

( 1)t[a

(mod d)

atn] + ( 1)t 1

a = [a

. . .

a2n] + [a2n 1

a2n]

[a2n

1

a0]

an] + [an 1

a0]

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

a0]

 Document views 62 Page views 66 Page last viewed Tue Jan 17 20:02:16 UTC 2017 Pages 15 Paragraphs 695 Words 3760