Divisibilidad [1] M´ ultiplos y divisores

Divisores. Definici´ on. Un n´ umero entero m es divisor de un n´ umero entero a si hay un n´ umero entero q tal que a = mq. Se indica esta relaci´ on escribiendo m | a, y su negaci´ on se denota m  | a.

Notas y ejemplos. • 8 | 24, −6 | 24, • 8  | 12,

7 | 7, −1 | 7.

12  | 8, −6  | 15,

7  | 1,

18  | 6.

• Seg´ un la definici´ on, si m es un divisor de a, entonces hay un entero q tal que a = mq; n´ otese que q es tambi´en un divisor de a. • Para cualquier entero a se cumplen las igualdades a = a.1 = (−a)(−1) = 1.a = (−1)(−a), por tanto a, −a, 1, −1 son divisores de a y, en particular, el conjunto de los divisores de un entero cualquiera es no vac´ıo. • Si m es un divisor de a y a = 0, digamos a = mq, entonces |a| = |mq| = |m| |q|; de donde |m| ≤ |a|, y − |a| ≤ m ≤ |a| . Por tanto se tiene que todo divisor de un entero a (a = 0) est´a comprendido entre − |a| y |a|; en particular: el conjunto de los divisores de un entero a no nulo es finito. • Para cualquier entero m se tiene 0 = m0; por tanto m | 0. En particular 0 | 0. Si a es un entero, a = 0, entonces a = 0q para todo entero q; por tanto 0  | a, si a = 0. • El conjunto de los divisores de 12 es {1, −1, 2, −2, 3, −3, 4, −4, 6, −6, 12, −12}. • El conjunto de los divisores de 7 es {1, −1, 7, −7}. • El conjunto de los divisores de 1 es {1, −1}. [ Se tiene 1 × 1 = (−1) × (−1) = 1; y si u y v son enteros tales que uv = 1, entonces |u| |v| = |uv| = 1, de donde |u| = 1 = |v|, por tanto debe ser u = v = 1 o´ u = v = −1 ]

Un test efectivo de divisibilidad. ¿C´omo decidir si un entero m = 0 es divisor o no de un entero a? Recu´erdese la propiedad de la divisi´ on: Dados a, m ∈ Z, m = 0, existen enteros qm (a) y rm (a) u ´nicos que cumplan a = mqm (a) + rm (a) y 0 ≤ rm (a) < |b| Esta propiedad proporciona un criterio eficiente de divisiblidad:

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

1

Proposici´ on. Para que un entero m sea divisor de un entero a es necesario y suficiente que se cumpla una de las dos condiciones siguientes: (a) m = 0 y a = 0, o´ (b) m = 0 y rm (a) = 0. Demostraci´ on. Es inmediata.

Ejemplos. • ¿Es 17 un divisor de 2096? Realizando la divisi´ on de 2096 entre 17 se obtiene 2096 = 17 × 123 + 5; con lo que r17 (2096) = 5 = 0 y, por tanto, 17  | 2096. • 17 | 9809, porque r17 (9809) = 0.

Enteros asociados. La relaci´on de divisibilidad en el conjunto de los enteros cumple las siguientes propiedades: – Es reflexiva (para todo entero a se tiene a | a). – Es transitiva (si a | b y b | c, entonces a | c). – No es antisim´etrica (7 | −7, −7 | 7 y 7 = −7). Por tanto la relaci´ on de divisibilidad no es de orden el el conjunto Z de los enteros. Definici´ on. Dos enteros a y b son asociados si a | b y b | a; en este caso se pone a ∼ b. Lema. La relaci´on “es asociado de” (∼) es de equivalencia en el conjunto Z de los enteros. Demostraci´ on. Es sencilla y se deja como ejercicio. Veamos c´omo son las clases de equivalencia de enteros m´odulo la relaci´ on de equivalencia ∼. Se cumple 0 ∼ 0; si a ∼ 0, entonces a = 0, por tanto 0 es el u ´nico asociado de 0. Si a ∼ b, y a = 0 o´ b = 0, entonces b = aq y a = bq
, por tanto a = 0 y b = 0 y a = aqq
, con lo que (por la propiedad de simplificaci´ on en Z) 1 = qq
; debe ser q = q
= 1 o´ q = q
= −1, de aqu´ı se obtiene a = b ´o a = −b. Rec´ıprocamente, si a = b o si a = −b, entonces (obviamente) a ∼ b. Por tanto, para cualquier entero a, la clase de a m´odulo ∼ es [a]∼ = {a, −a} N´ otese que “el paso” del conjunto Z al correspondiente conjunto cociente Z/∼ f

: Z → a →

Z/∼ [a]∼ = {a, −a}

consiste en identificar cualquier entero a con su opuesto −a. Convendremos en escoger como representante de cualquier clase de equivalencia [a]∼ al entero no negativo |a| de ese conjunto. Dado que, para enteros cualesquiera a y b, a ∼ b si, y s´olo si, |a| = |b|, la aplicaci´ on f induce una biyecci´ on f

: Z/∼ → [a]∼ →

N |a|

La relaci´on de divisibilidad en el conjunto de los enteros no negativos (esto es, en el conjunto de los n´ umeros naturales) es de orden; n´ otese que esta relaci´on de orden no es lineal (hay elementos que no son comparables, p. e. 8  | 12 y 12  | 8).

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

2

M´ ultiplos e ideales Definici´ on. Un entero a es m´ ultiplo de un entero m si m es un divisor de a. Se denota (m) al conjunto de los m´ ultiplos de m: (m) = {a | a = mz, z ∈ Z} = {mz | z ∈ Z}. Ejemplos. • • • •

(7) = (−7) = {. . . , −7n, . . . , −21, −14, −7, 0, 7, 14, 21, . . . , 7n, . . .}, (n ∈ N) (12) = (−12) = {. . . , −12t, . . . , −36, −24, −12, 0, 12, 24, 36, . . . , 12t, . . .}, (t ∈ N) (0) = {0}. (1) = Z = (−1).

Proposici´ on. Sean a y m enteros, las relaciones siguientes son equivalentes: (1.) a es m´ ultiplo de m, (2.) m | a, (3.) a ∈ (m), (4.) (a) ⊆ (m). Demostraci´ on. Es elemental y se deja como ejercicio. Proposici´ on. Sean a y b n´ umeros enteros. (a) = (b) si, y solamente si, a ∼ b; es decir, si, y s´olo si, a = b ´o a = −b. Si a > 0, entonces a es el menor entero positivo en (a). Demostraci´ on. Es elemental y se deja como ejercicio. • En la figura adjunta se pretende ilustrar la equivalencia de la relaci´ on m | a entre enteros del conjunto {2, 3, 4, 5, 6, 8, 9, 10, 12, 24, 30, 60} y la relaci´ on (a) ⊆ (m) entre los respectivos conjuntos de m´ ultiplos: 60

24

(2)

30

(4)

(3)

(6)

(5)

(10)

(9) 8

12

(8) 9

4

6

(12)

10 (24)

2

3

(30)

5 (60)

En el diagrama de la izquierda un segmento ascendente desde a hasta b significa a | b, mientras que en el diagrama de la derecha un segmento ascendente desde (b) hasta (a) significa (b) ⊂ (a).

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

3

El conjunto (m) de los m´ ultiplos de un entero cualquiera m verifica tres propiedades formales, especialmente importantes, relacionadas con las operaciones de adici´on y multiplicaci´ on y que se exponen en la siguiente Proposici´ on. Para cualquier entero m se cumplen: (1.) 0 ∈ (m). (2.) Si a, b ∈ (m), entonces a + b ∈ (m). (3.) Si z ∈ Z y a ∈ (m), entonces az ∈ (m). Demostraci´ on. (1.) 0 = m0. (2.) Si a = mza y b = mzb con za , zb ∈ Z, entonces a + b = mza + mzb = m(za + zb ) ∈ (m). (3.)

Si a = mza , entonces az = m(za z) ∈ (m).

Dicho en otra forma: (1.) El elemento neutro 0 es m´ ultiplo de cualquier entero m. (2.) La suma de dos m´ ultiplos de un entero m es un m´ ultiplo de m. (3.) Todo m´ ultiplo de un m´ ultiplo de un entero m es un m´ ultiplo de m. Como consecuencias se tienen: – (m) = ∅, porque 0 ∈ (m). – Si a ∈ (m), entonces −a = −1a ∈ (m); es decir, el opuesto de un m´ ultiplo de m es tambi´en un m´ ultiplo de m. – Si a, b ∈ (m), entonces a − b = a + (−b) ∈ (m); es decir, dos m´ ultiplos de m difieren en un m´ ultiplo de m. Definici´ on. Un ideal del anillo Z de los enteros es un subconjunto I de Z tal que: (1.) 0 ∈ I. (2.) Si a, b ∈ I, entonces a + b ∈ I. (3.) Si z ∈ Z y a ∈ I, entonces az ∈ I. Ejemplo. Para cada entero m, el conjunto (m) de los m´ ultiplos de m es un ideal de Z. Una propiedad crucial del anillo de los enteros es que si un subconjunto I de Z es un ideal de Z, entonces I debe ser de la forma (d) para alg´ un entero d; esto es, existe (al menos) un entero d tal que I = {dz | z ∈ Z} = (d). Ejemplo. El subconjunto S(8, 12) = {8x + 12y | x, y ∈ Z} de Z es un ideal de Z, en efecto: – 0 = 8 × 0 + 12 × 0 ∈ S(8, 12) – Si a, b son elementos de S(8, 12), digamos a = 8xa + 12ya y b = 8xb + 12yb , entonces a + b = 8(xa + xb ) + 12(ya + yb ) ∈ S(8, 12) – Si z es un entero y a = 8xa + 12ya es un elemento de S(8, 12), entonces az = 8(xa z) + 12(ya z) ∈ S(8, 12) En el cuadro adjunto se escriben algunos elementos del conjunto S(8, 12) correspondientes a valores de x en el rango −3 ≤ x ≤ 3 y a valores de y en el rango −2 ≤ y ≤ 2:

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

4

...

−3

−2

−1

...

...

...

...

...

...

. . .. . .

−2

...

−48

−40

−32

−24

−1

...

−36

−28

−20

−12

0

...

−24

−16

−8

1

...

−12

−4

4

2

...

0

8

16

24

y

\

x

...

...

...

...

...

0

3

...

...

...

...

−16

−8

0

...

−4

4

12

...

0

8

16

24

...

12

20

28

36

...

32

40

48

...

. . .. . .

...

...

...

...

1

2

De la observaci´on de la tabla parece desprenderse que S(8, 12) = (4); esta afirmaci´ on, que es cierta, ser´a comprobada m´ as adelante una vez que se estudie el algoritmo extendido de Euclides. De momento se probar´ a la siguiente Proposici´ on: Proposici´ on. Sea I un ideal del anillo Z de los enteros. Hay un u ´nico entero m ≥ 0 tal que I = (m). Adem´as, si I = {0}, entonces m es el menor entero positivo en I. Demostraci´ on. Si I = {0}, tomar m = 0. Suponer I = {0}, de modo que hay enteros no nulos a en I; si a ∈ I, entonces −a ∈ I, luego hay enteros positivos en I. Sea m el menor entero positivo en I. Veamos que I = (m), para ello se probar´ an las dos inclusiones: (m) ⊆ I y I ⊆ (m). La primera, (m) ⊆ I, es consecuencia inmediata de que m pertenezca a I y de la condici´ on (3.) de la definici´ on de ideal. Para demostrar la segunda, I ⊆ (m), hay que comprobar que todo elemento a ∈ I es m´ ultiplo de m: por la propiedad de la divisi´ on existen enteros qm (a) y rm (a) tales que a = mqm (a) + rm (a) y 0 ≤ rm (a) < m. Se cumple rm (a) = a − mqm (a) ∈ I [porque a, mqm (a) ∈ I]; por elecci´on m es el menor entero positivo en I; en conclusi´ on debe ser rm (a) = 0, de donde a ∈ I. Ejemplo. Sean m1 , m2 , . . . , ms n´ umeros enteros. El conjunto   S(m1 , m2 , . . . , ms ) = m1 x1 + m2 x2 + . . . + ms xx | x1 , x2 , . . . , xs ∈ Z es un ideal de Z [compru´ebese esta afirmaci´on como ejercicio], luego hay un (´ unico) entero m ≥ 0 tal que S(m1 , m2 , . . . , ms ) = (m).

[2] M´ aximo com´ un divisor El conjunto de los divisores de 12 es: D12 = {−12, −6, −4, −3, −2, −1, 1, 2, 3, 4, 6, 12}; el conjunto de los divisores de 30 es D30 = {−30, −15, −10, −6, −5, −3, −2, −1, 1, 2, 3, 5, 6, 10, 15, 30}; el conjunto de los divisores comunes de 12 y 30 (la intersecci´on de los dos conjuntos anteriores) es: D12 ∩ D30 = {−6, −3, −2, −1, 1, 2, 3, 6}. N´ otese que D12 ∩ D30 = D6 , el conjunto de los divisores de 6; y que 6 cumple las siguientes propiedades (respecto de 12 y 30): (1.) 6 | 12 y 6 | 30; (esto es, 6 es un divisor com´ un de 12 y 30) (2.) para cualquier entero c que cumpla c | 12 y c | 30, se tiene c | 6; (esto es, cualquier divisor com´ un de 12 y 30 es un divisor de 6)

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

5

El n´ umero −6 tambi´en cumple estas propiedades. Definici´ on. Un m´ aximo com´ un divisor de dos enteros a y b no ambos nulos es un entero d que cumpla: (1.) d | a y d | b, y (2.) si c es un entero tal que c | a y c | b, entoces c | d. Ejemplos. – El entero 6 es un m´ aximo com´ un divisor de 12 y 30. Tambi´en −6 es un m´aximo com´ un divisor de 12 y 30. – Los enteros 1 y −1 son m´aximos comunes divisores de 25 y 18. Se estudiar´ an los siguientes t´opicos relativos al m´aximo com´ un divisor de dos enteros: Unicidad, existencia, propiedades y c´ alculo efectivo. Proposici´ on (Unicidad). Si d y d
son ambos m´aximos comunes divisores de dos enteros a y b, entonces
d∼d. Demostraci´ on. Por ser d un m´ aximo com´ un divisor de a y b, y d
un divisor com´ un a a y a b, se tiene

d | d; por simetr´ıa d | d . Por tanto, si d y d
son m´aximos comunes divisores de a y b, se tendr´ a d = d
o d = −d
. Reciprocamente, si d es un m´aximo com´ un divisor de a y b, entonces −d tambi´en lo es. Se conviene en poner mcd(a, b) para denotar el m´ aximo com´ un divisor positivo de dos enteros a y b. Tambi´en por convenio se pone mcd(0, 0) = 0. Ejemplos. • mcd(12, 30) = 6. • mcd(−30, 12) = 6. • mcd(25, 18) = 1. • mcd(−25, −18) = 1. Teorema. (Existencia del m´ aximo com´ un divisor) Para dos enteros cualesquiera a y b se tienen; (1.) existe el m´aximo com´ un divisor d = mcd(a, b) de a y b, y (2.) existen enteros s y t tales que d = as + bt. Demostraci´ on. Pongamos S(a, b) = {ax + by | x, y ∈ Z}. Dado que el conjunto S(a, b) es un ideal de Z, existe un entero d ∈ S(a, b), d ≥ 0, y tal que S(a, b) = (d); y existen enteros sd , td tales que d = asd + btd . Veamos que d = mcd(a, b): – Como a, b ∈ S(a, b) = (d), se tiene a, b ∈ (d); esto es, d | a y d | b – Si c | a y c | b , entonces c |(asd + btd ); esto es, c | d Ni el teorema ni su demostraci´on proporcionan un m´etodo efectivo que permita calcular mcd(a, b) para dos enteros a y b. En las secciones siguientes se estudian, primero, un algoritmo (el algoritmo de Euclides) para el c´ alculo del m´ aximo com´ un divisor de dos enteros y, despu´es, una modificaci´ on de dicho algoritmo (el algoritmo extendido de Euclides) que permite calcular el m´ aximo com´ un divisor d de dos enteros a y b as´ı como enteros s y t tales que d = sa + tb.

Notas y ejemplos • El teorema asegura la existencia del m´aximo com´ un divisor d de dos enteros a y b, as´ı como la existencia de enteros s y t tales que d = as + bt pero debe notarse que ni s ni t tienen las identidades 2 2 2 ... 2

son u ´nicos: pongamos a = 4 y b = 6, entonces d = mcd(4, 6) = 2 y se = = = ... =

4 × (−1) 4 × (−4) 4×2 ... 4(−1 − 3t)

+ + + ... +

6×1 6×3 6 × (−1) ... 6(1 + 2t), (t ∈ Z)

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

6

• Habitualmente se conoce con el nombre identidad de Bezout cualquier expresi´ on del m´ aximo com´ un divisor d de dos enteros a y b como “combinaci´on lineal” de ´estos (sobre Z): d = as + bt con s, t ∈ Z. • Debe notarse que de una identidad tal como h = as + bt donde a, b, h, s, t son enteros no se concluye que h sea (necesariamente) el m´aximo com´ un divisor de a y b, por ejemplo 18 = 4 × (−3) + 6 × 5 Lo que si se puede asegurar, en estas condiciones, es que mcd(a, b) | h (¿demostraci´on?).

Consecuencias de la identidad de Bezout Sea d el m´aximo com´ un divisor de dos enteros a = 0 y b = 0, pongamos d = as + bt

(∗)

para adecuados enteros s, t. Dado que d | a y d | b, existen enteros a
y b
tales que a = a
d y b = b
d substituyendo en (∗) d = a
ds + b
dt = d(a
s + b
t) Dado que d = 0, se puede cancelar el factor d y se obtiene 1 = a
s + b
t De donde se deduce que mcd(a
, b
) = 1. Definici´ on. Dos enteros a = 0 y b = 0 son primos entre s´ı o primos relativos si mcd(a, b) = 1. De las consideraciones previas a la definici´ on se concluye Proposici´ on. Sea d el m´aximo com´ un divisor de dos enteros a = 0 y b = 0. Pongamos a = a
d y b = b
d.

Los enteros a y b son primos entre s´ı. Proposici´ on. Sean a = 0 y b = 0 dos enteros. Las condiciones siguientes son equivalentes (i) a y b son primos entre s´ı (ii) Existen enteros s y t tales que as + bt = 1 Proposici´ on. Si un entero divide a un producto de otros dos y es primo relativo con uno de ellos, entonces divide al otro. Demostraci´ on. Suponer que un entero m divide a un producto ab de dos enteros a y b, y que m y a son primos entre s´ı, probaremos que m | b. Existen enteros z, s y t tales que ab = mz y 1 = ms+at; multiplicando los dos miembros de la u ´ltima igualdad por b, se obtiene b = msb + abt = msb + mzt = m(sb + zt)

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

7

Proposici´ on. Sean a y b enteros primos entre s´ı, y sea m un entero tal que a | m y b | m. Entonces ab | m. Demostraci´ on. Existen enteros u y v tales que au + bv = 1, multiplicando ambos miembros por m se obtiene amu + bmv = m. Por otra parte, dado que a | m, se cumple ab | bm; y dado que b | m, se cumple ab | am. En consecuencia ab |(amu + bmv) = m.

Notas, ejemplos y contraejemplos • Los siguientes pares de enteros son primos entre s´ı: 3 y 7, 12 y 25, 33 y 32, -35 y 18, 12 y 1 • Los siguientes pares de enteros no son primos entre s´ı: 35 y 49, 4 y 2, -81 y 39, -12 y -8, 2925 y 2002 • El entero 6 divide al producto 8 × 9, pero 6  | 8 y 6  | 9 • Se tiene: 2 | 12 y 4 | 12, pero 2 × 4 = 8  | 12. • Puesto que 2925 × 461 + 1694 × (−796) = 1 (compru´ebese), se concluye que (1) mcd(2925, 1694) = 1, (2) mcd(2925, −796) = 1, (3) mcd(461, 1694) = 1 y (4) mcd(461, −796) = 1

C´ alculo del m´ aximo com´ un divisor Recordemos la propiedad de la divisi´ on en Z: Dados dos enteros a y b con b = 0, existen enteros qb (a) y rb (a) (´ unicos) tales que a = bqb (a) + rb (a), 0 ≤ rb (a) < |b| y hay un algoritmo que calcula qb (a) y rb (a). El algoritmo que se expondr´ a para el c´ alculo del m´ aximo com´ un divisor de dos enteros se basa en la siguiente Proposici´ on. Sean a y b enteros. Se tiene (1.) mcd(a, 0) = |a| , y (2.) mcd(a, b) = mcd(b, rb (a)), si b = 0. Demostraci´ on. La primera afirmaci´ on se obtiene directamente de la definici´ on de m´ aximo com´ un divisor y del convenio relativo al signo. Para probar la segunda afirmaci´ on pongamos a = bqb (a) + rb (a). Si c | a y c | b, entonces c | b y c | rb (a) = a − bqb (a); reciprocamente, si c | b y c | rb (a), entonces c | a = bqb (a) + rb (a) y c | b. Por tanto el conjunto de los divisores comunes de a y b coincide con el conjunto de los divisores comunes de b y rb (a). El inter´es de esta proposici´on radica en el hecho de que permite calcular efectiva y eficientemente el m´aximo com´ un divisor de dos enteros cualesquiera. Antes de justificar esta afirmaci´ on veamos algunos ejemplos sencillos. Ejemplos. • • • •

mcd(−747, 0) = 747 mcd(0, −16) = mcd(16, 0) = 16 mcd(12, 8) = mcd(8, 4) = mcd(4, 0) = 4 mcd(9, 15) = mcd(15, 9) = mcd(9, 6) = mcd(6, 3) = mcd(3, 0) = 3

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

8

•

mcd(121393, 17711) = mcd(17711, 15127) = mcd(15127, 2584) = = mcd(2584, 2207) = mcd(2207, 377) = mcd(377, 322) = mcd(322, 55) = = mcd(55, 47) = mcd(47, 8) = mcd(8, 7) = mcd(7, 1) = mcd(1, 0) = 1

Algoritmo mcd (El algoritmo de Euclides sobre Z) Entrada: a, b ∈ Z, dos enteros. Salida: mcd(a, b), el m´aximo com´ un divisor (no negativo) de a y b. mcd(a, b) 1 2 3 4

(r, r
) ← (a, b) mientras r
= 0 hacer (r, r
) ← (r
, resto(r, r
)) devolver |r|

Ejemplo. Se muestra una forma de disponer los c´ alculos para el c´ omputo, con l´ apiz y papel, del m´ aximo com´ un divisor de los n´ umeros 1127 y 354 seg´ un el algoritmo mcd: r

r


1127

354

3

354

65

5

65

29

2

29

7

4

7

1

7

1

0

q

En consecuencia mcd(1127, 354) = 1. Ejercicio. Calcular mediante el algoritmo mcd el m´aximo com´ un divisor de 3757 y 5083 .

Notas de programaci´ on • Un programa en Maple que implementa el algoritmo de Euclides sobre Z mcd := proc(a::integer, b::integer) local r, rp ; r, rp := a, b; while rp 0 do r, rp := rp, irem(r, rp) od; abs(r) end; • La primitiva igcd (integer greatest common divisor) de Maple hace, esencialmente, lo mismo.

El Algoritmo extendido de Euclides El m´ aximo com´ un divisor d de dos enteros a y b se puede expresar en la forma d = as+bt para adecuados enteros s y t. Nos ocupamos del desarrollo de un algoritmo eficiente que permita computar, simultaneamente, d, s y t. El algoritmo que discutiremos ser´ a una extensi´ on del Algoritmo de Euclides.

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

9

Sean pues a y b n´ umeros enteros; analicemos detalladamente el algoritmo de Euclides para el c´alculo de mcd(a, b). Pongamos r0 = a y r1 = b. Si b = 0, entonces el m´aximo com´ un divisor de a y b es |a|. Si b = 0, los pasos dados para el c´alculo de mcd(a, b) se pueden explicitar, simb´ olicamente, en la forma: r0

=

r1 q 1 + r2 ,

0 ≤ r2 < |r1 |

r1

=

r2 q 2 + r3 ,

0 ≤ r3 < r2

...

... ...

ri

=

ri+1 qi+1 + ri+2 , 0 ≤ ri+2 < ri+1

ri+1

=

ri+2 qi+2 + ri+3 , 0 ≤ ri+3 < ri+2

...

... ...

...

rn−2

=

rn−1 qn−1 + rn ,

0 ≤ rn < rn−1

rn−1

=

rn qn + 0,

(r2 es no negativo)

...

de donde se concluye que el m´aximo com´ un divisor d de a y b es rn . Proposici´ on. En la situaci´ on anterior se cumple: Para todo i, (0 ≤ i ≤ n), existen enteros ui , vi tales que ri = aui + bvi Demostraci´ on. Se expone una prueba constructiva; esto es, no s´ olo se prueba la existencia de los ui , vi , sino que se proporciona un m´etodo para calcularlos. Se tienen: r0

= a=a×1+b×0

r1

=

b=a×0+b×1

Por tanto pueden tomarse u0 = 1, v0 = 0 u1 = 0, v1 = 1 Suponer (hip´ otesis inductiva) que est´ an calculados enteros ui , vi , ui+1 , vi+1 tales que ri

= aui + bvi

ri+1

= aui+1 + bvi+1

y

entonces ri+2 = ri − ri+1 qi+1 = aui + bvi − (aui+1 + bvi+1 )qi+1 = = a(ui − ui+1 qi+1 ) + b(vi − vi+1 qi+1 )

.

Por tanto pueden tomarse ui+2 = ui − ui+1 qi+1 ,

vi+2 = vi − vi+1 qi+1

Como caso particular se obtiene la versi´on constructiva del teorema de existencia del m´aximo com´ un divisor: Teorema. Sea d el m´aximo com´ un divisor de dos enteros a y b. Existen enteros u y v tales que d = au + bv De las consideraciones anteriores se obtiene un m´etodo para el c´ alculo simult´ aneo de d, u y v a partir de a y b. Veamos un par de ejemplos.

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

10

Ejemplo. Calcular (a mano, con l´ apiz y papel) el m´ aximo com´ un divisor d de 256 y 117, y enteros u y v tales que d = 256u + 117v. i

qi

ri

ri+1

ui

ui+1

vi

vi+1

0

–

256

117

1

0

0

1

1

2

117

22

0

1

1

-2

2

5

22

7

1

-5

-2

11

3

3

7

1

-5

16

11

-35

4

7

1

0

16

-117

-35

256

En consecuencia, mcd(256, 117) = 1 = 256 × 16 + 117 × (−35) . Ejemplo. Calcular (a mano, con l´ apiz y papel) el m´ aximo com´ un divisor d de 8320 y -6591, y enteros u y v tales que d = 8320u + (−6591)v. i

qi

0

ri

ri+1

ui

ui+1

vi

vi+1

8320

-6591

1

0

0

1

1

-1

-6591

1729

0

1

1

1

2

-4

1729

325

1

4

1

5

3

5

325

104

4

-19

5

-24

4

3

104

13

-19

61

-24

77

5

8

13

0

61

-507

77

-640

En consecuencia, mcd(8320, −6591) = 13 = 8320 × 61 + (−6591) × 77 . Se tiene as´ı el Algoritmo Extendido de Euclides: Algoritmo mcdex (El Algoritmo Extendido de Euclides sobre Z) Entrada: Salida:

a, b ∈ Z, dos enteros. (d, u, v) ∈ Z3 tal que d = mcd(a, b) y u, v cumplen d = au + bv.

mcdex(a, b) 1 2 3 4 5 6 7 8 9

(r, r
) ← (a, b) (u, u
)← (1, 0) (v, v
) ← (0, 1) mientras r
= 0 hacer q ← coct(r, r
) (r, r
) ← (r
, r − r
q) (u, u
)← (u
, u − u
q) (v, v
) ← (v
, v − v
q) devolver sign(r) × (r, u, v)

Notas de programaci´ on • Un programa en Maple que implementa el algoritmo extendido de Euclides sobre Z

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

11

mcdex := proc(a::integer, b::integer) local r, rp, u, up, v, vp, q; r, rp := a, b; u, up := 1, 0; v, vp := 0, 1; while rp 0 do q := iquo(r, rp); r, rp := rp, r − rp*q; u, up := up, u − up*q; v, vp := vp, v − vp*q; od; signum(r)*[r, u, v] end; • La primitiva igcdex (integer greatest common divisor extended) de Maple hace, esencialmente, lo mismo.

[3] M´ınimo com´ un m´ ultiplo El concepto de m´ınimo com´ un m´ ultiplo es dual del concepto de m´ aximo com´ un divisor. Definici´ on. Un m´ınimo com´ un m´ ultiplo de dos enteros a = 0 y b = 0 es un entero m que cumpla: (1.) a | m y b | m, y (2.) si c es un entero tal que a | c y b | c, entonces m | c. Ejemplos. – El entero 24 es un m´ınimo com´ un m´ ultiplo de 12 y 8. Tambi´en -24 es un m´ınimo com´ un m´ ultiplo de 12 y 8. – El entero 6 es un m´ınimo com´ un m´ ultiplo de 2 y -3. El entero -6 tambi´en es un m´ınimo com´ un m´ ultiplo de 2 y -3. Proposici´ on (Unicidad). Si m y m
son m´ınimos comunes m´ ultiplos de dos enteros a = 0 y b = 0, entonces
m∼m. Demostraci´ on. Es trivial y se deja como ejercicio simple. Veamos que existe el m´ınimo com´ un m´ ultiplo de dos enteros a y b cualesquiera. Para ello usaremos la siguiente Proposici´ on. La intersecci´on I1 ∩ I2 de dos ideales I1 e I2 de Z es un ideal de Z. Demostraci´ on. Es trivial y se deja como ejercicio simple. Sean a y b enteros. La intersecci´on (a) ∩ (b) de los ideales (a) y (b) es un ideal de Z, por tanto existe un entero m ≥ 0 tal que (a) ∩ (b) = (m). Veamos que m es un m´ınimo com´ un m´ ultiplo de a y b: como (m) ⊆ (a), se tiene a | m; como (m) ⊆ (b), se tiene b | m; si c es un entero tal que a | c y b | c, entonces (c) ⊆ (a) y (c) ⊆ (b); por tanto (c) ⊆ (a) ∩ (b) = (m); de donde se concluye que m | c. En consecuencia se puede enunciar el siguiente resultado.

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

12

Proposici´ on. Sean a y b n´ umeros enteros. Existe un m´ınimo com´ un m´ ultiplo de a y b. Un entero m es un m´ınimo com´ un m´ ultiplo de a y b si, y s´olo si, (m) = (a) ∩ (b).

[4] N´ umeros Primos Para todo entero a = 0 se tienen las relaciones 1 | a,

−1 | a,

a|a y

− a | a;

porque a = 1a = a1 y a = (−1)(−a) = (−a)(−1). Los divisores 1, −1, a, −a de un entero no nulo a se denominan divisores impropios, los dem´as (si los hay) se denominan divisores propios. Definici´ on. Un entero mayor que 1 es primo si sus u ´nicos divisores son impropios. Un entero mayor que 1 es compuesto si no es primo. N´ otese que los conceptos de entero primo y de entero compuesto s´olo se definen para enteros > 1. Un entero p > 1 es primo si y s´olo si sus u ´nicos divisores positivos son 1 y p. Un entero a > 1 es compuesto si y s´olo si posee divisores positivos distintos de 1 y de a; esto es, si y s´olo si existen enteros b, c > 1 tales que a = bc. Se pueden interpretar los primos como los elementos minimales en el conjunto ordenado (por la relaci´on |) de los enteros mayores que 1. Ejemplos. • Los enteros 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 1997, 1999 son primos. • Los enteros 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 221, 3992003 son compuestos. • Los enteros 1, -1, -3, -6, -12 no son ni primos ni compuestos. Proposici´ on. Todo entero n > 1 posee, al menos, un divisor primo. Demostraci´ on. Suponer que hay alg´ un entero mayor que 1 que no posea divisores primos. Sea m el menor entero m > 1 que no posee divisores primos (aqu´ı se usa la buena ordenaci´ on de los enteros positivos). Como m es un divisor de m y m no posee divisores primos, se sigue que m no es primo. Por tanto hay enteros a y b tales que m = ab, 1 < a < m, 1 < b < m Dado que a < m, se sigue que a tiene, al menos, un divisor primo (que puede ser el propio a); y todo divisor de a es divisor de m, con lo que m posee divisores primos. Esta contradicci´on proviene de suponer que hay alg´ un entero mayor que 1 que no posea divisores primos. En consecuencia se cumple el enunciado de la proposici´ on. Proposici´ on. El conjunto de los n´ umeros primos es infinito. Demostraci´ on. Se deja como ejercicio. [ Una forma de proceder: Suponer que el conjunto P de los primos es finito, digamos P = {p1 , p2 , . . . , ps }. Considerar el entero z = p1 p2 . . . ps + 1. Probar que z posee un divisor primo que no est´ a en P . ] Definici´ on. Una factorizaci´ on de un entero es una expresi´ on del entero dado como producto de factores. Ejemplo. Las expresiones 2 × 6, 3 × 4, 2 × 2 × 3, 2 × 3 × 2, 6 × 2 × 1, y 12 son distintas factorizaciones del entero 12.

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

13

Teorema. (Existencia de una factorizaci´ on en primos) Todo entero n ≥ 2 se puede factorizar en primos. Demostraci´ on. Por inducci´ on sobre n. El entero 2 es primo, luego 2 es una factorizaci´ on de 2 en primos. Suponer el teorema probado para todo entero m, 2 ≤ m ≤ n. Si n + 1 es primo, ya est´a. Si n + 1 es compuesto, entonces tiene una factorizaci´on de la forma n + 1 = ab; donde 2 ≤ b < n + 1 y 2 ≤ b < n + 1. Por inducci´ on, a y b se expresan como producto de primos, digamos a = p1 . . . pr y b = q1 . . . qs ; por tanto ab = p1 . . . pr .q1 . . . qs . Antes de estudiar la unicidad de la factorizaci´ on en primos, veamos un lema que tiene inter´es independiente (este resultado ya fue probado previamente y con mayor generalidad ¿d´ onde?): Lema. Si p es un primo y p | ab, entonces p | a ´o p | b. (Si un primo divide a un producto de dos factores, entonces divide al menos a uno de ellos). Demostraci´ on. Suponer que p | ab y p  | a. Como p  | a y p es primo, el u ´nico divisor positivo com´ un de a y p es 1; esto es, mcd(a, p) = 1. Luego existen enteros s y t tales que 1 = sa + tp; entonces b = sab + tpb; por hip´ otesis p | ab, en consecuencia p | b. Corolario. Sea p un primo. Si p | a1 a2 . . . an , entonces p | ai para alg´ un i, 1 ≤ i ≤ n. Teorema. (Unicidad de la factorizaci´ on en primos) Todo entero n ≥ 2 se expresa de modo esencialmente u ´nico como producto de primos. Precisamente, si n = p1 . . . ps = q1 . . . qt , (con p1 , . . . , ps , q1 , . . . , qt primos), entonces s = t y existe una reordenaci´ on de los q1 , . . . , qt tal que p1 = q1 , . . . , ps = qs . Demostraci´ on. Por inducci´ on sobre n. Para n = 2 la afirmaci´ on es trivialmente cierta (porque 2 es primo). Suponer el teorema probado para cualquier m, 2 ≤ m ≤ n. Si n + 1 es primo, ya est´a. Si n + 1 es compuesto, se puede expresar en producto de primos, digamos de dos formas: n + 1 = p1 p2 . . . ps = q1 q2 . . . qt , (s, t ≥ 2). Como p1 | n + 1, se tiene p1 | q1 q2 . . . qt , luego p1 | qj para alg´ un j, 1 ≤ j ≤ t. Reordenando los qj , podemos suponer que p1 | q1 . Como q1 es primo, s´olo posee un divisor > 1; luego p1 = q1 . Dividiendo n + 1 por p1 (= q1 ) queda n+1 = p2 . . . ps = q2 . . . qt . p1 Ahora 2 ≤ n+1 otesis inductiva obtenemos s − 1 = t − 1 (por tanto s = t) y, mediante una p1 ≤ n. Por hip´ reordenaci´ on de q2 , . . . , qs , tenemos p2 = q2 , . . . , ps = qs . Corolario. Todo entero n ≥ 2 posee una u ´nica “descomposici´on en primos elevados a exponentes” de la forma n = pe11 pe22 . . . pess , (ei ≥ 1), donde los pi son los distintos divisores primos de n.

BIBLIOGRAFIA Childs, L., A Concrete Introduction to Higher Algebra. Springer (1.979). P´ aginas 19 a 36. Lipson, J. D., Elements of Algebra and Algebraic Computing. P´ aginas 46 a 50, y 203 a 206.

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

14

Rosen, K. H., Elementary Number Theory and its Applications. P´ aginas 70 a 104, incluyendo algunos ejercicios.

EJERCICIOS. 1. Probar que si a, b y c son enteros tales que a | b y b | c, entonces a | c. 2. Mostrar que si a, b y c son enteros tales que c | a y c | b, entonces c |(ma + nb) para todo m, n ∈ Z. 3. Si a y b son enteros no nulos tales que a | b y b | a, ¿qu´e puedes concluir con respecto a a y b? 4. ¿Existen enteros a, b y c tales que a | bc, pero a  | b y a  | c? 5. Probar que si a, b y c son enteros, c = 0, se tiene a | b si y s´olo si ac | bc. 6. Probar que si a y b son enteros positivos y a | b, entonces a ≤ b. 7. Demostrar que si a y b son enteros y a | b, entonces an | bn, para todo entero positivo n. 8. Probar que 3 |(n3 − n) para todo entero n. 9. Probar que el producto de tres enteros consecutivos cualesquiera es m´ ultiplo de 6. 10. Probar que 5 |(n5 − n) para todo entero n. 11. Sean a y b enteros positivos; pongamos a = pe11 pe22 . . . penn

y

b = pf11 pf22 . . . pfnn ; (ei , fi ≥ 0);

donde p1 , p2 , . . . , pn son los distintos divisores primos de a ´o b. Sean d = pd11 pd22 . . . pdnn con di = min(ei , fi ) y mi = m´ax(ei , fi ), Probar que d = mcd(a, b) y m = mcm(a, b). 12. Probar que

√

y

mn 1 m2 m = pm 1 p2 . . . pn

1 ≤ i ≤ n.

2 es irracional.

13. (Generalizaci´ on del ejercicio anterior) Sea r una ra´ız (esto es, un cero) de un polinomio m´ onico xn + an−1 xn−1 + · · · + a1 x + a0 con coeficientes enteros y a0 = 0. Probar que r es entero o irracional. 14. Para cada entero positivo n sea fn el correspondiente t´ermino de la sucesi´on de Fibonacci. (i) Probar que fn+1 fn−1 − fn2 = (−1)n ; (ii) Como consecuencia de (i) calcular mcd(fn , fn+1 ). 15. Sea E(a, b) el n´ umero de divisiones necesarias para calcular el m´aximo com´ un divisor de los enteros a y b (a > b) utilizando el algoritmo de Euclides. (i) Calcular E(21, 13), n´ otese que 13 y 21 son t´erminos consecutivos de la sucesi´on de Fibonacci. (ii) Calcular E(fn+1 , fn ); (iii) Sea b un entero b < fn+1 . Probar que E(a, b) ≤ E(fn+1 , fn ) para cualquier a > b.

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

15

16. Sean a, b y c enteros, a = 0 o´ b = 0; pongamos d = mcd(a, b). Probar: (i) mcd(a/d, b/d) = 1; (ii) mcd(a, b) = mcd(a + bc, b). 17. Sea n un entero positivo. (i) ¿C´ omo podr´ıas definir el m´ aximo com´ un divisor , mcd(a1 , a2 , . . . , an−1 , an ), de n enteros no todos nulos: a1 , a2 , . . . , an−1 , an ?. (ii) Demuestra que mcd(a1 , a2 , . . . , an−1 , an ) = mcd(a1 , a2 , . . . , mcd(an−1 , an )). (iii) Encontrar tres enteros a1 , a2 , a3 tales que mcd(a1 , a2 , a3 ) = 1 pero dos a dos no sean primos entre s´ı.

Lecciones de Algebra. Jaime Guti´ errez Guti´ errez y Carlos Ruiz de Velasco y Bellas Universidad de Cantabria. Santander, 27 de febrero de 2002 http://matsun1.matesco.unican.es/~velasco/algebra/

16