Seja \(n\in\N\). Definimos \[
\varphi(n)=|\{a\in\{1,\ldots,n\}\mid \mdc an=1\}|.
\] Ou seja, \(\varphi(n)\) é o número de naturais entre \(1\) e \(n\) que são coprimos com \(n\). Por exemplo, uma conta fácil mostra que \[
\varphi(1)=\varphi(2)=1,\quad \varphi(3)=\varphi(4)=2,\quad \varphi(5)=4,\quad \mbox{etc}.
\] A função \(\varphi\) é chamado função de Euler, ou função totiente de Euler. Segue imediatamente da definição de \(\varphi\) que \(\varphi(p)=p-1\) sempre que \(p\) é primo. O seguinte resultado dá uma generalização para o caso quando \(n\) é uma potência de primo.
Lema 23.1 Se \(n=p^k\) onde \(p\) é primo e \(k\geq 1\), então \[
\varphi(n)=p^k-p^{k-1}=p^{k-1}(p-1).
\]
Comprovação. Seja \(a\in\{1,\ldots,p^k\}\). Então \(\mdc a{p^k}=1\) se e somente se \(p\nmid a\). O número dos múltiplos de \(p\) entre \(1\) e \(p^k\) é \(p^{k-1}\). Então o número dos inteiros que não são divisíveis por \(p\) no mesmo intervalo é \(p^k-p^{k-1}=p^{k-1}(p-1)\)
Antes do teorema principal desta página, colocamos um exercício.
Exercício 23.1 Sejam \(a,m,n\in\N\) tais que \(\mdc mn=1\). Mostre que \(\mdc a{mn}=\mdc am\mdc an\). Mostre que a condição \(\mdc mn=1\) é necessária para deduzir esta afirmação
Teorema 23.1 Sejam \(m,n\in\N\) primos entre si. Então \[
\varphi(mn)=\varphi(m)\varphi(n).
\]
Comprovação. Primeiro observe que \(\mdc 0{mn}\neq 1\) e \(\mdc{mn}{mn}\neq 1\), então \[
\varphi(mn)=|\{a\in\{0,\ldots,mn-1\}\mid \mdc a{mn}=1\}|.
\] (Ou seja, vamos contar os números \(a\) entre \(0\) e \(mn-1\) que são coprimos com \(mn\).) Seja \(a\in\{0,\ldots,mn-1\}\) e escreva \[
a=q_mm+r_m=q_nn+r_n
\] onde \[
r_m\in\{0,\ldots,m-1\}\quad \mbox{e}\quad r_n=\{0,\ldots,n-1\}.
\] Defina a aplicação \(\psi\) como na demonstração do Teorema Chinês dos restos: \[\begin{align*}
\psi&:\{0,\ldots,mn-1\}\to \{0,\ldots,m-1\}\times\{0,\ldots,n-1\}\\
a&\mapsto(r_m,r_n).
\end{align*}\] Pelo Teorema Chinês dos Restos, \(\psi\) é bijetiva.
Agora note que \(\mdc {r_n}n=\mdc an\) e \(\mdc {r_m}m=\mdc am\). Usando o exercício anterior, obtemos que \[
\mdc a{mn}=\mdc am\mdc an=\mdc {r_m}m\cdot\mdc {r_n}n.
\] Mas a equação anterior implica também que \(\mdc a{mn}=1\) se e somente se \(\mdc {r_m}m=\mdc{r_n}n=1\).
Restringindo a bijeção \(\psi\) para o conjunto \(X=\{a\in\{0,\ldots,mn-1\}\mid \mdc a{mn}=1\}\) obtemos uma bijeção \[
\psi:X\to Y\times Z
\] onde \[\begin{align*}
Y&=\{a\in\{0,\ldots,m-1\}\mid \mdc a{m}=1\};\\
Z&=\{a\in\{0,\ldots,n-1\}\mid \mdc a{n}=1\}.
\end{align*}\] A existência da bijeção entre \(X\) e \(Y\times Z\) implica que \(|X|=|Y\times Z|\). Assim \[
\varphi(mn)=|X|=|Y\times Z|=|Y|\cdot |Z|=\varphi(m)\varphi(n).
\]
Corolário 23.1 Seja \(n\) um número inteiro com \(n\geq 2\) e assuma que \[
n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}
\] onde os \(p_i\) são primos distintos dois a dois. Então \[
\varphi(n)=\prod_{i=1}^k\varphi(p_i^{\alpha_i})=\prod_{i=1}^k p_i^{\alpha_i-1}(p_i-1)
\]
Comprovação. Segue dos dois resultados anteriores
Exemplo 23.1 Vamos calcular \(\varphi(10^n)\) para \(n\geq 1\). Temos que \[
10^n=2^n\cdot 5^n,
\] portanto \[
\varphi(10^n)=2^{n-1}\cdot 5^{n-1}\cdot 4=2^{n+1}\cdot 5^{n-1}.
\] Por exemplo \[
\varphi(1000)=\varphi(10^3)=2^4\cdot 5^2=400.
\] Ou seja, há \(400\) naturais \(a\) entre \(1\) e \(1000\) tal que \(\mdc a{1000}=1\)