Quantos inteiros positivos que não excedem 1000 são relativamente primos com 30 ?

Passo 1

O enunciado pede: contar quantos inteiros positivos, menores ou iguais a 1000, são relativamente primos com 30.
Informações relevantes dadas/derivadas:
  • Queremos os inteiros n tais que 1 \le n \le 1000 e \gcd(n,30)=1.
  • A fatoração de 30 é \;30=2\cdot3\cdot5. Portanto, um número é coprimo com 30 se e somente se não for divisível por 2, por 3 nem por 5.

Passo 2

Estratégia escolhida (explicada didaticamente): usar o princípio da inclusão-exclusão para contar quantos números entre 1 e 1000 são múltiplos de 2, 3 ou 5, e subtrair esse total de 1000.
Pequena aula sobre o que vou usar:
  • Contar múltiplos: o número de múltiplos de um inteiro d no conjunto \{1,2,\dots,N\} é \left\lfloor\dfrac{N}{d}\right\rfloor. Aqui \lfloor x\rfloor é a parte inteira de x (arredonda para baixo).
  • Inclusão-exclusão (para três conjuntos A,B,C):
    o número de elementos em A\cup B\cup C é |A|+|B|+|C| - (|A\cap B|+|A\cap C|+|B\cap C|) + |A\cap B\cap C|.
No nosso contexto, A = múltiplos de 2, B = múltiplos de 3, C = múltiplos de 5.

Passo 3

Calcular quantos são múltiplos de cada primo e das combinações (usando \left\lfloor\dfrac{1000}{d}\right\rfloor):
  • Múltiplos de 2: \left\lfloor\dfrac{1000}{2}\right\rfloor=500.
  • Múltiplos de 3: \left\lfloor\dfrac{1000}{3}\right\rfloor=333.
  • Múltiplos de 5: \left\lfloor\dfrac{1000}{5}\right\rfloor=200.
Interseções (múltiplos do \operatorname{lcm} dos pares):
  • Múltiplos de 2 e 3 (ou seja de 6): \left\lfloor\dfrac{1000}{6}\right\rfloor=166.
  • Múltiplos de 2 e 5 (ou seja de 10): \left\lfloor\dfrac{1000}{10}\right\rfloor=100.
  • Múltiplos de 3 e 5 (ou seja de 15): \left\lfloor\dfrac{1000}{15}\right\rfloor=66.
Interseção tripla (múltiplos de 2,3,5 simultaneamente, isto é de 30):
  • Múltiplos de 30: \left\lfloor\dfrac{1000}{30}\right\rfloor=33.

Passo 4

Aplicar inclusão-exclusão para obter quantos inteiros em \{1,\dots,1000\} são divisíveis por 2 ou 3 ou 5:
\begin{aligned} \#(\text{divisíveis por }2\text{ ou }3\text{ ou }5) &=500+333+200 - (166+100+66) + 33 \\\ &=1033 - 332 + 33 \\\ &=701 + 33 \\\ &=734. \end{aligned}í

Passo 5

Agora o número de inteiros entre 1 e 1000 que são relativamente primos com 30 é o total 1000 menos os que têm algum fator comum (os 734 acima):
1000 - 734 = 266.

Passo 6

Verificação alternativa (curta) — usando a função totiente de Euler como checagem rápida: \varphi(30)=30\left(1-\dfrac12\right)\left(1-\dfrac13\right)\left(1-\dfrac15\right)=30\cdot\dfrac12\cdot\dfrac23\cdot\dfrac45=8.
Em cada bloco de 30 inteiros há exatamente 8 números coprimos com 30. Como 1000=30\cdot33+10, temos 33 blocos completos dando 33\cdot8=264 e sobra o intervalo de 1 a 10 (os resíduos finais), entre os quais só 1 e 7 são coprimos com 30, ou seja mais 2. Total 264+2=266, confirmando o resultado.

Resposta

266

Exercícios relacionados