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).
\]
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$.