TAOCP 1.3.3 Exercise 27

Section 1.3.3: Applications to Permutations

Exercise 27. [M20] Use the principle of inclusion and exclusion to count the number of integers $n$ in the range $0 \le n < am_1m_2\cdots m_t$ that are not divisible by any of $m_1, m_2, \ldots, m_t$. Here $m_1, m_2, \ldots, m_t$, and $a$ are positive integers, with $m_j \perp m_k$ when $j \ne k$.

Verified: yes
Solve time: 42s

---

Solution

Let

$$ N=a,m_1m_2\cdots m_t, $$

and for each $j$ $(1\le j\le t)$ let

$$ S_j={,n:0\le n<N,\ m_j\mid n,}. $$

The required quantity is the number of integers in $[0,N)$ that belong to none of the sets $S_1,S_2,\ldots,S_t$.

By the principle of inclusion and exclusion,

$$ \left|,\overline{S_1\cup\cdots\cup S_t},\right| = N-\sum_j|S_j| +\sum_{j<k}|S_j\cap S_k| -\cdots +(-1)^t|S_1\cap\cdots\cap S_t|. $$

Since $m_j\mid N$, the multiples of $m_j$ in the interval $0\le n<N$ are

$$ 0,m_j,2m_j,\ldots,\left(\frac{N}{m_j}-1\right)m_j, $$

hence

$$ |S_j|=\frac{N}{m_j}. $$

More generally, because the numbers $m_1,\ldots,m_t$ are pairwise relatively prime,

$$ \operatorname{lcm}(m_{i_1},\ldots,m_{i_r}) = m_{i_1}\cdots m_{i_r}. $$

Therefore

$$ |S_{i_1}\cap\cdots\cap S_{i_r}| = \frac{N}{m_{i_1}\cdots m_{i_r}}. $$

Substituting into inclusion and exclusion gives

$$ \begin{aligned} \left|,\overline{S_1\cup\cdots\cup S_t},\right| &= N\Biggl( 1-\sum_j\frac1{m_j} +\sum_{j<k}\frac1{m_jm_k} -\cdots +(-1)^t\frac1{m_1m_2\cdots m_t} \Biggr). \end{aligned} $$

The expression in parentheses factors as

$$ \prod_{j=1}^{t}\left(1-\frac1{m_j}\right). $$

Hence

$$ \left|,\overline{S_1\cup\cdots\cup S_t},\right| = N\prod_{j=1}^{t}\left(1-\frac1{m_j}\right). $$

Since $N=a,m_1m_2\cdots m_t$,

$$ \left|,\overline{S_1\cup\cdots\cup S_t},\right| = a,m_1m_2\cdots m_t \prod_{j=1}^{t}\left(1-\frac1{m_j}\right) = a\prod_{j=1}^{t}(m_j-1). $$

Therefore the number of integers $n$ with

$$ 0\le n<a,m_1m_2\cdots m_t $$

that are not divisible by any of $m_1,m_2,\ldots,m_t$ is

$$ \boxed{,a\prod_{j=1}^{t}(m_j-1),}. $$