Angel "Java" Lopez en Blog

Publicado el 3 de Julio, 2010, 11:53

Presentemos una notación que creó Gauss. Escribimos

Se dice, a es congruente con b, módulo m, cuando la división (a-b)/m da resultado entero. Es fácil demostrar, entonces que:

Es decir, se pueden simplificar los factores primos con m.

Lo bueno de la notación de Gauss, es que sugiere resolver ecuaciones, donde se desconoce una letra, como en:

Surge la pregunta, ¿para qué valores de a,b,m hay solución x? Esto es lo importante de una notación: su facilidad de uso y lo que sugiere usar. Exploremos alguna de las cualidades de esta ecuación.
Sea m,  se dice que m números no congruentes dos a dos módulo m, se llaman un sistema de restos completo módulo m. Para fijar ideas, si m=7, un sistema de restos completo es:

{0,1,2,3,4,5,6}

Si multiplicamos cada uno de esos elementos por un número a primo con m, por ejemplo, a=5, queda:

{0,5,10,15,20,25,30}

Son todos no congruentes dos a dos. Para verlo mejor, tomemos sus restos módulo m:

{0,5,3,1,6,3,2}

Notablemente, son los mismos de los que partimos. Eso es así para todo conjunto de restos completos B: si a es primo con m, aB es también un conjunto de restos completo. No hace falta que m sea primo. Para verlo, tomemos m=6, partimos desde

{0,1,2,3,4,5}

Multiplicamos por a=5

{0,5,10,15,20,25}

Tomamos resto módulo m=6

{0,5,4,3,2,1}

De nuevo tenemos un conjunto de restos completo módulo 6. Esto es asi porque los a*b que obtenemos son no congruentes, pues si

Por ser a primo con m, podríamos simplificar ambos lados por a, quedando

Contra lo supuesto de los elementos de B, que eran no congruentes dos a dos. Toda esta disquisición nos sirve para ver que la ecuación que habíamos planteado:

Tiene solución x si a es primo con m. Basta con hacer recorrer x por un sistema de restos completos, que obtendremos ax que recorrerá un sistema de restos completos, uno de sus valores TIENE que ser congruente con cualquier b que nos planteen.

Sigamos con el tema de restos. Primero, recordemos que para m natural, hay

números primos con m, entre 1 y m. Llamamos conjunto reducido de restos a φ(m) números no congruentes dos a dos, y que no son divisibles por m. Ejemplo, para m = 7, un conjunto reducido de restos es:

{1,2,3,4,5,6}

También podría ser

{8,9,3,4,5,20}

Como antes, si tenemos un conjunto reducido de restos módulo m:

Y los multiplicamos por a, donde (a, m) = 1 (primos entre sí):

Obtenemos de nuevo un conjunto reducido de restos módulo m. Veamos, son todos distintos, porque los bi eran distintos. Son entonces φ(m) números distintos. Como en el caso de sistema de restos completos, podemos probar que son no congruentes dos a dos. También cada uno de esos elementos es primo con m, pues tanto a como los b son primos con m. En conclusión, si B es conjunto reducidos de restos mod m, y (a, m) = 1, entonces aB también es un conjunto reducido de restos mod m.

Este pequeño resultado, nos permite demostrar un teorema de Euler, que demostró al tratar de demostrar un resultado de Fermat, llamado el pequeño teorema de Fermat, que dice:

Para p primo. El resultado de Euler, más general, es

Para demostrarlo, primero hay que ver que los elementos de un conjunto B reducido de restos, recorre los mismos φ(m)  restos módulo m, que el conjunto aB. Visto esto, queda que multiplicar los elementos de B da algo congruente a multiplicar los elementos de aB:

Entonces, reagrupando:

Como los bi son primos con n, se pueden ir simplificando uno a uno, quedando:

Como queríamos demostrar.

Nos leemos!

Angel "Java" Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez