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

Conteúdo apagado Conteúdo adicionado
Kaktus Kid (discussão | contribs)
Linha 11:
 
== Calculando os valores da função ==
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>\varphi(n)=(p_{1}-1)p_{1}^{k_{1}-1} \cdots (p_{r}-1)p_{r}^{k_{r}-1}.</math>
Linha 21:
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 é [[função multiplicativa|multiplicativa]], e observando-se que, para um primo ''p'', <math>p^k - \varphi(p^k) = p^{k-1}\,</math>
 
== Propriedades da função ==
 
Se <math>2 \le n \in \mathbb{N}.</math>. Então:
 
:<math>\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>.
 
Prova: Se <math>n = 2^{a_0} \cdots (p_{r})^{a_{r}}</math> sendo <math>2 < p_{1} < p_{2} \cdots p_{r}</math> primos, e <math>a_{0} \ge 0,a_{1},a_{2} \cdots ,a_{r} \ge 1</math> inteiros.
 
<math>\varphi(n) = \varphi(2^{a_{0}})p_1^{a_{1}-1} \cdots p_r^{a_{r}-1}(p_{1}-1) \cdots (p_{r}-1)</math> onde <math>\varphi(2^{a_{0}}) = 1</math> se <math>a_{0} = 0 \quad</math> ou <math>2^{a_{0}-1}\quad</math> se <math>a_{0} \ge 1 \quad,</math>, segue então:
 
:<math>\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>
Linha 58:
*[http://www.mat.unb.br/~maierr/tnotas.pdf Teoria dos Números]
 
{{DEFAULTSORT:Funcao totiente de Euler}}
[[Categoria:Leonhard Euler]]
[[Categoria:Funções aritméticas]]