Função totiente de Euler

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

Se 2 ≤ n ∈ N . {\displaystyle 2\leq n\in \mathbb {N} .} Então: n 2 ≤ φ ( n ) ≤ n − 1 {\displaystyle {\frac {\sqrt {n}}{2}}\leq \varphi (n)\leq n-1} Prova: φ ( n ) = n − 1 ⟺ n {\displaystyle \varphi (n)=n-1\Longleftrightarrow n} é primo, se n {\displaystyle n} não é primo então φ ( n ) < n − 1. {\displaystyle \varphi (n)<n-1.} Agora só é necessário provar que n 2 ≤ φ ( n ) . {\displaystyle {\frac {\sqrt {n}}{2}}\leq \varphi (n).} Prova: Se n = 2 a 0 ⋯ ( p r ) a r {\displaystyle n=2^{a_{0}}\cdots (p_{r})^{a_{r}}} sendo 2 < p 1 < p 2 < ⋯ < p r {\displaystyle 2<p_{1}<p_{2}<\cdots <p_{r}} primos, e a 0 ≥ 0 , a 1 , a 2 ⋯ , a r ≥ 1 {\displaystyle a_{0}\geq 0,a_{1},a_{2}\cdots ,a_{r}\geq 1} inteiros. φ ( n ) = φ ( 2 a 0 ) p 1 a 1 − 1 ⋯ p r a r − 1 ( p 1 − 1 ) ⋯ ( p r − 1 ) {\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 φ ( 2 a 0 ) = 1 {\displaystyle \varphi (2^{a_{0}})=1} se a 0 = 0 {\displaystyle a_{0}=0\quad } ou 2 a 0 − 1 {\displaystyle 2^{a_{0}-1}\quad } se a 0 ≥ 1 , {\displaystyle a_{0}\geq 1\quad ,} segue então: