Con esta entrada comenzamos a tratar los temas de números enteros y su aritmética. Varios de los temas que se ven aquí se estudian a profundidad en un curso de Álgebra Superior, así que varios de los resultados los enunciaremos sin demostración. Lo que nos interesa es cómo se pueden utilizar los resultados principales de la teoría de números enteros para la resolución de problemas matemáticos.
Divisibilidad y máximo común divisor
Trabajaremos todo el tiempo con números enteros, a menos que digamos lo contrario.
Decimos que divide a
si
es un mútiplo de
, es decir, si existe un
tal que
. Lo escribimos en símbolos como
. También decimos que
es divisor de
.
Proposición 1. La relación de divisibilidad es reflexiva y transitiva, pero no es simétrica. Si y
, entonces
, es decir
o
.
Si tenemos varios números , el máximo común divisor es el mayor número que divide a todos. El mínimo común múltiplo es el menor entero positivo que es múltiplo de todos. Los denotamos respectivamente por
y
.
Proposición 2. Si divide a
y a
, entonces divide a cualquier combinación lineal entera
de ellos. En particular, si
divide a dos términos de la igualdad
, entonces divide al tercero.
Notemos que . Por la Proposición 2, un divisor de
y
será divisor de
, y uno de
y de
será divisor de
. De aquí sale que
Problema. Determina todas las funciones tales que cumplen las siguientes tres propiedades simultáneamente:
para todo entero positivo
.
para todo par de enteros positivos
y
.
para todo par de enteros positivos
y
.
Sugerencia pre-solución. Haz casos particulares que puedas obtener a partir de esas propiedades para conjeturar el valor de para todos
y
enteros positivos. Intenta probar tu conjetura por inducción fuerte.
Solución. Vamos a mostrar que para todo par de enteros positivos
y
. Vamos a probarlo por inducción sobre la suma
. Como
y
son enteros positivos, la menor suma que pueden tener es
y en este caso
implica
. Por la hipótesis 1, tenemos
, que coincide con
.
Supongamos que el resultado es cierto cuando para todo entero
y tomemos
y
enteros de suma
. Si
, entonces






El máximo común divisor y el mínimo común múltiplo de un número son especiales. No sólo son el divisor más grande y el múltiplo más chico, sino que además si hay otro divisor de todos los números (o múltiplo de todos los números), además se cumplen ciertas divisibilidades.
Proposición 3. Si tenemos otro número que sea divisor de
, entonces


Problema. Sean y
enteros positivos. Muestra que
Sugerencia pre-solución: Intenta resolver el problema antes de ver la solución. Para ello, necesitarás la Proposición 1 y la Proposición 3.
Solución. Para simplificar la notación, tomamos y
.
Como divide a
y
, existen enteros
y
tales que
y
. Notemos que
, así que
es un múltiplo de
y
, y por la Proposición 3, tenemos que
. Multiplicando por
esta divisibilidad, tenemos que
.
Como es múltiplo de
y de
, por la Proposición
es múltiplo de
, digamos
. Notemos que de aquí, tenemos
con
entero y
con
entero, de modo que
divide a
y a
. Como
es máximo común divisor, por la Proposición 3 tenemos que
. Multiplicando por
esta divisibilidad, tenemos que
, es decir,
.
Con esto logramos conseguir que y
. Por la Proposición
, tenemos que
, pero como
,
,
,
son positivos, entonces
.
Algoritmo de la división y algoritmo de Euclides
Tomemos y
enteros. Si intentamos expresar a
como múltiplo de
, puede que no lo logremos. Pero podemos acercarnos lo más posible y dejar un residuo «pequeño». Esto es lo que dice el algoritmo de la división.
Teorema 1 (Algoritmo de la división). Para enteros y
, existen únicos enteros
y
tales que
y
.
Consideremos la igualdad en el algoritmo de la división y apliquemos la Proposición 2. Si
divide a
y
, entonces divide a
. Si
divide a
y a
, entonces divide a
. Así,
, en donde
y
ahora son números más chicos que
y
. De este modo, podemos hacer varias veces el algoritmo de la división para obtener igualdades
de las que obtenemos
En las igualdades llegamos a un residuo


En particular, obtenemos
Teorema 2 (Algoritmo de Euclides). Podemos obtener el máximo común divisor de y
aplicando el algoritmo de la división a
y
, a
y el residuo obtenido y luego repetidamente a los residuos que se van obteniendo. El último residuo no cero es
.
Hay todavía una conclusión adicional muy importante que podemos obtener a partir del algoritmo de Euclides.
Problema. Sean enteros. Sean
y los
los números obtenidos en el algoritmo de Euclides. Definimos recursivamente una sucesión de
vectores en
como sigue:
Sean y
. Muestra que para
se tiene que
, en donde:
Sugerencia pre-solución. Intenta resolver el problema haciendo inducción sobre el índice. Los casos son inmediatos.
Solución. Procedemos por inducción fuerte en el subíndice . Para
, el resultado es cierto pues
,
,
y
. Supongamos el resultado cierto para los índices
para algún
. Tomemos el índice
.
Estudiemos primero la entrada . Por definición de la recursión e hipótesis inductiva
que es lo que queríamos mostrar para la entrada . Para la segunda parte, de nuevo usando la recursión e hipótesis inductiva, tenemos que
Con esto terminamos la inducción.
El problema anterior nos dice que, en particular, . Esta conclusión es muy importante y la enunciamos como teorema.
Teorema 3. El máximo común divisor de enteros y
se puede escribir como combinación lineal entera de
y
, es decir, existen enteros
y
tales que
.
Veamos un ejemplo concreto de cómo podemos usar el problema para encontrar la combinación lineal que da el máximo común.
Problema. Expresa al máximo común divisor de y
como combinación lineal entera de estos números.
Solución. Hacemos la siguiente tabla, en donde ponemos a los vectores del problema como vectores columna (en los renglones ). En el primer rengón vamos apuntando las
.
3 | 2 | 2 | 3 | ||
754 | 221 | 91 | 39 | 13 | 0 |
1 | 0 | 1 | -2 | 5 | -17 |
0 | 1 | -3 | 7 | -17 | 58 |
Explicamos un poco más de donde sale la tabla. Las primeras dos columnas son los vectores y
del problema, que son
y
. Para la tercer columna, nos preguntamos ¿cuántas veces cabe
en
? La respuesta es
, así que ponemos un
arriba (para acordarnos) y hacemos la resta de la primera columna menos tres veces la segunda. Eso va en la tercer columna.
Para la cuarta columna, nos preguntamos ¿cuántas veces cabe en
? La respuesta es
, así que lo apuntamos arriba, y la cuarta columna es la segunda, menos dos veces la tercera. Continuamos así hasta que obtengamos un
. La columna anterior nos dice que
es el máximo común divisor, y que la combinación lineal es
Aquí hay otros dos problemas con aplicaciones de las ideas que vimos en esta entrada.
Problema. Muestra que para todo entero se tiene que la fracción
es irreducible para todo entero.
Sugerencia pre-solución. Intenta resolver el problema. Lo que quieres mostrar es que y
nunca tienen divisores en común.
Solución. Notemos que y
tienen una combinación lineal que da
. En efecto,
Cualquier entero que divida a
y a
tiene entonces que dividir a
, lo cual muestra que
, y por lo tanto la fracción siempre es irreducible.
Problema. Se tiene un número irracional para el cual
y
son números racionales. Muestra que
es un número racional.
Sugerencia pre-solución. Encuentra el máximo común divisor de y
. Recuerda que las potencias de racionales son racionales, y productos de racionales también.
Solución. Como y
, tenemos que
. De esta forma, existen enteros
y
tales que
, de donde
.
Sabemos que es racional, así que
también. Análogamente,
es racional. De esta forma, el número
Más ejemplos
Puedes ver más ejemplos del uso de esta teoría en la Sección 3.1 del libro Problem Solving through Problems de Loren Larson.
El Teorema 3 es fundamental para cuando se quieren determinar inversos multiplicativos trabajando módulo .
Hola, tenog un problema que no puedo resolver por métodos «faciles»
Si (a,b)=1 entonces (a al cuadrado, b al cuadrado)=1.
Supongo que es un buen problema usando sólo divisibilidad, ¿Puedes ayudarme?.
P.D: Ya lo demostre usando el teorema fundamental de la aritmetica, necesito tú ayuda.
Gracias
Es una buena pregunta. Aquí va una demostración que acabo de pensar. Supon que k es un entero que divide a a^2 y a b^2. Como a y b son primos relativos, hay una combinación lineal de ellos que da 1, digamos am+bn=1. Multiplicando esta igualdad por ab, tenemos a^2bm+ab^2n=ab. Como k divide a a^2 y b^2, entonces divide a ab. Ahora, regresa a la combinación lineal que da 1 y multiplica por a. Entonces a^2m+abn = a. Como k divide a a^2 y a ab, entonces divide a a. Análogamente divide a b. Pero a y b son primos relativos, así que k=1.
Ohhh, esto estaba buscando, perdón por tardar en responder pero estaba ocupado resolviendolo pero no llegue a nada. Muchas gracias, aunque estoy preocupado, si podemos expresar números como combinación lineal i.e. ax+by=1 implica que serán coprimos? En caso de no ser así, existe una condición para poder determinar que tales x e y son únicos?
Sí. Existe una combinación lineal entera ax+by=1 si y sólo si a y b son primos relativos (coprimos). Esos x y y nunca son únicos. Hoy publico una entrada de ecuaciones diofantinas en donde hablo de cómo son todas las posibles soluciones. Pero a grandes rasgos, si x y y hacen esta combinación lineal, también x-kb, y+ka son soluciones para cualquier entero k (y estas son todas las soluciones que existen).