X hits on this document

49 views

0 shares

0 downloads

0 comments

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.

2

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 info
Document views49
Page views53
Page last viewedWed Dec 07 16:56:10 UTC 2016
Pages15
Paragraphs695
Words3760

Comments