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.