Para cada n ≥ 1 natural, define-se φ(n) como sendo a quantidade de números coprimos com n (dois inte.... Pergunta de ideia deNiiya

November 2019 1 385 Report

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

Lista de comentários

Lukyo

Verified answer

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! :-)

3 votes Thanks 2

Niiya Perfeita! obrigado :)

Lukyo De nada! :-)