Archivo de la etiqueta: divisor

Álgebra Superior II: El algoritmo de Euclides

Por Leonardo Ignacio Martínez Sandoval

Introducción

En entradas anteriores estudiamos los conceptos de máximo común divisor y de mínimo común múltiplo. Ahora nos enfocaremos en un aspecto un poco más práctico sobre el máximo común divisor que dejamos pendiente: ¿cómo lo calculamos? Para ello hablaremos de un procedimiento conocido como el algoritmo de Euclides, el cual afirma que afirma que podemos aplicar iteradas veces el algoritmo de la división en ciertos números específicos, comenzando con dos enteros a y b para encontrar su máximo común divisor de dos enteros positivos a y b.

Lo primero que haremos es explicar el procedimiento mediante el cual podemos encontrar el máximo común divisor de dos números aplicando repetidamente el algoritmo de la división. En la siguiente sección daremos la demostración de por qué funciona este procedimiento. Hacia el final de la entrada también veremos que este mismo procedimiento nos permite también escribir al máximo común divisor de dos enteros a y b como combinación lineal de ellos, es decir, de la forma ra+sb con r y s números enteros.

El procedimiento del algoritmo de Euclides

Sean a,b cualesquiera enteros positivos, con ab y a>b. Por el algoritmo de la división, sabemos que siempre existen q,rZ tales que podemos escribir a=bq+r,con0r<b.

Luego, como b y r son enteros, también existen q1 y r1 tales que b=rq1+r1,con0r1<r.

Y como r y r1 son enteros, existen q2 y r2Z+ tales que r=r1q2+r2,con0r2<r1.

Se puede continuar así sucesivamente. Pero este procedimiento debe de terminar, pues tenemos b>r>r1>r2>0, de modo que debe existir una i tal que ri=0. De esta forma, en el penúltimo paso tendremos que existen qi1 y ri1 enteros tales que ri3=ri2qi1+ri1,con0ri1<ri2.

Y en el último paso tendríamos qiZ+ y ri=0 tales que
ri2=ri1qi+0,con0=ri<ri1.

Lo que nos dice el algoritmo de Euclides es que el último residuo no cero, en este caso ri1 es el máximo común divisor de a y b.

Este procedimiento es particularmente útil cuando a y b son números tan grandes, tanto que determinar el máximo común divisor de ellos no sea inmediato. Aunque se comience con números muy grandes, el algoritmo de Euclides encuentra el MCD de manera rápida.

Ejemplo del algoritmo de Euclides

A continuación veremos el algoritmo de Euclides en acción.

Problema. Encuentra el máximo común divisor de 3456 y 6524.

Solución. Observamos que 6524>3456. Así, 6524=34561+3068,03068<3456.
Aplicando nuevamente el algoritmo de la división, obtenemos
3456=30681+388,0388<3068.
Aplicando una vez más el algoritmo de la división, se tiene
3068=3887+352,0352<388.
Siguiendo este procedimiento,
388=3521+36,036<352.
352=369+28,028<36.
36=281+8,08<28.
28=83+4,04<8.
8=42+0.

Como el último residuo no cero es 4, entonces (6524,3456)=4.

Observación. Aunque el algoritmo de Euclides requiere que los números a y b sean positivos, cuando ocurre el caso de que uno de ellos o los dos fueran negativos, no hay un gran obstáculo. Basta sacar el valor absoluto de ambos números al inicio, ya que los divisores de un número negativo son los mismos que los de su valor absoluto.

Veamos un ejemplo que usa esta observación.

Ejemplo. Obtén el máximo común divisor de 100 y 45.

Solución. Como uno de los números es negativo, antes que nada sacamos valores absolutos: |100|=100 y |45|=45. Le aplicamos el algoritmo de Euclides a estos números:
100=452+10,010<45.
45=104+5,05<10.
10=52+0.

Notemos que el último residuo no cero es 5. Por lo tanto, (100,45)=5.

Demostración de la validez del algoritmo de Euclides

Ahora, veamos la demostración de que el algoritmo de Euclides funciona. El resultado clave para demostrarlo es la siguiente proposición.

Proposición. Sean a,bZ+, tales que a=bq+r. Entonces (a,b)=(b,r).

Demostración. Sean a,bZ+. Sea d=(a,b) el máximo común divisor de a y b, y sea f=(b,r) el máximo común divisor de b y r.

Tenemos que da. Además, db, por lo que dbq. Así, dabq=r. De este modo, d es un divisor común de b y de r, de modo que df.

Por otro lado, fb, de donde fbq. Además, fr. De este modo, fbq+r=a. Concluimos entonces que f es divisor común de a y b. Pero entonces fd.

Por propiedades de divisibilidad, tenemos entonces que |f|=|d|, pero como ambos son números no negativos concluimos entonces que f=d, como queríamos.

◻

Ya con este resultado demostrado, enunciemos formalmente el algoritmo de Euclides y demos su demostración.

Teorema. Empecemos tomando dos enteros positivos a y b, con ab. Usando el algoritmo de la división, definimos sucesivamente los números r0,r1,,ri y q0,q1,,qi de manera que se cumpla

b=aq0+r0a=r0q1+r1

con 0r0<a, y 0r1<r0 y para j=2,,i que se cumpla

rj2=rj1qj+rj,

con 0rj<rj1.

Como ba>r0>r1>r2>>ri, entonces podemos suponer que ri=0. Entonces (a,b)=ri1.

Demostración. Por la proposición anterior, tenemos que (a,b)=(b,r0). También por esa misma proposición, tenemos que (b,r0)=(r0,r1). Y, de hecho, aplicando repetidamente la proposición tenemos que:

(r0,r1)=(r1,r2)==(ri1,ri)=(ri1,0)=ri1.

La penúltima igualdad es porque ri=0 y la última porque (n,0)=n para cualquier entero positivo n.

◻

Máximo común divisor como combinación lineal entera

Una última consecuencia del algoritmo de Euclides es que nos ayuda a poner al máximo común divisor de dos números a y b como combinación lineal entera de ellos dos.

Una forma práctica de encontrar la combinación lineal correspondiente es mediante el siguiente procedimiento. Tomaremos como ejemplo el algoritmo de Euclides que ya habíamos hecho para encontrar (6524,3456).

6524=34561+3068,03068<3456.
3456=30681+388,0388<3068.
3068=3887+352,0352<388.
388=3521+36,036<352.
352=369+28,028<36.
36=281+8,08<28.
28=83+4,04<8.
8=42+0.

Lo que haremos es la siguiente tabla, en donde en la columna izquierda ponemos todos los residuos que vamos encontrando. Además, completaremos la primera fila con 1,0 y la segunda con 0,1.

652410
345601
3068
388
352
36
28
8
4
Ejemplo de cómo poner al MCD como combinación lineal entera.

Vamos a ir llenando la tabla con lo que ya sabemos del algoritmo de Euclides. Por el algoritmo de Euclides, sabemos que 3456 cabe 1 vez en 6524. Por esta razón, restamos 1 vez la segunda fila de la primera, para obtener 10=1 y 01=1. Estos son los números que van en la fila 3, columnas 2 y 3:

652410
345601
306811
388
352
36
28
8
4
Ejemplo de cómo poner al MCD como combinación lineal entera.

De nuevo, 3068 cabe una vez en 3456, así que de nuevo restamos una vez el tercer renglón del segundo. Nos queda 01=1 y 1(1)=2 para las nuevas entradas:

652410
345601
306811
38812
352
36
28
8
4
Ejemplo de cómo poner al MCD como combinación lineal entera.

Ahora cambia un poco, pues 388 ya sabemos que cabe 7 veces en 3068 (por lo que hicimos del algoritmo de Euclides). Así, para la nueva fila restamos siete veces la cuarta fila de la tercera, para obtener como nuevos números 17(1)=8 y 17(2)=15. La tabla queda así:

652410
345601
306811
38812
352815
36
28
8
4
Ejemplo de cómo poner al MCD como combinación lineal entera.

Siguiendo este procedimiento repetidamente, llegamos a la siguiente tabla:

652410
345601
306811
38812
352815
36917
2889168
898185
4383723
Ejemplo de cómo poner al MCD como combinación lineal entera.

Los últimos dos números que pusimos en la tabla nos dan la respuesta de cómo poner a 4 como combinación lineal entera de 6524 y de 3456:

4=38365247233456.

Verifica que en efecto las cuentas son correctas, y que esta expresión final es válida.

¿Cómo se demuestra que este procedimiento siempre funciona? Se puede mostrar inductivamente que, de hecho, para cada uno de los renglones con entradas a,b,c se cumple que a=6524b+3456c. Esto queda como uno de los problemas de tarea moral.

Más adelante…

Esta entrada termina nuestra exploración introductoria al mundo de la aritmética de los números enteros. Sin embargo, todavía hay otros lugares a los que nos llevará el algoritmo de la división. Hasta ahora hemos discutido mucho el caso de la divisibilidad, es decir, cuando el residuo de la división de un número entre otro es igual a cero. Pero también podemos encontrar estructuras matemáticas muy ricas si estudiamos al resto de los posibles residuos. A partir de la siguiente entrada hablaremos del anillo de enteros módulo n, lo cual nos ayudará a formalizar estas ideas.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Usa el algoritmo de Euclides para encontrar el máximo común divisor de las siguientes parejas de números, y para escribirlo como combinación lineal entera de ellos.
    1. 15 y 35
    2. 18 y 92
    3. 201 y 153
    4. 328 y 528
  2. ¿Cómo usarías el algoritmo de Euclides para encontrar el máximo común divisor de los números 91, 105 y 119? Es decir, debes encontrar el mayor entero d que divida a estos tres números de manera simultánea.
  3. Hay otra forma de encontrar el máximo común divisor de dos números si conocemos su factorización en números primos. Imagina que tenemos dos números n y m y que, conjuntamente, usan los números primos distintos p1,p2,,pk en su factorización en primos (quizás con exponente cero). Esto nos permite escribirlos como:
    m=p1α1p2α2pkαkn=p1β1p2β2pkβk .
    1. Demuestra que la máxima potencia de p1 que divide tanto a m como a n es p1min(α1,β1).
    2. Demuestra que el máximo común divisor de m y n es p1min(α1,β1)p2min(α2,β2)pkmin(αk,βk).
  4. Demuestra un resultado análogo al del inciso anterior para el mínimo común múltiplo y usa ambos resultados para dar otra demostración de que (m,n)[m,n]=mn.
  5. Verifica que, en efecto, el método explicado en la entrada ayuda a escribir al máximo común divisor de dos enteros como combinación lineal de ellos.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Álgebra Superior II: Teorema fundamental de la aritmética e infinidad de números primos

Por Ana Ofelia Negrete Fernández

Introducción

En la entrada anterior comenzamos a hablar de los números primos. Lo que ahora veremos es que, en un sentido muy preciso, los números primos son los bloques con los cuales se construyen todos los demás enteros. El enunciado preciso estará dado por el teorema fundamental de la aritmética.

A grandes rasgos, el teorema fundamental de la aritmética afirma que todo entero se puede escribir como producto de primos, quizás algunos repetidos. Nos referimos a situaciones del tipo
8=222=23,13=131,152=2319,etc.

Otro resultado que demostraremos en esta entrada es que hay una infinidad de primos. Euclides fue una de las primeras personas de quienes nos queda registro que lo notó. Veremos una demostración similar a la que él dió.

El teorema fundamental de la aritmética

El teorema fundamental de la aritmética dice que cualquier número entero es producto de números primos. Pero, más aún, nos dice que este producto es único, bajo ciertas condiciones que le ponemos a la representación. Para simplificar la presentación, estudiaremos primero lo que dice el enunciado para enteros positivos.

Teorema. Sea n un entero positivo. Entonces, existe un único entero k y únicos números primos p1p2p3pk tales que n=p1p2pk.

Por ejemplo, consideremos el número 1060. Notemos que en efecto se puede escribir como producto de primos de la siguiente manera: 1060=22553. El teorema fundamental de la aritmética nos dice que esta es la única manera en la que podemos ponerlo como producto de primos. Si lo piensas un poco, no es totalmente obvio. ¿Qué impide que, por ejemplo, no pase que 1060 tenga otra posible representación en donde el 5 aparezca más veces, o el 2 menos veces? Es lo que debemos estudiar.

Demostración de la existencia

Vamos a partir la demostración del teorema fundamental de la aritmética en dos partes. Primero veremos la existencia, y después la unicidad. Así, nos enfocaremos primero en ver que cualquier entero positivo tiene una factorización en números primos.

La demostración será por inducción fuerte. Si n=1, la factorización es la factorización vacía, en donde k=0, y como no estamos multiplicando nada obtenemos 1. Si n=2, entonces la factorización es precisamente 2=2, pues 2 es un número primo. Supongamos que el resultado es cierto hasta antes de cierto número fijo n y veamos qué pasa con n. Si n es un número primo, entonces n=n ya es una factorización como las que buscamos. Si n no es un número primo, entonces lo podemos factorizar como n=ab, en donde a y b son enteros positivos distintos de 1. Por ello, cada uno de a y b son menores que n y por hipótesis inductiva tienen una factorización en primos, digamos
a=q1q2qlb=r1r2rm.

Así, renombrando q1,,ql,r1,,rm como p1pk (donde k=l+m) para que queden en orden no decreciente obtenemos la factorización n=p1p2pk buscada. Esto termina la prueba de la primera parte.

Demostración de la unicidad

Veamos ahora que las factorizaciones en primos son únicas. Una vez más, procedemos por inducción fuerte. El resultado claramente es cierto para n=1 y n=2. Supongamos que el resultado es cierto hasta antes de cierto entero n dado y supongamos que tenemos dos factorizaciones para n:

n=p1p2pkn=q1q2ql.

Notemos que pk es un divisor de n, así que debe dividir a q1ql. Por una propiedad de divisibilidad que vimos en la entrada pasada, debe suceder que o bien pk divide a ql, o bien que divide a q1ql1. Si pasa lo segundo, debe dividir o bien a ql1, o bien a q1ql2. Y así sucesivamente, de modo que pk debe dividir a alguno de los qi. Pero como pk y qi son primos, debe suceder entonces que pk=qi. Tras cancelar este término en ambas expresiones de n, llegamos a que:

p1p2pk1=q1qi1qiql,

pero esto es una igualdad de factorizaciones en primos para un número menor estricto a n. Por hipótesis inductiva, ambas factorizaciones deben de ser la misma. Así, ambas factorizaciones de n son la misma, pues se obtienen a partir de estas multiplicando por el número pk=qi.

◻

Otra forma de escribir el teorema fundamental de la aritmética

Hay otra manera de escribir el teorema fundamental de la aritmética, en donde los primos iguales se agrupan en un mismo término, y se coloca la potencia correspondiente.

Teorema. Sea n un entero positivo. Existe un único entero no negativo k, únicos primos p1pk y únicos exponentes α1,,αk tales que:

n=p1α1p2α2pkαk.

En realidad esta segunda versión del teorema se deduce de manera inmediata de la anterior.

Ejemplo. Consideremos el número 36. El 2 lo divide, así que 36=182. Luego, el 3 divide al 18, de manera que 36=362. Finalmente, notamos que 6=23, de donde 36=3232. Para obtener la «forma estándar» de la factorización, agrupamos los primos iguales, les ponenmos el orden correspondiente y escribimos en orden creciente de primos. Así, la factorización de 36 quedaría 36=2232.

El conjunto de primos es infinito

En esta sección queremos demostrar otro resultado importante sobre el conjunto de los números primos.

Teorema. El conjunto de números primos es infinito.

Para dar la demostración, usaremos el método de demostración por contradicción, es decir, partiremos de que el conjunto de primos no es finito y, eventualmente se disparatará el asunto.

Este en efecto parece ser el método más conveniente. Sería difícil usar inducción dado que, si bien el conjunto de primos puede indexarse por p1,p2,p3,, no es fácil determinar cuál es el primo que sigue en la lista. O bien, dado un entero n, no es fácil determinar si n+1 será o no un número primo. Resultaría igualmente difícil intentar la demostración por algún otro método directo.

La idea que usaremos es la siguiente. Si hay finitos primos, digamos k, significa que se puede crear una lista finita con ellos: p1,p2,,pk. Veremos que siempre debe existir un primo distinto de los de la lista, lo que llevará a una contradicción con la hipótesis de que sólo existían k primos.

Veamos primero unos casos particulares del argumento que usaremos. Supongamos que sólo existieran 2 primos, el 2 y el 3. Consideremos el número z=23+1. De acuerdo al teorema fundamental de la aritmética, este número o bien es primo, o bien debe tener un divisor primo p. No puede ser primo, pues dijimos que los únicos primos eran 2 y 3. No puede ser divisible entre 2 pues deja residuo 1 al hacer la división. Tampoco puede ser divisible entre 3 pues también deja residuo 1 al hacer la división. Así, debe haber otro primo que no sea 2 y 3 y que divida a este número. Esto contradice que sólo existieran 2 primos.

Veamos otro ejemplo. Supongamos que hay únicamente 4 primos: 2,3,5,7. Consideremos el número 2357+1=211. Si dividimos este número entre 2, nos da 211=1052+1, así que 2211. Si lo dividimos entre 3, nos da 211=703+1, así que 3211. De manera similar, se puede ver que las divisiones entre 5 y 7 también dejan residuo 1, así que 5211 y 7211.

Por el teorema fundamental de la aritmética, debe haber algún primo que divida a 211. Pero estamos suponiendo que los únicos primos que existen son 2,3,5,7 y acabamos de ver que ninguno de estos funciona. ¡Esto es una contradicción! Lo mismo ocurrirá sin importar la cantidad de primos p1,p2,,pk inicial. El problema no es cuántos son exactamente, sino la suposición de que son una cantidad finita.

Demostración. Supongamos, para buscar una contradicción, que el conjunto de números primos es finito y que consiste de exactamente los k números primos p1,p2,,pk. Consideremos el número p1p2pk+1.

El anterior número no es divisible por ninguno de los primos p1,p2,,pk, pues precisamente al hacer la división el residuo que queda es igual a 1.

Por el teorema fundamental de la aritmética, p1p2pk+1 debe tener entonces un divisor primo p diferente de p1,p2,,pk. Esto es una contradicción, pues supusimos que sólo existían los primos p1,,pk.

◻

Más adelante…

Con los dos teoremas de esta entrada hemos profundizando un poco más en por qué los números primos son interesantes e importantes. La exploración de los números primos en este curso no irá mucho más lejos, pues pronto comenzaremos a tratar otros temas de aritmética modular. Sin embargo, te dejamos algunos pocos párrafos más sobre los números primos.

Los números primos siguen siendo interesantes para los matemáticos hoy en día; primero por la irregularidad con que van apareciendo en la recta numérica y porque hay muchas cosas que aún no se sabe acerca de su raro comportamiento. Por ejemplo, se conjetura que hay infinitos «primos gemelos», es decir, se cree que siempre es posible encontrar dos primos a y b que estén distanciados en dos unidades; no importa qué tan alejados estén del cero. El 3 y el 5 son primos gemelos. También los son el 17 y el 19. Nadie sabe si esta conjetura es cierta o falsa.

Los números primos aparecen en patrones muy irregulares, pero sí es posible decir algunas cosas al respecto. Por ejemplo, después del 2 todo número primo p, es de la forma 4n+1 o de la forma 4n1 para alguna nN. Un resultado lindo en teoría de números es que para aquéllos primos que pertenecen a la primera categoría, que son los de la forma 4n+1, siempre existe su expresión como una suma de cuadrados: p=4n+1=m2+n2, n,mZ. Pero a los primos de la segunda categoría es imposible expresarlos como suma de cuadrados. Estos son dos de los muchos resultados que demostró Euler para números primos, y puedes ahondar en ello en un curso de teoría de números.

Los números primos también han encontrado aplicaciones en criptografía, pues es bien sabido que si se eligen dos primos p1 y p2 tales que al multiplicarlos se obtenga un número compuesto z de más de 100 dígitos, y si luego se establece que p1 y p2 sean la «clave» de mi mensaje cifrado pero yo únicamente doy a conocer el número compuesto z a otra persona, entonces a una computadora le resultaría imposible factorizar z en un corto lapso de tiempo. ¡Le tomaría años! De ahí que la contraseña secreta sería indescifrable.

Ahora, lo que se conoce como el «teorema fundamental de la aritmética» también tiene varias extensiones interesantes en otras áreas de las matemáticas. De hecho, en algunas estructuras la unicidad deja de ser cierta. Si combinamos a los números enteros con los números complejos (que veremos después), tenemos algunos ejemplos como 12=(1+11)(111) pero también 12=(2+8)(28).

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Encuentra la factorización en primos de cada uno de los siguientes números 100, 170, 2022, 5000 y 713.
  2. Encuentra el menor entero positivo k que haga que 775k sea un número cuadrado perfecto, es decir, de la forma n2 para algún entero n.
  3. Halla el número de divisores de 2360 y calcula la suma de todos ellos.
  4. ¿Cuál es el número entero de 1 a 100 que tiene la mayor cantidad posible de divisores?
  5. Demuestra que un entero tiene una cantidad impar de divisores si y sólo si es un número cuadrado.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Álgebra Superior II: Máximo común divisor

Por Ana Ofelia Negrete Fernández

Introducción

La entrada anterior fue un poco técnica y habló acerca de ideales en los números enteros. Podemos apoyarnos de los ideales para construir otras nociones conocidas de la teoría de números enteros. En esta entrada hablaremos de una de ellas: la de máximo común divisor.

Quizás recuerdes la idea general del máximo común divisor a partir de lo que aprendiste en la educación básica. Por ejemplo, si tenemos a los números 14 y 35,y queremos encontrar su máximo común divisor, lo que se hacía es escribir los divisores de ambos:

  • Divisores de 14: 1,2,7,14.
  • Divisores de 35: 1,5,7,35.

Ya teniendo ambas listas, se elige número más grande que estén en ambas: el 7.

Con lo que platicaremos en esta entrada vamos a recuperar esta misma noción, sin embargo lo haremos desde un punto de vista un poco más teórico, el cual nos permitirá entender más aspectos de divisibilidad de los máximos comunes divisores.

Definición de máximo común divisor

Recordemos, que en la entrada pasada vimos cómo encontrar al «ideal más pequeño» que tuviera a dos números a y b enteros dados.

Proposición. Si a y b son enteros, entonces:

  • El conjunto M={ra+sb:r,sZ} es un ideal de Z que tiene a a y a b.
  • Si I es un ideal de Z que tiene a a y a b, entonces MI.

Como M es el ideal más pequeño que tiene a a y a b, le llamamos el ideal generado por a y b, y lo escribimos como a,b.

Además, en la entrada anterior también vimos que cualquier ideal de Z forzosamente es de la forma kZ para algún entero no negativo k, es decir, que consiste justo de los múltiplos de algún entero no negativo k. Esto nos permite plantear la siguiente definición.

Definición. Si a y b son enteros, definimos a su máximo común divisor como el entero no negativo k tal que kZ=a,b. A este número k a veces se le denota por MCD(a,b), o bien simplemente (a,b).

Esta es una definición muy distinta de la que nos dan en la educación básica, sin embargo, pronto recuperaremos las propiedades familiares: veremos que en efecto es un divisor de a, es un divisor de b, y que de entre los divisores en común, es el más grande de ellos. Antes de pasar a las propiedades, veamos un ejemplo.

Ejemplo. Tomemos a los enteros 6 y 14. ¿Qué ideal I generan? Es decir, ¿quién es 6,8? Bueno, dicho ideal I debe tener a 6 y 14, así que por cerradura de la resta tiene también a 1468, y similarmente debe tener a 86=2. Pero recordemos que los ideales también son cerrados bajo producto por cualquier entero, así que al estar 2 en I, debe pasar que todos los números pares están en I. Y en efecto, los números pares son un ideal de Z que tienen a 6 y 14. Con esto acabamos de demostrar que 6,14=2Z. De este modo, por definición, el máximo común divisor de 6 y 14 es igual a 2.

Propiedades del máximo común divisor

En esta sección veremos dos propiedades muy importantes del máximo común divisor. Por un lado, veremos que siempre se puede escribir «como combinación» de los números originales, en un sentido muy específico. Por otro lado, recuperaremos las «propiedades usuales» que queremos que se cumplan por lo que aprendimos en educación básica.

Proposición. Sean a y b números enteros. Entonces, existen enteros r y s tales que (a,b)=ra+sb.

Demostración. Por definición, (a,b) es el entero tal que a,b=(a,b)Z, en particular, (a,b) está en a,b. Pero también ya sabemos que a,b={ra+sb:r,sZ}. Como (a,b) está en a,b, entonces se puede escribir de la forma de los elementos del conjunto de la derecha también, es decir, existen enteros r y s tales que (a,b)=ra+sb.

◻

Como estamos poniendo a (a,b) de la forma ra+sb, en donde los coeficientes de a y b son los números enteros r y s, decimos que (a,b) se puede escribir como una combinación lineal entera de a y b. La proposición anterior nos demuestra la existencia de dicha combinación lineal, sin embargo no nos dice exactamente cómo encontrarla. Más adelante veremos el algoritmo de Euclides, el cual nos da una forma práctica de encontrar al máximo común divisor de dos números como combinación lineal de ellos.

Veamos ahora el resultado que nos dice que, en efecto, el máximo común divisor divide a cada número, y que es «el más grande» que hace esto.

Proposición. Sean a y b números enteros. Entonces, se cumple lo siguiente:

  • (a,b)|a y (a,b)|b.
  • Si d es algún otro número tal que d|a y d|b, entonces d|(a,b).

Demostración. Notemos que aa,b, y que por definición a,b=(a,b)Z. De este modo, a es múltiplo de (a,b). Análogamente, b es múltiplo de (a,b). Esto muestra el primer inciso.

Ahora supongamos que d es otro número tal que d|a y d|b. Por la proposición anterior, existen enteros r y s tales que (a,b)=ra+sb. Como d|a, entonces d|ra. Como d|b, entonces d|sb. Así, d|ra+sb=(a,b), como queríamos.

◻

La proposición anterior sí dice que el máximo común divisor divide a ambos, sin embargo no es totalmente directo por qué es el «máximo» en tamaño. La segunda parte habla más bien de una divisibilidad. Pero esto se traduce rápidamente a una desigualdad con la ayuda de las propiedades de la divisibilidad. Observa que si d es un número tal que d|a y d|b, entonces d|(a,b). Tenemos entonces que |d||(a,b)|. Pero (a,b) siempre es no negativo por definición, así que |d|(a,b). En resumen, tenemos el siguiente resultado.

Corolario. Si a y b son enteros y d es un entero tal que d|a y d|b, entonces |d|(a,b).

Números primos relativos (de máximo común divisor igual a uno)

Una situación muy especial en la teoría de los números ocurre cuando el máximo común divisor de dos números es igual a 1.

Definición. Decimos que dos números enteros a y b son primos relativos si su máximo común divisor es igual a 1. En símbolos, son primos relativos si (m,n)=1.

Por lo que hemos discutido hasta ahora, algunas de las consecuencias de que dos números a y b sean primos relativos son las siguientes:

  • Si d es un número que divide a a y a b, entonces |d|(a,b)=1, es decir, d=1 o d=1. De este modo, los únicos divisores que tienen en común son el 1 y el 1.
  • El ideal generado por a y b es 1Z=Z, es decir, consiste de todos los enteros.
  • Por esa misma razón, se tiene que {ra+sb:r,sZ}=Z, en otras palabras, cualquier entero es combinación lineal entera de a y de b.
  • En particular, el 1 es combinación lineal entera de a y de b, es decir, existen enteros r,s tales que ra+sb=1.

Estas consecuencias son prácticamente inmediatas de la definición, y es recomendable que intentes deducirlas por tu cuenta.

Veamos algunas otras propiedades que relacionan a los números primos relativos, con divisibilidad de algunas expresiones.

Proposición. Sean a,b,c números enteros . Si abc y (a,b)=1, entonces ac.

Demostración. Como a divide a bc, existe xZ tal que ax=bc. Como a y b son primos relativos, sabemos que existen enteros r y s tales que 1=ra+sb. Multipliquemos esta última igualdad por c. Tenemos entonces que:
c=rac+sbc=rac+sax=a(rc+sx).

De aquí obtenemos la divisibilidad ac que buscábamos.

◻

En la proposición anterior es crucial la hipótesis de que a y b sean primos relativos. Por ejemplo, 7|28=142, pero no pasa que 7|2. Es decir, usualmente si dividimos a un producto, no se cumple que dividamos a cualquiera de sus factores.

A continuación tenemos otro resultado con un estilo similar.

Proposición. Sean a,b,cZ. Si ac, bc y (a,b)=1, entonces abc.

Demostración. Ya que a,b son primos relativos, existen m,nZ tales que 1=am+bn. Multipliquemos dicha ecuación por c: c=cam+cbn.

Como ac y bc, existen q,rZ tales que aq=c y br=c. Sustituyendo esto en la ecuación anterior, obtenemos que: c=cam+cbn=bram+aqbn=ab(rm+qn).

Esta igualdad justo nos dice que abc, como queríamos.

◻

Intenta encontrar un contraejemplo cuando no se cumple la hipótesis de que a y b son números primos relativos.

Más adelante…

Dejaremos el estudio del máximo común divisor hasta aquí por el momento. En la siguiente entrada hablaremos de un concepto muy cercano: el de mínimo común múltiplo. Así como en el caso de esta entrada, introduciremos la noción a partir de un contexto de ideales, para luego ver ejemplos y algunas propiedades clave.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Demuestra todas las consecuencias de ser primos relativos de la lista enunciada en la entrada.
  2. Prueba que dos enteros consecutivos siempre son primos relativos. Usa esto para demostrar que siempre que se eligen 51 números distintos entre 1 y 100, forzosamente debes tener dos de ellos que sean primos relativos.
  3. Sea m un entero positivo. Demuestra que (a,b)=1 si y sólo si (am,bm)=1.
  4. De acuerdo a la entrada, al tomar dos números a y b podemos encontrar enteros r y s tales que (a,b)=ra+sb. Demuestra que siempre sucede que (r,s)=1.
  5. Encuentra el máximo común divisor de 91 y 70 e intenta escribirlo como combinación lineal entera de ellos.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»