Capı́tulo 3

Números naturales

3.1 Conjuntos finitos. Definición y caracterización.

Recordemos el conjunto de los números naturales positivos N∗ = {1, 2, 3, · · · , n, · · · , }. Asociados a
él están las secciones N∗n = {1, 2, 3, · · · , n}, definidas para todo n ∈ N∗ . (Podemos definir N∗0 = ∅).
Las secciones N∗n nos van a servir de modelos de conjuntos finitos ya que tiene n elementos.

Definición 3.1.1 Un conjunto X tiene n elementos (o es finito de cardinal n, de orden n, o de

potencia n) si ∃n ∈ N∗ tal que X es biyectivo con N∗n . Si X = ∅ decimos que tiene orden 0.

Nota 3.1.2 Observemos que todo conjunto biyectivo con uno de n elementos tiene n elementos.

El número n es el resultado de contar los elementos de X. Vamos a ver que está bien definido.

Lema 3.1.3 Si existe una inyección N∗n → N∗m , entonces n ≤ m.

Demostración Probemos la expresión por inducción. A mano se comprueba el caso m = 1.

Sea válido para m − 1 y consideremos una inyección f : N∗n → N∗m . Veamos el caso cuando
f (n) = m. Entonces la restricción N∗n−1 → N∗m−1 es una inyección. Por inducción n − 1 ≤ m − 1,
con lo que n ≤ m.
Sea ahora f (n) = k = m. Consideremos la biyección φ : N∗m → N∗m dada por φ(i) = i si i < k,
φ(k) = m y φ(i) = i − 1 si i > k. La composición f  = φ ◦ f es una inyección que cumple f  (n) = m,
luego n ≤ m. ✷

Corolario 3.1.4 Si existe una biyección entre N∗n y N∗m , entonces n = m.

Nota 3.1.5 El número de elementos de un conjunto X está bien definido y se denota por |X|.

Los mismos resultados anteriores se pueden generalizar a conjuntos finitos.

Propiedad 3.1.6 Si existe una inyección de un conjunto de n elementos a uno de m elementos,

entonces n ≤ m.

25
November 4, 2002 26

Otra forma de expresar el mismo resultado que es útil a veces es el “principio del casillero”.

Teorema 3.1.7 Sean X un conjunto de n elementos e Y un conjunto de m elementos con n > m.

No hay ninguna aplicación f : X → Y inyectiva. O sea, para cada f , existen x = x con f (x) = f (x ).

Nota 3.1.8 El motivo del nombre es por la observación trivial siguiente “Si estamos repartiendo
cartas en un casillero y hay más cartas que casillas, en alguna casilla habrá dos cartas”.

Propiedad 3.1.9 Dos conjuntos, X de orden n e Y de orden m, son biyectivos sii n = m.

Nota 3.1.10 Igualmente podı́a haberse hecho todo el trabajo anterior usando aplicaciones suprayec-
tivas. Es un buen ejercicio para el estudiante escribirlos.

Definición 3.1.11 Un conjunto X es finito si tiene un número finito de elementos. O sea, si existe
un número natural n y una aplicación biyectiva, φ : N∗n → X. Entonces |X| = n.

Veamos ahora que la finitud es una propiedad hereditaria.

Lema 3.1.12 Todo conjunto A ⊆ N∗n , es finito y |A| ≤ n. Además |A| = n sii A = N∗n

Demostración Por inducción en n empezando con n = 0, 1.

Para un n genérico, si A = N∗n ya está. Si A ⊂ N∗n , hacemos como antes. Obtenemos un A
biyectivo tal que A ⊆ N∗n − {n} = N∗n−1 . ✷

Propiedad 3.1.13 Sea |Y | = m y X ⊆ Y . Entonces X es finito y |X| = n ≤ m. Además m = n

sii X = Y .

Nota 3.1.14 Un conjunto finito nunca es biyectivo con un subconjunto propio.

Propiedad 3.1.15 Sea |Y | = m y f : X → Y una aplicación inyectiva. Entonces X es finito y

|X| = n ≤ m. Además m = n sii f es una biyección.

Corolario 3.1.16 Entre conjuntos finitos de igual orden, una aplicación es biyectiva sii es inyectiva.

Como colofón, dos caracterizaciones de finitud. Una usando inyectividad, consecuencia de lo

anterior y la otra la dual, usando suprayectividad, ya que la usaremos luego.

Teorema 3.1.17 Un conjunto X es finito sii existe n ∈ N∗ y una aplicación f : X → N∗n inyectiva.
En ese caso, |X| ≤ n.

Teorema 3.1.18 Un conjunto X es finito sii existe n ∈ N∗ y una aplicación f : N∗n → X suprayec-
tiva. En ese caso, |X| ≤ n.
November 4, 2002 27

3.2 Conjuntos finitos. Aritmética.

Vamos a ver las operaciones elementales de conjuntos finitos y su relación con la aritmética. Em-
pecemos con la unión.

Propiedad 3.2.1 Si X e Y son conjuntos finitos disjuntos, X ∪ Y es finito y |X ∪ Y | = |X| + |Y |.

Demostración Sean f : N∗n → X y g : N∗m → Y biyecciones. Definimos h : N∗n+m → X ∪ Y como

h(i) = f (i) si i ≤ n, h(i) = g(i − n) si i > n. La aplicación h es una biyección. ✷

Corolario 3.2.2 Si X e Y son conjuntos finitos, X ∪ Y es finito y |X ∪ Y | = |X| + |Y | − |X ∩ Y |.

Demostración Cada uno de los dos conjuntos descompone en la unión disjunta de la intersección
(X ∩ Y ) y las diferencias. Igualmente, X ∪ Y descompone en la unión disjunta de los tres. ✷

Corolario 3.2.3 La unión finita de conjuntos finitos es finito.

Nota 3.2.4 Se puede obtener una formula para uniones finitas que darı́a

n 
| Ai | = (−1)r−1 |AI |
i=1 I

donde I = {i1 , i2 , · · · , ir } recorre todos los subconjuntos no vacı́os de N∗n y AI = Ai1 ∩ Ai2 ∩ · · · ∩ Air

Propiedad 3.2.5 Si X e Y son conjuntos finitos, X × Y es finito y |X × Y | = |X||Y |.

Demostración Sean f : N∗n → X y g : N∗m → Y biyecciones. Definimos h : N∗nm → X × Y como

h((p − 1)m + q) = (f (p), g(q)). La aplicación h es una biyección.

También se puede ver que X × Y es la unión disjunta x∈X {x} × Y , y cada uno de ellos es
biyectivo con Y . ✷

Corolario 3.2.6 El producto finito de conjuntos finitos es finito.

Propiedad 3.2.7 Si X e Y son conjuntos finitos, Y X es finito y |Y X | = |Y ||X| .

∗
Demostración Se puede reducir a los modelos y probar que (N∗n )(Nm ) es biyectivo con N∗nm .
Una biyección viene dada por f → f (1) + f (2)m + · · · + f (n)mn−1 . (La prueba de que es una
biyección se aplaza hasta bases de numeración) ✷

Corolario 3.2.8 Si X es un conjunto finito, P (X) es finito y |P (X)| = 2|X| .

November 4, 2002 28

Veamos subconjuntos interesantes de Y X y de P (X).

Definición 3.2.9 Dados X e Y conjuntos finitos tales que |X| = n ≤ m = |Y |. El conjunto
Iny(X, Y ) = {f : X → Y : f inyectiva} se llama variaciones de X respecto a Y . Si X = Y se llaman
permutaciones de X.
Nota 3.2.10 En ambos casos se pueden coger conjuntos modelo. Si X = N∗n y Y = N∗m hablamos
de variaciones de m elementos tomados de n en n y de permutaciones de n elementos.
Propiedad 3.2.11 En el caso anterior, el conjunto de variaciones de X respecto de Y es finito de
orden m(m − 1) · · · (m − n + 1) = m!/(m − n)! .
Demostración Hay un procedimiento corto para calcularlo en el modelo hablando del número de
elecciones para f (i) en cada i. Una forma más correcta puede hacerse por inducción en n. ✷

Definición 3.2.12 Dado X un conjunto y r ∈ N∗ , el conjunto de las partes de orden r de X (o

r-subconjuntos) es
Pr (X) = {A ⊆ X : |A| = r}.
Ejemplo 3.2.13 Calcula las partes de orden 2 de X = {a, b, c, d}
Propiedad 3.2.14 Si X es finito de orden n, Pr (X) es finito y |Pr (X)| = 0 si r > n y n!/r!(n−r)! =
n(n − 1) · · · (n − r + 1)/r! si r ≤ n.
Demostración Como antes, hay un procedimiento de contar chapucerete que da el resultado.
Para hacerlo formalmente se puede usar la aplicación suprayectiva Iny(N∗r , X) → Pr (X) dada
por f → f (N∗n ), comprobar que todas las anti-imágenes de los puntos tienen el mismo número de
elementos (r!) y despejar. ✷

 
Definición 3.2.15 Dado X un conjunto y r ∈ N∗ , definimos el número combinatorio nr como el
orden de Pr (X).
   n  n n    n   
Propiedad 3.2.16 Si r ≤ n, nr = n−r ; 0 = n = 1; n1 = n−1 = n; si r > n, nr = 0.
Demostración Se pueden probar por la fórmula, pero es instructivo hacerlo de la definición. ✷

n n
Propiedad 3.2.17 r=0 r
= 2n .
Demostración Esto pasa ya que P (X) es la unión disjunta de los Pr (X). ✷

n n−1 n−1

Lema 3.2.18 r
= r−1
+ r
para r ≤ n − 1.
Demostración Se puede ver por la fórmula. También se puede ver que Pr (N∗n ) es la unión disjunta
de Pr−1 (N∗n−1 ) y Pr (N∗n−1 ). ✷

Nota 3.2.19 Esta propiedad es el principio subyacente al triángulo de Pascal.

November 4, 2002 29
n n
Teorema 3.2.20 (a + b)n = r=0 r
ar bn−r .

Demostración Por inducción en n, siendo obvios los casos n = 0, 1. Si es válido para n−1, tenemos
n−1 
 n−1 

n n−1 n−1 n−1 k+1 n−k−1 n−1
(a + b) = a(a + b) + b(a + b) = a b + al bn−l .
r=0
k l=0
l
n n−1 n−1 n
Entonces (a + b)n = r=0 αr ar bn−r . Igualando αr = r−1
+ r
= r
✷

n n
Nota 3.2.21 Este teorema da otra prueba de r=0 r
= 2n .

3.3 Conjuntos infinitos. Numerabilidad

Hasta ahora hemos considerado el caso de conjuntos finitos. Veamos algo sobre los que no lo son.

Definición 3.3.1 Recordemos que un conjunto X es finito si existe un número natural n y una
aplicación biyectiva, φ : N∗n → X. Decimos que es infinito si no existen.

Propiedad 3.3.2 N∗ es un conjunto infinito.

Demostración Si existiera una biyección φ : N∗ → N∗n , la restricción nos darı́a una aplicación
inyectiva φ : N∗n+1 → N∗n , lo que es imposible por 3.1.3. ✷

Vamos a concentrarnos en los conjuntos infinitos que son biyectivos con este caso especial.

Definición 3.3.3 Decimos que X es infinito numerable si existe una biyección, φ : N∗ → X. Decimos
que es numerable si es finito o infinito numerable.

Nota 3.3.4 El concepto de infinito empieza a introducir rarezas. Muchos subconjuntos de N∗ son
infinito numerables, como las secciones {n, n + 1, · · · }, los números pares, los cuadrados, etc. Desde
este punto de vista también es equivalente N. Los comentarios se pueden hacer usando el hotel con
infinitas habitaciones.

Veamos el que el numerable es el infinito de menor orden.

Propiedad 3.3.5 Todo subconjunto no acotado de N∗ es biyectivo con él.

Demostración La aplicación se construye recursivamente. Sea A ⊆ N∗ infinito. Defino φ : N∗ → A

por φ(1) = min A. Una vez definido φ(n − 1), defino φ(n) = min{x ∈ A : x > φ(n − 1)}. ✷

Corolario 3.3.6 Todo subconjunto infinito de N∗ es infinito numerable.

Corolario 3.3.7 Todo subconjunto infinito de uno infinito numerable es infinito numerable.
November 4, 2002 30

Desde el punto de vista de las propiedades, a veces es más fácil usar la siguiente caracterización
de conjuntos numerables.

Propiedad 3.3.8 Un conjunto X es numerable si y sólo si existe una suprayección φ : N∗ → X.

Demostración Basta considerar los casos X = N∗n y X = N∗ .

Es fácil construir las aplicaciones suprayectivas.
Dada una aplicación suprayectiva φ : N∗ → X, construimos un inverso ψ : X → N∗ , donde
ψ(x) = min φ−1 (x). Entonces ψ(X) y X son biyectivos. Si ψ(X) es acotado, es finito y X también.
Si ψ(X) no es acotado, son infinito numerable. ✷

Nota 3.3.9 Esta propiedad puede interpretarse como que un conjunto X es numerable si existe una
sucesión cuyo conjunto imagen es todo X. Da igual que el dominio de la sucesión sea N, N∗ o N(n) .

Veamos como usando tanto la definición como esta propiedad se pueden demostrar algunas
propiedades de numerabilidad que generalizan propiedades conocidas de finitud.
Para demostrar propiedades algo más interesantes de conjuntos numerables es crucial la siguiente
observación.

Lema 3.3.10 El conjunto N × N es infinito numerable.

Demostración Para ello construimos una aplicación biyectiva θ : N → N × N definida por θ(n) =
(m − k, k) donde m es el único natural tal que

m(m + 1) (m + 1)(m + 2)
≤n<
2 2

y k = n − m(m+1)
2
(Figura 4.1).
Está claro que la aplicación ası́ definida es biyectiva, con lo que N × N es infinito numerable. ✷

θ(9)

θ(8)

θ(5)

θ(7)
θ(4)

θ(2)

θ(0) θ(1) θ(3) θ(6)

Figura 3.1
November 4, 2002 31

Con una fácil inducción se comprueba entonces el siguiente resultado.

Corolario 3.3.11 Para todo n, Nn es infinito numerable.

Con este resultado es fácil probar que numerabilidad se conserva por uniones numerables.

Propiedad 3.3.12 Sea I un conjunto numerable de ı́ndices, y para cada i ∈ I, sea Xi un conjunto

numerable. Entonces, X = i∈I Xi es numerable.

Demostración Por ser Xi numerable, para cada i existe φi : N → Xi una aplicación suprayectiva.
Entonces, la aplicación
φ:I ×N→X
dada por φ(i, n) = φi (n) también es suprayectiva.
Por ser I numerable, existe ψ : N → I una aplicación suprayectiva. Sea θ : N → N × N la
aplicación suprayectiva del Lema anterior (3.3.10). Entonces la composición
θ (ψ,Id) φ
N → N × N −→ I × N → X

es una aplicación suprayectiva, con lo que X es numerable. ✷

Corolario 3.3.13 El conjunto de los números enteros, Z, es infinito numerable.

Demostración Evidentemente son infinitos numerables los enteros positivos y los enteros negativos.
Por la Propiedad anterior (3.3.12) también lo es Z que es su unión. ✷

Veamos que la numerabilidad también se conserva por productos finitos.

Propiedad 3.3.14 Sean Xi conjuntos numerables para i = 1, 2, ...n. Entonces,

X = X1 × X2 × ... × Xn

es numerable.

Demostración Sean φi : N → Xi las aplicaciones suprayectivas que existen por la caracterización

de numerabilidad. Sea θn : N → Nn la aplicación suprayectiva de 3.3.11. Entonces, la composición
θ (φ1 ,φ2 ,...,φn )
N −→
n
Nn −→ X

es una aplicación suprayectiva. ✷

Corolario 3.3.15 El conjunto de los números racionales, Q, es infinito numerable.

Demostración Por la propiedad anterior, es infinito numerable el conjunto Z × Z y, evidentemente,

Q puede ser considerado un subconjunto de él mediante la representación irreducible de cada fracción,
luego Q es numerable. ✷
November 4, 2002 32

Por ahora todos los conjuntos numéricos han salido numerables. Veamos que no siempre es ası́.
Los intervalos proporcionan el primer ejemplo de conjuntos no numerables.

Propiedad 3.3.16 El intervalo ]0, 1[ no es numerable.

Demostración Como es sabido, todo número real admite una única expresión decimal excepto
los que tienen un desarrollo decimal finito. Para estos escogemos la forma .0200000.. en vez de
.0199999....
Supongamos que ]0, 1[ fuera numerable. Tenemos entonces una sucesión, {xn }∞ n=1 , cuya imagen
es ]0,1[.
Vamos a construir un número real entre 0 y 1 que no puede ser ningún xn . El número real se
construye tomando como parte entera 0 y como decimal n-ésimo un número entre 0 y 8 que no sea
el decimal n-ésimo de xn . Evidentemente es un número real entre 0 y 1 bien definido y no puede ser
igual a ningún xn por ser distintos sus desarrollos decimales en el lugar n-ésimo. ✷

Como consecuencia, todo conjunto que contiene a ]0, 1[ es no numerable. En particular, lo es R.

3.4 La división con resto. Bases de numeración.

El resto de las secciones de este tema están basadas en el hecho de que los números enteros admiten
división con resto para cada número natural. Empecemos enunciándolo y probándolo.

Teorema 3.4.1 (Algoritmo de la división con resto) Dados dos números a ∈ Z y b ∈ N∗ , existen
unos únicos q ∈ Z y r ∈ N con 0 ≤ r < b tales que a = bq + r.

Demostración Existencia. Sea A = {s : a − bs ≥ 0} ⊆ Z.

Señalemos que A está acotado superiormente y no es vacı́o. Ası́, si a ≥ 0, a es cota superior y
0 ∈ A y si a < 0, 0 es cota superior y a ∈ A.
Por tanto, existe q = max A. Llamemos r = a − qb. Como q ∈ A. 0 ≤ r. Además r < b, ya que
si r ≥ b, q + 1 ∈ A y q no serı́a el máximo.
Unicidad. Si bq + r = bq  + r , se tiene b(q − q  ) = r − r. Como −b < r − r < b, ha de ser
q − q  = 0. Luego, q = q  y r = r . ✷

Nota 3.4.2 Por tanto si definimos el conjunto de restos para b como Rb = {0, 1, · · · , b − 1}, el
algoritmo anterior proporciona una aplicación (“la aplicación resto módulo b”) rb : Z → Rb .

Una consecuencia elemental que se saca del algoritmo de la división con resto es la posibilidad de
expresar los números en la forma decimal acostumbrada. Veamos que también se pueden representar
con base en cualquier número natural.
November 4, 2002 33

Definición 3.4.3 Dados dos números a ∈ N y b ∈ N(2) , realizamos la división con resto a =
bq1 + a0 , con 0 ≤ a0 < b, luego q1 = bq2 + a1 , con 0 ≤ a1 < b, inductivamente llegamos a un
0 ≤ qk < b y definimos ak = qk . Entonces a = ak bk + · · · + a1 b + a0 con 0 ≤ a0 , a1 , · · · , ak < b.
Además estos a0 , a1 , · · · , ak son únicos. Decimos que ak ak−1 · · · a1 a0 es la expresión de a en base b.
A −ak ak−1 · · · a1 a0 le llamamos la expresión de −a en base b.

Nota 3.4.4 La notación habitual de los números naturales corresponde a base 10. Ası́ el número
27304 es 2 · 104 + 7 · 103 + 3 · 102 + 4.

Ejemplo 3.4.5 Expresar el número 27304 en base 8.

3.5 Congruencia y divisibilidad.

Definición 3.5.1 Dados a ∈ Z y b ∈ N∗ decimos que a es múltiplo de b (a = ḃ), o que b divide a a
(b|a), si existe un k ∈ Z tal que a = kb.

Nota 3.5.2 Nótese que, si a ∈ N∗ y b|a, se cumple b ≤ a.

Propiedad 3.5.3 Usando el algoritmo de la división con resto, b|a sii rb (a) = 0.

Definición 3.5.4 Dados a, b ∈ Z decimos que son congruentes modulo m ∈ N (a ≡ b mod m) si

b − a es múltiplo de m.

Nota 3.5.5 Notar que a es divisible por m sii a ≡ 0 mod m.

Ejemplo 3.5.6 Todo número impar es congruente con 1 mod 2.

Propiedad 3.5.7 La congruencia módulo m es una relación de equivalencia.

Demostración Verifica las tres propiedades. ✷

Definición 3.5.8 Dados a ∈ Z su clase de congruencia mod m es [a]m = {a + mq : q ∈ Z}. El

conjunto cociente se representa Zm .

Propiedad 3.5.9 Sean a, b ∈ Z. Entonces a ≡ b mod m sii rm (a) = rm (b).

Demostración Sea a = mq1 + r1 y b = mq2 + r2 . Entonces b − a = m(q2 − q1 ) + (r2 − r1 ), con lo

que m|(b − a) sii m|(r2 − r1 ). Como −m < r2 − r1 < m, m|(r2 − r1 ) sii r2 − r1 = 0. ✷

Nota 3.5.10 La relación de equivalencia asociada a rb es la misma que la dada por la congruencia,
con lo que la aplicación inducida r̄m : Zm → Rm es una biyección. Por tanto, otra forma de interpretar
el conjunto de clases de congruencia o enteros mod m es como el conjunto de restos.
November 4, 2002 34

Veamos ahora el comportamiento de la congruencia respecto a las operaciones aritméticas.

Propiedad 3.5.11 Sean a, b, a , b ∈ Z. Si a ≡ b mod m y a ≡ b mod m, entonces a + a ≡ b + b

mod m y −a ≡ −b mod m.

Corolario 3.5.12 La suma Z × Z → Z induce una “suma” Zm × Zm → Zm conservando las

propiedades.

Propiedad 3.5.13 Sean a, b, a , b ∈ Z. Si a ≡ b mod m y a ≡ b mod m, entonces aa ≡ bb mod

m.

Corolario 3.5.14 El producto Z × Z → Z induce un “producto” Zm × Zm → Zm conservando las

propiedades.

Nota 3.5.15 Mediante la biyección r̄m : Zm → Rm , inducimos la suma y el producto en Rm el

conjunto de los restos.

Propiedad 3.5.16 Sean a, b ∈ Z, n ∈ N+ . Si a ≡ b mod m, entonces an ≡ bn mod m.

Nota 3.5.17 i) Usando congruencia y su aritmética, se pueden enunciar y probar los criterios de
divisibilidad por 2, 3, 4, 5, 6, 8, 9, 10 y 11.
ii) Usando congruencia se obtienen criterios para ver si un número es cuadrado perfecto, e.g. todo
cuadrado perfecto, es congruente con 0 o con 1 mod 3.

3.6 El máximo común divisor. El algoritmo euclı́deo

Definamos el máximo común divisor y veamos un procedimiento de cálculo que ya está en “Los
Elementos” de Euclides.

Definición 3.6.1 Dados a, b ∈ N (alguno de ellos = 0), decimos que d es su máximo común divisor,
y lo expresamos d = (a, b), si cumple las dos propiedades
i) d divide a a y a b (es un divisor común)
ii) d es el mayor de los divisores comunes. O sea, todo d que divide a a y a b, cumple d ≤ d.

Teorema 3.6.2 Si d es el máximo común divisor de a y b, entonces

d = min{ma + nb : m, n ∈ Z∗ , ma + nb > 0}.

Demostración Sea d = min{ma + nb : m, n ∈ Z∗ , ma + nb > 0}. Veamos que divide a a y a b.

Por la división con resto, existen q y r, con 0 ≤ r < d , tales que a = qd + r. Si r = 0, entonces
r ∈ {ma + nb : m, n ∈ Z∗ , ma + nb > 0}, por lo que r ≥ d , contradiciendo r < d . Por tanto, d
divide a a. Igualmente, divide a b y, como consecuencia, d ≤ d.
Por otra parte, como d divide a a y a b, divide a toda expresión de la forma ma + nb. En
particular, d divide a d . Luego, d ≤ d . ✷
November 4, 2002 35

Nota 3.6.3 El hecho de que el máximo común divisor se puede expresar como ma + nb es conocido
como “igualdad de Bezout”.

Corolario 3.6.4 Todo divisor común divide al máximo común divisor.

Demostración Por la igualdad de Bezout, todo divisor de a y b divide a d. ✷

Nota 3.6.5 Esto da una caracterización más habitual del máximo común divisor como aquel que
i) Divide a a y a b y ii) Es divisible por todos los divisores comunes.

Corolario 3.6.6 Dados dos números, b|a sii (a, b) = b.

Lema 3.6.7 Dados dos números a, b, si a = bq + r es el resultado de aplicar la división con resto,
se cumple (a, b) = (b, r)

Demostración Probar que d divide a a y b sii divide a b y r es fácil, dada la ecuación a = bq + r

(y su equivalente r = a − bq). ✷

Teorema 3.6.8 Dados dos números a, b definimos a0 = a y a1 = b. Realizamos la división con resto
a0 = a1 q1 + r1 , con 0 ≤ r1 < a1 . Llamamos a2 = r1 . Inductivamente ak = ak+1 qk+1 + rk+1 , con
0 ≤ rk < ak = rk−1 < rk−2 < · · · < b. Como el resto disminuye, llegamos a un primer caso en el que
rn = 0. Entonces (a, b) = an

Demostración Por el lema (ao , a1 ) = (a1 , a2 ) = · · · = (an−1 , an ) = an

✷

Nota 3.6.9 Vamos a hacer un ejemplo fácil (72, 30) por ejemplo) y ver que de los cálculos se puede
extraer los coeficientes m, n de la “igualdad de Bezout”.

3.7 Factorización.
Vamos a ver el resultado clásico de descomposición de todo número natural en producto de factores
indescomponibles. Fijemos primero estos.

Definición 3.7.1 Decimos que p ∈ N es primo si es divisible sólo por 1 y por él mismo. Entonces
no se puede expresar como producto de dos números naturales distintos de la unidad.

Ejemplo 3.7.2 Por ejemplo, es fácil ver que 2 es primo.

Nota 3.7.3 Aunque 1 satisface esta definición es costumbre no considerarlo primo, ya que en todos
los teoremas posteriores 1 serı́a un caso especial. Entonces, a partir de ahora, 1 no es primo.
November 4, 2002 36

Veamos que todo número natural puede descomponerse en forma única como producto de primos.

Teorema 3.7.4 Dado un número a ∈ N(2) existe un número finito de primos p1 , p2 , · · · , pn tal que
a = p 1 p2 · · · pn .

Demostración Veámoslo por inducción en a, usando la hipótesis débil de inducción.

El resultado es cierto para a = 2.
Sea cierto para todo b < a y probémoslo para a. Si a es primo ya está. Si no, tiene un divisor
d < a. Con ello, a = da . Como d, a < a por inducción cada uno admite descomposición. ✷

Nota 3.7.5 Reordenando los primos ası́ obtenidos, se llega a una descomposición en factores a =
p1 p2 · · · pn 1 ≤ p1 ≤ p2 ≤ · · · ≤ pn . Agrupando los factores iguales, se obtiene a = q1r1 q2r2 · · · qkrk con
1 < q1 < q2 < · · · < qk . A estas dos maneras le llamamos factorización estándar. Vamos a probar su
unicidad.

Lema 3.7.6 Dados números a, b, c con c|ab. Si (a, c) = 1, entonces c|b.

Demostración Como (a, c) = 1, existen m, n tales que am + cn = 1, por lo que b = abm + cbn.
Como c divide a ab, también divide a b. ✷

Corolario 3.7.7 Sean p, p1 , p2 , · · · , pn números primos. Si p|p1 p2 · · · pn , hay un 1 ≤ i ≤ n tal que

p = pi .

Demostración Como son primos, (p, pi ) = 1 o (p, pi ) = p, siendo (p, pi ) = p si p = pi y (p, pi ) = 1

si p = pi .
Si (p, pi ) = 1 para todo i = 2, · · · , k, por aplicación inductiva del lema anterior llegamos a p|p1 ,
luego p = p1 . ✷

Teorema 3.7.8 Dadas dos factorizaciones de un número a = p1 p2 · · · pn = p 1 p 2 · · · p m se tiene

n = m y pi = p i ..

Demostración Vamos a probar por inducción en n. Explicitemos sólo el paso de inducción.

Como p1 |a, por el último corolario, debe existir algún p j tal que p j = p1 . Si j = 1, dividimos
por p1 obteniendo p2 · · · pn = p 2 · · · p m . Por inducción sale.
Si j = 1, de forma simétrica, obtenemos un k tal que p 1 = pk . Entonces, se tendrı́a p1 = p j >
p 1 = pk que es una contradicción con p1 ≤ pk .
✷