How to Count Elements Divisible by Exactly Two of Three Numbers

Suppose you have a finite set of integers and three distinct positive numbers, and you want to count the elements divisible by exactly two of those numbers. The key is to count the overlaps for each pair, then correct for numbers divisible by all three.

This method works for any finite set. If the set is the consecutive integers from 1 to N, least common multiples give a direct formula for each overlap.

Count using divisibility sets

Let the three divisors be $a$, $b$, and $c$. Define $A$, $B$, and $C$ as the subsets of your given set whose elements are divisible by $a$, $b$, and $c$, respectively.

An element divisible by exactly two numbers appears in exactly one of these pairwise intersections: $A \cap B$, $A \cap C$, or $B \cap C$. An element divisible by all three appears in all three intersections, so the pairwise counts together include it three times. Since it should contribute zero to the exact-two count, subtract those three appearances.

The result is

$$|A \cap B| + |A \cap C| + |B \cap C| - 3|A \cap B \cap C|.$$

The formula applies to a finite set of any shape; the set does not have to contain consecutive integers. You just need the sizes of the pairwise intersections and the triple intersection.

Use least common multiples for 1 through N

When the set is $\{1,2,\ldots,N\}$, an integer is divisible by both $a$ and $b$ precisely when it is divisible by $\mathrm{lcm}(a,b)$. Therefore, the number of elements divisible by both is

$$\left\lfloor \frac{N}{\mathrm{lcm}(a,b)} \right\rfloor.$$

Likewise, the triple intersection consists of multiples of $\mathrm{lcm}(a,b,c)$. Thus, the number divisible by exactly two of $a$, $b$, and $c$ is

$$\left\lfloor \frac{N}{\mathrm{lcm}(a,b)} \right\rfloor + \left\lfloor \frac{N}{\mathrm{lcm}(a,c)} \right\rfloor + \left\lfloor \frac{N}{\mathrm{lcm}(b,c)} \right\rfloor - 3\left\lfloor \frac{N}{\mathrm{lcm}(a,b,c)} \right\rfloor.$$

Here, $\lfloor x \rfloor$ means the greatest integer less than or equal to $x$.

Worked example: numbers from 1 to 100

How many integers from 1 through 100 are divisible by exactly two of 2, 3, and 5?

First count the multiples of each pair:

• Divisible by 2 and 3: multiples of $\mathrm{lcm}(2,3)=6$, giving $\lfloor 100/6 \rfloor=16$.
• Divisible by 2 and 5: multiples of 10, giving $\lfloor 100/10 \rfloor=10$.
• Divisible by 3 and 5: multiples of 15, giving $\lfloor 100/15 \rfloor=6$.

Numbers divisible by all three are multiples of 30, so there are $\lfloor 100/30 \rfloor=3$ of them. Substitute these counts:

$$16+10+6-3(3)=23.$$

So 23 integers from 1 to 100 are divisible by exactly two of 2, 3, and 5. As a check, the three groups are: divisible by 2 and 3 but not 5 (16 − 3 = 13), by 2 and 5 but not 3 (10 − 3 = 7), and by 3 and 5 but not 2 (6 − 3 = 3). These add to 23.

Exactly two is not at least two

The formula counts elements divisible by exactly two of the divisors. It excludes elements divisible by all three. If you want the count divisible by at least two, the triple-overlap elements should be included once, not removed entirely. In that case, add the three pairwise counts and subtract twice the triple count.

Common mistakes

• Forgetting the triple overlap: Each element divisible by all three appears in all three pair counts. Subtracting it only once leaves it counted twice; subtract it three times for an exact-two count.
• Using a product instead of an LCM: The common multiples of 4 and 6 are multiples of 12, not 24. Use the least common multiple.
• Counting only one pair: The desired elements may be divisible by any of the three pairs, so all three pairwise counts are needed.
• Applying the range formula to another set: The floor-and-LCM formula counts elements in $\{1,\ldots,N\}$. For a different finite set, count its actual elements in each intersection.