Teorema fundamental de la Aritmética

De Wikipedia, la enciclopedia libre

En matemática, y particularmente en la teoría de números, el teorema fundamental de la Aritmética es la afirmación de que todo entero positivo se puede representar como producto de factores primos de una forma única, salvo el orden.

Por ejemplo, podemos escribir

6936 = 2³ · 3 · 17²

1200 = 2⁴ · 3 · 5²

y no existe ninguna otra factorización de 6936 y 1200 en números primos, excepto cambiando el orden de los factores anteriores.

Para hacer que el Teorema vaya bien con el número 1, pensaremos en 1 como el producto de cero factores primos (véase producto vacío).

[editar] Aplicaciones

El teorema establece la importancia de los números primos. En esencia, son los "ladrillos básicos" con los que se "construyen" los enteros positivos, en el sentido de que todo entero positivo puede construirse a partir de los números primos de una única manera.

Conocer la factorización de un número en factores primos es conocer todos y cada uno de los factores del mismo. Por ejemplo, la factorización de 6936 nos dice que los factores positivos de 6936 son de la forma

2^a · 3^b · 17^c

con [0 ≤ a ≤ 3], [0 ≤ b ≤ 1], y [0 ≤ c ≤ 2]. Esto supone un total de 4 · 2 · 3 = 24 factores positivos.

Una vez que se conoce la factorización de dos números en sus respectivos factores primos, se puede hallar fácilmente su máximo común divisor (m.c.d.) y mínimo común múltiplo (m.c.m.). Por ejemplo, de las factorizaciones anteriores de 6936 y 1200, podemos inferir que su m.c.d. es 2³ · 3 = 24. Sin embargo, si no se conocen los factores primos, el uso del algoritmo de Euclides, en general, requiere muchos menos cálculos que la factorización de los dos números.

El teorema fundamental asegura que las funciones aritméticas aditivas y multiplicativas están completamente determinadas por sus valores en las potencias de los números primos.

[editar] Demostración

Existen varias pruebas de este teorema que fue descubierto por los griegos hace más de dos milenios: las pruebas por reducción al absurdo y las pruebas constructivas (es decir que permiten efectivamente encontrar tal factorización, o descomposición, en factores primos). Si la prueba ad absurdum no es significativamente más corta se prefiere la constructiva. Empezaremos con la prueba por reducción al absurdo.

La demostración por reducción al absurdo tiene dos partes: primero, hemos de mostrar que todo número entero positivo puede en efecto escribirse como producto de primos, y después tenemos que probar que dos representaciones de un número en factores primos son esencialmente iguales.

Existencia: Supóngase que existe algún entero positivo que no puede representarse como producto de primos. Entonces, entre todos los números para los que el teorema falla, debe existir un número más pequeño: llamémosle n. Este número n no puede ser 1, por la convención anterior. Tampoco puede ser un número primo, porque todo número primo es el producto de un único número primo: él mismo. Así que n = ab, donde a y b son enteros positivos menores que n. Como n es el número más pequeño para el que falla el teorema, entonces tanto a como b pueden escribirse como producto de primos. Pero entonces n = ab también puede escribirse como producto de primos, con lo que obtenemos una contradicción.

Unicidad (1ª demostración): La demostración de la unicidad se apoya en el siguiente hecho: si un número primo p divide a un producto ab, entonces divide a a o divide a b.

Si p no divide a a, entonces p y a son primos entre sí y por la identidad de Bézout existen x e y enteros tales que px + ay = 1. Multiplicando por b se obtiene que pbx + aby = b. Los dos sumandos del término de la izquierda son divisibles por p, así que el término de la derecha también es divisible por p.

Ahora tómense dos productos de primos que sean iguales. Escójase un factor primo p del primer producto. Divide al primer producto, y por lo tanto también divide al segundo. Por el hecho anterior, p debe dividir al menos a un factor del segundo producto, pero todos los factores son primos, así que p debe ser igual a uno de los factores del segundo producto. Así que podemos cancelar a p de ambos productos. Siguiendo de esta forma, acabaremos viendo que los factores primos de los dos productos se corresponden exactamente.

Unicidad (2ª demostración): También se puede emplear el método del descenso infinito para demostrar la unicidad de la factorización de un entero dado en números primos.

Supóngase que cierto número entero puede escribirse como producto de factores primos de (al menos) dos maneras distintas. Entonces, debe existir un número que sea el más pequeño de los que cumplen esa propiedad: llamémosle s. Sean p₁*...*p_m y q₁*...*q_n las dos factorizaciones de s. Ningún p_i (con 1≤i≤m) puede ser igual a un q_j (con 1≤j≤n), porque de lo contrario habría un número más pequeño que s que puede factorizarse de dos maneras (concretamente s dividido entre los factores primos comunes en sus dos factorizaciones), lo que contradiría nuestra suposición.

Ahora podemos asumir sin pérdida de generalidad que p₁ es un factor primo más pequeño que cualquier q_j (con 1≤j≤n). Tómese q₁. Entonces existen d y r enteros tales que q₁/p₁ = d+r/p₁ y 0<r<p₁<q₁ (r no puede ser 0, ya que, de lo contrario, q₁ sería un múltiplo de p₁ y por tanto compuesto). Obtenemos p₂×...×p_m = (d+r/p₁)×q₂×...×q_n = d×q₂×...×q_n+r*q₂×...×q_n/p₁.

El segundo término de la última expresión debe ser igual a un entero que llamaremos k, y en efecto k=r×q₂×...×q_n/p₁. A partir de esto, obtenemos p₁×k = r×q₂×...×q_n. El valor de los dos términos de esta ecuación es obviamente menor que s, pero sigue siendo lo bastante grande como para ser factorizable. Como r es menor que p₁, las dos factorizaciones que obtenemos en cada lado, después de haber escrito k y r como producto de primos, deben ser diferentes. Esto contradice la suposición de que s es el entero más pequeño que puede factorizarse de más de una forma. Por tanto, la suposición debe ser falsa.

La prueba constructiva sugiere el método siguiente: encontramos dos (o más) factores obvios (y de ser posible bastante grandes), a y b tales que n = a×b de n, y luego descomponemos a y b y repetimos la operación hasta obtener solo factores primos. La mejor representación es la de un árbol cuya "raíz" es el número por descomponer y las hojas son los factores primos. Con los ejemplos precedentes se obtiene el esquema de la derecha:

Imagen:descomposición_mediante_divisiones.png

Si no hay factores grandes obvios, el método alternativo es tratar de dividir n por todos los primos empezando por el 2 y después de haberlo agotado el 3 y así sucesivamente, dividiendo a medida por los factores y ayudándose de los criterios de divisibilidad.
El cálculo se presenta como una sucesión de divisiones y concluye cuando aparece el 1, indivisible.
Nótese también que cuando se busca un factor primo de un entero n, no hay que ir más allá de su raíz cuadrada √n: En efecto si existe un factor a mayor que √n también habrá uno menor (concretamente: n/a)

Véase: Algoritmo de factorización en números primos