How many integers in the interval $[0, 5999]$ are coprime with either $10$ or $15$ (or both)?

Question

How many integers in the interval $[0, 5999]$ are coprime with either $10$ or $15$ (or both)?

My idea is to use the inclusion-exclusion principle four times: (1) to determine the numbers that are coprime with $10$ or $15$, (2) to find the numbers in $[0,5999]$ that are not coprime with $10$, (3) to find the numbers in $[0,5999]$ that are not coprime with $15$, and (4) to find the numbers in $[0,5999]$ that are not coprime with $10$ and are not coprime with $15$. The proof then follows:

Let $$ S=\{\text{all integers in }[0,5999]\}\\ A_1=\{\text{all integers in }[0,5999] \text{ that are not coprime with }10\},\\ A_2=\{\text{all integers in }[0,5999] \text{ that are not coprime with }15\} $$

To determine all numbers that are not coprime with 10, we note that they cannot have a $5$ or $2$ in their prime factorization. By the inclusion-exclusion principle, this is $$|A_1|=(\frac{6000}{5}-1)+(\frac{6000}{2}-1)-(\frac{6000}{10}-1)=3599$$ where I've subtracted $1$ to account for the fact that $6000$ is not counted in our interval. Similarly, to determine all numbers that are not coprime with 15, we note that they cannot have a $5$ or $3$ in their prime factorization. By the inclusion-exclusion principle, this is $$|A_2|=(\frac{6000}{5}-1)+(\frac{6000}{3}-1)-(\frac{6000}{15}-1)=2799$$ In order to not be coprime with 10 and not be coprime with 15, the integer cannot contain a $5,3,$ or $2$ in its prime factorization. By the inclusion-exclusion principle, this is $$|A_1 \cap A_2|=(\frac{6000}{5}-1)+(\frac{6000}{3}-1)+(\frac{6000}{2}-1)-(\frac{6000}{10}-1)-(\frac{6000}{15}-1)-(\frac{6000}{6}-1)+(\frac{6000}{30}-1)=4399$$

Thus, our desired number is $$|S-(A_1 \cup A_2)|=|S|-|A_1|-|A_2|+|A_1 \cap A_2|\\ \quad\quad\quad\quad\;\;\;=6000-3599-2799+4399\\ =4001$$ This seems like an awfully large number, and I am wondering if anyone could verify this or show me where I went wrong!

Answer 1

I will take a simpleminded approach. The prime factors of $10$ are $2$ and $5$, and the prime factors of $15$ are $3$ and $5$, so a number is relatively prime to both $10$ and $15$ if and only if it is not divisible by $2,3$, or $5$. There are $6000$ integers in that interval.

• $\frac{6000}2=3000$ of them are multiples of $2$.
• $\frac{6000}3=2000$ of them are multiples of $3$.
• $\frac{6000}5=1200$ of them are multiples of $5$.
• $\frac{6000}6=1000$ of them are multiples of both $2$ and $3$.
• $\frac{6000}{10}=600$ of them are multiples of both $2$ and $5$.
• $\frac{6000}{15}=400$ of them are multiples of both $3$ and $5$.
• And $\frac{6000}{30}=200$ of them are multiples of $2,3$, and $5$.

By the inclusion/exclusion principle there are therefore

$$6000-3000-2000-1200+1000+600+400-200=1600$$

that are relatively prime to $10$ and $15$.

The first problem that I see with your solution is the subtraction of $1$ in all of those calculations: there are $1200$ multiples of $5$ in that interval, not $1199$: $0$ is a multiple of $5$. Thus, there are $3600$ numbers in the interval that are not relatively prime to $10$ and $2800$ that are not relatively prime to $15$. A bigger problem is your calculation of $|A_1\cap A_2|$: the numbers that are not relatively prime to $10$ and not relatively prime to $15$ are those that have a factor of $5$ or a factor of $6$, not those that have a factor of $5$ and a factor of $6$.