Matemáticas

Divisibilidad
Mario Pineda Ruelas
Departamento de Matem´ticas,
a
Universidad Aut´noma Metropolitana-Iztapalapa
o
correo electr´nico: mpr@xanum.uam.mx
o

Gabriel D. Villa Salvador
Departamento de Control Autom´tico,
a
Centro de Investigaci´n y de Estudios Avanzados, IPN
o
correo electr´nico gvilla@ctrl.cinvestav.mx
o

1

Inducci´n matem´tica
o
a

En este trabajo N, Z, Q, R yC denotan a los n´meros naturales, enteros, rau
cionales, reales y complejos respectivamente. Por principio, no consideramos al
n´mero 0 como n´mero natural y escribiremos N0 = N ∪ {0}. Esto es todo lo
u
u
que necesitamos para empezar nuestro estudio de la aritm´tica de Z.
e
La esencia de las matem´ticas se encuentra en la construcci´n de pruebas de
a
o
afirmaciones generales por mediode argumentos l´gicos. Por supuesto que el
o
realizar ´stas construcciones puede requerir de gran talento. Afortunadamente,
e
existen m´todos elementales y poderosos que sirven para llevar a cabo ´stas
e
e
construcciones, es decir, sirven para hacer demostraciones matem´ticas.
a
Nuestro primer objetivo es explorar dos de los m´todos m´s importantes
e
a
en la matem´tica que son usadospara hacer demostraciones. Estos son: el
a
Principio de Inducci´n Matem´tica (PI) y su equivalente, el Principio del Buen
o
a
Orden (PBO). Concretamente, estos dos m´todos establecen lo siguiente:
e
Principio de Inducci´n Matem´tica: Sea S un subconjunto de N tal que:
o
a
(1) 1 ∈ S , y
(2) Si los enteros 1, ..., n ∈ S , se tiene que n + 1 ∈ S .
Entonces S = N.
Principio del Buen Orden:Cualquier subconjunto S = ∅ de N contiene un
elemento m que satisface m ≤ x para todo elemento x ∈ S .
Una observaci´n simple en el Principio del Buen Orden es que el entero m es
o
unico. En el siguiente resultado vamos a suponer que N est´ dotado del orden
´
a
natural ≤ y usaremos que el 1 no es el sucesor de ning´n otro n´mero natural.
u
u
´
Esta ultima propiedad en realidad es uno delos axiomas de Peano.
´

1

Teorema 1.1. El Principio del Buen Orden es equivalente al Principio de Inducci´n Matem´tica.
o
a
Demostraci´n: Sea S un conjunto que satisface (1) y (2) del Principio de
o
Inducci´n y S c su complemento con respecto a N. Vamos a suponer que el
o
PBO se cumple. Si S c = ∅, entonces existe m ∈ S c tal que m ≤ n, para todo
n ∈ S c y m = 1. Observemos enparticular que m − 1 ∈ S c pues m es el menor
elemento de S c . Por lo tanto m − 1 + 1 = m ∈ S . Esto ultimo no es posible
´
pues m ∈ S c . As´ S c = ∅ y S = N.
ı,
Ahora supongamos el PI v´lido y sea S un subconjunto no vac´ de N.
a
ıo
Vamos a suponer que el conjunto S no contiene un elemento m tal que m ≤ x
para todo x ∈ S . Es claro que 1 ∈ S pues de lo contrario S tendr´ un elemento
ıamenor. Sea C = {n ∈ N : n < x, para cualquier x ∈ S }. Es claro que 1 ∈ C
pues 1 < x para todo x ∈ S . Mostraremos que si k ∈ C , entonces k + 1 ∈ C y
luego usaremos el PI para concluir que C = N. Si k ∈ C y k + 1 ∈ C , entonces
para alg´n x1 ∈ S se tiene x1 ≤ k + 1. Puesto que S no tiene un elemento
u
m´
ınimo, existe x2 ∈ S tal que x2 < x1 ≤ k + 1. As´ que x2 < k + 1 y en
ı
consecuenciax2 ≤ k . Esto ultimo no es posible pues k < x2 . Este absurdo
´
nace de suponer que k + 1 ∈ C . Por lo tanto k + 1 ∈ C y por el PI tenemos
que C = N. Particularmente, si x ∈ S , se tiene que x ∈ C . Esto significa que
x < x, lo cual no es posible. Por lo tanto, S debe contener un elemento m tal
que m ≤ x para todo x ∈ S .

Nota importante: En el conjunto N0 = N ∪ {0} tambi´n se cumple elPBO.
e
Es muy f´cil entender esto. Recordemos que la relaci´n ≤ define en N un orden
a
o
parcial (es reflexivo, antisim´trico y transitivo) que adem´s satisface la ley de
e
a
tricotom´ (orden parcial + tricotom´ orden total). Este orden total resulta
ıa
ıa=
ser un buen orden porque satisface el PBO. Para N0 aprovechamos el orden total
de N simplemente extendi´ndolo, i.e, definimos 0 < j...