Função totiente de Euler

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
A função φ de Euler.

A função totiente, por vezes também chamada de função tociente, ou função phi (fi), – representada por φ(x) – é, na teoria dos números, definida para um número natural x como sendo igual à quantidade de números menores ou igual a x co-primos com respeito a ele. Matematicamente:

\varphi(x) = \sharp\{n \in \mathbb{N} | n \leq x \and \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 chamada função totiente de Euler, pois foi o matemático suíç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 do grupo multiplicativo de inteiros módulo n — mais precisamente, φ(n) é a cardinalidade do grupo de unidades do anel Z/nZ. Este fato, ao lado do teorema de Lagrange, fornece a prova do teorema de Euler.

A função totiente possui esse nome graças ao matemático inglês James Joseph Sylvester, que gostava de inventar palavras novas e diferentes para às 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, então pode-se determinar o valor da função em n:

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

A última fórmula é um produto 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 distintos p que dividem n.

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

Propriedades da função[editar | editar código-fonte]

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

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

Prova: \varphi(n) = n-1  \Longleftrightarrow n é primo, se n não é primo então \varphi(n) < n-1. Agora só é necessário provar que  \frac{\sqrt{n}}{2} \le \phi(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} \ge 0,a_{1},a_{2} \cdots ,a_{r} \ge 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} \ge 1 \quad, segue então:

\varphi(n) \ge \varphi(2^a_{0})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^a_{0})}{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^a_{0})}{2^{\left ( \frac{a_{0}}{2} \right )}} \right )\sqrt{n} \ge \left ( \frac{1}{2} \right ) \sqrt{n}

O que conclui a prova.

Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.

Ver também[editar | editar código-fonte]

Bibliografia[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]