Questão 19 Fuvest 2020 - 1ª fase - Elite Colégio e Pré-Vestibular

Questão 19

Divisibilidade

A função $E$ de Euler determina, para cada número natural $n$ , a quantidade de números naturais menores do que $n$ cujo máximo divisor comum com $n$ é igual a 1. Por exemplo, $E$ (6) = 2 pois os números menores do que 6 com tal propriedade são 1 e 5. Qual o valor máximo de $E (n)$ , para $n$ de 20 a 25?

a)	19
b)	20
c)	22
d)	24
e)	25

Resolução

Segundo o exemplo do enunciado, temos que $E (6) = 2$ , já que $m d c (6, 1) = 1$ , $m d c (6, 2) = 2$ , $m d c (6, 3) = 3$ , $m d c (6, 4) = 2$ e $m d c (6, 5) = 1$ , ou seja, os números 1 e 5 são os únicos naturais menores que 6 cujo máximo divisor comum com 6 é 1.

Podemos dizer que um número $a$ é primo com $b$ quando $m d c (a, b) = 1$ , ou seja, quando não possuem fatores em comum em sua decomposição em fatores primos.

Para $n = 20$ encontramos $n = 2^{2} \cdot 5$ , portanto todos os naturais menores que 20 que tiverem 2 e/ou 5 como fator em sua decomposição não serão primos com 20, e, consequentemente, o máximo divisor comum é diferente de 1.

Número $n$	Decomposição de $n$ em fatores primos	Números naturais menores do que $n$ cujo máximo divisor comum é 1	$E (n)$
20	$2^{2} \cdot 5$	1, 3, 7, 9, 11, 13, 17, 19	$E (20) = 8$
21	$3 \cdot 7$	1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20	$E (21) = 12$
22	$2 \cdot 11$	1, 3, 5, 7, 9, 13, 15, 17, 19, 21	$E (22) = 10$
23	$23$	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22	$E (23) = 22$
24	$2^{3} \cdot 3$	1, 5, 7, 11, 13, 17, 19, 23	$E (24) = 8$
25	$5^{2}$	1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24	$E (25) = 20$

Por definição, um número natural $p$ é primo quando tem exatamente quatro divisores inteiros: 1, -1, $p$ e $- p$ . Observe que no intervalo pedido, o único primo é 23.

Ao analisar os números naturais menores que $p$ , todos têm máximo divisor comum com $p$ igual a 1, portanto $E (p) = p - 1$ .

Então seria possível concluir sem listar casos que $E (23)$ tem o valor máximo já que 23 é o único primo e os números 24 e 25 tem mais do que 2 divisores

Portanto o valor máximo de $E (n)$ , para $n$ de 20 a 25 é 22.