Question

Quantos números menores que 7865 e maiores ou iguais a 1, são primos com 7865?


Dica: Use a função phi de Euler.

_______________________

Por favor responder de forma detalhada. Respostas com brincadeiras serão eliminadas.

Answer 1

A função Φ de Euler calculada sobre um natural n > 1 fornece a quantidade de naturais menores que n que são primos com n.

No caso particular em que n = 1, temos Φ(1) = 1.

Esta função possui as propriedades seguintes:

• Se n é primo, e k natural, então

Φ(n^k) = n^(k − 1) · (n − 1)

Em particular, fazendo k = 1, se n é primo, então

Φ(n) = n − 1

• Para a, b naturais, se mdc(a, b) = 1, então

Φ(a · b) = Φ(a) · Φ(b)

=====

O que esta tarefa pede nada mais é do que calcular Φ(7865).

Decompondo 7865 em fatores primos, obtemos

7865 = 5 · 11² · 13

Portanto,

Φ(7865) = Φ(5 · 11² · 13)

Aplicando as propriedades,

Φ(7865) = Φ(5) · Φ(11²) · Φ(13)
Φ(7865) = (5 − 1) · [11²⁻¹ · (11 − 1)] · (13 − 1)
Φ(7865) = 4 · [11¹ · 10] · 12
Φ(7865) = 4 · 110 · 12

Φ(7865) = 5280 <——— esta é a resposta.

Bons estudos! :-)