Processing math: 1%

(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 φ (phi), bastante utilizada em Teoria dos Números, em particular na Criptografia.
Essa função, hoje conhecida como função \varphi de Euler, associa a cada inteiro positivo n a quantidade de inteiros positivos menores do que n que são coprimos com n.




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

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

explicador_p

Lembrete

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

Solução


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

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

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

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



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



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

\underbrace{1 \, , \, 2 \, , \, 3 \, , \, \dots \, , \, p-1}_{p-1}

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

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


Solução elaborada pelos Moderadores do Blog.

Um vídeo


A função \varphi de Euler é também conhecida como função totiente de Euler e pode ser denotada igualmente pela letra grega phi maiúscula: \Phi.
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/