21 O Pequeno Teorema de Fermat, o Teorema de Euler e o Teorema de Wilson

21.1 O Pequeno Teorema de Fermat

Exercício 21.1 Sejam $a,b\in\Z$ e seja $p\in\N$ um primo. Mostre que \[ (a+b)^p\equiv a^p+b^p\pmod p \]

A afirmação do exercício anterior é conhecido como o sonho do calouro.

Teorema 21.1 (O Pequeno Teorema de Fermat, versão com congruência) Seja $p\in\N$ um primo e $a\in\Z$. Então \[ a^p\equiv a\pmod p. \] Além disso, se $p\nmid a$, então \[ a^{p-1}\equiv 1\pmod p. \]

Comprovação. Vamos provar a primeira afirmação. Como todo inteiro negativo é congruente com algum inteiro positivo módulo $p$, é suficiente provar a afirmação para $a\in\N$. De fato, é suficiente provar para $a\in\{0,\ldots,p-1\}$, mas isso não simplifica nosso argumento. A prova vai por indução em $a$. Como $0^p=0\equiv 0\pmod p$, a afirmação é verdadeira para $a=0$. Assuma que a afirmação para algum $a$ e use o exercício anterior para obter que \[ (a+1)^p\equiv a^p+1^p=a+1\pmod p. \]

Agora a segunda afirmação. Se $p\nmid a$, então $a$ possui inverso módulo $p$. Multiplicando a congruência $a^p\equiv a\pmod p$ pelo inverso de $a$, obtemos que $a^{p-1}\equiv 1\pmod p$.

Uma forma alternativa do Pequeno Teorema de Fermat usando $\Z_n$ é a seguinte.

Teorema 21.2 (Pequeno Teorema de Fermat, versão $\Z_n$). Seja $p\in\N$ primo e $\overline a\in\Z_n$. Então \[ \overline a^p=\overline a. \] Além disso, se $\overline a\neq\overline 0$, então \[ \overline a^{p-1}= \overline 1. \]

Corolário 21.1 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}. \]

Comprovação. 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

21.2 O Teorema de Euler

Exercício 21.2 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)$.

Exercício 21.3 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^*$.

Teorema 21.3 (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. \]

Comprovação. 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.

21.3 O Teorema de Wilson

Lema 21.1 Seja $p$ um primo e seja $\overline a\in\Z_p$.

Se $\overline a^2=\overline 1$ então $\overline a\in\{\overline 1,\overline{-1}\}$.
Se $\overline a\neq\overline 0$ e $\overline a^{-1}=\overline a$ então $\overline a\in\{\overline 1,\overline{-1}\}$.

Comprovação. Vamos provar a primeira afirmação. Assuma que $\overline a^2=\overline 1$. Então $a^2\equiv 1\pmod p$ e $p\mid a^2-1=(a-1)(a+1)$. Como $p$ é primo, isso implica que $p\mid (a-1)$ ou $p\mid (a+1)$; ou seja $a\equiv 1\pmod p$ ou $a\equiv -1\pmod p$. No primeiro caso $\overline a=\overline 1$, enquanto no segundo $\overline a=\overline{-1}$.

Na segunda afirmação, assuma que $\overline a^{-1}=\overline a$ e multiplique os dois lados com $\overline a$ para obter que $\overline 1=\overline a^2$. Agora a primeira afirmação implica que $\overline a\in\{\overline 1,\overline{-1}\}$.

Podemos expressar estes resultados na linguagem das congruências na forma seguinte.

Lema 21.2 Seja $p$ um primo e seja $a\in\Z$.

Se $a^2\equiv 1\pmod p$ então $a\equiv \pm 1\pmod p$.
Assuma que $p\nmid a$ e seja $b$ um inverso de $a$ módulo $p$. Se $b\equiv a\pmod p$, então $a\equiv \pm 1\pmod p$.

Teorema 21.4 (O Teorema de Wilson). Um número $n\in\N$ é primo se e somente se $(n-1)!\equiv -1\pmod n$

Comprovação. Vamos começar com a volta, pois esta direção é mais fácil. Assuma que $(n-1)!\equiv -1\pmod n$ e seja $a\in\{1,\ldots,n-1\}$ tal que $a\mid n$. Em particular, $a\mid (n-1)!$. A congruência $(n-1)!\equiv -1\pmod n$ implica que $n\mid (n-1)!+1$ e obtemos destas duas divisibilidades que $a\mid 1$ que implica que $a=1$. Obtivemos então que o único divisor de $n$ entre $1$ e $n-1$ é o $1$ e assim $n$ é primo.

Agora demonstremos a ida. Assuma que $p$ é primo e escreva \[ (n-1)!=1\cdot 2\cdot 3\cdots (n-2)\cdot (n-1). \] Note que todo fator neste produto possui inverso módulo $p$ pois $p$ é primo. Além disso, se $a\in\{1,\ldots,n-1\}$ então existe único elemento $b\in\{1,\ldots,n-1\}$ tal que $b$ é inverso de $a$ módulo $p$; ou seja, $ab\equiv 1\pmod p$. Pelo lema anterior $b=a$ se e somente se $a=1$ ou $a=n-1$, Isso quer dizer que no produto na última linha destacada módulo $p$, cada fator aparece com seu inverso exceto o primeiro ($1$) e o último ($n-1$). Assim \[ (n-1)!=1\cdot 2\cdot 3\cdots (n-2)\cdot (n-1)\equiv n-1\equiv -1\pmod p. \]