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
, são relativamente primos com
.
Informações relevantes dadas/derivadas:
Informações relevantes dadas/derivadas:
- Queremos os inteiros
tais que e . - A fatoração de
é . Portanto, um número é coprimo com se e somente se não for divisível por , por nem por .
Passo 2
Estratégia escolhida (explicada didaticamente): usar o princípio da inclusão-exclusão para contar quantos números entre
e
são múltiplos de
,
ou
, e subtrair esse total de
.
Pequena aula sobre o que vou usar:
Pequena aula sobre o que vou usar:
- Contar múltiplos: o número de múltiplos de um inteiro
no conjunto é . Aqui é a parte inteira de (arredonda para baixo). - Inclusão-exclusão (para três conjuntos
):
o número de elementos emé
No nosso contexto,
= múltiplos de
,
= múltiplos de
,
= múltiplos de
.
Passo 3
Calcular quantos são múltiplos de cada primo e das combinações (usando
):
- Múltiplos de
: . - Múltiplos de
: . - Múltiplos de
: .
Interseções (múltiplos do
dos pares):
- Múltiplos de
e (ou seja de ): . - Múltiplos de
e (ou seja de ): . - Múltiplos de
e (ou seja de ): .
Interseção tripla (múltiplos de
simultaneamente, isto é de
):
- Múltiplos de
: .
Passo 4
Aplicar inclusão-exclusão para obter quantos inteiros em
são divisíveis por
ou
ou
:
Passo 5
Agora o número de inteiros entre
e
que são relativamente primos com
é o total
menos os que têm algum fator comum (os
acima):
Passo 6
Verificação alternativa (curta) — usando a função totiente de Euler como checagem rápida:
.
Em cada bloco de inteiros há exatamente
números coprimos com
. Como
, temos
blocos completos dando
e sobra o intervalo de
a
(os resíduos finais), entre os quais só
e
são coprimos com
, ou seja mais
. Total
, confirmando o resultado.
Em cada bloco de
Resposta
266