Algebra

Cap´
ıtulo 2
Divisibilidad en Z
2.1.

Divisi´n eucl´
o
ıdea en Z. M´ximo com´ n divia
u
sor

Definici´n 2.1 Dados dos n´meros enteros a y b, con b = 0, se dice que b divide
o
u
a a o que a es m´ltiplo de b o que b es divisor de a, si existe otro entero q tal que
u
a = bq . Se escribe
b|a
Naturalmente, todo n´mero entero a distinto de 1 y −1 tiene, al menos, cuatro
u
divisores,a saber, ±1 y ±a. A estos divisores se les conoce con el nombre de divisores
(o factores) triviales de a. Otras propiedades, de todos conocidas, de la divisibilidad
se recogen en la siguiente Proposici´n:
o
Proposici´n 2.2 En las propiedades siguientes todos los n´meros ser´n enteros y
o
u
a
|a| denotar´ el valor absoluto de a.
a
1) d|a ⇐⇒ −d|a ⇐⇒ d| − a,
2) d|a, a = 0 y d ≥ 0 =⇒ 1 ≤ d≤ |a|,
3) d|1 =⇒ d = 1 o d = −1,
4) a|b y b|a =⇒ b = a o b = −a,
5) a|b y b|c =⇒ a|c,
6) a|b y a|c =⇒ a|b + c,
7) a|b y a|c =⇒ a|bc,
8) a|b y c ∈ Z =⇒ ac|bc,
25

CAP´
ITULO 2. DIVISIBILIDAD EN Z

26
9) a|b y c|d =⇒ ac|bd,
10) ac|bc y c = 0 =⇒ a|b.

Nota. La prueba de estas propiedades requiere el uso de la Definici´n 2.1 y de los
o
axiomas que definen los n´meros enteros. Como laprueba de dichas propiedades es
u
sencilla, la dejaremos como ejercicio.
De entre todos los n´meros enteros, adquieren una singular importancia los conou
cidos como n´meros primos que, desde siempre, han fascinado a los matem´ticos
u
a
y al resto de los mortales. Por poner un ejemplo, en la pel´
ıcula Contact dirigida
por Robert Zemeckis en 1997 y cuyo gui´n se basa en una novela de CarlSagan, el
o
primer mensaje que recibe de los extraterrestres la Dra. Arroway, interpretada por
Jodie Foster, es una sucesi´n de n´meros primos.
o
u
Definici´n 2.3 Un entero p > 1 se dice primo si sus unicos divisores positivos son
o
´
los triviales, es decir, 1 y p.
Los primeros primos son:
2, 3, 5, 7, 11, 13, 17, 19, 23, ...
N´tese que 1 no es primo.
o
Teorema 2.4 (Euclides, Libro IXde los Elementos, aprox. 300 a. C.) Todo
n´mero entero mayor que 1 es producto de primos.
u
Demostraci´n.– Inducci´n en la talla.
o
o
En particular, todo entero no nulo es producto de uno de los n´meros ±1 y de
u
n´meros primos. Veremos m´s adelante que esta expresi´n es, esencialmente, unica.
u
a
o
´

Teorema 2.5 (Euclides, Libro IX de los Elementos) Existen infinitos n´meros
uprimos.
La prueba de este resultado es sencilla y su inter´s radica en el hecho de que es
e
una de las primeras demostraciones conocidas en las que se utiliz´ la reducci´n al
o
o
absurdo.
Demostraci´n.– Supongamos que hay un n´mero finito, digamos n, de primos a los
o
u
que denotaremos por p1 , p2 , . . . , pn . Consideremos el n´mero
u

´
´
´
2.1. DIVISION EUCL´
IDEA EN Z. MAXIMOCOMUN DIVISOR

27

N = p1 p2 · · · pn + 1.
Por el teorema anterior, sabemos que N es producto de primos. Sea, pues, p un
factor primo de N . Este primo ha de ser uno de los p1 , p2 , . . . , pn , digamos p = pi .
Entonces, pi divide a N − p1 p2 · · · pn que es igual a 1, con lo que hemos llegado a
una contradicci´n.
o
Una de las primeras tareas matem´ticas (y algor´
a
ıtmicas) querealizamos en nuestra
vida es la de aprender a dividir n´meros naturales con resto. La forma en la que nos
u
ense˜an a dividir, basada en la b´squeda de un natural que “quepa”(si no la mejor
n
u
desde un punto de vista de eficiencia) es, en cierto modo, la misma idea en la que
se basa la demostraci´n del siguiente teorema.
o
Teorema 2.6 (Divisi´n eucl´
o
ıdea) Si a y b son dos enteros, b = 0,existe un unico
´
par de enteros q y r tales que:
a = bq + r y 0 ≤ r < |b|.
A q y a r se les conoce, respectivamente, como cociente y resto de la divisi´n eucl´
o
ıdea
de a por b.
Demostraci´n.– Empecemos por demostrar la existencia de cociente y resto.
o
Supongamos, primero, que b > 0 y sea S = {x ∈ Z : bx ≤ a}. Este conjunto S es
no vac´ (−|a| pertenece a S ) y est´ acotado...