O Pequeno Teorema de Fermat e o Teorema de Euler

Seja $p$ um número primo positivo e $a,b\in\Z$. Tem-se que
\[
(a+b)^p\equiv a^p+b^p\pmod p.
\]
Exercício.

Note que o lema acima pode ser expresso na estrutura $\Z_p$ (onde $p$ é primo). De fato, o lema é equivalente a afirmar que
\[
(\bar a+\bar b)^p=\bar a^p+\bar b^p\quad\mbox{para todo}\quad \bar a,\bar b\in\Z_p.
\]
Este mesmo lema é conhecido também como o Sonho do Calouro.

(Pequeno Teorema de Fermat). 
Se $p$ é um primo positivo e $a\in \Z$, então
\begin{equation}\label{eq:cong}
a^p\equiv a\pmod p.
\end{equation}
Além disso, se $p\nmid a$, então
\[
a^{p-1}\equiv 1\pmod p.
\]
Existe um único inteiro $a_0\in\{0,\ldots,p-1\}$ tal que $a\equiv a_0\pmod p$ e $a^p\equiv a_0^p\pmod p$. Possivelmente trocando $a$ com $a_0$, podemos assumir que $a\in\{0,\ldots,p-1\}$. Se $a=0$, então a afirmação será verdadeira trivialmente. Se $a>0$ é um número positivo,  podemos escrever que $a=1+\cdots+1$ ($a$ vezes). Pelo lema anterior,
\[
a^p=(1+\cdots+1)^p\equiv 1^p+\cdots+1^p=1+\cdots +1=a\pmod p.
\]
Isso mostra que a primeira afirmação é válida.

Assuma agora que $p\nmid a$. Como no parágrafo anterior, podemos assumir sem perder generalidade que $a\in\{1,\ldots,p-1\}$ (note que $a\neq 0$ pela condição que $p\nmid a$). Em particular, $a$ é invertível módulo $p$; ou seja existe $b\in\{1,\ldots,p-1\}$ tal que $ab\equiv 1\pmod p$. Multiplicando a congruência $\bar a^p\equiv a\pmod p$ por $b$, obtemos que
\[
a^{p-1}\equiv (ba)a^{p-1}=ba^p\equiv ba\equiv 1\pmod p.
\]

Seja $p\in\N$ primo e $a\in\Z$ tal que $p\nmid a$. Então $a^{p-2}$ é um inverso de $a$ módulo $p$. Equivalentemente
\[
\overline a^{-1}=\overline a^{p-2}.
\]
O Pequeno Teorema de Fermat implica que
\[
1\equiv a^{p-1}=a\cdot a^{p-2}.
\]
Ora a definição do inverso modular implica que $a^{p-2}$ é um inverso de $a$ módulo $p$. A segunda afirmação segue imediatamente da primeira.
Seja $n\in\N$ e seja
\[
\Z_n^*=\{\overline a\in\Z_n\mid\mbox{$\overline a$ é invertível}\}.
\]
Demonstre as seguintes propriedades de $\Z_n^*$:
  • $\overline 1,\overline{-1}\in\Z_n^*$, mas $\overline 0\not\in\Z_n^*$;
  • $\Z_n^*$ é fechado para a multiplicação; ou seja, se $\overline a,\overline b\in\Z_n^*$ então $\overline a\overline b\in\Z_n^*$;
  • $|\Z_n^*|=\varphi(n)$.
Usando a notação do exercício anterior, para $\overline a\in\Z_n$ defina
\[
\mu_{\overline a}:\Z_n\to \Z_n,\quad \mu_{\overline a}(\overline b)=\overline a\overline b.
\]
Mostre que as seguinte afirmações são equivalentes:
  • $\mu_{\overline a}$ é injetiva;
  • $\mu_{\overline a}$ é sobrejetiva;
  • $\mu_{\overline a}$ é bijetiva;
  • $\overline a\in\Z_n^*$.
(O Teorema de Euler.) Seja $n\in\N$ e $a\in\Z$ tal que $\mdc an=1$. Então
\[
a^{\varphi(n)}\equiv 1\pmod n.
\]
Equivalentemente
\[
\overline a^{\varphi(n)}=\overline 1.
\]
As duas afirmações são claramente equivalentes e desta vez nós vamos provar a segunda.
Usando o exercício imediatamente anterior a esse teorema, assuma que
\[
\Z_n^*=\{\overline a_1,\overline a_2,\ldots,\overline a_{\varphi(n)}\}.
\]
Note que $\overline a\in\Z_n^*$, pois $\mdc an=1$. Considere o conjunto
\[
\overline a\Z_n^*=\{\overline a\overline a_1,\overline a\overline a_2,\ldots,\overline a\overline a_{\varphi(n)}\}
\]
Note que todo elemento de $\overline a\Z_n^*$ está contido em $\Z_n^*$ (exercício anterior) e se $i\neq j$, então $\overline a\overline a_i\neq \overline a\overline a_j$. Portanto $\overline a\Z_n^*=\Z_n^*$. Isso quer dizer que multiplicando os elementos de $\Z_n^*$ e os elementos de $\overline a \Z_n^*$ nós obtemos o mesmo elemento de $\Z_n$. De fato
\[
\prod_{i=1}^{\varphi(n)}{\overline a_i}=\prod_{i=1}^{\varphi(n)}{\overline a\overline a_i}=\overline a^{\varphi(n)}\prod_{i=1}^{\varphi(n)}{\overline a_i}.
\]
Ora, $\prod {\overline a_i}$ é um elemento invertível (primeiro exercício) e podemos multiplicar os dois lados da última equação acima com seu inverso. Fazendo isso, obtemos que
\[
\overline 1=\overline a^{\varphi(n)}.
\]

Note que o Teorema de Euler implica o Pequeno Teorema de Fermat (tomando $n=p$ primo e observando que $\varphi(p)=p-1$), mas nós decidimos deduzir o PTF de fatos mais elementares.