Achar os elementos do conjunto
que são primos com 8.
Passo 1
O enunciado pede: encontrar, dentro do conjunto
, os elementos que são "primos com
".
Informações dadas:
Informações dadas:
- O conjunto é
. - O número com o qual vamos testar primalidade relativa é
.
A pergunta concreta é: quais elementos detêm máximo divisor comum igual a com ?
Passo 2
Entender o que significa "primos com
". Dois inteiros
e
são primos entre si (ou coprimos) quando
Aqui
é o maior inteiro que divide simultaneamente
e
. Uma maneira prática de verificar isso é fatorar
ou usar o algoritmo de Euclides (que calcula
por restos sucessivos). Vou explicar os dois caminhos, que são úteis na prova.
Passo 3
Fatoração rápida de
. Como lembrete, fatorar significa escrever como produto de primos:
Isto diz que o único primo que divide
é
. Logo qualquer número que compartilhe um fator primo com
necessariamente será divisível por
(ou seja, será par). Portanto, um atalho: um inteiro
é coprimo com
se, e somente se,
não for múltiplo de
— isto é, se
for ímpar.
Passo 4
Aplicando o atalho aos elementos do conjunto: os ímpares em
são
. Esses são candidatos a serem coprimos com
. Os pares
e
não poderão ser coprimos com
porque compartilham o fator
.
Passo 5
Para ser totalmente rigoroso, calculamos
para cada
usando o algoritmo de Euclides (mostro os passos dos restos):
Cálculo de
. Como
divide
, temos diretamente
Passo 6
Cálculo de
. Como
divide
(resto zero),
portanto
não é coprimo com
.
Passo 7
Cálculo de
pelo algoritmo de Euclides:
O último resto não nulo é
, logo
portanto
é coprimo com
.
Passo 8
Cálculo de
. Como
divide
,
portanto
não é coprimo com
.
Passo 9
Cálculo de
pelo algoritmo de Euclides:
O último resto não nulo é
, então
portanto
é coprimo com
.
Passo 10
Conclusão: entre os elementos de
, os que são primos com
(ou seja, têm
igual a
com
) são exatamente
. Bom trabalho — já pode decorar o truque: se um número é potência de
, os coprimos com ele são os números ímpares.