Propiedades de la divisibilidad de los enteros

Vista previa del material en texto

Teoría de Números I
Propiedades de la divisibilidad de los
enteros
Material elaborado por
Osvaldo Vega
Campus Universitario
San Lorenzo, Paraguay
Índice
1. Divisibilidad en Z 3
2. Algoritmo de la división 5
3. Paridad de un entero 6
4. Máximo común divisor de dos enteros 7
5. Primos relativos 9
6. Características del mcd de dos enteros 11
7. El máximo común de más de dos enteros 12
8. Algoritmo Euclidiano 12
9. Mínimo Común Múltiplo 14
10.Números primos y compuestos 16
11.Ecuaciones Diofánticas Lineales 19
Bibliografía 22
2
1. Divisibilidad en Z
La Teoría elemental de números estudia principalmente los números enteros y sus propieda-
des mediante sus propios métodos y técnicas sin involucrar a otros campos de Matemática
además de las elementales. Algunos temas que trata la Teoría elemental de números son la
divisibilidad y las congruencias, y este material pretende brindar los conceptos y fundamen-
tos básicos sobre la divisibilidad en Z.
El desarrollo del material seguirá pincipalmente la misma línea del texto (Filho, 1981), pero
con consultas a libros clásicos de Teoría de números como (Zuckerman, 1976) y (Pettofrez-
zo, 1986).
Definición 1.1. Sean a y b dos números enteros, con a 6= 0. Se dice que a divide a
b si existe un entero q tal que b = a q y se denotará por a | b. Si a no divide a b se
escribirá a - b.
Cuando se escriba a | b se entenderá que a debe ser distinto de cero. La división por cero
no se define.
Otras formas de expresar que a divide a b son: "a es un divisor de b", "a es un factor
de b", "b es un múltiplo de a " o que "b es divisible por a".
Observación 1.1. Si a | b, entonces (−a) | b porque b = aq = (−a)(−q), por lo que los
divisores de un número entero son dos a dos iguales en valor absoluto y de signos opuestos.
Ejemplo 1.1.
a) 3 | 15 porque 15 = 3 · 5.
b) −7 | 42 porque 42 = (−7) · 6.
c) 9 | 9 porque 9 = 9 · 1.
d) 8 | 0 porque 0 = 8 · 0.
e) 4 - 6 porque no existe un entero q tal que 6 = 4 · q.
Teorema 1.1. Si a, b, c y d son enteros cualesquiera, se verifican las siguientes propieda-
des:
i) a | 0
ii) 1 | a
iii) a | a
iv) Si a | 1, entonces a = ±1
v) Si a | b y c 6= 0, entonces c a | c b
vi) Si c a | c b y c 6= 0, entonces a | b
vii) Si a | b y c | d, entonces a c | b d
viii) Si a | b y b | c, entonces a | c
ix) Si a | b y b | a, entonces a = ±b
3
x) Si a | b y b 6= 0, entonces |a| ≤ |b|
xi) Si a | b y a | c, entonces a | (bx+ cy), ∀x, y ∈ Z
Demostración.
i) a | 0 porque 0 = a · 0.
ii) 1 | a porque a = 1 · a.
iii) a | a porque a = a · 1.
iv) Si a | 1, entonces existe q ∈ Z tal que 1 = a · q. La última igualdad implica que
a = q = 1 0 a = q = −1, es decir, a = ±1.
v) Si a | b, entonces existe q ∈ Z tal que b = a q. Multiplicando ambos lados de la
última igualdad por el entero no nulo c tenemos que c b = (c a)q lo que implica que
c a | c b.
vi) Si c a | c b entonces existe q ∈ Z tal que c b = (c a)q; ya que c 6= 0, por la
propiedad cancelativa del producto en Z se tiene que b = a q, lo que permite concluir
que a | b.
vii) Si a | b y c | d, entonces existen q1, q2 ∈ Z tales que b = a q1 y d = c q2. Por lo
tanto b d = (a c)(q1q2) que su vez implica que a c | b d.
viii) Si a | b y b | c, entonces existen q1, q2 ∈ Z tales que b = a q1 y c = b q2.Por lo
tanto c = a(q1q2) que su vez implica que a | c.
ix) Si a | b y b | a, entonces existen q1, q2 ∈ Z tales que b = a q1 y a = b q2. Por
lo tanto a = a(q1q2), del cual se concluye que q1q2 = 1 que a su vez implica que
q2 = ±1 y por consiguiente a = ±b.
x) Si a | b y b 6= 0, entonces existe q ∈ Z−{0} tal que b = a q. Así |b| = |a q| = |a| |q|
y como q 6= 0 se tiene que |q| ≥ 1. Por lo tanto |a| ≤ |b|.
xi) Sean x y y enteros cualesquiera. Si a | b y a | c, entonces existen q1, q2 ∈ Z tales
que b = a q1 y c = a q2. De las dos últimas igualdades tenemos que b x = a(x q1)
y c y = a(y q2) que al sumar miembro a miembro da como resultado b x + c y =
a(x q1 + y q2), lo que nos permite concluir que a | (bx+ cy).
Observación 1.2. Mediante un proceso inductivo se puede generalizar la propiedad xi) del
Teorema 1.1, esto es, si x1, x2, . . . , xn son enteros cualesquiera, y a | b1, a | b2, . . . , a | bn,
entonces a | (b1x1 + b2x2 + · · ·+ bnxn).
Observación 1.3. En Z sea a 6= 0. Si x es un divisor de a , por la propiedad x) del
Teorema 1.1, |x| ≤ |a|, es decir, −|a| ≤ x ≤ |a|. Por lo tanto un entero no negativo tiene
un número finito de divisores.
Ejemplo 1.2. Si a | (3x− 2y), y a | (4x− 3y), vamos a demostrar que a | x.
Si a | (3x − 2y), y a | (4x − 3y), entonces a | [3 · (3x − 2y) + (−2) · (4x − 3y)].
Como 3 · (3x− 2y) + (−2) · (4x− 3y) = x, tenemos que a | x.
4
2. Algoritmo de la división
Teorema 2.1 (Algoritmo de la división). Dados a, b ∈ Z, con b > 0, existen dos números
enteros q y r tal que a = b q + r con 0 ≤ r < b. Los números enteros q y r,
denominados cociente y resto repectivamente en la división de a por b, son únicos.
Demostración. Consideremos el conjunto S = {a− bx|x ∈ Z y a− bx ≥ 0}. El conjunto S
no es vacío porque al ser b positivo se tiene que b ≥ 1, y para x = −|a|,
a− bx = a+ b|a| ≥ a+ |a| ≥ 0
y por lo tanto tenemos al menos un elemento de S. Por el Principio de la buena ordenación,
S tiene un elemento mínimo r. Este elemento cumple:
r ≥ 0 y r = a− bq con q ∈ Z
Así existen q y r en Z tal que a = b q + r. Además r < b pues de lo contrario, es
decir, si r ≥ b tendríamos:
0 ≤ r − b = a− b q − b = a− b (q + 1) < r
que contradice la minimalidad de r ya que a− b (q + 1) sería un elemento de S menor
que r. Ahora solo falta probar la unidad de q y r, para ello supongamos que existen
otros dos enteros q1 y r1, tales que
a = b q1 + r1 con 0 ≤ r1 < b
Entonces, tenemos:
a = b q1 + r1 = b q + r ⇒ r1 − r = b (q − q1) ⇒ b | (r1 − r)
Si suponemos que r1 − r 6= 0, tendremos que |r − r1| > b. Por otro lado, las condiciones
−b < −r ≤ 0 y 0 ≤ r1 < b nos permiten concluir que:
−b < r1 − r < b, equivalentemente |r − r1| < b
llegando así a una contradicción. Luego se tiene que cumplir que r1−r = 0, y como b > 0,
también q − q1 = 0. Es decir, r = r1 y q = q1.
Corolario 2.2. Dados a, b ∈ Z, con b 6= 0, existen dos números enteros q y r tal que
a = b q+ r con 0 ≤ r < |b|. Los números enteros q y r, denominados cociente y resto
repectivamente en la división de a por b, son únicos.
Demostración. Si b > 0 la proposición ya está demostrada. Entonces supongamos que b < 0
y consideremos el entero positivo |b|, por el Teorema 2.1 existen enteros únicos q1 y r
tales que
a = |b| q1 + r con 0 ≤ r < |b|
y al ser b negativo se cumple que |b| = −b, por lo que se tiene
a = b (−q1) + r con 0 ≤ r < |b|
Por lo tanto existen enteros únicos q = −q1 y r tales que
a = b q + r con 0 ≤ r < |b|.
5
Observación 2.1. Si en la división de a por b se tiene que r = 0 entonces a | b y
diremos que la división es exacta. Caso contrario, es decir, si el resto es r 6= 0 se tiene
lo que se denomina una división inexacta. Si la división de a por b es exacta podemos
indicar el cociente por
a
b
o a/b que leeremos "a sobre b".
Ejemplo 2.1. Hallar el cociente q y el resto r al dividir a por b, siendo:
a) a = 45 y b = 7.
Aplicando la división usual tenemos: 45 = 7 · 6 + 3 y como 0 ≤ 3 < 7, entonces
q = 6 y r = 3.
b) a = 71 y b = −15.
Aplicando la división usual tenemos: 71 = (−15) · (−4)+11 y como 0 ≤ 11 < |−15|,
entonces q = −4 y r = 11.
c) a = −98 y b = 45.
Aplicando la división usual tenemos: −98 = 45 · (−3) + 37 y como 0 ≤ 37 < 45,
entonces q = −3 y r = 37.
d) a = −62 y b = −11.
Aplicando la división usual tenemos: −62 = (−11) · 6 + 4 y como 0 ≤ 4 < | − 11|,
entonces q = 6 y r = 4.
Ejemplo 2.2. Demostrar que el cubo de un número entero tiene una de las tres formas
siguientes: 9k , 9k + 1 o 9k + 8.
Sea a un entero cualquiera, por el Algoritmo de la división a = 3q a = 3q + 1 o
a = 3q + 2. Al calcular a3 tenemos:
a3 = (3q)3 = 27q3 = 9(3q3), haciendo k = 3q3 tenemos que a3 = 9k.
a3 = (3q+1)3 = 27q3+27q2+9q+1 = 9(3q3+3q2+q)+1, haciendo k = 3q3+3q2+q
tenemos que a3 = 9k + 1.
a3 = (3q+2)3= 27q3+54q2+36q+8 = 9(3q3+6q2+4q)+8, haciendo k = 3q3+6q2+4q
tenemos que a3 = 9k + 8.
Así, a3 tiene una de las tres formas siguientes: 9k , 9k + 1 o 9k + 8.
3. Paridad de un entero
Definición 3.1. Sea a un entero cualquiera, al dividir a por 2 los posibles restos son
r = 0 y r = 1 . Si r = 0 , se dice que a e un entero par y si r = 1, el número a es
un entero impar.
Observación 3.1. Si a es un entero par tendrá la forma a = 2 q, y si a e un entero impar
tendrá la forma a = 2 q + 1 o esta otra: a = 2 q − 1.
Ejemplo 3.1. Demostrar que todo entero impar tiene la forma 4q + 1 o 4q + 3.
Sea a un número entero impar, entonces a = 2k + 1 para algún entero k. El entero k
puede ser par o impar, por lo que k = 2q o k = 2q+1 . Por lo tanto a = 2(2q)+1 = 4q+1
o a = 2(2q + 1) + 1 = 4q + 3.
6
Ejemplo 3.2. Demostrar que n2 − n es divisible por 2 para cualquier entero n.
Analicemos los casos según la paridad de n.
Si n es par, entonces n = 2q . Luego n2−n = 2q(2q−1) = 2k1, donde k1 = q(2q−1) ∈
Z, así por definición de divisibilidad tenemos que 2 | n2 − n.
Si n es impar, entonces n = 2q + 1 . Luego n2 − n = n(n − 1) = (2q + 1)(2q) =
2q(2q+1) = 2k2, donde k2 = q(2q+1) ∈ Z, así por definición de divisibilidad tenemos que
2 | n2 − n.
Entonces, 2 | n2 − n para cualquier entero n.
4. Máximo común divisor de dos enteros
Definición 4.1. Sean a y b dos números enteros no simultáneamente nulos, el máximo
común divisor de a y b es un entero positivo d tal que:
i) d | a y d | b
ii) Si c | a y c | b , entonces c ≤ d
El máximo común divisor de a y b se denota por mcd(a, b) o simplemente (a, b).
Observación 4.1. Teniendo en cuenta la definición anterior se puede deducir que:
1) Si existe el mcd(a, b) , entonces mcd(a, b) = mcd(b, a).
2) El máximo común divisor de a y b es el mayor de los divisores comunes de a y
b.
3) mcd(0, 0) no está definido.
4) Si a 6= 0 , entonces mcd(a, 0) = |a|.
5) Si a | b , entonces mcd(a, b) = |a|.
6) Si a 6= 0 , entonces mcd(a, 1) = 1.
Ejemplo 4.1. Hallar el mcd(18, 90).
Los divisores positivos y comunes de 18 y 90 son: 1 , 2 , 3 6 y 9. Por lo tanto
mcd(18, 90) = 9.
Ejemplo 4.2. Hallar el mcd(−42, 231).
Los divisores positivos y comunes de −42 y 231 son: 1 , 3 , 7 y 21. Por lo tanto
mcd(−42, 231) = 21.
Teorema 4.1 (Existencia y unicidad del mcd). Si a y b son dos números enteros no
simultáneamente nulos, entonces existe y es único el mcd(a, b). Además existen enteros x
e y tales que mcd(a, b) = ax+ by.
Demostración. Consideremos el conjunto S = {au + bv |u, v ∈ Z y au + bv > 0}. El
conjunto S no es vacío porque uno de los números enteros:
a = a · 1 + b · 0; b = a · 0 + b · 1; −a = a · (−1) + b · 0 y − b = a · 0 + b · (−1)
es positivo y además es un elemento de S .
7
Por el Principio de la buena ordenación S tiene un elemento mínimo d. Entonces existen
x e y tales que d = ax+ by.
Ahora vamos a probar que d = mcd(a, b). Por el Algoritmo de la división existen números
enteros q y r, tales que:
a = dq + r, con 0 ≤ r < d
Despejando r tenemos:
r = a− dq = a− (ax+ by)q = a(1− qx) + b(−qy), con 0 ≤ r < d
Así, r es una combinación lineal de a y b y por la minimalidad de d, no puede darse
que 0 < r < d. Por lo tanto r = 0 y d | a. Análogamente se prueba que d | b.
Por otro lado, si c es un entero positivo tal que c | a y c | b implica que c | ax + by.
Luego c | d por lo que c ≤ d.
Todo lo anterior nos permite concluir que d = mcd(a, b). Ahora solo falta probar la unicidad
del mcd(a, b).
Supongamos que d = mcd(a, b) y d1 = mcd(a, b). Como d | a y d | b, se tiene que
d ≤ d1. De forma análoga se llega a que d1 ≤ d. Por lo tanto d = d1
Observación 4.2.
1) El mcd(a, b) es el menor entero positivo que se puede escribrir como combinación
lineal ax+ by.
2) La forma en que se representa el mcd(a, b) como combinación lineal no es única, pues
si mcd(a, b) = ax+ by, entonces:
mcd(a, b) = a(x+ bz) + b(y − az)
donde z es un entero cualquiera.
3) Pero no toda combinación lineal ax+ by es el mcd(a, b), por ejemplo si mcd(a, b) =
ax+ by, entonces:
z ·mcd(a, b) = azx+ bzy
cualquiera sea el entero z.
Corolario 4.2. Si k es un entero positivo entonces mcd(k a, k b) = kmcd(a, b).
Demostración.
mcd(k a, k b) = menor entero positivo de {(ka)x+ (kb)y : x, y ∈ Z}.
mcd(k a, k b) = menor entero positivo de {k(ax+ by) : x, y ∈ Z}.
mcd(k a, k b) = k· menor entero positivo de {ax+ by : x, y ∈ Z}.
mcd(k a, k b) = kmcd(a, b).
Ejemplo 4.3. Dados los enteros positivos a = 15 y b = 18, el mcd(15, 18) = 3 y
tenemos que:
3 = 15 · (−1) + 18 · 1
Ejemplo 4.4. Dados los enteros a = −21 y b = −35, el mcd(−21,−35) = 7 y tenemos
que:
7 = (−21) · (−2) + (−35) · 1
8
Teorema 4.3. Sean a y b dos números enteros no simultáneamente nulos, entonces el
conjunto de todos los múltiplos de mcd(a, b) = d es:
S = {ax+ by |x, y ∈ Z}
Demostración. Como d|a y d|b, se tiene que d | (ax+ by), para cualesquiera números
enteros x e y, y por consiguiente todo elemento del conjunto S es un múltiplo de
d = mcd(a, b).
Por otro lado, existen enteros x0 e y0 tales que:
d = ax0 + by0
de modo que todo múltiplo kd de d tendrá la siguiente forma:
kd = k(ax0 + by0) = a(kx0) + b(ky0)
por lo que kd ∈ S.
5. Primos relativos
Definición 5.1. Sean a y b dos enteros no simultáneamente nulos. Diremos que a y b
son primos relativos o primos entre sí, si el mcd(a, b) = 1.
Ejemplo 5.1. 7 y 13, −2 y −49, −1 y 142 son ejemplos de primos entre sí.
Observación 5.1. Si a y b son primos relativos, entonces sus únicos divisores comunes
son 1 y −1.
Teorema 5.1. Dos enteros a y b, no simultáneamente nulos, son primos realtivos si y solo
si existen x e y en Z, tales que ax+ by = 1.
Demostración. Si a y b son primos relativos, entonces el mcd(a, b) = 1 y por consi-
guiente existen enteros x e y tal que:
ax+ by = 1.
Recíprocamente, supongamos que existen enteros x e y tales que ax + by = 1. Si
mcd(a, b) = d, entonces d|a al igual que d|b, lo que implica que d|(ax+ by). Pero como
ax + by = 1 se tiene d|1, por consiguiente d = mcd(a, b) = 1. Luego a y b son
primos relativos.
Corolario 5.2. Si el mcd(a, b) = d, entonces el mcd
(
a
d
,
b
d
)
= 1.
Demostración.
Para comenzar observemos que
a
d
y
b
d
pertenecen a Z porque d es un divisor común
de a y b. Teniendo en cuenta lo anterior, si el mcd(a, b) = d, entonces existen enteros x
e y tal que ax+ by = d, y dividiendo ambos lados de la última igualdad por d tenemos:(a
d
)
x+
(
b
d
)
y = 1
Entonces, por el Teorema 5.1 , los enteros
a
d
y
b
d
, son primos relativos, y por tanto
mcd
(
a
d
,
b
d
)
= 1.
9
Ejemplo 5.2.
mcd(−18, 15) = 3 y mcd
(
−18
3
,
15
3
)
= mcd(−6, 5) = 1
.
Corolario 5.3. Si a|b y mcd(b, c) = 1, entonces mcd(a, c) = 1.
Demostración.
Si a|b, existe q ∈ Z tal que b = aq. Por otra parte, si mcd(b, c) = 1 existen enteros x e
y tales que bx+ cy = 1.
Por lo tanto a(qx) + cy = 1, lo que implica que mcd(a, c) = 1.
Corolario 5.4. Si a|c, b|c y mcd(a, b) = 1; entonces ab|c.
Demostración.
Las hipótesis nos llevan a las siguientes implicancias:
a|c⇒ c = aq1, con q1 ∈ Z
b|c⇒ c = bq2, con q2 ∈ Z
mcd(a, b) = 1⇒ ax+ by = 1 con x, y ∈ Z
Multiplicando ambos lados de la última igualdad por c tenemos que acx + bcy = c, y con
las dos primeras implicancias podemos escribir:
c = a(bq2)x+ b(aq1)y = ab(q2x+ q1y)
Por lo tanto ab|c.
Observación 5.2. Solamente las condiciones a|c y b|c no implican ab|c. Por ejemplo
4 | 20 y 10 | 20, pero (4 · 10) - 20. notemos que no se cumple parte de la hipótesis,
mcd(4, 10) = 2 6= 1.
Corolario 5.5. Si mcd(a, b) = 1 = mcd(a, c), entonces mcd(a, bc) = 1.
Demostración.
Por la hipótesis tenemos:
mcd(a, b) = 1⇒ ax+ by = 1, con x, y ∈ Z
mcd(a, c) = 1⇒ az + ct = 1, con z, t ∈ Z
Entonces:
1 = ax+ by(az + ct) = a(x+ byz) + bc(yt)
lo que implica mcd(a, bc) = 1.
Corolario 5.6. Si el mcd(a, bc) = 1, entonces mcd(a, b) = 1 = mcd(a, c).
10
Demostración.
Por hipótesis tenemos:
mcd(a, bc) = 1⇒ ax+ (bc)y = 1, conx, y ∈ Z
De la última igualdad tenemos estas dos implicancias:
ax+ b(cy) = 1⇒ mcd(a, b) = 1
ax+ c(by) = 1⇒ mcd(a, c) =1
que es lo que se quería probar.
Teorema 5.7 (Teorema de Euclides). Si a|bc y mcd(a, b) = 1, entonces a|c.
Demostración.
Por hipótesis tenemos:
a|bc⇒ bc = aq, con q ∈ Z
mcd(a, b) = 1⇒ ax+ by = 1, conx, y ∈ Z
Multiplicando ambos lados de la última igualdad por c, tenemos:
acx+ bcy = c
y como bc = aq, se sigue que:
c = acx+ aqy = a(cx+ qy)⇒ a|c
Observación 5.3. Solamente la condición a|bc no implica que a|c. Por ejemplo, 14|(7 · 10),
pero 14 - 7 y además 14 - 10. Notemos que mcd(14, 7) = 7 6= 1 y mcd (14, 10) = 2 6= 1, es
decir, no se cumplen todas las hipótesis del Teorema 5.7 de Euclides.
6. Características del mcd de dos enteros
Teorema 6.1. Sean a y b dos enteros no simultáneamente nulos, un entero positivo d
es el mcd(a, b) si y solamente si satisface las condiciones:
(1) d|a y d|b
(2) si c|a y si c|b, entonces c|d
Demostración.
(⇒) Supongamos que el mcd (a, b) = d, entonces d|a y d|b, esto significa que la condi-
ción (1) es satisfecha. Por otra parte existen enteros x e y tal que ax+ by = d y por
lo tanto, si c|a y si c|b entonces c|(ax + by) y c|d, esto significa que la condición (2)
también se cumple.
(⇐) Recíprocamente, sea d un entero positivo cuaquiera que satisfaga las condiciones
(1) y (2). Entonces, por la condición (2), todo divisor común c de a y b también es
divisor de d, esto es, c|d, y esto implica c ≤ d. Luego d es el mcd(a, b).
11
7. El máximo común de más de dos enteros
Definición 7.1. Sean a, b y c tres números enteros no simultáneamente nulos, el
máximo común divisor de a, b y c es el entero positivo d tal que:
i) d | a, d | b y d | c
ii) Si e | a, e | b y e | c , entonces e ≤ d
El máximo común divisor de a, b y c se denota por mcd(a, b, c) o simplemente (a, b, c).
Teorema 7.1. Si a, b y c son tres números enteros no simultáneamente nulos, entonces
mcd(a, b, c) = mcd(mcd(a, b), c).
Demostración.
Si mcd(a, b, c) = d1 y mcd(a, b) = d2, entonces d1 | a, d1 | b, d1 | c y además existen
enteros x e y tal que ax + by = d2. Por otro lado, como d1 | a, y d1 | b, se tiene que
d1 | (ax+ by), es decir, d1 | d2. Así d1 es un divisor común de d2 y c.
También, si f es un divisor común de c y d2, se tiene que f | a, f | b y f | c, lo que
implica que f ≤ d1. Luego, d1 = mcd(d2, c), esto es, mcd(a, b, c) = mcd(mcd(a, b), c).
Definición 7.2. Sean a1, a2, . . . , y an números enteros no simultáneamente nulos, el
máximo común divisor de a1, a2, . . . , y an es el entero positivo d tal que:
i) d | ai para i = 1, 2, . . . , n.
ii) Si c | ai para i = 1, 2, . . . , n, entonces c ≤ d.
El máximo común divisor de a1, a2, . . . , y an se denota por mcd(a1, a2, . . . , an) o
simplemente (a1, a2, . . . , an).
Observación 7.1. Si a1, a2, . . . , y an son n números enteros no simultáneamente nulos,
entonces mcd(a1, a2, . . . , an) = mcd(mcd(a1, a2, . . . , an−1), an). La demostración es análoga
a la demostración del Teorema 7.1.
Definición 7.3. Sean a1, a2, . . . , y an números enteros no simultáneamente nulos. Dire-
mos que a1, a2, . . . , y an son primos relativos o primos entre sí si el mcd(a1, a2, . . . , an) =
1 sin que sean necesariamente primos entre sí dos a dos.
8. Algoritmo Euclidiano
Sean a y b dos números enteros positvos tales que a > b. Por el Algoritmo de la división
existen qi y ri tales que:
a = b q1 + r1 con 0 < r1 < b;
b = r1 q2 + r2 con 0 < r2 < r1;
r1 = r2 q3 + r3 con 0 < r3 < r2;
...
...
rk−3 = rk−2 qk−1 + rk−1 con 0 < rk−1 < rk−2;
rk−2 = rk−1 qk + rk con 0 < rk < rk−1;
rk−1 = rk qk+1 + 0
12
Notemos que r1, r2, . . . , rk−1, rk forman una suceción estrictamente decreciente de números
enteros positivos, por lo tanto la sucesión termina en algún rk. En este proceso, denominado
Algoritmo Euclidiano se llega a mcd(a, b) = rk. Demostremos esta última igualdad, es
decir, demostremos estas dos condiciones:
(1) rk|a y rk|b
(2) si c|a y si c|b, entonces c|rk
Empecemos demostrando la primera. De la última igualdad tenemos que rk|rk−1 y reem-
plazando rk−1 = rk qk+1 en la penúltima igualdad, se tiene que:
rk−2 = rk−1 qk + rk = rk qk+1 qk + rk = rk(qk+1 qk + 1)
de donde se deduce que rk|rk−2. Reemplazando rk−2 y rk−1 en la antepenúltima
igualdad, se tiene que:
rk−3 = rk−2 qk−1 + rk−1 = rk(qk+1 qk + 1) qk−1 + rk qk+1 = rk(qk+1 qk qk−1 + qk−1 + qk+1)
Así rk|rk−2. Repitiendo el proceso para rk−3, rk−4, . . . , r2, r1 llegamos a que rk|r2 y
rk|r2 y por lo tanto a que rk|b. De la primera igualdad se concluye que rk|a y por lo tanto
la condición (1) queda probada.
Para probar la condición (2) partimos de la suposición de que c|a y c|b . Entonces,
la primera igualdad implica c|r1, la segunda c|r2,. . ., y así sucesivamente hasta que la
penúltima igualdad implica que c|rk.
Por lo tanto mcd(a, b) = rk.
Observación 8.1. Notemos que el Algoritmo Euclidiano se puede aplicar para hallar el máxi-
mo común divisor de dos enteros no nulos cualesquiera ya que mcd(a, b) = mcd(−a,−b) =
mcd(−a, b) = mcd(a,−b).
Ejemplo 8.1.
Vamos a probar que mcd(−21,−35) = 7.
Notemos que mcd(−21,−35) = mcd(35, 21) y apliquemos el algoritmo euclidiano:
35 = 21 · 1 + 14
21 = 14 · 1 + 7
14 = 7 · 2 + 0
El último resto distinto de cero es 7, luego mcd(−21,−35) = mcd(35, 21) = 7.
Observación 8.2. El Algoritmo Euclidiano puede utilizarse para hallar enteros x e y tales
que mcd(a, b) = ax + by. Esto se puede lograr escribiendo los sucesivos restos ri como
una combinación lineal de a y b partiendo de r1 = a+ b(−q1).
Ejemplo 8.2. En el Ejemplo 8.1 hemos probado que mcd(−21,−35) = 7. Ahora vamos a
encontrar x y y tal que:
7 = (−21) · x+ (−35) · y
Cuando habíamos aplicado el Algoritmo Euclidiano, tuvimos esta lista de igualdades:
35 = 21 · 1 + 14
21 = 14 · 1 + 7
14 = 7 · 2 + 0
13
De la primera igualdad tenemos que:
14 = 35 + (−1) · 21
Llevando en la segunda:
21 = (35 + (−1) · 21) · 1 + 7
Despejando 7 que es el máximo común divisor, llegamos a:
7 = 21 · 2 + 35 · (−1)
Luego:
7 = (−21) · (−2) + (−35) · 1.
Por lo que x = −2 e y = 1.
9. Mínimo Común Múltiplo
Definición 9.1. Sean a y b dos números enteros no nulos. Se denomina múltiplo común
de a y b a todo entero m tal que a | m y b | m.
Definición 9.2. Sean a y b dos números enteros no nulos. Se denomina mínimo común
múltiplo de a y b al entero positivo m que cumple las siguientes condiciones:
i) a | m y b | m
ii) Si a | c y b | c , entonces m ≤ c
El mínimo común múltiplo de a y b se denota por mcm(a, b) o [a, b].
Observación 9.1. Teniendo en cuenta la definición mínimo común múltiplo se puede deducir
que:
1) Si existe el mcm(a, b) , entonces mcm(a, b) = mcm(b, a).
2) El mínimo común múltiplo de a y b es el menor de los múltiplos comunes positivos
de a y b.
3) Por el Principio de la buena ordenación, el conjunto de los múltiplos comunes positivos
de a y b tiene un elemento mínimo y es único. Por lo tanto, si a y b son enteros
no nulos, el mcm(a, b) existe y es único.
4) mcm(a, b) ≤ |a b|.
5) Si a | b , entonces mcm(a, b) = |b|.
6) mcd(a, b) = mcd(−a, b) = mcd(a,−b) = mcd(−a,−b).
Ejemplo 9.1. Vamos a calcular mcm(−6, 7)
Los múltiplos de −6 son: 0,±6,±12,±18,±24,±30,±36,±42,±48, . . ., y
los múltiplos de 7 son: 0,±7,±14,±21,±28,±35,±42,±49,±56, . . ..
El primer múltiplo común positivo es 42, luego mcm(−6, 7) = 42.
Teorema 9.1. Sean a y b enteros no nulos y sea c un múltiplo común de a y b
entonces mcm(a, b) | c.
14
Demostración. Si mcm(a, b) = m entonces a | m y b | m. Por otro lado, por hipótesis
a | c y b | c.
Por el Algortimo de la división, existen q y r en Z tales que:
c = mq + r con 0 ≤ r < m
Despejando r se tiene tenemos: r = c+m (−q) y como a | m, b | m, a | c y b | c;
se concluye que a | r y b | r. Por lo tanto r no puede ser menor que el mínimo común
múltilplo m. Luego r = 0 y m | c.
Teorema 9.2 (Relación entre el mcd y el mcm). Si a y b son enteros positivos, entonces
mcd(a, b) ·mcm(a, b) = ab.
Demostración. Supongamos que mcd(a, b) = d y que mcm(a, b) = m. Entonces
a
d
,
b
d
,
m
a
y
m
b
son números enteros; además a |
(
a · b
d
)
y b |
(
b · a
d
)
, lo que implica que
a · b
d
=
a b
d
esun múltiplo común de a y b.
Por el Teorema 9.1, existe un entero positivo k tal que
a b
d
= mk. De esta última igualdad
se puede deducir estas dos:
a
d
=
m
b
· k y b
d
=
m
a
· k. Por lo tanto k es un divisor común
de los primos relativos
a
d
y
b
d
. Luego k = 1 y en consecuencia
a b
d
= m, es decir,
a b = dm = mcd(a, b) ·mcm(a, b).
Ejemplo 9.2. Vamos a calcular mcm(−6, 7) utilizando el Teorema 9.2.
Apliquemos el Algoritmo Euclidiano para calcular mcd(−6, 7) = mcd(7, 6):
7 = 6 · 1 + 1
6 = 1 · 6 + 0
Luego mcd(−6, 7) = mcd(7, 6) = 1. Ahora, por el Teorema 9.2, tenemos:
7 · 6 = mcd(7, 6) ·mcm(7, 6)
42 = 1 ·mcm(−6, 7)
Así mcm(−6, 7) = 42.
Corolario 9.3. Si a y b son enteros positivos, entonces mcm(a, b) = ab si y solo si
mcd(a, b) = 1.
Demostración.
Por un lado, si mcm(a, b) = ab por el Teorema 9.2 se tiene que a b = mcd(a, b) · (a b).
Cancelando a b queda que mcd(a, b) = 1.
Recíprocamente, si mcd(a, b) = 1, por el Teorema 9.2 se tiene que a b = 1 ·mcm(a, b) =
mcm(a, b).
Definición 9.3. Sean a1, a2, . . . , y an números enteros no nulos, el mínimo común
múltiplo de a1, a2, . . . , y an es el entero positivo m tal que:
i) ai | m para i = 1, 2, . . . , n.
ii) Si c es un entero positivo tal que ai | c para i = 1, 2, . . . , n, entonces m ≤ c.
El mínimo común múltiplo de a1, a2, . . . , y an se denota por mcm(a1, a2, . . . , an) o
[a1, a2, . . . , an].
15
10. Números primos y compuestos
Definición 10.1. Un número entero positivo p mayor que 1 se dice que es un número
primo o simplemente primo si los únicos divisores positivo de p son p y 1. Un número
entero positivo p mayor que 1 que no es primo se dice que es un número compuesto o
simplemente compuesto.
Teorema 10.1. Si p es un número primo que no divide al entero a, entonces a y p
son primos realtivos.
Demostración. Supongamos que mcd(a, p) = d, entonces d | p y d | a. Pero como p
es primo d = 1 o d = p. Esta última igualdad no es posible por la hipótesis del teorema
por lo que d = 1. Luego a y p son primos relativos.
Corolario 10.2. Si p es un número primo tal que p | ab, entonces p | a o p | b.
Demostración. Si p | a el Corolario ya está probado. Supongamos que p - a, por el
Teorema 10.1 se tiene que mcd(a, p) = 1. Luego por el Teorema 5.7 de Euclides p | b.
La demostración del siguiente corolario se puede hacer por inducción matemática.
Corolario 10.3. Si p es un número primo tal que p | a1a2 · · · an, entonces p | aj para
alguna j, 1 ≤ j ≤ n.
Corolario 10.4. Si p, q1, q2, . . . , qn son primos y p | q1q2 · · · qn, entonces p = qj para
alguna j, 1 ≤ j ≤ n.
Demostración. Por el Corolario 10.3, existe una j tal que p | qj . Pero como qj es primo
p = 1 o p = qj . La igualdad p = 1 es imposible ya que p es primo, por lo tanto
p = qj .
Teorema 10.5. Si a es un número compuesto, entonces a tiene un divisor primo p.
Demostración. Sea a un número compuesto. Consideremos el conjunto
S = {x ∈ Z : x | a y 1 < x < a}, el conjunto S 6= ∅ ya que a es un número
compuesto y por lo tanto tendrá un divisor que esté entre 1 y a. Por el Teorema de la
buena ordenación, S tiene un elemento mínimo p. Si p fuera compuesto tendría un
divisor d tal que 1 < d < p. Entonces d sería un divisor de a tal que 1 < d < a, lo
que contradice la minimalidad de p. Luego p es primo.
Teorema 10.6 (TEOREMA FUNDAMENTAL DE LA ARITMÉTICA). Todo entero a > 1
puede expresarse como un producto de un número finito de primos.
Demostración. Sea a un número entero mayor que 1. Si a es primo ya terminamos,
caso contrario, si a es un número compuesto, por el Teorema 10.5, a tiene un factor
primo p1. Por lo tanto, existe un entero positivo a1 tal que:
a = p1 a1 con 1 < a1 < a
Si a1 es primo ya no hay nada que probar. Si a1 fuera compuesto nuevamente por por el
Teorema 10.5, a1 tendría un factor primo p2 y existiría un entero positivo a2 tal que:
16
a = p1 p2 a2 con 1 < a2 < a1 < a
Repitiendo el mismo razonamiento, llegamos a la sucesión decreciente de números enteros
positivos
a > a1 > a2 > a3 > · · · > 1
Este proceso debe terminar, es decir, debe existir ak = pk que sea primo, ya que solo
existe un número finito de enteros positivos menores que a. Así,
a = p1 p2 · · · pk
es una expresión de a como un producto de un número finito de primos.
Corolario 10.7. La descomposición de un entero a > 1 en un producto de primos es única,
salvo el orden de los factores.
Demostración. Sea a un número entero mayor que 1 y supongamos que:
a = p1 p2 · · · pr = q1 q2 · · · qs
son dos factorizaciones de a en primos. No perdemos generalidad si suponemos r ≤ s.
Además haciendo un reordenamiento, podemos suponer que p1 ≤ p2 ≤ · · · ≤ pr y que
q1 ≤ q2 ≤ · · · ≤ qs.
La igualdad p1 p2 · · · pr = q1 q2 · · · qs implica que p1 | q1 q2 · · · qs, y como p1 es primo,
entonces existe j tal que p1 = qj . Luego
p1 ≥ q1.
Análogamente, existe k tal que q1 = pk, por tanto
q1 ≥ p1.
Así p1 = q1. Al reemplazar q1 por p1 en p1 p2 · · · pr = q1 q2 · · · qs, y cancelando
posteriormente p1, tenemos:
p2 p3 · · · pr = q2 q3 · · · qs
Repitiendo el mismo procedimiento para los demás pi, llegaremos a:
1 = qr+1 qr+2 · · · qs
Para no llegar a una contradicción, se debe cumplir que r = s. Luego la descomposición de
un entero a > 1 en un producto de primos es única, salvo el orden de los factores.
La demostración del siguiente Corolario es trivial, por eso dejamos como un ejercicio al
estudiante.
Corolario 10.8. Sea a un entero mayor 1, entonces a admite una única descomposición
de la forma a = pn11 p
n2
2 · · · p
nk
k , donde los ni son enteros positivos y los pj son primos.
Definición 10.2. La descomposión de un entero a > 1 un entero mayor 1 en la forma
a = pn11 p
n2
2 · · · p
nk
k , se denomina descomposición canónica de a.
Teorema 10.9. El conjunto de los números primos es infinito.
17
Demostración. Supongamos que la cantidad de números primos es finita y sea p el mayor
de todos, y consideremos el entero
a = 2 · 3 · 5 · 7 · 11 · · · p+ 1
donde 2 · 3 · 5 · 7 · 11 · · · p es el producto de todos los números primos. Claramente a > p
por lo que a no es un número primo. Por otro lado, si a fuera un compuesto tendría
un factor primo menor que él, pero la divisón de a por un primo menor que él deja como
resto 1, entonces tampoco es posible que a fuera compuesto. Llegamos así a un absurdo.
Luego el conjunto de los números primos es infinito.
Teorema 10.10. Sea a un entero compuesto mayor 1, entonces a tiene un divisor primo
p ≤
√
a.
Demostración. Si a es un número entero compuesto mayor que 1, entonces tiene una
factorización
a = b · c
donde b y c son enteros tales que 1 < b < a y 1 < b < a. No perdemos generalidad
si suponemos que b ≤ c, y con esta suposición tenemos que:
a = b · c ≥ b2
que implica lo siguiente:
b ≤
√
a
Por otro lado, por el Teorema Fundamental de la Aritmética, b tiene un factor primo p, y
como b | a, entonces p también es un factor primo de a tal que p ≤ b ≤
√
a. Por lo tanto
a tiene un divisor primo p ≤
√
a.
Observación 10.1. Existe un método para obtener la lista completa de los números primos
que son menores o iguales que un entero positivo n. Dicho método, denominado criba de
Eratóstenes, es razonable cuando n es pequeño. El método consiste en escribir la lista de
los enteros positivos menores o iguales a n a partir de 2 y luego ir tachando los números
compuestos de la siguiente manera: se tachan primero los múltiplos de 2 excepto el mismo
2; seguidamente se tachan los múltiplos de 3 excepto el mismo 3; continuamos tachando
los múltiplos de 5 excepto el mismo 5, y así sucesivamente tachamos los múltiplos de
un primo p excepto el mismo p. Todos los tachados son números compuestos y algunos
son tachados más de una vez. El proceso termina cuando todos los múltiplos de todo primo
p ≤
√
n, excepto el mismo p, se hayan tachado. Los números que quedan sin tachar son
los números primos menores o iguales que n.
2 3 �4 5 ��6
7 ��8 ��9 ��10 11 ��12
13 ��14 ��15 ��16 17 ��18
19 ��20 ��21 ��22 23 ��24
��25 ��26 ��27 ��28 29 ��30
Tabla 1: Criba de Eratóstenespara n = 30.
18
11. Ecuaciones Diofánticas Lineales
Definición 11.1. Una ecuación diofántica lineal con incógnitas x e y es una ecuación
de la forma:
ax+ by = c
donde a, b y c son números enteros con a · b 6= 0.
Todo par de enteros x0, y0 tal que ax0+ by0 = c es una solución entera o simplemente
una solución de la ecuación diofántica lineal ax+ by = c.
Ejemplo 11.1. En la ecuación diofántica lineal con dos incógnitas 12x+ 4y = 8, tenemos
que:
12 · 1 + 4 · (−1) = 8
12 · 2 + 4 · (−4) = 8
12 · 0 + 4 · 2 = 8
Por lo tanto, los pares de enteros: 1 y − 1, 2 y − 4, 0 y 2 son soluciones de la ecuación
diofántica lineal 12x+ 4y = 8.
Observación 11.1. No toda ecuación diofántica lineal cuenta con solución, por ejemplo, la
ecuación diofántica lineal
3x+ 6y = 14
no tiene solución porque si la igualdad
3x0 + 6y0 = 3(x0 + 2y0) = 14
es verdadera para ciertos enteros x0 e y0, se tendría que 3 | 14, y sabemos que este
hecho no es cierto.
Notemos que 3 = mcd(3, 6) no divide a 14.
En general, la ecuación diofántica lineal ax+ by = c no tendrá solución si mcd(a, b) - c.
Teorema 11.1 (Condición necesaria y suficiente para existencia de solución de una ecuación
diofántica lineal). La ecuación diofántica lineal ax + by = c tiene solución si y sólo si
mcd(a, b) | c.
Demostración. Supongamos que la ecuación diofántica lineal ax + by = c tiene una so-
lución, es decir, que existen x0 e y0 en Z, tal que ax0 + by0 = c. Por otro lado, si
mcd(a, b) = d, entonces existen los enteros r y s tales que a = dr y b = ds, entonces
tenemos que:
c = ax0 + by0 = drx0 + dsy0 = d(rx0 + sy0)
y como (rx0 + sy0) ∈ Z, mcd(a, b) | c.
Recíprocamente, supongamos que mcd(a, b) = d y que d | c, esto es, que existe q ∈ Z
tal que c = dq.
Siendo mcd(a, b) = d, existen enteros x0 e y0 tales que
d = ax0 + by0
lo que implica que:
c = dq = (ax0 + by0)q = a(qx0) + b(qy0)
19
esto es, el par de enteros:
x = qx0 = (c/d)x0, y = qy0 = (c/d)y0
es una solución de la ecuación diofántica lineal ax+ by = c.
Teorema 11.2 (Soluciones de la ecuación diofántica ax + by = c). Si mcd(a, b) | c y el par
de enteros x0, y0 es una solución (particular) de la ecuación diofántica lineal ax+ by = c,
entonces todas las soluciones de esta ecuación son dadas por las formulas:
x = x0 + (b/d)q, y = y0 − (a/d)q
donde q es un entero arbitrario.
Demostración. Supongamos que el par de enteros x0, y0 es una solución particular de
la ecuación ax + by = c, y sea x1, y1 otra solución cualesquiera de esta ecuación.
Entonces, tenemos:
ax0 + by0 = c = ax1 + by1
del que sigue que:
a(x1 − x0) = b(y0 − y1).
Siendo mcd(a, b) = d, existen enteros r y s tales que a = dr y b = ds, con r y s
primos relativos. Sustituyendo estos valores de a y b en la igualdad anterior y cancelando
el factor d, obtenemos:
r(x1 − x0) = s(y0 − y1).
Entonces, r|s(y0 − y1), y como mcd(r, s) = 1 implica que r|(y0 − y1), esto es:
y0 − y1 = rq y x1 − x0 = sq
donde q es un entero. Por tanto, tenemos:
x1 = x0 + sq = x0 + (b/d)q
y1 = y0 − rq = y0 − (a/d)q.
Por otro lado, x1 = x0 + (b/d)q e y1 = y0− (a/d)q satisfacen la ecuación diofántica lineal
ax+ by = c, para todo entero q, pues tenemos que:
ax1 + by1 = a[x0 + (b/d)q] + b[y0 − (a/d)q] = (ax0 + by0) + (ab/d− ab/d)q = c+ 0 · q = c
Observación 11.2. En el Teorema 11.2 se concluye que, si mcd(a, b) | c, entonces la
ecuación diofántica lineal ax+ by = c admite infinitas soluciones y todas las soluciones se
pueden obtener a partir de una particular.
La demostración del siguiente corolario es bastante trivial teniendo en cuenta el Teorema
11.2
Corolario 11.3. Si mcd(a, b) = 1, y si el par de enteros x0, y0 es una solución particular
de la ecuación diofántica lineal ax+by = c, entonces todas las soluciones de esta ecuación
son dadas por las fórmulas:
x = x0 + bq, y = y0 − aq
donde q es un entero arbitrario.
20
Ejemplo 11.2. Determine todas las soluciones de la ecuación diofántica lineal
14x+ 22y = 50.
Primeramente calculamos el mcd(14, 22) aplicando el algoritmo de Euclides:
22 = 14 · 1 + 8
14 = 8 · 1 + 6
8 = 6 · 1 + 2
6 = 2 · 3
Por lo tanto mcd(14, 22) = 2 y como 2 | 50, la ecuación diofántica 14x + 22y = 50
tiene solución. A continuación, vamos a obtener la expresión del entero 2 = mcd(14, 22)
como combinación lineal de 14 y 22:
2 = 8− 6 = 8− (14− 8) = (22− 14)− 14 + (22− 14) = 14 · (−3) + 22 · 2
O sea:
2 = 14 · (−3) + 22 · 2
Multiplicando ambos miembros de esta igualdad por 50/2 = 25, obtenemos:
50 = 14 · (−75) + 22 · 50.
Entonces, el par de enteros x0 = −75, y0 = 50 es una solución particular de la ecuación
14x+ 22y = 50 y la solución general sería:
x = −75 + (22/2)q = −75 + 11q
y = 50− (14/2)q = 50− 7q
donde q es un entero arbitrario.
Ejemplo 11.3. Resolver la ecuación diofántica lineal
35x+ 28y = 100.
Como el mcd(35, 28) = 7 y como 7 - 100, la ecuación 35x+ 28y = 100 no tiene solución.
21
Bibliografía
[1] Zuckerman, H. & Niven, I. (1976). Introducción a la Teoría de los Números. México:
Limusa.
[2] de Alencar Filho, E. (1981). Teoria elementar dos números. Sao Paulo: Nobel.
[3] Pettofrezzo, A. (1986). Introducción a la teoría de números. México: Prentice Hall.
22