Movatterモバイル変換

Função totiente de Euler

Origem: Wikipédia, a enciclopédia livre.

Afunção totiente, por vezes também chamada defunção tociente, oufunção phi (fi), – representada por φ(x) – é, nateoria dos números, definida para umnúmero naturalx como sendo igual à quantidade de números menores ou igual axco-primos com respeito a ele. Matematicamente:

$\varphi (x)=\sharp \{n\in \mathbb {N} |n\leq x\land \mathrm {mdc} (n,x)=1\}$

Por exemplo, φ(8) = 4, uma vez que 1, 3, 5 e 7 são co-primos de 8. Um outro exemplo, φ(1) = 1 pois mdc(1, 1) = 1. A função é por vezes chamadafunção totiente de Euler, pois foi o matemáticosuíço Leonhard Euler quem a determinou. A função totiente é também chamada simplesmente por função fi, por ser essa (φ) a letra grega usada para representá-la.

A função totiente é importante principalmente porque fornece o tamanho dogrupo multiplicativo de inteiros módulo n — mais precisamente, φ(n) é acardinalidade do grupo de unidades doanelZ/nZ. Este fato, ao lado doteorema de Lagrange, fornece a prova doteorema de Euler.

A função totiente possui esse nome graças ao matemático inglêsJames Joseph Sylvester, que gostava de inventar palavras novas e diferentes para as coisas com as quais lidava.

Calculando os valores da função

[editar |editar código-fonte]

Se $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}},$ onde os $p_{j}$ são os fatores primos (distintos) de $n {\displaystyle n}$ e $k_{j}$ sua respectiva multiplicidade, então pode-se determinar o valor da função em $n : {\displaystyle n:}$

$\varphi (n)=(p_{1}-1)p_{1}^{k_{1}-1}\cdots (p_{r}-1)p_{r}^{k_{r}-1}.$

A última fórmula é umproduto de Euler e frequentemente se escreve como:

\varphi (n)=n\prod _{p|n}\left(1-{\frac {1}{p}}\right)

sendo que este produto varia apenas sobre os primos distintosp que dividemn.

Esta fórmula pode ser deduzida mostrando-se que a função émultiplicativa, e observando-se que, para um primop, $\varphi (p^{k})=p^{k}-p^{k-1}$

Propriedades da função

[editar |editar código-fonte]

Se $2\leq n\in \mathbb {N} .$ Então:

${\frac {\sqrt {n}}{2}}\leq \varphi (n)\leq n-1$

Prova: $\varphi (n)=n-1\Longleftrightarrow n$ é primo, se $n {\displaystyle n}$ não é primo então $\varphi (n)<n-1.$ Agora só é necessário provar que ${\frac {\sqrt {n}}{2}}\leq \varphi (n).$

Prova: Se $n=2^{a_{0}}\cdots (p_{r})^{a_{r}}$ sendo $2<p_{1}<p_{2}<\cdots<p_{r}$ primos, e $a_{0}\geq 0,a_{1},a_{2}\cdots ,a_{r}\geq 1$ inteiros.

$\varphi (n)=\varphi (2^{a_{0}})p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}-1}(p_{1}-1)\cdots (p_{r}-1)$ onde $\varphi (2^{a_{0}})=1$ se $a_{0}=0\quad$ ou $2^{a_{0}-1}\quad$ se $a_{0}\geq 1\quad ,$ segue então:

$\varphi (n)\geq \varphi (2_{0}^{a})p_{1}^{\left({\frac {a_{1}-1}{2}}\right)}\cdots p_{r}^{\left({\frac {a_{r}-1}{2}}\right)}{\sqrt {p_{1}}}\cdots {\sqrt {p_{r}}}=\left({\frac {\varphi (2_{0}^{a})}{2^{\left({\frac {a_{0}}{2}}\right)}}}\right)p_{1}^{\left({\frac {a_{1}}{2}}\right)}p_{2}^{\left({\frac {a_{2}}{2}}\right)}\cdots p_{r}^{\left({\frac {a_{r}}{2}}\right)}=\left({\frac {\varphi (2_{0}^{a})}{2^{\left({\frac {a_{0}}{2}}\right)}}}\right){\sqrt {n}}\geq \left({\frac {1}{2}}\right){\sqrt {n}}$

O que conclui a prova.

Ver também

[editar |editar código-fonte]

Bibliografia

[editar |editar código-fonte]

Milton Abramowitz andIrene A. Stegun,Handbook of Mathematical Functions, (1964)Dover Publications, New York.ISBN 0-486-61272-4. See paragraph 24.3.2.
Eric Bach andJeffrey Shallit,Algorithmic Number Theory, volume 1, 1996, MIT Press.ISBN 0-262-02405-5, see page 234 in section 8.8.
Kirby Urner,Computing totient function in Python and scheme, (2003)

Ligações externas

[editar |editar código-fonte]

Miyata, Daisuke & Yamashita, Michinori,Derived logarithmic function of Euler's function
Bordellès, Olivier,Numbers prime toq in $[1,n]$
Calcule ø(n)para um número até 2³¹.
Teoria dos Números

Este artigo sobrematemática é umesboço. Você pode ajudar a Wikipédiaexpandindo-o.

Portal da matemática

v d e Teoria dos números
Princípios gerais	Indução Princípio da boa ordenação Relação de equivalência
Áreas	Teoria algébrica dos números teoria dos corpos de classes teoria de Iwasawa teoria de Kummer Teoria analítica dos números teoria analítica das funções L teoria probabilística dos números teoria dos crivos Teoria computacional dos números Geometria diofantina Combinatória aritmética (teoria aditiva dos números) Geometria aritmética
Conceitos-chave	Números 0 Números naturais Unidade Paridade paridade do zero Números primos Teorema de Euclides Crivo de Eratóstenes Teste de primalidade Teorema dos números primos Números compostos Números racionais Números irracionais Números algébricos Números transcendentes Números p-ádicos análise p-ádica Aritmética Aritmética modular Teorema fundamental da aritmética Teorema chinês do resto Funções aritméticas
Conceitos avançados	Formas quadráticas Formas modulares Funções L Equações diofantinas Aproximação diofantina Frações contínuas
Principais teóricos	Fibonacci Fermat Gauss Euler Legendre Riemann Dirichlet
Categoria Wikibook

Obtida de "https://pt.wikipedia.org/w/index.php?title=Função_totiente_de_Euler&oldid=56868887"

Categorias:

Categorias ocultas:

[8]ページ先頭