Angel "Java" Lopez en Blog

Publicado el 4 de Mayo, 2011, 11:40

Ya estuve escribiendo que los enteros forman anillo. Es más, forman anillo conmutativo. Veamos hoy que en este anillo en particular podemos encontrar lo que los matemáticos llaman el máximo común divisor de dos elementos. Ya traté el tema el año pasado en Un pequeño ejercicio de teoría de números, donde presenté la demostración de abajo, pero esta vez he escrito más sobre anillos y quisiera usar este post como introducción a otros temas más generales.

Comentaba en ese post que hay demostraciones que se basan en la aplicación repetida del algoritmo de Euclides. No lo voy a usar de esa forma en esta demostración, sino sólo una vez. Pero quiero anotar: están los anillos euclídeos, que tengo que comentar en futuro post. Es interesante notar que no todos los anillos tendrán un algoritmo como el de Euclides. También tengo que mostrar (y demostrar) la factorización única en enteros, y mostrar anillos donde esa factorización única no existe (lo que nos llevará por primera vez cerca del último teorema de Fermat). Pero vayamos hoy por la demostración de m.c.d. (máximo común divisor) en el anillo de enteros.

Sean dos elementos del anillo de enteros, a y b. Escribimos:

(a, b)

para denotar al máximo común divisor de a y de b, un elemento entero c que cumpla con dos puntos:

- c divide al elemento a, y c divide al elemento b
- Si d divide al elemento a, y al elemento b, entonces d divide también a c

Claro, en anillos no hay "división" como operación binaria definida. Decimos que "m divide a n" en un anillo (conmutativo para simplificar) si existe  elemento k, tal que

mk = n

Para encontrar el m.c.d., tenemos que encontrar un elemento que cumpla con los dos puntos de arriba. Dados a y b, formemos todos los números de la forma:

xa + yb

donde x, y recorren todos los enteros. Es un conjunto no vacío, y tiene números naturales. Ahora, aplico una propiedad de los naturales que tendríamos que demostrar, pero hoy la damos por probada. Todo conjunto de números naturales tiene un mínimo. Es decir para un conjunto L de naturales, existe un número natural que es menor o igual que todos los elementos del conjunto, Y ADEMAS, es elemento del conjunto L (veremos más adelante que esa propiedad no se cumpe con los racionales). También me anoto: un conjunto L de naturales ACOTADO tiene un máximo. Pero no vamos a usar esto último en la demo.

Sea

ra + sb = t

ese número mínimo. Demostremos que es divisor de todos los xa + yb. Pues si hubiera uno que no lo fuera, entonces sería de la forma

e = fa + gb  = tn + k

con k como resto. Acá es donde aplicamos Euclides: si es así, siempre podemos encontrar k < t (si me extendiera un poco más, podemos deducir la existencia de resto 0<=k<t apelando a la existencia de mínimo entre los naturales de la forma e-xt, x recorriendo todos los enteros). Estamos aplicando algo que tenemos que demostrar, hoy lo tomamos por dado. Quiero destacar, entonces, que estamos aplicado dos propiedades (resto de Euclides, existencia de mínimo en naturales), que tenemos que demostrar. Y vamos a ver que no todos los anillos tienen estas propiedades. Vean que estamos usando un "<" que no sabemos si va existir en otros anillos (¿cómo pondremos "<" en un anillo de polinomios? ¿y en anillos más complicados?).

Bien, volvamos a la demostración. Si existiera ese número e, entonces, k sería:

k = fa + gb - tn = fa + gb - ra - sb = (f-r)a + (g-s)b

y pertenecería al conjunto que formamos, SIENDO MENOR que t, contra lo supuesto: t era nuestro mínimo natural elemento de ese conjunto. Contradicción. Entonces, nuestra suposición de existenia de e no divisble por t, es falsa. (Vean cómo encontramos en este paso la demostración por absurdo: para probar P, suponemos no P, y si llegamos a contradicción, damos P por probada. Todo esto descansa en una gran suposición: la no generación de contradicciones en nuestro sistema de lógica matemática, gran tema para varios posts ;-)

Queda demostrado que t divide a todos los elementos xa+yb, donde x, y recorren los enteros. Los elementos a y b están en ese conjunto:

a = 1a + 0b
b = 0a + 1b

entonces, t divide a ambos elementos. Ese esa la primera propiedad de (a, b). Vayamos por la segunda. Si el elemento d divide a los elementos a y b, entonces d divide a t, pues divide a ra y a sb,  y dividirá a su suma:

ra + sb = t

Queda demostrada la segunda propiedad esperada de m.c.d. Tenemos forma entonces de demostrar su existencia, necesaria, dados dos a y b cualesquiera del anillo de enteros.

Ahora que ya escribí sobre anillos, puedo agregar:

- Los xa (múltiplos de a) y los yb (múltiples de b) forman lo que se llama un ideal: una especie de "subanillo" sin unidad, cerrado para la suma entre sus elementos y cerrado para  la multiplicación con los elementos de todo el anillo
- Esos ideales se escriben (a) y (b), diciendo que son generados por a, y por b.
- Los elementos xa + ya definen OTRO ideal, que se llama la suma de los iniciales, (a) + (b)
- La gran propiedad que hemos demostrado, es que ese ideal (a) + (b) es igual a un (t). Uno podría esperar que combinar dos "cosas" cada una generada por un elemento distinto, daría una "cosa" con dos generadores. Pero nones. En los enteros, gracias a las dos propiedades que encontramos (resto de Euclides, mínimo en naturales, esta última también se usa en la demostración de la primera propiedad), tenemos este resultado: (a)+(b) es el idea generado por el m.c.d de a y b.

Temas pendientes:

- Ideales en anillos
- Bases para ideales (qué elementos iniciales generar un ideal, si es que existen)
- Demostrar que en el anillo de enteros todos los ideales son generados por un solo elemento, es decir, son de la forma (a) para algún a.
- Factorización única en anillos

Vean cómo, un tema sencillo, el buscar el m.c.d. en enteros, nos abre las puertas a muchos temas en anillos conmutativos generales (también hay ideales en no conmutativos, pero los encontraremos raramente).

Nos leemos!

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