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.
\[
\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.
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).
\]
\[
\varphi(n)=p^k-p^{k-1}=p^{k-1}(p-1).
\]
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.
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.
Sejam $m,n\in\N$ primos entre si. Então
\[
\varphi(mn)=\varphi(m)\varphi(n).
\]
\[
\varphi(mn)=\varphi(m)\varphi(n).
\]
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.
\[
\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).
\]
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)
\]
\[
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)
\]
Segue dos dois resultados anteriores.
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$.
\[
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$.