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

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 $\varphi$ (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)$.

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.