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

A função gama é definida, para cada x > 0, por Prove que, para todo x > 0, Conclua que a função gama interpola os fatoriais, isto é, que todo fatorial pertence à imagem de

Responda

Niiya November 2019 | 0 Respostas

Prove que, se um número real tem uma quantidade finita de dígitos, então ele é racional. Dê um contra exemplo para a recíproca (isto é, dê exemplo de um número que é racional mas que possui infinitos dígitos).

Responda

Niiya November 2019 | 0 Respostas

Seja x um número real positivo qualquer. Definimos o logaritmo de x como sendo Utilizando exclusivamente essa definição, mostre que, para quaisquer x, y positivos,

Responda

Niiya November 2019 | 0 Respostas

Prove o critério de divisibilidade do 11 utilizando congruências ou o princípio de indução finita Isto é, mostre que um número inteiro da forma ( são os dígitos do número) é divisível por 11 se, e somente se, é um número divisível por 11.

Responda

Niiya November 2019 | 0 Respostas

Teorema de Euler (Álgebra) Dado dois inteiros m e n com mdc(m,n) = 1, tem-se que Onde é a função Phi de Euler, que, para cada inteiro n, retorna a quantidade de inteiros menores que n que são coprimos com n Algumas propriedades importantes de : ________________________________ Encontre o resto da divisão de por .

Responda

Niiya November 2019 | 0 Respostas

Seja a área de um polígono regular de n lados, isto é Podemos imaginar um círculo como um "polígono de infinitos lados", logo sua área pode ser definida por Considere um círculo de raio r e polígonos regulares inscritos nesse círculo, de modo que represente a área do polígono regular de n lados inscrito no círculo. Mostre, via limites, que .Dica: Encontre uma fórmula geral para Obs: O limite fundamental pode ser utilizado Se f é uma função derivável com f(x₀) = 0.

Responda

Niiya November 2019 | 0 Respostas

Sejam a, m, n inteiros com mdc(m,n) = 1 Mostre que, se m divide a e n divide a, então(mn) divide a

Responda

Lista de comentários

Verified answer

A função gama é definida, para cada x > 0, por Prove que, para todo x > 0, Conclua que a função gama interpola os fatoriais, isto é, que todo fatorial pertence à imagem de

Prove que, se um número real tem uma quantidade finita de dígitos, então ele é racional. Dê um contra exemplo para a recíproca (isto é, dê exemplo de um número que é racional mas que possui infinitos dígitos).

Seja x um número real positivo qualquer. Definimos o logaritmo de x como sendo Utilizando exclusivamente essa definição, mostre que, para quaisquer x, y positivos,

Se é uma função crescente, prove queonde é a função mínimo (retorna o mínimo entre dois valores).

Seja uma função contínua. Mostre que Obs: A notação é para indicar que a função é nula em todo o intervalo

Sejam a, b, m números inteiros com mdc(a,m) = 1. Mostre que, se a divide (mb), então a divide b.

Prove o critério de divisibilidade do 11 utilizando congruências ou o princípio de indução finita Isto é, mostre que um número inteiro da forma ( são os dígitos do número) é divisível por 11 se, e somente se, é um número divisível por 11.

Sejam a, m, n inteiros com mdc(m,n) = 1 Mostre que, se m divide a e n divide a, então(mn) divide a

Recomendar perguntas

Helpful Links

Helpful Social