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

2 Answers 2

7
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .