X hits on this document

# StupidDivisibilityTricks.pdf - page 3 / 15

49 views

0 shares

3 / 15

this age of the graphing calculator and laptop computer. Moreover, long divi- sion is often just as fast and you end up knowing the quotient and remainder as well. However, there is something intriguing about the fact that you can test divisibility by 3 by adding all the digits or you can test divisibility by 67 as outlined above, and it is this aspect of divisibility that motivates this article.

# Modular Arithmetic

Modular arithmetic is the tool that allows us to find and analyze divisibility tests. Let a and b be integers, and let m be a positive integer. We say that a and b are congruent modulo m (or a is congruent to b modulo m) if a and b both leave the same remainder when divided by m, and we write this mathematically as a b (mod m). For example,

13 22

(mod 3)

80

(mod 4)

14

1

(mod 5)

Equivalently, a b (mod m) if a b is a multiple of m. When n 0 (mod d) we say that n is divisible by d, or d divides n. There are two facts about modular arithmetic that will be particularly helpful.

• 1.

If a b (mod m) and c d (mod m), then a + c b + d (mod m).

• 2.

If a b (mod m) and c d (mod m), then ac bd (mod m).

For example, 36 1 (mod 5) and 9872 2 (mod 5), so by the first property, 36 + 9872 1 + 2 = 3 (mod 5), and by the second property, (36)(9872) (1)(2) = 2 (mod 5). What is the remainder when 3243847 is divided by 5?

3

 Document views 49 Page views 53 Page last viewed Wed Dec 07 16:56:10 UTC 2016 Pages 15 Paragraphs 695 Words 3760