Number Divisibility

Date: 11/01/98 at 23:13:54
From: Cecilia Coltrain
Subject: Divisibility

How many natural numbers under 2,000 are divisible by either 5 or 7? 
What is the quickest way to figure this out?

Date: 11/02/98 at 12:46:11
From: Doctor Peterson
Subject: Re: Divisibility

Hi, Cecilia, 

I would break the problem into pieces. First, how many numbers under 
2000 are divisible by 5? That is, how many are in the set:

   { 5, 10, 15, 20, ... 1995 }

You can figure that out by dividing. Just be careful to think about 
whether you will be including 2000 when you divide. 

Here is one way to think about what division will be doing. Picture a 
one-to-one correspondence:

     5   <--> 1
    10   <--> 2
    15   <--> 3
    ...
    1995 <--> ?

This shows how dividing counts the members of the set.

Next, do the same thing to count numbers divisible by 7.

Now, how many of the numbers have you just counted twice, because they 
are divisible by both 5 and 7? Those are the numbers that are divisible 
by 35.

Finally, your answer will be the sum of the counts you got for 5 and 7, 
minus the number counted twice. You might like to picture it like this:

            *********
        ****  5      ****
       *          10     *
     **                   **
     *   divisible    15   *
    *      by 5         *********
    *               ****    *    ****
     *             *   35  *   7     *
     **          **       **      14  **
       *         *  70   *     28      *
        ****    *    ****            21 *
            *********     divisible     *
                 *          by 7       *
                 **                   **
                   *                 *
                    ****         ****
                        *********

The count of numbers included in either set (their union) is the sum of 
count of numbers in each set, minus their overlap (the intersection).

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/