Função totiente de Euler: diferenças entre revisões

[[FicheiroImagem:EulerPhi.svg|thumb|300px|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-primo]]s com respeito a ele. Matematicamente:

: <math display="block">\varphi(x) = \sharp\{n \in \mathbb{N} | n \leq x \and \mathrm{mdc}(n, x) = 1\}</math>

Se <math>n = p_1^{k_1} \cdots p_r^{k_r},</math> onde os <math>p_j</math> são os fatores primos (distintos) de <math>n,</math> então pode-se determinar o valor da função em <math>n:</math>

:<math display="block">\varphi(n)=(p_{1}-1)p_{1}^{k_{1}-1} \cdots (p_{r}-1)p_{r}^{k_{r}-1}.</math>

:<math display="block">\frac {\sqrt{n}}{2} \le \varphi(n) \le n-1</math>

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

:<math display="block">\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}</math>

* [[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.