Função totiente 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:

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

$${\displaystyle \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:

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

Propriedades da função

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

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

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

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

${\displaystyle \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 ${\displaystyle \varphi (2^{a_{0}})=1}$ se ${\displaystyle a_{0}=0\quad }$ ou ${\displaystyle 2^{a_{0}-1}\quad }$ se ${\displaystyle a_{0}\geq 1\quad ,}$ segue então:

$${\displaystyle \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

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 ${\displaystyle [1,n]}$
• Calcule ø(n)para um número até 2³¹.
• Teoria dos Números

Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o. v d e

• Portal da matemática