Suppose we have a positive integer $n$ that has exactly three distinct prime factors, say $p,q, r$. How can we find a formula for the number of positive integers $\leq n$ that are divisible by none of $pq, qr,$ or $pr$ ??
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Count them. For example, the multiples of $pq$ are $pq, 2pq, \ldots, rpq$.
$\begingroup$
$\endgroup$
Let $n=p^aq^br^c$ where $a$, $b$, and $c$ are $\ge 1$. Call a number $\le n$ bad if it is divisible by at least one of $pq$, $qr$, or $rp$. We count the bad numbers. There are $\frac{n}{pq}$ numbers in our interval that are divisible by $pq$, and $\frac{n}{qr}$ that are divisible by $qr$, and $\frac{n}{rp}$ that are divisible by $rp$.
But if we add these three numbers, we have counted $3$ times the numbers that are divisible by all of $pq$, $qr$, and $rp$. So we must subtract $\frac{2n}{pqr}$ from the sum. It follows that there are $$\frac{n}{pq}+\frac{n}{qr}+\frac{n}{rp}-\frac{2n}{pqr}$$ bad numbers. This can be simplified to $\frac{n}{pqr}\left(p+q+r-2\right)$.
answered Apr 9, 2013 at 3:14