Dado um inteiro positivo m e sendo p_{1}, p_{2}, \ldots, p_{r} números menores do que ou iguais a m e primos entre si, encontrar uma fórmula para o cálculo do número de inteiros positivos menores do que ou iguais a m e que não são divisíveis por nenhum dos números p_{1}, p_{2}, \ldots, p_{r}.

Passo 1

O enunciado pede o número de inteiros positivos \le m que não são divisíveis por nenhum dos inteiros p_1,p_2,\dots,p_r, os quais são dois a dois primos e \le m. O conteúdo principal é o princípio da inclusão–exclusão e a função piso \lfloor x\rfloor.

Passo 2

Definimos para cada i o conjunto\r
A_i = \{\,n\le m \mid p_i\text{ divide }n\}.\r
Pelo princípio da inclusão–exclusão, o total de inteiros \le m divisíveis por pelo menos um p_i é\r
\Bigl|\bigcup_{i=1}^r A_i\Bigr| = \sum_{k=1}^r (-1)^{\,k-1} \sum_{1\le i_1<\cdots<i_k\le r} \bigl|A_{i_1}\cap\cdots\cap A_{i_k}\bigr|.

Passo 3

Como os p_i são primos entre si, a interseção A_{i_1}\cap\cdots\cap A_{i_k} é o conjunto dos múltiplos de p_{i_1}\cdots p_{i_k}. Portanto,\r
\bigl|A_{i_1}\cap\cdots\cap A_{i_k}\bigr| = \left\lfloor \frac{m}{p_{i_1}\cdots p_{i_k}} \right\rfloor.

Passo 4

O número de inteiros \le m que não são divisíveis por nenhum dos p_i é\r
m \;-\;\Bigl|\bigcup_{i=1}^r A_i\Bigr|.\r
Substituindo a expressão de \bigl|\bigcup A_i\bigr| e lembrando que o produto vazio vale 1 para k=0, obtemos\r
\sum_{k=0}^r (-1)^k \sum_{1\le i_1<\cdots<i_k\le r} \left\lfloor \frac{m}{p_{i_1}\cdots p_{i_k}} \right\rfloor.

Resposta

\sum_{k=0}^r (-1)^k \sum_{1\le i_1<\cdots<i_k\le r} \left\lfloor \frac{m}{p_{i_1}\cdots p_{i_k}} \right\rfloor
ou, de forma escrita,
m - \sum_{i=1}^r \left\lfloor \frac{m}{p_i}\right\rfloor + \sum_{1\le i<j\le r} \left\lfloor \frac{m}{p_i p_j}\right\rfloor - \cdots + (-1)^r \left\lfloor \frac{m}{p_1p_2\cdots p_r}\right\rfloor.

Exercícios relacionados