Teorema de Euler-Fermat

Definições

Primeiramente vamos considerar algumas definições para tornar tudo mais compacto e simples de entender.

Definição: Definimos $\varphi (n)$ como a quantidade de inteiros positivos menores ou iguais a $n$ que são relativamente primos com $n$.

Alguns exemplos imediatos seriam

$\varphi (6)=2$, pois $1$ e $5$ são relativamente primos com $6$, enquanto nenhum dos números $2,3,4,6$ é.

$\varphi (1)=1$, pois $mdc(1,1)=1$.

$\varphi (p)=p-1$ para todo número primo $p$, pois todos os números $1,2,...,p-1$ são relativamente primos com $p$, enquanto $mdc(p,p) \ne 1$.

Agora podemos passar para o que realmente vai nos ajudar!

Teorema de Euler-Fermat

Teorema 1 (Fermat): Seja $p$ um número primo e $a$ um inteiro não múltiplo de $p$ qualquer, então

$a^{p-1} \equiv 1 (\text{mod} p )$

Teorema 2 (Euler): Seja $n$ um inteiro positivo qualquer e $a$ um inteiro relativamente primo com $n$, então

$a^{\varphi (n)} \equiv 1 (\text{mod} n )$

 Note que o Teorema de Fermat é o caso particular do Teorema de Euler quando $n$ é um número primo. No entanto, o Teorema de Fermat é muito mais comum em problemas de olimpíada e, portanto, vale a pena olhá-lo com mais atenção do que um simples caso particular.

Agora vejamos a prova dos dois Teoremas:

Prova: Primeiro vamos pensar em como utilizar a informação de que $\varphi (n)$ é a quantidade de inteiros positivos menores ou iguais a $n$ e primos com $n$. Para isso, vamos considerar o conjunto

$A = \{a_1,a_2,...,a_{\varphi (n)} \}$

desses inteiros. observe que se dois deles deixam o mesmo resto na divisão por $n$, teríamos dois números distintos $1 \le x,y \le n$ deixando o mesmo resto por $n$, o que é claramente impossível. Agora observe o seguinte: Se $a_i, a_j$ são elementos distintos de $A$, então

$aa_i \not\equiv aa_j ( \text{mod} n )$

De fato, como $n$ é primo com $a$ então

$n|aa_i-aa_j \Rightarrow n|a_i-a_j$

contradição com o nosso resultado anterior. Para finalizar, vamos olhar os restos que $aa_1, aa_2,..., aa_{\varphi (n)}$ deixam por $n$. Como vimos, todos esses restos são distintos. Além disso, podemos concluir que, como

$mdc(n,a)=mdc(n,a_i)=1$

para cada $i=1,2,...,\varphi (n)$, cada um dos restos que esses números deixam são relativamente primos com $n$. Mas vamos nos lembrar que, por definição, existem exatamente $\varphi (n)$ restos que são primos com $n$, que são exatamente os restos que aparecem em $A$. A conclusão é que o conjunto dos restos de $aa_1, aa_2,...aa_{\varphi (n}$ por $n$ é exatamente o conjunto $A$. Note que a palavra "conjunto" é bem importante, pois a ordem que esses restos desaparecem é desconhecida para nós, sabemos apenas qual é o seu conjunto. Como sabemos que o produto dos restos é o resto dos produtos, então temos que o resto que $a1a_2...a_{\varphi (n)}$ deixa por $n$ é o mesmo de $aa_1, aa_2,... aa_{\varphi (n)} = a^{\varphi (n)} a_1a_2...a_{\varphi (n)}$. Em outras palavras,

$a^{\varphi (n)} a_1a_2...a_{\varphi (n)} \equiv a_1a_2...a_{\varphi (n)} (\text{mod} n)$

mas como $mdc(a_1a_2...a_{\varphi (n)}, n)=1$, podemos "cancelar" o produto $a_1 a_2 ... a_{\varphi (n)}$ e obter

$a^{\varphi (n)} \equiv 1 (\text{mod} n )$

Como desejado.