Exercise 4.5.15 (Number of positive integers $k \leq n = p^\alpha q ^\beta r^\gamma$ that are divisible by none of $pq,\, pr$, or $qr$)

Question

Let $n$ be a positive integer having exactly three distinct prime factors $p,\, q$ and $r$. Find a formula for the number of positive integers $\leq n$ that are divisible by none of $pq,\, pr$, or $qr$

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

\begin{proof} 
The decomposition of $n$ in prime factors is 
$$n = p^\alpha q^\beta r^\gamma,\qquad \alpha>0, \beta>0, \gamma>0.$$
We define 
$$A_{pq} = \{k \in [\![1,n]\!] \mid pq \mid k\},$$
and similarly $A_{qr}$ and $A_{pr}$.

Then the number of positive integers $k \leq n$ that are divisible by none of $pq,\, pr$, or $qr$ is the cardinality $N$ of $E$, where
$$E =  [\![1,n]\!]  \setminus (A_{pq}  \cup A_{qr}  \cup A_{pr}).$$
Then
\begin{align}
N = |E| &= n - |A_{pq}  \cup A_{qr}  \cup A_{pr})|,
\end{align}
where
\begin{align*}
 |A_{pq}  \cup A_{qr}  \cup A_{pr})| =  &|A_{pq}| + |A_{qr}|+ |A_{pr}| \
 &- |A_{pq} \cap A_{qr}| - |A_{pq} \cap A_{pr}|  - |A_{qr} \cap A_{pr}|  \
 &+ |A_{pq} \cap A_{pr}  \cap A_{qr} |.
\end{align*}
Moreover
$|A_{pq}| = \left \lfloor \frac{n}{pq} ight floor = \frac{n}{pq}$, and similarly $|A_{qr}| =  \frac{n}{qr}$, $|A_{pr}| =  \frac{n}{pr}$.
Since
\begin{align*}
A_{pq} \cap A_{qr} &= \{k \in [\![1,n]\!] : pq \mid k 	ext{ and } qr \mid k\}\
&=\{k \in [\![1,n]\!] : p \mid k 	ext{ and }  q \mid k 	ext{ and }  r \mid k\}\
&= \{k \in [\![1,n]\!] : pqr \mid k\},
\end{align*}
and similar results for $A_{pq} \cap A_{pr}$ and $A_{qr} \cap A_{pr}$, we obtain
$$|A_{pq} \cap A_{qr}|  =  |A_{pq} \cap A_{pr}|  = |A_{qr} \cap A_{pr}|   = \frac{n}{pqr}.$$
Finally,
\begin{align*}
A_{pq} \cap A_{pr}  \cap A_{qr} &=  \{k \in [\![1,n]\!] : pq \mid k 	ext{ and }  pr \mid k  	ext{ and }  qr \mid k \}\
&=\{k \in [\![1,n]\!] : p \mid k 	ext{ and }  q \mid k 	ext{ and }  r \mid k\}\
&= \{k \in [\![1,n]\!] : pqr \mid k \},
\end{align*}
thus
$$|A_{pq} \cap A_{pr}  \cap A_{qr}| = \frac{n}{pqr}.$$
Then (1) becomes
$$N = n - \frac{n}{pq} -  \frac{n}{qr}-  \frac{n}{pr} + 3  \frac{n}{pqr} -  \frac{n}{pqr},$$
so
$$N = n - \frac{n}{pq} - \frac{n}{qr} - \frac{n}{pr} +  2 \frac{n}{pqr}.$$
\end{proof}

Exercise 4.5.15 (Number of positive integers $k \leq n = p^\alpha q ^\beta r^\gamma$ that are divisible by none of $pq,\, pr$, or $qr$)

Answers

Comments

Exercise 4.5.15 (Number of positive integers $k \leq n = p^\alpha q ^\beta r^\gamma$ that are divisible by none of $pq,\, pr$, or $qr$)

Answers

Comments

Add answer