X hits on this document

53 views

0 shares

0 downloads

0 comments

14 / 15

Why it works: Suppose d = mn where m and n are relatively prime. If d divides a, then clearly m divides a and n divides a. Conversely, suppose that m and n each divide a. Then a = mr for some integer r. But if n divides mr, where m and n are relatively prime, one can consider the prime factorization of both sides and see that n must divide r; that is, r = nx for some integer x. So, a = m(nx) = (mn)x and thus mn divides a.

Running total: We now have divisibility tests for all the numbers from 2 to 102!

14

Document info
Document views53
Page views57
Page last viewedFri Dec 09 15:42:21 UTC 2016
Pages15
Paragraphs695
Words3760

Comments