X hits on this document

# StupidDivisibilityTricks.pdf - page 9 / 15

32 views

0 shares

9 / 15

However, note that 10 has no inverse modulo 25, that is, there is no number u such that 10u 1 (mod 25).

Knowing the inverse of 10 mod d (if it exists) leads to a nice divisibility test. To test if 283757 is divisible by 13 we can trim o the rightmost digit (7), multiply it by 10 1 mod 13 (for example, 4) and add that result to the remaining digits (28375 + 28 = 28403). The original number, 283757, is divisible by 13 if and only if the new number, 28403, is divisible by 13. If it is still unclear whether or not the new numbers is divisible by 13, we can repeat the process. Any inverse of 10 will work; instead of 4, we can use

9. Thus 283757 is divisible by 13 if and only if 28375 + ( 9)7 = 28312 is divisible by 13.

28375/

• 63 2831/

• 18 281/

• 81 20/

• 0 20

Since 20 is not divisible by 13, we conclude that 283757 is not divisible by 13.

# Trim from the Right Trick:

• Let u 10

1

(mod d), write a = [a

a0], and let a0 = [a

a1] +

u[a0]. Then a is divisible by d if and only if a0 is divisible by d.

• Let v 100

1

(mod d), write a = [a

a0], and let a00 = [a

a2] +

v [ a 1 a 0 ] . T h e n a i s d i v i s i b l e b y d i f a n d o n l y i f a 0 0 i s d i v i s i b l e b y d .

9

 Document views 32 Page views 36 Page last viewed Sat Oct 22 00:20:33 UTC 2016 Pages 15 Paragraphs 695 Words 3760