Função φ de Euler

Seja $n$ um número natural. Então $\varphi(n)$ representa a quantidade de inteiros $k$ menores ou iguais a $n$ tais que $\operatorname{mdc} (n,k)=1$.

Proposição

Se $n = p^k$, onde $p$ é primo e $k$ é inteiro positivo, então $\varphi(n)=p^k-p^{k-1}$.

Prova: Calcularemos a quantidade de números que são menores que $n$ e que não são primos com ele. De fato, um número não é primo com $p^k$ se, e somente se, ele for múltiplo de $p$. Observe ainda que os múltiplos de $p$ menores ou iguais a $p^k$ são $p,p^2,p^3,...,p^k$, ou seja, existem $p^{k-1}$. Com isso, a quantidade de primos menores que $n$ e primos com ele é $p^k-p^{k-1}$.

Proposição

Se $\operatorname{mdc}(m,n) = 1$, então $\varphi(mn)=\varphi(m)\varphi(n)$. Em outras palavras, $\varphi$ é uma função multiplicativa.

Proposição

Se $n=p_1^{\alpha_1}.p_2^{\alpha_2} \dots p_k^{\alpha_k}$ é a fatoração em primos de $n$, então

$\varphi (n)=n(1-{\frac {1}{p_{1}}})(1-{\frac {1}{p_{2}}})\dots (1-{\frac {1}{p_{k}}}).$

Exemplo (OBM 2002 - 3ª Fase - Nível 2)

Prove que para todo $m\ge 1$, existe $n$ tal que $\varphi(n)=m!$.

Solução: Para tirarmos as frações da nossa vida, vamos pensar que se $k=p_1^{e_1}p_2^{e_2}\dots p_t^{e_t}$, então

$\varphi(k)=p_1^{e_1-1}p_2^{e_2-2}\dots p_t^{e_t-1}(p_1-1)(p_2-1)\dots(p_t-1).$

Já que nesta fórmula aparecem primos, a estratégia principal será fazer um indução controlando os primos.

Antes, façamos alguns casos particulares. Para isto, escreveremos $M!$ e forçaremos ele virar o $\varphi$ de algum número. Por exemplo,

$1!=2^0.(2-1)=\varphi(2)$

$2!=2^1.(2-1)=\varphi(4)$

$3!=2^0.3^1.(2-1).(3-1)=\varphi(18)$

$4!=2^2.3^1.(2-1).(3-1)=\varphi(72).$

Vamos usar indução. Considere $p_n \geq 5$ o $n$-ésimo primo. A ideia será a seguinte:

(i) Iremos supor para todo $k$ menor que $p_n$, $k!$ pode ser escrito conforme a forma do enunciado, usando apenas primos menores que $p_n$ na sua fatoração.

(ii) A partir disto, provaremos que a afirmação vale para $p_n$.

(iii) Provemos para os números não primos, digamos $m$, tais que $p_n<m<p_{n+1}$.

Se supormos que $(p_n-2)!=\varphi(p_1^{e_1}p_2^{e_2}\dots p_{n-1}^{e_{n-1}})$. Assim,

$p_n!=p_n.(p_n-1).(p_n-2)!=p_n.(p_n-1).\varphi(p_1^{e_1}p_2^{e_2}\dots p_{n-1}^{e_{n-1}})=$

$=\varphi(p_n^2)\varphi(p_1^{e_1}p_2^{e_2}\dots p_{n-1}^{e_{n-1}})=\varphi(p_1^{e_1}p_2^{e_2}\dots p_{n-1}^{e_{n-1}}p_n^2).$

Já fizemos (ii). Vamos focar em (iii). Observe que $m$ (no caso da condição (iii)) é o produto de primos menores ou iguais a $p_n$. Vamos supor que a afirmação vale para $m - 1$. Escrevamos $m!=m(m-1)!$. Basta fazermos para $(m-1)!$ e usarmos a fatoração em primos de $m$ (use o fato que já provamos que o resultado vale para todos os primos).

Portanto, para todo $m\ge 1$, existe $n$ tal que $\varphi(n)=m!$.

Referências Bibliográficas

[1] E. Lozansky, C. Rousseau : Winning Solutions, Springer-Verlag, New York, 1996. E