(A) Problema para ajudar na escola: Uma função de Euler

Clique no botão abaixo para visualizar o problema.

Problema
(A partir da 1ª série do E. M. – Nível de dificuldade: Médio)


Leonhard Euler (1707-1783) foi um brilhante matemático suíço que deixou inúmeras contribuições não só para a Matemática, mas também para a Física, para a Química e para a Astronomia.
Entre seus inúmeros feitos, Euler definiu uma importante função, comumente denotada pela letra grega [tex]\varphi[/tex] (phi), bastante utilizada em Teoria dos Números, em particular na Criptografia.
Essa função, hoje conhecida como função [tex]\varphi[/tex] de Euler, associa a cada inteiro positivo [tex]n[/tex] a quantidade de inteiros positivos menores do que [tex]n[/tex] que são coprimos com [tex]n.[/tex]




Considere a função
[tex]\qquad \qquad \begin{align*} \varphi: \, \{1,2,3,4,5, \, \cdots \, \} & \rightarrow \, \{1,2,3,4,5, \, \cdots \, \}\\
n &\mapsto \, \varphi(n)\end{align*}[/tex]
em que [tex]\varphi(n)[/tex] é a quantidade de inteiros positivos menores do que [tex]n[/tex] que são coprimos com [tex]n.[/tex]

(a) Determine [tex]\varphi(20)[/tex].
(b) Determine [tex] \varphi(23)[/tex].
(c) Se [tex]p[/tex] é um número natural primo, determine [tex] \varphi(p)[/tex].

explicador_p

Lembrete

Se [tex]m[/tex] e [tex]n[/tex] são números naturais tais [tex]mdc(n,m)=1[/tex], então [tex]m[/tex] e [tex]n[/tex] são ditos coprimos, ou relativamente primos ou, ainda, primos entre si.

Solução


(a) Poderíamos calcular o [tex]mdc[/tex] entre [tex]20[/tex] e todos os números naturais menores do que [tex]20[/tex] e contarmos aqueles para os quais o [tex]mdc[/tex] é igual [tex]1.[/tex] Mas podemos economizar tempo e contas, observando que:

Como [tex]20[/tex] é um número par, então todo número natural par [tex]a[/tex] é tal que [tex]mdc(a,20)\ne 1[/tex]; já que, nesse caso, [tex]mdc(a,20)\geqslant 2.[/tex]
Como [tex]20[/tex] é um múltiplo de [tex]5[/tex], então todo número natural [tex]b[/tex] múltiplo de [tex]5[/tex] é tal que [tex]mdc(b,20)\ne 1[/tex]; já que, nesse caso, [tex]mdc(b,20)\geqslant 5.[/tex]

Dessa forma, não precisamos calcular o [tex]mdc[/tex] entre [tex]20[/tex] e os números naturais menores do que [tex]20[/tex] que são pares ou múltiplos de [tex]5.[/tex] Vamos então aos cálculos, lembrando que a decomposição de [tex]20[/tex] como produto de potências de números primos é [tex]20=2^2 \cdot 5.[/tex]

[tex]mdc(20,\textcolor{red}{1})=1[/tex] ; [tex]mdc(20,\textcolor{red}{3})=1[/tex] ; [tex]mdc(20,\textcolor{red}{7})=1[/tex] ; [tex]mdc(20,\textcolor{red}{9})=1[/tex] ; [tex]mdc(20,\textcolor{red}{11})=1[/tex] ; [tex]mdc(20,\textcolor{red}{13})=1[/tex] ; [tex]mdc(20,\textcolor{red}{17})=1[/tex] ; [tex]mdc(20,\textcolor{red}{19})=1.[/tex]
Pelos nossos cálculos, concluímos que [tex] \, \fcolorbox{black}{#eee0e5}{$\varphi(20)=8$} \, .[/tex]



(b) Neste item também poderíamos calcular o [tex]mdc[/tex] entre [tex]23[/tex] e todos os números naturais menores do que ele. Mas observe que [tex]23[/tex] é um número primo; assim, se [tex]x[/tex] é um número natural menor do que [tex]23[/tex], todos os fatores primos de [tex]x[/tex] são menores do que [tex]23[/tex] e, com isso, [tex]mdc(23,x)=1.[/tex] Assim, todo número natural menor do que [tex]23[/tex] é coprimo com [tex]23[/tex]; portanto, concluímos que [tex] \, \fcolorbox{black}{#eee0e5}{$\varphi(23)=22$} \, .[/tex]



(c) Este item é uma generalização do item anterior, por isso vamos utilizar o mesmo raciocínio!
Sejam [tex]p[/tex] um número natural primo e [tex]m[/tex] um número natural menor do que [tex]p[/tex]. Note que qualquer divisor [tex]d[/tex] de [tex]m[/tex] é tal que [tex]d \leqslant m[/tex], donde [tex]d \lt p[/tex]. Como [tex]p \, [/tex] e [tex] \, 1[/tex] são os únicos divisores de [tex]p[/tex], então [tex]p[/tex] e [tex]m[/tex] têm apenas um divisor comum: [tex]1.[/tex]
Dessa forma, qualquer número natural não nulo [tex]m[/tex] menor do que [tex]p[/tex] é tal que [tex]mdc(p,m)=1[/tex] e, portanto, os coprimos com [tex]p[/tex] menores do que ele são:

[tex]\underbrace{1 \, , \, 2 \, , \, 3 \, , \, \dots \, , \, p-1}_{p-1}[/tex]

Com isso, concluímos que se [tex]p[/tex] é um número natural primo, então [tex] \, \fcolorbox{black}{#eee0e5}{$\varphi(p)=p-1$} \, .[/tex]

Assim, em particular, [tex]\varphi(11)= 10[/tex] , [tex]\varphi(13)= 12[/tex] , [tex]\varphi(19)= 18[/tex] , [tex]\varphi(2719)= 2718[/tex] , [tex]\varphi(8893)= 8892[/tex] e [tex]\varphi(p)=p-1[/tex], para todos os [tex]1229[/tex] números desta lista.


Solução elaborada pelos Moderadores do Blog.

Um vídeo


A função [tex]\varphi[/tex] de Euler é também conhecida como função totiente de Euler e pode ser denotada igualmente pela letra grega phi maiúscula: [tex]\Phi.[/tex]
Assista a um vídeo da Khan Academy sobre essa função e aprenda um pouco mais sobre ela: é só clicar na setinha e

Bons Estudos!



Se for conveniente, você pode obter um arquivo PDF desta página, com o problema e a solução, clicando no botão abaixo.
Você pode abrir o arquivo diretamente no seu navegador (Chrome, Edge, Firefox, Safari, entre outros), mas também pode utilizar o software gratuito Adobe Acrobat Reader.
Caso o dispositivo que você está utilizando não tenha o Acrobat Reader instalado, é só clicar AQUI para fazer o download adequado ao seu dispositivo.

Link permanente para este artigo: http://clubes.obmep.org.br/blog/a-problema-para-ajudar-na-escola-uma-funcao-de-euler/