More Divisibility Tests

E. L. Lady

MATH 111 unit III set 4\frac{1}{2}

5. 7 is the problem child of the world of divisibility tests. However the trick in question 1 and the multiplication table will let you test two digit numbers for divisibility by 7. Numbers with three or four digits can be reduced to two digit numbers using the fact that 100 ≡ 2 (mod 7) (because 98 = 7 × 14). Show how to use this fact to fill in the blanks below with two digit numbers. (You can also use the trick in question 1 to make the numbers come out smaller.)

193 ≡  (mod 7)  285 ≡  (mod 7)  8469 ≡  (mod 7).

Now describe a method for quickly testing numbers (up to four digits) for divisibility by 7, and use it on the following numbers:

7890  609  301  1211  7843  365  2904

6. Almost all the numbers we have considered so far have been either prime numbers or powers of prime numbers. Use several examples to decide on the answers to the following questions:

If a number is divisible by 2 and also by 3, does it have to be divisible by 6? If a number is divisible by 2 and also by 4, does it have to be divisible by 8? If a number is divisible by 3 and also by 4, does it have to be divisible by 12? If a number is divisible by 2 and also by 6, does it have to be divisible by 12? If a number is divisible by 4 and also by 6, then it has to be divisible by . If a number is divisible by 6 and also by 9, then it has to be divisible by .

What is the rule illustrated by the questions above?

How would you test for divisibility by 15? by 20? by 18? by 24? by 35?

7. The law of diminishing returns discourages us from inventing tests for divisibility by 13 or larger numbers. However when trying to decide whether a large number is prime or not, one very worthwhile thing to know is when you can stop. The idea can be discovered from the following examples:

If two numbers are both larger than 17, how big would their product have to be at a minimum?

If 31 goes into 307, how big could the quotient be, at the maximum?

If 2, 3, 5, 7, and 11 do not divide 307, could 31 divide 307? Could 29? Could 23? Could 19? Could 17? Could 13? Explain how you can know that 307 is a prime number.

In order to find out whether 307 is a prime number or not, what is the largest possible prime factor you would have to try?

For the exercise at the end of this set, it will be worthwhile to remember

13^{2} = 169  13 × 17 = 221  13 × 19 = 247  17^{2} = 289  13 × 23 = 299.

If a number smaller than 300 is not in this list and fails all the divisibility tests for primes up to 11, then it is a prime.

As an example, we now find the prime factorization of 129360. We start by noticing that 129360 = 12936 × 10. Now test 12936 for divisibility by 4 or by 8, and use this to reduce down to a smaller number if possible. Then test the smaller number for divisibility by 3 or by 9, and use this to get a still smaller number. Then test for divisibility by 2 and by 5 and by 11. Each time you find a factor, divide out by that factor. What is the prime factorization of 129360?

Now find the prime factorizations of the following numbers: (Do not use a calculator.)

2744  3375  22627  1771  2821  1859
1729  29,601  5525  22,561  12,005  70,543