Função totiente de Euler

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:

$$\phi (x)=\mathrm{♯}\{n\in \mathbb{N}|n\le x\wedge \mathrm{m}\mathrm{d}\mathrm{c}(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 as coisas com as quais lidava.

Calculando os valores da função

Se $n=p_1^{k_1}\cdots p_r^{k_r},$ onde os $p_j$ são os fatores primos (distintos) de $n$ e $k_j$ sua respectiva multiplicidade, então pode-se determinar o valor da função em $n:$

$$\phi (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:

$$\phi (n)=n\prod _{p|n}(1-\frac{1}{p})$$

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, $\phi (p^k)=p^k-p^{k-1}$

Propriedades da função

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

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

Prova: $\phi (n)=n-1⟺n$ é primo, se $n$ não é primo então $\phi (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.

$\phi (n)=\phi (2^{a_0})p_1^{a_1-1}\cdots p_r^{a_r-1}(p_1-1)\cdots (p_r-1)$ onde $\phi (2^{a_0})=1$ se $a_0=0$ ou $2^{a_0-1}$ se $a_0\ge 1,$ segue então:

$$\phi (n)\ge \phi (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{\phi (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{\phi (2_0^a)}{2^{\left(\frac{a_0}{2}\right)}}\right)\sqrt{n}\ge \left(\frac{1}{2}\right)\sqrt{n}$$

O que conclui a prova.

Ver também

• Função divisor
• Função de Carmichael
• Criptografia RSA

Bibliografia

• Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions, (1964) Dover Publications, New York. ISBN 0-486-61272-4. See paragraph 24.3.2.
• Eric Bach and Jeffrey 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

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