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: 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 \geq 1, existe n tal que \varphi(n)=m!.

Referências BibliográficasEditar

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