Story Transcript
Solía permitirme creer que la mente es un subproducto del cuerpo. ¾ Dónde se llega primero, al puerto o a ciudad, a la ciudad o al Estado, al Estado o al mundo? Mi hermana y yo, Federico Nietzsche.
Capítulo 1
Los Números Enteros 1.1. Introducción El objetivo de este capítulo es presentar las propiedades básicas de los números enteros que vamos a necesitar en los próximos capítulos. Con el n de tener una de nición formal de los números enteros, en el marco de la teoría de conjunto, mostraremos como se construyen a partir de los números naturales. Sin embargo no nos detendremos a probar todas las propiedades básicas de los enteros a partir de su de nición sino que las enunciaremos y las usaremos. Invitamos al lector a realizar las pruebas de dichas propiedades que sólo requieren de las de niciones presentadas. Los números enteros se de nen como clases de pares ordenados, pero para simpli car su notación y manipulación los denotaremos como se hace usualmente. Los puntos más importantes tratados en este capítulo son: el principio de buena ordenación, los principios de inducción, el algoritmo de Euclides y el teorema de descomposición en primos (teorema fundamental de la aritmética).
1.2. La De nición Sobre el conjunto
IN × IN
se de ne la siguiente relación:
< a, b >≡< c, d >⇐⇒ a + d = b + c . Esta relación es una relación de equivalencia sobre parte al conjunto
IN × IN
IN × IN ,
(1.1) y por consiguiente,
en clases disjuntas. Al conjunto de dichas clases, esto
es, al conjunto cociente se le denomina conjunto de los enteros racionales y se denota por la letra
Z.
Entonces se tiene que
Z = {[< n, 0 >] : n ∈ IN ∗ } ∪ {[< 0, n >] : n ∈ IN ∗ } ∪ {[< 0, 0 >]} .
(1.2)
Al primero de los conjuntos de esta unión se le denomina conjunto de los enteros + positivos y se le denota por Z , al segundo se le denomina conjunto de los enteros 1
Capítulo 1. Los Números Enteros
2
negativos y se le denota por
Z−
y nalmente el último de los conjunto de esta
unión es un singletón cuyo único elemento es el cero. Al entero denotaremos por
−n.
n
o
+n,
mientras que al entero
[< 0, n >]
[< n, 0 >]
lo
lo denotaremos por
Recuerde que los corchetes signi can la clase del elemento tal.
1.2.1.
Aritmética Entera
Sobre el conjunto de los números enteros se de nen dos operaciones que denominamos adición y multiplicación como sigue:
[< a, b >] + [< c, d >] = [< a, b >] ∗ [< c, d >] =
[< a + c, b + d >] [< ac + bd, ad + bc >] .
(1.3)
Sobre la adición se pueden probar las siguientes propiedades: 1. Clausura:
(∀x, y ∈ Z)(x + y ∈ Z)
2. Asociatividad:
(∀x, y, z ∈ Z)((x + y) + z = x + (y + z))
3. Existencia de Neutro:
(∀x ∈ Z)(x + 0 = 0 + x = x)
4. Existencia de inverso:
(∀x ∈ Z)(x + (−x) = (−x) + x = 0)
5. Conmutatividad:
(∀x, y ∈ Z)(x + y = y + x)
y para la multiplicación se pueden probar las siguientes propiedades: 1. Clausura:
(∀x, y ∈ Z)(x ∗ y ∈ Z)
2. Asociatividad:
(∀x, y, z ∈ Z)((x ∗ y) ∗ z = x ∗ (y ∗ z))
3. Existencia de Neutro: 4. Conmutatividad:
(∀x ∈ Z)(x ∗ 1 = 1 ∗ x = x)
(∀x, y ∈ Z)(x ∗ y = y ∗ x)
Además se cumplen las leyes distributivas de la multiplicación con respecto a la adición, esto es:
(∀x, y, z ∈ Z)(x(y + z) = xy + xz ∧ (x + y)z = xz + yz)
Otras dos propiedades importantes de los números enteros son las siguientes: En los enteros se cumplen las leyes cancelativas, esto es,
0 ∧ zx = zy ⇒ x = y)
(∀x, y, z ∈ Z)(z ̸=
En los enteros no existen divisores de cero distintos de cero, esto es,
(∀x, y ∈ Z)(xy = 0 ⇒ x = 0 ∨ y = 0)
1.3. Principio de Buena Ordenación
1.2.2.
Vicente Yriarte
3
Un Orden en los Enteros
Sobre el conjunto de números enteros se de ne la siguiente relación de orden
< a, b > ≤ < c, d > ⇐⇒ a + d ≤ b + c . Donde el signo
≤
(1.4)
del lado derecho es la relación de orden usual en los números
naturales. Puede probarse que con esta relación de orden el conjunto de los números enteros es un conjunto linealmente ordenado. Alerta: No es la única relación de orden que se puede de nir sobre los enteros, pero es la que usamos con más frecuencia: la denominamos orden usual. A continuación mostramos algunas de las propiedades más importantes del orden en los enteros. Como es usual denotaremos al orden estricto asociado a signi ca que
a ≤ b ∧ a ̸= b.
≤
0, P (k)
implica
P (k + 1),
entonces
todo entero positivo. El siguiente teorema se conoce como segundo principio de inducción o principio de inducción generalizada.
Teorema 1.5 (Segundo Principio de Inducción)
P es una proposición m > 0 la hipótesis de que P (m) es verdadera, Si
que pueden o no satisfacer los enteros y para cualquier que
P (k)
entonces
es verdadera para todo
P (n)
0 < k < m
implica
es cierta para todo entero positivo.
1.5. Divisibilidad en los Enteros
Prueba: S
Sea
S
m
S
5
el conjunto de enteros positivos para los cuales
es vacío, entonces
existe en
Vicente Yriarte
P
es verdadera para todo entero positivo. Si
mprincipio
un elemento mínimo
P es falsa. Si S no es vacío,
de buena ordenación. Como
P , se tiene que P (m) también es no vacío. 2
es el entero positivo más pequeño para el cual no se cumple
para todo
k < m, P (k)
es verdadera; luego, se concluye que
verdadera. Esto es una contradicción, luego,
S
no puede ser
1.5. Divisibilidad en los Enteros La ecuación ax = b no siempre tiene solución en los enteros, esto es, dados a, b ∈ Z , no siempre existe c ∈ Z tal que ac = b; por ejemplo, la ecuación 2x = 3 no tiene solución en los enteros porque no existe un entero que multiplicado por
2
de
de
b
3.
Cuando tal solución existe se dice que a divide a
o que b es divisible por
a.
También se dice que
b
b,
que a es divisor
es múltiplo de
a.
Este
concepto se formaliza a continuación.
De nición 1.3
Dados dos enteros
presentamos por
a|b,
a
y
b,
decimos que a divide a
si y sólo si existe un número entero
z
tal que
b, y lo az = b.
re-
Alerta: Dado que los divisores de un entero no nulo vienen por pareja, muchos autores usan la frese es divisor sólo para referirse a los divisores no negativos, por ejemplo, suelen decir: los divisores de 12 son 1,2,3,4,6,12. Nosotros usaremos explícitamente el cali cativo positivos cuando necesitemos referirnos sólo a los divisores positivos.
Teorema 1.6
La relación divide a es re exiva y transitiva, esto es:
re exividad:
∀a ∈ Z
transitividad:
∀a, b, c ∈ Z
a|a (a|b ∧ b|c ⇒ a|c)
Prueba: Sea a ∈ Z ; se tiene que a = a · 1, luego a|a. Sean a, b, c ∈ Z ; si a|b y b|c se tiene que existen enteros z1 y z2 tales que b = az1 y c = bz2 . Por lo tanto, c = az1 z2 , lo que indica que a|c. 2 a es un divisor de b y a es un divisor de c, decimos que a es un divisor común b y c; por ejemplo, 1, 2, 3 y 6 son divisores comunes de 18 y 24. Un resultado importante y fácil de probar sobre los divisores comunes es el siguiente: Si d es un divisor común de a y b, entonces d es un divisor de cualquier combinación lineal de a y b. Si
de
Ejercicio 1.1
Demuestre que si
a|b
y
a|c,
entonces
a|b ± c.
Ejercicio 1.2
Demuestre que si
a|b
o
a|c,
entonces
a|bc.
Ejercicio 1.3
Demuestre que si
a|b ± c
y
a|b,
entonces
a|c.
Capítulo 1. Los Números Enteros
6
De nición 1.4 (Unidades) Teorema 1.7 Prueba:
Se denominan unidades a los divisores de
Las únicas unidades de
Z
son
1.
±1.
Z si y sólo si existe b ∈ Z tal que ab = 1 se tiene que a ̸= 0 y que b ̸= 0 (porque de ser alguno cero el producto sería cero) y que |ab| = |a| · |b| = 1. Luego, como |a| > 0 y |b| > 0 y como no existe un entero k tal que 0 < k < 1 se tiene que |a| ≥ 1 y |b| ≥ 1. Si |a| > 1, entonces se tiene que |a| · |b| > |b| ≥ 1 (x < y ∧ c > 0 ⇒ cx < cy y transitividad). Por consiguiente |ab| > 1 que contradice |ab| = 1. Esto implica que |a| = 1 y en consecuencia que a = ±1. 2 ab = 1.
El entero
a
es una unidad de
Debemos probar que
a = ±1.
Si
2|−2 y −2|2, pero 2 ̸= −2. El siguiente corolario muestra una propiedad parecida a la antisimetría.
La relación divide a no es antisimétrica porque, por ejemplo,
Él dice que los enteros mutuamente divisible son solamente los opuestos.
Corolario 1.8 b|a,
Si los enteros
a
a = ±b.
entonces
y
b
son mutuamente divisibles, esto es,
a|b
y
Prueba:
Si a|b, se tiene que existe z1 ∈ Z tal que b = az1 . De igual forma, b|a implica que a = bz2 para algún z2 ∈ Z . Luego, sustituyendo se tiene que a = az1 z2 ; si a = 0, entonces b = 0, y si a ̸= 0, se tiene que a − az1 z2 = a(1 − z1 z2 ) = 0, y dado que Z no tiene divisores de cero distintos de cero, se concluye que z1 z2 = 1 y por el teorema anterior obtenemos que z1 = ±1, de donde concluimos que a = ±b. 2 Nota: si consideramos el conjunto de los enteros positivos o el conjunto de los enteros no negativos, la relación de divisibilidad es un orden parcial y no total.
1.5.1.
Algoritmo de Euclides
Teorema 1.9 (Algoritmo de la División de Euclides)
Dados dos enteros
a
r
y
b
tales que
b > 0,
se tiene que existen únicos enteros
a = bq + r
∧
q
y
que cumplen con
0≤r 0,
mientras
a≥b
se le puede restar
quiere hallar también el valor de
q = 0,
incrementar
q
r
b
a
a: r
r, si a ≥ 0 a. Si se
es el valor nal de
todo lo que hay que hacer es empezando con
en uno cada vez que se le reste
b
a
a.
Esto produce el
siguiente algoritmo: |[
const A, B : int {A ≥ 0 ∧ B > 0}; var r := A, q := 0 : int;
A = q ∗ b + r ∧ r ≥ 0 } {cota: do r ≥ B → r, q := r − B, q + 1od {A = q ∗ B + r ∧ 0 ≤ r < B } { inv:
r}
En lenguaje C: int r = A, q = 0;
]|
Este es un algoritmo muy simple que sólo usa las operaciones binarias sustracción y adición y cuyo orden en todos los casos es
O(A/B). Se pueden escribir
varias versiones del mismo orden, una basada en la forma como se probó el teorema es escrita en lenguage C es:
while (r ≥ B){r = r − B; q
++; }
Capítulo 1. Los Números Enteros
8
int const A,B; int r, q = 0; while (A − q ∗ B >= 0){x++; } q = q − 1; r = A − q ∗ B
Pero este además de la adición y de la sustracción, usa la multiplicación de dos
a ≥ 0 y b < 0. O(lg A/B). Se deja
enteros y al igual que el anterior tiene como precondición que Al estilo del primero se puede escribir un algoritmo orden
como ejercicio. En los ejercicios se les pedirá probar dos propiedades que nos permitiran usando cualquiera de estos algoritmos escribir uno que funcione para todo entero
a
y para todo entero no nulo
b.
b a se puede escribir de forma única como a = qb+r con 0 ≤ r < b, esto parte al conjunto Z en b clases, a saber: tomando 0 ≤ r < b se tiene que el conjunto [r] = {x ∈ Z : x = qb + r ∧ q ∈ Z} Sale que de ellas la Una consecuencia inmediate es que cualquiera que sea el entero positivo
que consideremos todo entero
unica cerrda para la adición y la sustracción es la del CERO. Por ejemplo, en
b = 2, se tiene que las clases son: 2Z = {x ∈ Z : x = 2k + 0 ∧ k ∈ Z} 2Z + 1 = {x ∈ Z : x = 2k + 1 ∧ k ∈ Z}. Y puesto que son disjuntas y su unión es Z sale que todo impar se puede escribir como 2k + 1 para algún k ∈ Z , el caso
y
resultado que hasta ahora lo habíamos dado por sentado.
Lema 1.10
Todo subconjunto no vacío de números enteros cerrado para la adi-
ción y la sustracción, contiene sólo al cero, o contiene un número entero positivo mínimo del cual son múltiplos todos los demás.
Prueba:
S , un conjunto no vacío cerrado para la adición y para la susa ̸= 0 un elemento de S ; por de nición de S , a − a = 0 ∈ S , por lo tanto 0 − a = −a ∈ S . Luego, S contiene tanto a a como a −a, uno de los cuales debe ser positivo, luego S contiene un subconjunto no vacío de números Sea
tracción, y sea
enteros positivos, que por el principio de buena ordenación tiene mínimo. Deno-
b. Este conjunto S debe contener todos los múltiplos b. Contiene a b · 1; si contiene a b · k , entonces contiene a b · (k + 1) pues b · k + b = b · (k + 1). También contiene a los múltiplos negativos −n · b = 0 − nb. Veamos que S no contiene no múltiplos de b. Si c ∈ S y c no es múltiplo de b, por el algoritmo de Euclides se tendrá que c = qb + r , lo cual implicaría que r = c − qb ∈ S , con 0 ≤ r < b. Si r = 0, se tiene que c = qb, lo cual es una contradicción pues supusimos que c no es múltiplo de b. Si r ̸= 0, también se tiene una contradicción porque r es estrictamente menor que b y por elección b era el menor entero positivo de S . 2 minemos a dicho mínimo de
Ejercicio 1.4
Halle los sub-conjunto de
Z,
cerrados para la adición y la sus-
tracción. ¾Cuántos son? ¾Cómo sabe que son todos? ¾Son nitos? ¾Por qué? Expréselos por comprensión. Halle los sub-conjuntos de
Z
cerrados para la adi-
ción, pero no para la sustracción. ¾Cuántos son?
Ejercicio 1.5
¾Es el conjunto de los números impares cerrado para la adición?
¾y para sustracción?
1.5. Divisibilidad en los Enteros
Ejercicio 1.6
Vicente Yriarte
¾Puede mostrar un sub-conjunto de
Z
9
cerrado para la sustracción
que no lo sea para la adición?
1.5.2.
Máximo Común Divisor
En esta sección daremos la de nición de máximo común divisor y máximo común divisor positivo de un par de números enteros, mostraremos que todo par de enteros no ambos nulos tienen un máximo común divisor positivo único que no es otro que la menor combinación lineal entera positiva que se puede hacer con dichos números. Además mostraremos las propiedades relevantes del máximo común divisor positivo algunas de cuales nos permitirán obtener métodos para el cálculo del mismo. Finalmente presentaremos el concepto de mínimo común múltiplo.
De nición 1.5 (Máximo Común Divisor) común divisor de dos números enteros
a
y
b
Un entero
d
se llama máximo
si y sólo si es simultáneamente
a y de b y además es múltiplo de cualquier otro divisor común. La M CD(a, b) = d signi ca en lo sucesivo que d es máximo común divisor de b.
divisor de expresión de
a
y
Simbólicamente:
M CD(a, b) = d ⇐⇒ d|a ∧ d|b
∧
(∀c ∈ Z)(c|a ∧ c|b ⇒ c|d)
y −4 son máximos comunes divisores de 12 y 8. Pero no existe d que sea el máximo común divisor del par < 0, 0 >, pues si d = M CD(0, 0) si bien es cierto que d|0 y d|b, no es cierto que todo divisor común de 0 y 0 divida a d, eg.: (d + 1)|0 y (d + 1)|0, pero (d + 1) ̸ |d. Nótese
Por ejemplo,
4
ningún entero
que todo par de enteros no ambos nulos parecieran tiener dos máximos comunes divisores que di eren sólo en el signo. Puesto que todos los enteros dividen al cero, no podremos de nir el máximo común divisor para el para
< 0, 0 >,
pero
para garantizar la unicidad del máximo común divisor lo de niremos siempre positivo. A continuación se da la de nición del máximo común divisor positivo.
De nición 1.6 (Máximo Común Divisor Positivo) se llama máximo común divisor de dos números enteros simultáneamente divisor de
a
y de
b
divisor común. Usaremos la expresión común divisor positivo de los enteros
mcd(a, b)
Un entero positivo
a
y
b
d
si y sólo si es
y además es múltiplo de cualquier otro
(a, b) = d para indicar que d es a y b; En ocasiones usaremos
máximo también
En simbolos se anota:
(a, b) = d ⇔ d > 0 ∧ d|a ∧ d|b
Teorema 1.11
∧
(∀c ∈ Z)(c|a ∧ c|b ⇒ c|d)
El máximo común divisor positivo de dos enteros, si exite es
único. En adelante cuando hablemos de máximo común divisor estaremos re riendonos al máximo común devisor positivo. La primera de ellas está aca sólo por aclarar las cosasespero no haberlas oscuresido o enturbiado. La mayoría de los
Capítulo 1. Los Números Enteros
10
matemáticos usan la última. Esta última tiene la ventaja de ser una función de
Z × Z − {< 0, 0 >}
Teorema 1.12 divisor positivo
b
en
Z;
ello se justi ca con el teorema anterior y el siguiente.
a
Dos enteros no ambos nulos
(a, b).
y
b
tienen un máximo común
Este puede expresarse como combinación lineal de
con coe cientes enteros
u
y
w
a
y
como sigue
(a, b) = ua + wb
Prueba:
xa+yb se llama una combinación lineal de
a
y de
b
a y b no ambos nulos, consideremos el conjunto de xa + yb, esto es, consideremos S = {xa + yb : x, y ∈ Z}. Claramente 0, a y b pertenecen a S pues 0 = 0a + 0b, a = 1a + 0b, y b = 0a + 1b. Por lo tanto, S no sólo contiene al cero y como es cerrado bajo la adición y la Sean dos enteros
los números de la forma
sustracción (½Verifíquelo!), entoncesLema 1.10todos sus elementos son múltiplos de algún entero positivo algún
u, w ∈ Z .
d
que debe ser de la forma
Falta ver que este número
d
d = ua + wb
para
es, en efecto, el máximo común
a pues a ∈ S y S sólo tiene múltiplos de d es divisor de b. Además como d = ua + wb se tiene que si c|a y c|b, entonces c|ua + wb, esto es, c|d, por lo tanto d es el máximo común divisor positivo de a y b, o sea, d = (a, b) 2 divisor positivo de
d.
a
y
b.
Es divisor de
Por igual razonamiento,
Es importante notar de la prueba de este teorema que: El máximo común divisor positivo de los enteros no ambos nulos
a y b es el mínimo del conjunto de a y b. Ello da pie a los siguientes
las combinaciones lineales enteras de los enteros dos corolarios.
Corolario 1.13
Dados dos enteros no ambos nulos
a, b,
su máximo común di-
visor positivo es el valor de la combinación lineal de los enteros
a
y
b
que tiene
el menor valor positivo.
Corolario 1.14 tales que
a y b no (a, b) = 1
Dados dos enteros
ua + wb = 1,
entonces
ambos nulos
1
, si existen enteros
Pero, ½alerta rojo!: No es cierto que: si ua + wb = c ∧ c > 1, entonces (a, b) = c. Este c es un múltiplo de (a, b), pero no necesariamente él. Por ejemplo, 2(6) + 3(3) = 21 es una combinación limeal de los enteros 6 y 3, pero no es su máximo comun divisor positivoes un múltiplo de mismo. Si bien el Teorema 1.12 habla de la existencia de una combinación lineal de
a y b, no indica < u, w > en Z que hacen esto posible. Ilustrémoslo con un ejemplo: puesto que (12, 18) = 6 se tiene que existe u y w tales que 12u + 18w = 6 o equivalentemente tales que 2u + 3w = 1. Por simple inspeción se tiene que el par < −1, 1 > satisface dicha ecuación. Halle-
los enteros
a
y
b
que da el máximo común divisor positivo de
que ella sea única, de hecho, hay in nitos pares
mos otros pares, se podría de nuevo proceder por inspeccíon, pero de esa forma
1 podemos
remover la hipotesis: no ambos nulos", pues si lo fueran la hipótesis
no se cumpliría
ua + wb = 1
1.5. Divisibilidad en los Enteros
Vicente Yriarte
11
no la hallaremos todas. Para ello escribamos la ecuación de esta recta en forma u−u0 0 paramétrica usando la fórmula = w−w = k donde < u0 , w) > es un punto a b por donde pasa la rectaque conviene sea de coordenadas enteras y < a, b > es el vector director de la recta que hallaremos restando los puntos de corte de
< 1/2, 0 > y < 0, 1/3 >, nos da: < 1/2, −1/3 > y lo multiplicamos w−1 6 para hacerlo entero., nos da: < 3, −2 >. Nos queda que u+1 3 = −2 = k u = 3k −1 y w = −2k +1, con lo que podemos hallar in nitas soluciones con tan solo cambiar el valor de k , e.g.: si k = 0 tenemos la solución ya hallada u = −1 y w = 1. Mientras que si k = 1, nos que 2u = y w = −1. la recta: por
El teorema tampoco propone un método para obtener los coe ciente de la combinación lineal, más adelante propndremosnun método basado en ... Este teorema tiene un interés bastante teórico y se usará con frecuencia como apoyo para probar un buen número de proposiciones en el futuro.
Ejercicio 1.7
Halle el máximo común divisor positivo de los enteros
36
y
27
y expréselo como una combinación lineal de dichos enteros. Halle una ecuación paramétrica para las coordenas de las combinaciones lineales. El siguiente teorema enuncia algunas de las propiedades básicas de la función
mcd
positivo. Se deja como ejercicio.
Teorema 1.15
Para todos los wnteros
a
y
b
el máximo común divisor positivo
satisface las siguientes propiedades:
cordenada nula:
(a, 0) = |a|
cordenada jguales:
(a, a) = |a|,
si
uno absorbente:
(a, 1) = 1
conmutatividad:
(a, b) = (b, a)
signo don't-care:
(−a, b) = (a, b)
valor absoluto basta: factor común:
a ̸= 0
(a, b) = (|a|, |b|)
∀k ∈ Z : (ka, kb) = |k|(a, b)
coordenadas múltiplos:
∀k ∈ Z : (ak, a) = |a|
A continuación presentaremos dos teoremas que nos permitiran escribir algoritmos para determinar el máximo común divisor positivo de dos enteros no ambos nulos
a
y
b.
El primero nos permitira obtener un algoritmo extremada-
mente sencillo pero que en el peor de los casos es lineal en el tamaño del máximo entre
a
y
b,
esto es:
O(m´ ax ({a, b})). Mientras que el segundo Θ(lg m´ax ({a, b})).
tener un algorimo de orden exacto
nos permitirá ob-
Capítulo 1. Los Números Enteros
12
Teorema 1.16 (Recursión Resta) a
b,
y
se tiene que si
a > b,
entonces
Para todo par de enteros no ambos nulos
(a, b) = (a − b, b).
Prueba:
′ Denotemos a (a, b) por d y a (a − b, b) por d , la prueba consiste en ′ ′ probar que d|d y que d |d, para concluir que como ambos son positivos, son iguales. Puesto que
d
es el máximo comun divisor positivo de
a
y
b,
se tiene
por consiguiente divide también a a − b y a b, por lo tanto ′ ′ divide a su máximo común divisor positivo que es d , luego d|d . Analogamente, ′ d divide a a − b y a b, por lo tanto divide a a y a b, luego divide a su máximo ′ común divisor positivo, esto es d |d. 2 que
d|a
y que
d|b,
Note que la proposición también es cierta si se sustituye
a−b
por
a + b.
Usando este teorema construiremos un algoritmo que permita hallar el máximo común divisor positivo entre dos enteros entonces
(a, a) = a.
positivos. Usaremos que si a ̸= 0, a y b, el algoritmo consiste
Dados dos enteros positivos
en sustituir el mayor por la resta del mayor menos el menor hasta que ambos números sean iguales. |[
const A, B : int {A > 0 ∧ B > 0}; var a := A, b := B : int;
{ inv: (A, B) = (a, b) ∧ a > 0 ∧ b > 0} do a ̸= b → if a > b → a := a − b [] b > a → b := b − a fi od {a = (A, B)}
{cota:
a + b}
]|
Es muy fácil probar que este algoritmo termina pues su cota siempre decrece y que es correcto en base al teorema anterior. La inicialización claramente establece el invariante la primera vez y después de cada iteración es fácil probar que el mismo se preserva y que la negación de la guarda más el invariante implican la poscondición. Su peor caso es cuando uno de los enteros es
1,
en cuyo caso el algoritmo
entra al ciclo tantas veces como el tamaño del otro número. A continuación presentaremos un teorema que nos permitirá deducir un algoritmo, un poco más complejo, pero mucho más e ciente. Se basa en el Algoritmo de la División y establece una recurrencia que permite hallar el máximo común divisor positivo de cualquier par de enteros no ambos nulos.
Teorema 1.17 (Recursión de Euclides) también
se
puede
probar al estilo del Teorema 1.16 y vicerversa :)
que
a = bq + r
con
0 ≤ r < b,
entonces
Si a y b (a, b) = (b, r)
son enteros positivos tales
1.5. Divisibilidad en los Enteros
Prueba:
13
x|a ∧ x|b,
x|r y en b y r. Además, si x|b ∧ x|r , entonces x|a, y por lo tanto todo divisor común de b y r , es divisor común de a y b. Luego, el conjunto de los divisores comunes de a y b es igual al conjunto de los divisores comunes de b y r ; por consiguiente su máximo es el mismo, esto es: (a, b) = (b, r). 2 Como
a = bq + r
Vicente Yriarte
se tiene que si
consecuencia todo divisor común de
a
y
b
entonces
es divisor común de
El Teorema 1.9 se denomina Algoritmo de Euclides porque él permite plantear un procedimiento (algoritmo) para determinar el máximo común divisor de cualquier par de enteros positivos. Realmente aun cuando los dos enteros no sean positivos el algoritmo puede hallar su máximo común divisor considerando los números positivos, porque el valor del máximo común divisor positivo no depende de los signos de los números. En el siguiente ejemplo se muestra como se usa el algoritmo de Euclides para hallar el máximo común divisor positivo de dos enteros positivos.
Ejemplo 1.1
Halle el máximo común divisor positivo de los enteros
210
y
33
y expréselo como combinación lineal de dichos enteros.
Explicación:
Al dividir 210 entre 33 se tiene que el resto es 12 y el cociente 6, esto es, 210 = 33 · 6 + 12. Luego, en base al lema anterior se tiene que (210, 33) = (33, 12). Repitiendo el proceso se tiene que 33 = 12 · 2 + 9 y por lo tanto (210, 33) = (33, 12) = (12, 9). Si repetimos el proceso una vez más se tiene que 12 = 9 · 1 + 3 y que (210, 33) = (33, 12) = (12, 9) = (9, 3). Finalmente, 9=3·3+0 y es
(210, 33) = (33, 12) = (12, 9) = (9, 3) = (3, 0) = 3 . Para expresar a
3
como combinación lineal de
120
y de
33
se despeja el último
resto no nulo, en este caso el tres y en esta expresión se van sustituyendo los restos anteriores como se muestra a continuación.
3
= 12 − 9 · 1 = 12 − (33 − 12 · 2) · 1 = −33 + 12 · 3 = −33 + (210 − 33 · 6) · 3 = 3(210) − 19(33) •
El procedimiento usado en la primera parte del ejercicio anterior para hallar el máximo común divisor se puede expresar por medio del siguiente algoritmo. El mismo es recursivo y se basa en el Teorema 1.17. Nota: El resto a
a
entre
b,
se denota por
a mod b,
{ Retorna el máximo común divisor positivo de
mcd(a, b); si b = 0
retorna a
r,
de dividir
y está garantizado por el teorema 1.9
a
y
b}
Capítulo 1. Los Números Enteros
14
de lo contrario retorna mcd(b, a mod b); Su versión iterativa en C:
int mcd(int a, int b){ int c; while (b != 0){ c = a; a = b; b = c%b; } return a; } El teorema 1.12 establece que el máximo común divisor de dos enteros es el valor de la combinación lineal de dichos enteros que produce el menor entero positivo. poner una nota
A continuación deduciremos un algoritmo que extienda el anterior para obtener los coe cientes que permiten escribir al máximo común divisor positivo de
b
como combinación lineal de
la terna
(d, u, w)
donde
d
a
y
b.
Al ser invocado con
a
y
b
es el máximo común divisor positivo de
son los coe cientes de la combinación lineal. Si
b = 0, (a, b) = a
a
y
debe retornar
a
y
b,
y
u, w
y por lo tanto
a = 1 · a + 0 · b, y en consecuencia el algoritmo que buscamos debe devolver la terna (a, 1, 0). De lo contrario se invoca de nuevo al algoritmo con b, a mod b. Si ′ ′ ′ ′ esta invocación retorna la terna (d , u , w ), dado que d = d y puesto que d′
= bu′ + (a mod b)w′ = bu′ + (a − b⌊a/b⌋)w′ = aw′ + b(u′ − ⌊a/b⌋w′ )
(1.7)
⌊a/b⌋ representa la división entera (el cociente entero de dividir a entre b, q del algoritmo de la división) Luego, en este caso el algoritmo debe retornar w′ por u y a (u′ − ⌊a/b⌋w′ ) por w. A continuación se muestra el código.
Aquí, el a
{ Retorna
(d, u, w),
donde
d = (a, b) = ua + wb}
mcdExtendido(a, b) :;
si b = 0 retorna (a, 1, 0);
(d′ , u′ , w′ ) ← mcdExtendido(b, a mod b); (d, u, w) ← (d′ , w′ , u′ − ⌊a/b⌋w′ ); retorna (d, u, w);
Ejercicio 1.8 242
Si un entero
b,
Halle el máximo común divisor positivo de los enteros
2520
y
y expréselo como combinación lineal de dichos enteros.
m
por ejemplo,
es múltiplo de
12
y
24
a
y de
b
se dice que
son múltiplos comunes de
m es múltiplo común de a y 4 y de 6. De manera similar
como se de ne la función máximo común divisor se de ne la función mínimo común múltiplo.
1.6. Números Primos
Vicente Yriarte
15
De nición 1.7 (Mínimo Común Múltiplo)
Dados dos enteros positivos
b decimos que m es el mínimo común múltiplo de a, b y lo representamos mcm (a, b) si y sólo si a|m, b|m y (∀z ∈ Z + )(a|z ∧ b|z ⇒ m|z). Esto es,
y
a
por
mcm (a, b) = m ⇐⇒ a|m ∧ b|m ∧ (∀z ∈ Z + )(a|z ∧ b|z ⇒ m|z) ⟨Z + ∪ {0}, | ⟩ es un reticulado acotado con mínimo b 0 = 1 y b máximo 1 = 0 y que el máximo común divisor positivo y el mínimo común múltiplo de a y b son justamente el ´ ınf (a, b) y el sup (a, b) en dicho reticulado. Nótese que
Alerta: Las palabras máximo y mínimo en las de niciones de máximo común divisor y de mínimo común múltiplo se re eren al máximo y al mínimo de la relación divide a; no deben confundirse con máximo y mínimo de la relación menor o igual. Sin embargo, no se crea con icto con la idea de máximo o mínimo de la relación
≤
porque si
a|b,
a ≤ b.
se tiene que
1.6. Números Primos Los números primos fueron extensamente estudiados por los matemáticos griegos. Matemáticos de la escuela de Pythagoras (500 a 300 a.c) se interesaron en sus propiedades. Euclides (323-283 a.c) en el Libro IX de los Elementos probó que hay in nitos primosdicha prueba es uno de los primeros ejemplos de una prueba por absurdo. También probó el Teorema fundamental de la aritmética que establece que todo número entero se puede descomponer como producto de primos en forma única. Cerca del año 200 a.c. Eratosthenes propuso un algoritmo para hallar primos llamado la criba de Eratosthenes. El hombre parece haberse olvidado de los números primos por cerca de 18 siglos. Los siguientes resultados importantes fueron obtenidos por Fermat en el siglo XVII.
De nición 1.8 (Primo) tinto de
0
y de
±1
2p
Un número entero (positivo)
y es divisible solamente por
±1
y por
es primo si es dis-
±p.
Una de nición equivalente y más compacta es la siguiente:
De nición 1.9 (Primo)
Un número entero
p
es primo si y sólo si es positivo
y tiene exactamente dos divisores positivo. Si un número entero positivo mayor que Observe que el
1
el
0
1
no es primo, se llama compuesto.
y los enteros negativos no son ni primos ni compuestos.
A continuación se muestra la lista de los primeros
50
números primos: 2, 3, 5,
7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, y @229 Si
a
bc, no tiene por qué dividir a a es primo, debe dividir a algunos de
divide a un número compuesto, digamos
alguno de sus factores por separado. Pero si
sus factores. Esto se establece en el siguiente teorema que es una consecuencia
2 Seguiremos
a la mayoría de los matemáticos al considerar la primalidad una propiedad
exclusiva de los enteros positivos
Capítulo 1. Los Números Enteros
16
del Teorema 1.12 que asegura la existencia de enteros
u
y
w
tales que
(a, b) =
ua + wb.
Teorema 1.18
Si
p
es primo y
p|ab,
entonces
p|a
o
p|b.
Prueba:
Supongamos que p ̸ |a, como p es primo sus únicos divisores son ±1 y ±p, como p ̸ |a los únicos divisores comunes de a y p son ±1. Luego, 1 es máximo común divisor positivo de p y a, esto es, (a, p) = 1, y por consiguiente existen u y w tales que 1 = ua + wp. Si multiplicamos por b se tiene que b = uab + wpb, y además como p|ab se tiene que existe z ∈ Z tal que ab = zp, y por lo tanto b = uzp + wpb = p(uz + wb) y en consecuencia p|b. 2
Corolario 1.19 Ejercicio 1.9 tonces
p = q1
es primo y
p|a2 ,
entonces
Demuestre que si
p, q1
y
o
Si
p
q2
p|a.
son primos positivos y
p|q1 q2 ,
en-
p = q2 .
De nición 1.10 (Primos Relativos)
Se dice que dos números enteros
a
y
b
son primos entre sí, o que son primos relativos si y sólo si sus únicos divisores comunes son
±1,
esto es, si y sólo si
(a, b) = 1.
El siguiente teorema es una generalización del anterior.
Teorema 1.20
Si
c|ab
Teorema 1.21
Si
(a, b) = 1, a|x
Ejercicio 1.10
Pruebe que para todo
1.6.1.
y
(a, c) = 1, y
entonces
b|x,
c|b.
entonces
a ∈ Z, a
y
ab|x. a+1
son primos entre sí.
Teorema Fundamental de la Aritmética
En esta sección se estudiará el teorema fundamental de la aritmética. Dicho teorema a rma que todo entero no primo se puede descomponer en el producto de factores primos, en forma única salvo por el orden de aparición de los factores. La prueba de este teorema se basa en el segundo principio de inducción matemática de los enteros positivos.
Teorema 1.22 (±1)
Todo entero no nulo se puede expresar como el producto de
por factores primos positivos. Dicha expresión es única, salvo por el orden
de los factores.
Prueba:
Consideraremos sólo el caso en que
n
sea un entero positivo. (¾Por
qué?) y lo probaremos por inducción generalizada sobre
n. Primero probaremos
la existencia de una tal descomposición y luego la unicidad de la misma. Paso base: si
n
es
1
se cumple porque
1
es
1
por un producto vacío de facto-
res primos. Paso inductivo: Asumimos que todo entero menor que descomponer como producto de factores primos y probaremos que
n n
se puede se puede
1.6. Números Primos
Vicente Yriarte
17
n es primo, enn no es primo, entonces tiene algún n; por consiguiente n = n1 · n2 con
descomponer como producto de factores primos. Por casos: si tonces es el producto de un solo primo y si
1 y distinto de 1 < n1 , n2 < n se pueden, por hipótesis inductiva, descomponer como producto de primos, digamos: n1 = p1 p2 · · · pr y n2 = q1 q2 · · · qs , se tiene que n = p1 p2 · · · pr q1 q2 · · · qs que es una descomposición en primos de n. Probemos ahora la unicidad también por inducción sobre n. De nuevo, para n igual a 1 se tiene que se cumple porque el producto de primos es vacío. divisor positivo mayor que
n1 , n 2 > 1
Luego, como
Si asumimos que la descomposición es única para todo entero positivo menor
n debemos probar que la descomposición es única para n. Su pongamos que n = p1 p2 · · · pr y n = q1 q2 · · · qs son dos descomposiciones en primos de n. Como p1 divide a n se tiene que p1 divide a algún qi , pero además como p1 es primo se tiene que p1 = qi quedando que p2 · · · pr = q1 · · · qi−1 qi+1 · · · qs y como este número es menor que n se tiene que cada pi debe corresponder a algún qj y que r = s. 2 que
De la prueba del Teorema anterior se desprenden varias consecuencias no triviales, a saber: todo entero no nulo a excepción de
±1 usa al menor un primo
en su descomposición, si usa exactamente uno, el claro que el número es primo o el opuesto de un primo, si usa más de uno se dice que es compuesto. Se pueden dar dos de niciones equivalentes de número compuesto, a saber:
De nición 1.11 (Número Compuesto) compuesto si y sólo si existen dos enteros
n
cuyo producto es
Un número entero
n1 , n 2
mayores que
n se dice que es 1 y menores que
n.
De nición 1.12 (Número Compuesto)
Un número entero
n
se dice que es
compuesto si y sólo si en su descomposición en primos usa al menos dos primos.
Ejercicio 1.11
Demuestre que las dos de nicines anteriores son equivalentes.
Esto hace que todo entero positivo sea o bien el
1,
o bien primo, o bien un
número compuesto. Una consecuencia del teorema anterior es el Teorema demostrado por Euclides que a rma la existencia de in nitos primos. Ya comentamos que es uno de los ejemplos más antiguos de una prueba por absurdo.
Teorema 1.23 (Euclides) Prueba:
Existen in nitos números primos positivos.
Supongamos, por absurdo, que hay un número nito de primos
y enumerémoslos como sigue:
p1 p2 · · · pk + 1.
p1 , p2 , . . . , pk .
Consideremos al entero positivo
Claramente es mayor que cada uno de los
pi ,
por lo tanto no es
primono está en nuestra lista de primos.Como también es mayor que 1, debe ser compuesto y contener al menos un primo en su descomposiciónTeorema Fundamental de la Aritmetica, esto es, alguno de nuestros primos debe dividirlo. Pero si alguno de nuestros primos, digamos
pi ,
lo divide, entonces como
Capítulo 1. Los Números Enteros
18
también divide a
p1 p2 . . . pk , se tiene que divide a 1, lo cual es una contradicción. 2
Luego el conjunto de los primos no es nito.
Nota: Agrupando los primos iguales de la descomposición en primos del αk 1 α2 n se tiene que n = pα 1 p2 · · · pk . Esto nos permite hallar una fórmula para contar los divisores del número n porque un divisor de n debe ser β1 β2 βk forzosamente de la forma d = p1 p2 · · · pk con 0 ≤ βi ≤ αi . Justi que esta a rmación. entero positivo
El teorema anterior proporciona además la base para determinar el mínimo común múltiplo de dos enteros. Se deja como ejercicio.
Ejercicio 1.12 ple que
Demuestre que para todo par de enteros positivos
a
y
b
se cum-
ab = mcd (a, b) mcm (a, b).
Ejercicio 1.13
Halle una fórmula que permita calcular el número de divisores
positivos de un número entero
Ejercicio 1.14
n
en base a su descomposición en primos.
Halle una fórmula que permita calcular la suma de los divisores
positivos del número entero
n.
1.7. Ecuaciones Diofánticas En esta sección presentaremos una breve introducción a las ecuaciones diofánticas.
De nición 1.13 (Ecuaciones Diofánticas)
Una ecuación Diofántica es una
ecuación algebraica con coe cientes enteros, con una o más incognitas de la que se desean sólo las soluciones enteras. Por lo general se tienen algunas otras restricciones. Cuando las variables tienen esponente es lineal como es el caso de
ax + by = c.
1
se dice que la ecuación
Aca sólo discutiremos algunas del caso
lineal.
Teorema 1.24
Dados tres números enteros
a, b
y
c
la ecuación
ax + by = c ayb
tiene soluciones enteras si y sólo si el máximo común divisor positivo de divide a
c.
Prueba:
ax + by = c donde a, b, c ∈ Z . ax + by = c tiene alguna solución en Z , entonces el máximo común divisor positivo de a y b divide a c. Sea x0 , y0 una solución de ax + by = c y denotemos por d a (a, b), entonces se tiene que ax0 + by0 = c y que d|a y d|b, por lo cual d|(ax0 + by0 ), esto es: d|c. (⇐) Probaremos que si d|c, entonces la ecuación tiene una solución exhibiéndola. Puesto que d es (a, b) se tiene que d|a y d|b, y como por hipótesis d|c, entonces ′ ′ ′ ′ ′ ′ existen tres enteros, digamos: a , b y c tales que a = a d, b = b d y c = c d, lo ′ ′ bueno es que a y b son coprimos. ?Por qué? Luego por el teorema 1.12 existen u y w tales que a′ u + b′ w = 1. Si multiplicamos por c′ d y conmutamos nos ′ ′ ′ ′ ′ ′ ′ ′ quda: a dc u + b dc w = c d, y si ahora sustituimos a d, b d y c d por a, b y c Consideremos la ecuación
(⇒) Probaremos que si
1.7. Ecuaciones Diofánticas
Vicente Yriarte
ac′ u + bc′ w = c ax + by = c.
respectivamente tenemos que solución de la ecuación
Ejemplo 1.2 Respuesta:
Diga si existen enteros tales que
19
con lo que
< c′ u, c′ w >
es una
2 4x + 6y = 15.
Usando el teorema anterior basta con chequear si máximo común
divisor positivo de
4
y
6
divide a
15. (4, 6) = 2
y
2 ̸ |15,
entonces no existen so-
luciones enterasa esta ecuación. Por supuesto que sin usar el teorema pudimos, por absurdo, suponer que existía una solución
2
divide a
4x0
y divide a
6y0
< x 0 , y0 >
y observar que como
entonces tiene que dividir a su suma que es
15
y
•
no lo hace, lo cual es una contradicción.
Para hallar una primera soluciónque llamaremos particular puesto que
ax + by = c tiene soluciíon ssi (a, b) divide a c el (a, b) y chequear si divide a c. Lo siguiente es combinación lineal de a y b, bien por simple inspección
la ecuación diofántica lineal
primer paso obligado es hallar expresar a
(a, b)
como
o usando el algoritmo extendido de euclides. Pero para hallar el resto de las soluciones nos basaremos en el siguiente teorema.
Teorema 1.25
Dados tres enteros no nulos a. b y c tales que el máximo común d de a y b divide a c, si < x0 , y0 > es una solución cualquiera de la ecuación ax + by = c, entonces cualquiera solución se puede expresar como: < x0 + db k, y0 − ad k > donde k es un entero. En otras palabras si < u, w > es b una solución cualquiera de ax + by = c, entonces existe k ∈ Z tal que u = x0 + d a y w = y0 + d . divisor positivo
Prueba:
< u, w > una solución cualquiera de ax + by = c, entonces ax + by = c y por ser d el máximo común divisor positivo de a y b se tiene d|a y d|b, y como además por hipotesis d|c se tiene ad u + db w = dc pero como además < x0 , y0 > también es solución de ax + by = c, se tiene que ad x0 + db y0 = dc . Sea
Resulta que:
{
a b du + dw b a d x0 + d y0
= =
c d c d
a b a lo que implica que d (u − x0 ) + d (w − y0 ) = 0 y esto equivale a d (u − x0 ) = b b a a b d (y0 − w). Luego d divide a d (u − x0 ). Pero, puesto que d y d son coprimos, b se tiene que d divide a (u − x0 ), por lo tanto debe existir un entero, digab b mos k , tal que (u − x0 ) = d k lo que dice que u = x0 + d k y sustituyendo en a b a 2 d (u − x0 ) = d (y0 − w) sale que w = y0 − d k lo que termina la prueba.
formalmente: el entero
a = a′ d.
a′
a es d
tal que
Capítulo 1. Los Números Enteros
20
1.8. Ejercicios Resueltos Ejercicio Resuelto 1.1 Demuestre que si
Respuesta:
n
n se llama compuesto si y 1 < n1 , n2 < n y n = n1 n2 .
Un número entero positivo
sólo si existen enteros positivos
n1
y
n2
tales que
es compuesto existe un primo que lo divide.
La respuesta es inmediata de la de nición, si un entero es com-
puesto no puede ser
1
ni puede ser primo, por lo tanto en su descomposición
en primos usa el menos dos primos, que pueden ser igualesuno para la descomposición de
n1
n2 . Es más, por el teorema ±1 su descomposición en pridivide. ♡
y otro para la descomposición de
fundamental de la aritmetica, si un número no es mos usa al menos un primo que por supuesto lo
Ejercicio Resuelto 1.2 33w = 211.
Diga si existen enteros
u, v, w
tales que
12u + 6v +
Muestre los valores o dé un argumento que justi que su existencia
o no.
Respuesta: u, v, w
Puesto que cada sumando, sin importar el valor que se le dé a
3, la suma debería serlo también, pero no lo es pues 211 3la suma de sus guarismos es 4, que no rs divisible entre ♡
es divisible entre
no es divisible entre 3.
Ejercicio Resuelto 1.3 Respuesta:
Como
k, 2
Para todo entero
2|2k , si k
dividiera a
no divide a
2k + 1
2k + 1, entonces 2 dividiría a 1, lo cual 1 son ±1. ♡
es una contradicción pues los únicos divisores de
Ejercicio Resuelto 1.4 suma, entonces
Respuesta: · · · sn
a
a
divide a cada sumando de una
Supongamos sin perder generalidad que la suma es:
a|si para si = ki a, por
y que
tales que
Demuestre que si
divide a la suma.
todo
i,
entonces existen enteros, digamos
lo tanto sustituyendo y usando la propiedad distributiva
de la multiplicación con respecto a la suma se tiene que
(k1 + k2 + · · · + kn )a.
s = s1 + s2 + k 1 , k2 , . . . , k n
s = k1 a+k2 a+· · · kn a =
Luego, como la suma de enteros es un entero, usando la
de nición de divisibilidad, concluimos que
Ejercicio Resuelto 1.5
♡
a|s.
Demuestre que si
k
es un entero, entonces
k(k + 1)
es un número par.
Respuesta:
puesto que
k
es un número entero y
2
es un entero positivo, en-
tonces en base del teorema algoritmo de la división, se tiene que existen enteros
q, r
k = 2q + r con 0]ler < 2. Luego, r = 0 o r = 1, Por casos: Si r = 0, k = 2q y por lo tanto k(k + 1) = 2q(2q + 1) es par. Si r = 1, entonces
tales que
entoces
1.8. Ejercicios Resueltos
k = 2q + 1
y por lo tanto
Vicente Yriarte
21
k + 1 = 2q + 2 = 2(q + 1)
que también, clarmente es par.
Ejercicio Resuelto 1.6 divide a
n2 − 1.
Demuestre que si
n
y
k(k + 1) = 2(2q1 )(q + 1) ♡
es un entero impar, entonces
8
Respuesta:
Si n es un entero impar, entonces se tiene que existe un único k ∈ Z tal que n = 2k + 1Teorema algoritmo de la división: todo número entero n se puede expresar como n = 2k + r con 0 ≤ r < 2, si y sólo si r = 1 se llama 2 2 2 2 2 impar. Luego, n = (2k + 1) = 4k + 4k + 1 y n − 1 = 4k + 4k = 4k(k + 1); y puesto que el producto de dos números consecutivos es par se tiene que, en 2 efecto 8 divide a n − 1, como queríamos demostrar. ♡
Ejercicio Resuelto 1.7 n+1
Demuestre que para todo
n∈Z
se cumple que,
n
y
son coprimos.
Respuesta:
Esta prueba se puede hacer de varias maneras usando algunso
resultados ya obtenidodos:
a > b, entonces (a, b) = (a − b, b), puesto que (n + 1, n) = (1, n) = 1, y por consiguiente son coprimos.
Prueba1: Recordando que si
n+1 > n
tenemos que
1. Por el n y n+ ambos no son nulos su máximo común divisor
Prueba2: De nuevo basta ver que su máximo común divisor positivo es Teorema 1.12, puesto que
positivo existe y es el valor de su combinación lineal positiva con valor mínimo
1 = (−1)n + (1)(n + 1)no hay un entero positivo (n, n + 1) = 1 y por consiguiente n y n + 1 son coprimos.
que en este caso es que
1.
Luego,
menor
(a, b) = (|a|, |b|), podemos considerar, sin perder generalin < 2 ∨ n > 1. Por casos: si n = 0, entonces n+1 = 1 y (0, 1) = 1; si n = 1, entonces n+1 = 2 y (1, 2) = 1; si n > 1, entonces por el Teorema 1.9 existen únicos enteros q y r tales tales que n + 1 = qn + r con 0 ≤ r < n, y como n + 1 = (1)n + 1, tenemos que el resto de dividir a n + 1 entre n es 1, y en base al Teorema 1.17 (Recursión de Euclides) se tiene que (n + 1, n) = (n, 1) = 1. Luego, en efecto, n y n + 1 son coprimos. Prueba3: Puesto que dad, que
n
no es negativo, luego
Prueba4: De nuevo, como Si
n = 0 ∨ n = 1,
(a, b) = (|a|, |b|), basta probarlo para n no negativos. (0, 1) = (1, 2) = 1; si n > 1, por el Teorema Fun-
es claro pues
damental de la Aritmética se puede descomponer como un producto de primos
n = p1 p22 · · · pk con n + 1 = p1 p22 · · · pk + 1, sale que el único divisor positivo común de estos dosnúmeros es 1, porque si d los divide a ambos, entonces también divide a 1, pero los únicos divisores de 1 son ±1 y −1 no es positivo. Luego, (n, n + 1) = 1. ♡ con al menos un primo en la descomposición, digamos que
k > 1,
y por lo tanto
Capítulo 1. Los Números Enteros
22
Un número real se llama racional ssi se puede expresar como el cociente de dos enteros.
Ejercicio Resuelto 1.8
√
2 no es un número racional. √ Respuesta: Por absurdo supongamos que 2 es racional, √ estopes, que existen dos enteros, digamos p y q , primos entre sí, tales que 2 = q . Entonces, se Demuestre que
p2 2 2 2 q 2 y por lo tanto que p = 2q , con lo que tenemos que p es un 2 número par, esto es, 2 divide a p , en concsecuencia divide a p, y por lo tanto p 2 2 es par, esto es, existe un entero, digamos k , tal que p = 2k . Luego, (2k) = 2q 2 2 o equivalentemente q = 2k , lo que dice que también q es par, lo cual es una tiene que
2=
contradicción pues
p
y
q
son coprimos.
♡
Ejercicio Resuelto 1.9 Respuesta:
♡
Ejercicio Resuelto 1.10 Respuesta:
♡
1.9. Ejercicios
Vicente Yriarte
23
1.9. Ejercicios 1. Demuestre que si
a|b ∧ a|c,
2. Demuestre que si
a
y
b
entonces
a|(b ± c).
son enteros positivos tales que
a|b ∧ b|a,
entonces
a = b. 3. Use el Teorema 1.16 y cualquier otra propiedad conocida para determinar el máximo común divisor positivo de los siguientes pares de números.
(24, 30)
Justi ca cada paso y sea e ciente. a) c)
b)
(82, 28)
(120, 270).
4. Use el Algoritmo de Euclides para calcular el máximo común divisor a)
(24, 18)
b)
(7, 35)
c)
(120, 270).
5. Exprese el máximo común divisor de los pares de números siguientes como combinación lineal de dichos números. Esto es, escriba en cada caso
(x, y) = sx + ty , a) (36, 9)
con
s
t
enteros.
b)
(11, 35)
y
6. Demostrar que si
a > 0 ∧ x ̸= 0,
7. Demuestre que si
a|bc ∧ (a, b) = 1, d
8. Demuestre que si
c)
entonces
(ax, ay) = a(x, y).
entonces
a|c.
b y c, es divisor de cualquier b y c, esto es, que d|xb+yc para todo x, y ∈ Z .
es divisor común de
combinación lineal entera de
9. Pruebe que para toda terna de enteros que el máximo común divisor de 10. Demostrar que si
(48, 18).
a, b, c
a, b, c
existen enteros
es igual a
(a, b) = 1 ∧ (a, c) = 1,
entonces
r, s, t
tales
ra + sb + tc. (a, bc) = 1.
11. Probar que todo conjunto de enteros cerrado para la sustracción también es cerrado para la adición. 12. Dé ejemplos de conjuntos de enteros cerrados para la adición, pero no para la sustracción.
a (a, p) = p.
13. Demuestre que si entonces
14. Dados dos enteros
p
es un entero y
a, b,
es un entero positivo tal que
demuestre que si
p
es primo y
p|ab,
entonces
p|a,
p|a ∨
p|b. 15. Pruebe que si
d = (a, b)
y
a|c ∨ b|c,
b√es un d ≤ b.
16. Demostrar que si primo positivo 17.
Computacional:
entonces
entero positivo
n
compuesto,
tiene un divisor
Use el resultado del Ejercicio 16 para diseñar un al-
goritmo e cienteDe orden exacto: entero positivo
d|c.
es primo.
√ Θ( n)
que permita decidir si el
Capítulo 1. Los Números Enteros
24
a|b,
18. Demuestre que si que si
a|b
y
b|a,
|a| ≤ |b| a = ±b.
entonces
entonces
b = 0,
o
y úselo para demostrar
19. Use el principio de buena ordenación para probar que no existe ningún entero positivo entre los enteros cero y uno. 20. Demuestre que si
p|a1 a2 · · · an ,
ai ∈ Z +
con
1 ≤ i ≤ n y p es un número primo tal aj , con 1 ≤ j ≤ n tal que p|aj .
que
entonces existe algún
21. Pruebe que para todos
a, b, k ∈ Z
se tiene que
(a, b) = (a + bk, b).
22. Use el algoritmo de Euclides para calcular el máximo común divisor de las siguientes parejas de números y expréselo como combinación lineal de dichos números. ((a, b) 23. Demuestre que si
a
y
= wa + zb) b
a) 24, 30; b) 240, 125; c) 32, 18.
son enteros positivos y
a > b,
entonces
(a, b) =
(b, a − b). 24.
computacional
Usando el resultado del ejercicio anterior y el hecho de
(a, a) = a, escriba un algoritmo iterativo que reciba como entrada dos enteros positivos a, b y dé como salida en la variable x el máximo común divisor positivo de a, b. Use una variable auxiliar y para almacenar el valor actual de b. No modi que los valores de entrada. Indique la condición de que
parada de la iteración y la función de cota de la misma. 25. Dados dos enteros positivos
a
y
b,
demuestre que si
p1 , p2 , . . . , pk
es una
lista sin repeticiones de todos los primos que aparecen en la descomposición β1 β2 βk αk α1 α2 y b = p1 p2 · · · pk con en primos de a y de b, y a = p1 p2 · · · pk αi ≥ 0 y βi ≥ 0 para todo i, entonces el máximo común divisor positivo m´ın(α1 ,β1 ) m´ın(αk ,βk ) entre a y b es p1 · · · pk y su mínimo común múltiplo es m´ ax(α1 ,β1 ) m´ ax(αk ,βk ) p1 · · · pk . 26.
interesante
a, b
Demuestre que para todo par de números enteros positivos
se cumple que
ab = mcd (a, b) · mcm (a, b).
27. Use el principio de buena ordenación para probar que racional. Sug.: Considere el conjunto S = {x ∈ Z + 28. Decimos que un número entero positivo divisores es
2n,
a) Veri que que
por ejemplo,
28
y
b) Demuestre que si
6
496 son m ∈ Z+
a
y
b
es perfecto si la suma de sus
es perfecto porque
1 + 2 + 3 + 6 = 12.
perfectos. m y 2 − 1 es primo, entonces
es un entero perfecto. (Sug.: Tal vez necesite 29. Si
n
√ 2 no es un número
√ : x 2 ∈ Z + }.
son enteros positivos y
∑n
i=0
ri =
b = pβ1 1 pβ2 2 · · · pβkk ,
r
n+1
2m−1 (2m − 1)
−1 ) r−1
pi son todos a|b si y sólo si
donde los
primos distintos y los βi 's son enteros positivos, entonces αk 1 α2 a = pα 1 p2 · · · pk , y se tiene que 0 ≤ αi ≤ βi .
1.9. Ejercicios
30.
Vicente Yriarte
interesante
25
Dado un entero positivo
n ̸= 1,
basándose en su descompo-
sición en primos, halle una fórmula que permita saber cuántos divisores tiene el número 31.
n,
sin tener que hallarlos.
interesante Demuestre que un número entero positivo
n
es un cuadrado
perfecto si y sólo si tiene un número impar de divisores positivos.
a, b son dos enteros positivos, el conjunto de números sa + tb, donde s, t son enteros positivos, incluye todos los (a, b) mayores que ab.
32. Demuestre que si de la forma múltiplos de
33. Cuantos divisores positivos tiene 34. Si
A = {a1 , a2 , a3 , a4 , a5 }
n
si
n = pα , p
S
α≥0
es un subconjunto de enteros positivos, demues-
tre que existe un subconjunto no vacío elementos de
es primo y
S
de
A
tal que la suma de los
es múltiplo de 5.
a|c, b|c
35. Demuestre que si
y
(a, b) = 1,
entonces
ab|c.
ab es un entero positivo cuadrado tal que (a, b) = 1, a, b son ambos cuadrados. Un entero positivo n se llama cuadrado 2 existe un entero k tal que n = k ; tambié se suele llamar cuadrado
36. Demuestre que si entonces ssi
perfecto. 37. Demuestre que si
n es un entero positivo, entonces n y n + 1 son coprimos.
38. Demuestre que para todo
m, n ∈ Z
39. Pruebe que para todo entero 40.
computacional
k
existe
r∈Z
k
y
k + 1.
Proponga un algoritmo e ciente para hallar el mínimo
a
41. Demuestre que si
42.
m = n + r.
no existe un entero entre
común múltiplo entre dos enteros positivos
entonces
tal que
y
b
a
y
b.
son dos enteros tales que
¾Orden?
(a, 4) = 2
y
(b, 4) = 2,
4|a + b.
computacional Escriba un algoritmo e ciente que permita determinar si dos enteros
a
y
b
son coprimos. ¾
O(lg a)?
n1 , n2 , n3 (n1 , n2 n3 ) = (n1 n2 , n3 ) = 1.
43. Demuestre que los enteros
son coprimos dos a dos si y sólo si
44. Dados dos enteros a y b tales que b > 0, si se tiene que a = qb+r∧0 ≤ r < b ′ ′ ′ ′ y que −a = q b + r ∧ 0 ≤ r < b, entonces si r ̸= 0, entonces r = b − r y ′ ′ q = −(q + 1), y si r = 0, entonces r = r y q = −q . 45. Explique como usar el resultado del Ejercicio 44 para a partir de un algoritmo que resuelve el problema de hallar el máximo común divisor positivo de los dos enteros
a ≥ 0 a.
para cualquier entero
y
b > 0
obtener uno que resuelva el problema
Capítulo 1. Los Números Enteros
26
46. Dados dos enteros a y b tales que b > 0, si se tiene que a = qb+r∧0 ≤ r ′ ′ entonces si b = −b, entonces se tiene que a = −qb = r y 0 ≤ r < b. 47. Muestre que la hipótesis
b>0
|b| > 0 0 ≤ r < |b|.
del Teorema 1.9 por la más débil
seguir siendo cierta si se sustituye también
0≤r