Teorema de Euler y pequeño teorema de Fermat

RESUMEN. Demostramos el Teorema de Euler y el pequeño teorema de Fermat

1. Definición. Elijamos un número $a_i$ de cada clase de residuos módulo $m.$ Al conjunto $\{a_1,a_2,\ldots,a_m\}$ se le llama sistema completo de residuos módulo $m.$
2. Ejemplo. Los conjuntos $\{0,1,2,3,4\}$ y $\{4,-7,14,7\}$ son sistemas completos de residuos módulo $4.$
3. Lema.
   $(i)$ Para todo entero $n$ se verifica $(a,b)=(a-nb,b).$
   $(ii)$ Si $x\equiv y\;(\text{mód }m)$, entonces $(x,m)=(y,m)$.
   Demostración.
   $(i)$ Si $c$ es divisor de $a$ y de $b$, entonces $a=kc$ y $b=sc$ y por tanto $a-nb=kc-nsc$ $=(k-ns)c$, es decir $c$ es divisor de $a-nb$ y de $b$. Por otra parte, si $c$ es divisor de $a-nb$ y de $b$, entonces $a-nb=k_1c$ y $b=k_2c.$ Por tanto, $a=nb+k_1c=nk_2c+k_1c$ $=(nk_2+k_1)c$, es decir todo divisor de $a-nb$ y de $b$ es divisor de $a$ y de $b$. Concluimos pues que $(a,b)=(a-nb,b).$
   $(ii)$ Si $x\equiv y\;(\text{mód }m)$ entonces, $x=y+qm$ con $q$ entero. Ahora basta aplicar $(i).$ $\square$
4. Definición. Una clase residual $\bar{a}$ se dice que es relativamente prima con $m$, si $(a,m)=1.$
5. Nota. Por el lema 3, la definición no depende del representante elegido de la clase $\bar{a}.$
6. Definición. Supongamos que $\phi (m)$ denota el número de clases residuales que son relativamente primas con $m.$ A la función $\phi$ se la llama función $\phi$ de Euler. Cualquier conjunto $\{r_1,r_2,\ldots,r_{\phi (m)}\}$ de enteros elegidos de entre cada una de las clases residuales que son relativamente primas con $m$ se llama sistema reducido de residuos módulo $m.$
   Por supuesto, que $\phi(m)$ es el número de enteros del intervalo $[0,m-1]$ que son relativamente primos con con $m$ y tales números $\{x_1,x_2,\ldots,x_{\phi(m)}\}$ forman un sistema reducido de residuos módulo $m.$
7. Ejemplos.
   $1)$ Los enteros positivos menores que $9$ que son relativamente primos con $9$ son $1,2,4,5,7,8$, por tanto $\phi (m)=6$ y $\{1,2,4,5,7,8\}$ es un sistema reducido de residuos módulo $9.$
   $2)$ Si $p$ es primo, los números $1,2,\ldots, p-1$ son relativamente primos con $p$, por tanto $\{ 1,2,\ldots, p-1\}$ es un sistema reducido de residuos módulo $p.$
   $3)$ Sea $p$ primo y $k>0$ entero. Un entero $a$ es relativamente primo con $p^k$ si y sólo si $a$ no es divisible por $p.$ En consecuencia, en el intervalo $[0,p^{k}-1]$ hay exactamente $p^{k-1}$ enteros que no son relativamente primos con $p^k$ a saber: los enteros de la forma $np$ con $n=0,1,2,\ldots, p^{k-1}-1$, mientras que los restantes $p^k-p^{k-1}$ en el intervalo son relativamente primos con $p^k$, por tanto, $$ \phi(p^k)=p^k-p^{k-1}=p^k\left(1-\frac{1}{p}\right).$$
8. Teorema. Sea $(a,m)=1$, $\{r_1,r_2,\ldots,r_m\}$ un sistema completo de residuos y $\{s_1,s_2,\ldots,s_{\phi(m)}\}$ un sistema reducido de residuos. Entonces, $\{ar_1,ar_2,\ldots,ar_m\}$ es un sistema completo de residuos y $\{as_1,as_2,\ldots,s_{\phi(m)}\}$ es un sistema reducido de residuos.
   Demostración. Para demostrar que $\{ar_1,ar_2,\ldots,ar_m\}$ es un sistema completo de residuos, basta demostrar que $ar_i\not\equiv ar_j\;(\text{mód }m)$ si $i\ne j.$ Pero por el teorema $11,$ $(ii),$ de Congruencias y anillo de clases residuales, $ar_i\equiv ar_j\;(\text{mód }m)$ implica $r_i\equiv r_j\;(\text{mód }m)$, absurdo.
   Recordemos la propiedad: $(x,y)=(x,z)=1$ implica $(x,yz)=1.$ Dado que $(s_i,m)=1$ y $(a,m)=1$, tenemos que $(as_i,m)=1$ para todo $i=1,2,\ldots,\phi (m)$, es decir $as_1,as_2,\ldots,as_{\phi(m)}$ son $\phi (m)$ números pertenecientes a clases que son relativamente primas con $m,$ y por el mismo argumento anterior son distintas dos a dos. Esto demuestra que $\{as_1,as_2,\ldots,s_{\phi(m)}\}$ es un sistema reducido de residuos. $\square$
9. Teorema de Euler. Si $(a,m)=1$, entonces $$a^{\phi (m)}\equiv 1\;(\text{mód }m).$$ Demostración. Sea $\{s_1,s_2,\ldots,s_{\phi(m)}\}$ un sistema reducido de residuos módulo $m$. Por el teorema anterior, también $\{as_1,as_2,\ldots,s_{\phi(m)}\}$ es un sistema reducido de residuos. En consecuencia existe un único producto $as_i$ tal que $s_i\equiv as_i\;(\text{mód }m).$ Por el teorema $8$, $(2)$ de Congruencias y anillo de clases residuales, $$\prod_{i=1}^{\phi (m)}as_i\equiv \prod_{i=1}^{\phi (m)}s_i \;(\text{mód }m),$$ y por tanto $$a^{\phi (m)}\prod_{i=1}^{\phi (m)}s_i\equiv \prod_{i=1}^{\phi (m)}s_i \;(\text{mód }m).$$ Dado que $(s_i,m)=1$ para todo $i$ podemos aplicar el teorema $11,$ $(ii)$ de Congruencias y anillo de clases residuales repetidamente para cancelar los $s_i$, obteniendo $a^{\phi (m)}\equiv 1\;(\text{mód }m).$ $\quad\square$
10. Pequeño teorema de Fermat. Si $p$ es primo y $p\nmid a$, entonces $$a^{p-1}\equiv 1\;(\text{mód }p).$$ Demostración. Si $p\nmid a$, entonces $(a,p)=1$ y por el ejemplo $7,$ $2)$, $\phi(p)=p-1$. Por el teorema de Euler, $a^{p-1}\equiv 1\;(\text{mód }p).$ $\quad\square$