3
$\begingroup$

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$ ??

$\endgroup$
3
$\begingroup$

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)$.

$\endgroup$
7
$\begingroup$

Count them. For example, the multiples of $pq$ are $pq, 2pq, \ldots, rpq$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.