FANDOM


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çãoEditar

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çãoEditar

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

ProposiçãoEditar

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)Editar

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

Solução: A fórmula da expressão de $ \varphi(n) $ envolve frações. Para tirarmos elas 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 \geq 1 $, existe $ n $ tal que $ \varphi(n)=m! $.

BibliografiaEditar

  • E. Lozansky, C. Rousseau : Winning Solutions, Springer-Verlag, New York, 1996. E