Question

Para cada n ≥ 1 natural, define-se φ(n) como sendo a quantidade de números coprimos com n

(dois inteiros x, y são coprimos se mdc(x,y) = 1)

Isto é, φ(n) = #{ 1 ≤ m ≤ n : mdc(m,n) = 1 }

Tal função φ é chamada Função Phi de Euler (ou função totiente).

Seja p um número primo. Encontre φ(p) e φ(pᵏ) usando conceitos conhecidos de números primos e de número de divisores de um inteiro

Answer 1

Para cada natural  n ≥ 1,  considere o conjunto

     $\mathsf{A(n):=\{m\in\mathbb{N}:~~1\le m\le n~~e~~mdc(m,n)=1\}}$


Perceba que

     •  para  n = 1,  A(n)  só tem um elemento:

        A(1) = {1}


     •  para  n > 1,  A(n)  é formado por todos os naturais  m  menores que  n  de modo que  m  e  n  são primos entre si (ou coprimos).


Define-se a função Phi de Euler (ou função totiente) para cada  n  natural,  n ≥ 1  como sendo a quantidade de elementos (cardinalidade) do conjunto  A(n)  definido acima. Denotamos a função Phi de Euler da seguinte forma:

     $\mathsf{\varphi(n):=\#\{m\in\mathbb{N}:~~1\le m\le n~~e~~mdc(m,n)=1\}=\#\big[A(n)\big].}$

—————

Considere  p  um número primo. Queremos calcular

a)  φ(p).

Para facilitar o raciocínio intuitivo, vamos verificar quais são os elementos do conjunto  A(p):

Considerando todos os naturais de  1  até  p,  todos eles deixam mdc  1  com  p,  exceto o próprio  p:

     $\mathsf{mdc(m,\,p)}=\left\{ \begin{array}{ll} \mathsf{1,}&\quad\mathsf{se~~1\le m<p}\\\\ \mathsf{p,}&\quad\mathsf{se~~m=p} \end{array}\right.$


Portanto, o conjunto  A(p)  é

     $\mathsf{A(p)=\{1,\,\ldots,\,p-1\}}\\\\ \mathsf{A(p)=\{m\in\mathbb{N}:~~1\le m\le p-1\}}$


A quantidade de elementos de  A(p)  é

     $\mathsf{\varphi(p)=\#\big[A(p)\big]}$

     $\mathsf{\varphi(p)=p-1}$        ✔

—————

b)  φ(pᵏ),  com  k  natural,  k > 1.

O número  n = pᵏ  é uma potência de primo, logo ele já está em sua forma decomposta.

Considerando os naturais de  1  até  pᵏ,  temos que

     $\left\{\begin{array}{ll} \mathsf{mdc(m,\,p^k)=1,}&\quad\mathsf{se~~m~n\tilde{a}o~\acute{e}~m\acute{u}ltiplo~de~p}\\\\ \mathsf{mdc(m,\,p^k)\ge p>1,}&\quad\mathsf{se~~m~\acute{e}~m\acute{u}ltiplo~de~p} \end{array}\right.$


Então vamos calcular quantos múltiplos de  p  existem  de  1  até  pᵏ,  isto é, a quantidade de elementos do conjunto  M(p)  definido logo abaixo:

     $\mathsf{M(p):=\{m\in\mathbb{N}:~~m=pq,~~p\le pq\le p^k,~~k,\,q\in\mathbb{N}^*\}}\\\\ \mathsf{M(p)=\{p,\,2p,\,3p,\,\ldots,\,p^k-p,\,p^k\}}\\\\ \mathsf{M(p)=\{p,\,2p,\,3p,\,\ldots,\,(p^{k-1}-1)\cdot p,\,p^{k-1}\cdot p\}}\\\\ \mathsf{M(p)=\{m\in\mathbb{N}:~~m=pq,~~1\le q\le p^{k-1},~~k,\,q\in\mathbb{N}^*\}}$


Note que

     $\mathsf{\#\big[M(p)\big]=p^{k-1}}$

isto é, existem  $\mathsf{p^{k-1}}$  naturais  de  1  até  pᵏ  que não são coprimos com  pᵏ,  pois o cálculo do mdc de  pᵏ  com qualquer elemento de  M(p)  é no mínimo igual a  p.


Portanto,

     $\mathsf{A(p^k)=\{1,\,2,\,\ldots,\,p^k\}\setminus M(p)}$


e como  $\mathsf{M(p)\subset \{1,\,2,\,\ldots,\,p^k\},}$  temos que

     $\mathsf{\varphi(p^k)=\#\big[A(p^k)\big]}\\\\ \mathsf{\varphi(p^k)=\#\big[\{1,\,2,\,\ldots,\,p^k\}\setminus M(p)\big]}\\\\ \mathsf{\varphi(p^k)=\#\big[\{1,\,2,\,\ldots,\,p^k\}\big]-\#\big[M(p)\big]}\\\\ \mathsf{\varphi(p^k)=p^k-p^{k-1}}\\\\ \mathsf{\varphi(p^k)=p^{k-1}\cdot p-p^{k-1}}$

     $\mathsf{\varphi(p^k)=p^{k-1}\cdot (p-1)}$        ✔


Tags:  teoria dos números função phi euler totiente natural primo mdc matemática discreta álgebra


Bons estudos! :-)