# Finding Integers using Counting Rules

I'm studying, and got this problem in the book,

How many positive integers between 50 and 100 are divisible by 7, and what are they? The same for number divisible by both 7 and 11.

I'm reviewing Counting Basics, and this looks like counting subsets on a finite set, but I'm not sure how to solve this (I've seen combinations, like strings, but not this). Can someone help me get started?

If you'd like, the answers are: 7 for the first one (56, 63, 70, 77, 84, 91, 98), and 1 for the second (77). But again, I'm interested in the process itself.

-

The smallest multiple of $7$ that is larger than or equal to $50$ is $56=7\times 8$. On the other hand, the largest multiple of $7$ that is less than or equal to $100$ is $98 = 7\times 14$ (which can be found by computing $50/7$ and rounding up, and $100/7$ and rounding down). So... every number in this class must be of the form $7\times k$, and we must have $7\times 8\leq 7\times k\leq 7\times 14$. So... what are the possible values of $k$, and how many are there?

As for being divisible by $7$ and $11$, since $7$ and $11$ are distinct primes, if a number is divisible by both $7$ and $11$, then it has to be divisible by $7\times 11=77$. How many positive integers between $50$ and $100$ are multiples of $77$?

-
It looks so simple now! Thanks Arturo, the explanation's great! I imagine, I can use this technique for anything, correct? (I have another problem from 100 to 999). –  Cathy Jun 18 '11 at 22:42
@Cathy: If you get stuck on that problem (100 - 999), don't hesitate to ask for help! –  amWhy Jun 18 '11 at 22:50

Your best bet in a situation like this, where there are relatively few numbers between $50$ and $100$ which are divisible by $7$, is to just list them, and count the number of entries on the list. (Of course, you'd like a more efficient means if the interval over which multiples of a given number span is very very large!) Note: When computing the number of integers between $50$ and $100$ that are divisible by both $7$ and $11$, there is only one such number: $7 \times 11 = 77$.

If, however, the question asked how many such numbers are divisible by $7$ OR $11$, then you'd need to list/count

(1) those divisible by $7$,

(2) those divisible by $11$;

(3) those divisible by both $7$ and $11$: any multiple of $7 \times 11$ in the given range;

Then add the number of entries on list (1) to those on (2), and then subtract the number of entries on (3) from that sum. (Otherwise, without subtracting, you'd be counting, e.g. 77, twice, since it would appear on both (1) and (2).)

In general, if the lower bound of the interval under consideration is $L$, and the upper bound of the interval under consideration is $U$, then the smallest multiple of a positive integer $n$ that is larger than or equal to $L$ is $L/n$, and if the result is not an integer, round up to the next integer (say $k_{min}$). On the other hand, the largest multiple of $n$ that is less than or equal to $U$ is $U/n$, but if the result is not an integer, round down (drop off the remainder), say $k_{max}$. Then, count all multiples of $n$ such that $L \leq nk_{min} < nk_i < nk_{max} \leq U$, where $nk_i$ are all the multiples of $n$ between the least and greatest integers in the given interval [$L, U$].

-