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

a_{0}], and let a^{0 }= [a

a_{1}] +

u[a_{0}]. Then a is divisible by d if and only if a^{0 }is divisible by d.

•

Let v ≡ 100

1

(mod d), write a = [a

a_{0}], and let a^{00 }= [a

a_{2}] +

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