6.1: El teorema fundamental de la aritmética

En los últimos capítulos, hemos encontrado todas las principales técnicas de prueba que uno necesita en matemáticas y mejorado nuestras habilidades de prueba de escritura. En este capítulo, ponemos a trabajar estas técnicas y habilidades para probar tres teoremas famosos, así como numerosos resultados intermedios en el camino. Todos estos teoremas son aquellos con los que probablemente estés familiarizado desde la escuela primaria, pero quizás estos hechos nunca fueron justificados rigurosamente para ti.

En la primera sección, desarrollamos todos los conceptos necesarios para afirmar y luego probar el Teorema Fundamental de la Aritmética (Teorema 6.17), que quizás no reconozcas por nombre. El Teorema Fundamental de la Aritmética establece que cada número natural mayor que 1 es el producto de una combinación única de números primos. Para probar el Teorema Fundamental de la Aritmética, necesitaremos hacer uso del Algoritmo de División (Teorema 6.7), que a su vez utiliza el Principio de Ordenación del Bien (Teorema 4.38). En el segundo apartado, probamos que √ 2 es irracional, lo que resuelve una pretensión hecha en la Sección 5.1. En la sección final, demostramos que hay infinitamente muchos primos.

El objetivo de esta sección es probar El Teorema Fundamental de la Aritmética. El Teorema Fundamental de la Aritmética (a veces llamado Teorema de Factorización Único) establece que cada número natural mayor que 1 es primo o es producto de números primos, donde este producto es único hasta el orden de los factores. Por ejemplo, el número natural 12 tiene factorización prima\(2^2\cdot 3\), donde el orden en que escribimos los factores primos (es decir, 2, 2 y 3) es irrelevante. Es decir,\(2^2\cdot 3\),\(2\cdot 3\cdot2\), y\(3\cdot 2^2\) son todos la misma factorización prima de 12. El requisito de que los factores sean primos es necesario ya que las factorizaciones que contienen números compuestos pueden no ser únicas. Por ejemplo,\(12=2\cdot 6\) y\(12=3\cdot 4\), pero estas factorizaciones en números compuestos son distintas. Acabamos de lanzar unos términos elegantes; debemos asegurarnos de entender su significado preciso.

Definición 6.1. Vamos\(n\in\mathbb{Z}\).

1. Si\(a\in \mathbb{Z}\) tal eso\(a\) divide\(n\), entonces decimos que\(a\) es un factor de\(n\).
2. Si\(n\in \mathbb{N}\) tal que\(n\) tiene exactamente dos factores positivos distintos (a saber, 1 y\(n\) sí mismo), entonces\(n\) se llama primo.
3. Si\(n>1\) tal eso no\(n\) es primo, entonces\(n\) se llama compuesto.

Problema 6.2. Según nuestra definición, ¿es 1 un número primo o un número compuesto? Explica tu respuesta. Es posible que hayas escuchado números primos definidos como algo así como, “un número primo es un número natural que solo es divisible por 1 y por sí mismo”. ¿Esta definición concuerda con la anterior?

El resultado es que según nuestra definición, 1 no es ni primo ni compuesto. No obstante, a lo largo de la historia, no siempre ha sido así. Hubo momentos en los que y matemáticos para quienes el número uno se consideraba primo. Que 1 sea primo o no es una cuestión de definición y, por lo tanto, una cuestión de elección. Hay razones convincentes —que no vamos a explicar aquí— por qué 1 es excluido intencionalmente de ser prime. No obstante, si quieres saber más, consulta el excelente artículo “¿Qué es el Prime más pequeño?” de Chris Caldwell y Yeng Xiong.

Problema 6.3. Enumere los primeros 10 números primos.

Problema 6.4. Probar o proporcionar un contraejemplo: Para todos\(n\in\mathbb{N}\), si\(4^n-1\) es primo, entonces\(n\) es impar.

Problema 6.5. Probar o proporcionar un contraejemplo: Para todos\(n\in\mathbb{N}\),\(n^2-n+11\) es primo.

El siguiente resultado constituye la mitad del Teorema Fundamental de la Aritmética. Proporcionamos una pista sustancial para su prueba. \(S\)Sea el conjunto de números naturales para los que falla el teorema. En aras de una contradicción, asumamos\(S\neq \emptyset\). Por el Principio Bien Ordenado (Teorema 4.38),\(S\) contiene un elemento mínimo, digamos\(n\). Entonces\(n\) no puede ser primo ya que esto satisfacería el teorema. Entonces, debe darse el caso que\(n\) tenga un divisor distinto al 1 y a sí mismo. Esto implica que existen números naturales\(a\) y\(b\) mayores a 1 tal que\(n=ab\). Ya que\(n\) fue nuestro contraejemplo más pequeño, ¿qué se puede concluir sobre ambos\(a\) y\(b\)? Utilice esta información para derivar un contraejemplo para\(n\).

Teorema 6.6. Si\(n\) es un número natural mayor a 1, entonces se\(n\) puede expresar como un producto de primos. Es decir, podemos escribir\[n=p_1 p_2 \cdots p_k,\] donde cada uno de\(p_1, p_2, \ldots, p_k\) es un número primo (no necesariamente distinto).

El teorema 6.6 establece que podemos escribir cada número natural mayor que 1 como producto de primos, pero no dice que los primos y el número de veces que aparece cada primo sean únicos. Para probar la singularidad, necesitaremos el Lema de Euclides (Teorema 6.15). Para probar el Lema de Euclides, utilizaremos un caso especial del Lema de Bézout (Teorema 6.13), cuya prueba se basa en el siguiente resultado, conocido como Algoritmo de División. A continuación incluimos la prueba del Algoritmo de División, que hace uso del Principio de Ordenación del Bien (Teorema 4.38).

Teorema 6.7. Si\(n,d\in\mathbb{Z}\) tal eso\(d>0\), entonces existe único\(q,r\in\mathbb{Z}\) tal que\(n=dq+r\) con\(0\leq r<d\).

Que\(n,d\in\mathbb{Z}\) tal que\(d>0\) tal eso\(n>0\). Tenemos dos tareas. Primero, tenemos que demostrar eso\(q\) y\(r\) existir, y luego tenemos que demostrar que ambos son únicos.

Si\(d=1\), es claro que podemos tomar\(q=n\) y\(r=0\), para que\(n=1\cdot n+0=dq+r\), como se desee. Ahora bien, supongamos eso\(d>1\) y definimos\[S:= \{n-dk\mid k\in\mathbb{Z}\text{ and } n-dk\geq 0\}.\] Si podemos demostrar eso\(S\neq\emptyset\), entonces podemos aplicar el Principio de Ordenamiento Bien (Teorema 4.38) para concluir que\(S\) tiene un elemento menor de S. Este elemento menor será el resto\(r\) que están buscando. Hay dos casos.

Primero, supongamos\(n\geq 0\). Si tomamos\(k=0\), entonces obtenemos\(n-dk=n-d\cdot 0=n\geq 0\), lo que demuestra que\(n\in S\).

Ahora, supongamos\(n<0\). En este caso, podemos tomar\(k=n\), así que eso\(n-dk=n-dn=n(1-d)\). Desde\(n<0\) y\(d>1\),\(n(1-d)>0\). Esto demuestra que\(n-dn\in S\).

Eso lo hemos demostrado\(S\neq\emptyset\), y así\(S\) contiene un elemento mínimo\(r=n-dq\) para algunos\(q\in\mathbb{Z}\). Después\(n=dq+r\) con\(r\geq 0\). En aras de una contradicción, asumamos\(r\geq d\). Esto implica que existe\(r'\in \mathbb{Z}\) tal que\(r=d+r'\) y\(0\leq r'<r\). Pero luego vemos que\[n=dq+r=dq+d+r'=d(q+1)+r'.\] Esto implica eso\(r' = n-d(q+1)\). Ya que\(0\leq r'<r\), hemos producido un elemento de\(S\) que es menor que\(r\). Esto contradice el hecho de que\(r\) es el menor elemento de\(S\), y así\(r<d\).

Queda por demostrarlo\(q\) y\(r\) son únicos. Supongamos\(q_1,q_2, r_1,r_2\in\mathbb{Z}\) tal que\(n=dq_1+r_1\) y\(n=dq_2+r_2\) y\(0\leq r_1,r_2<d\). Sin pérdida de generalidad, supongamos\(r_2\geq r_1\), así que eso\(0\leq r_2-r_1<d\). Ya que\(dq_1+r_1=dq_2+r_2\), vemos eso\(r_2-r_1=d(q_1-q_2)\). Pero luego\(d\) divide\(r_2-r_1\). Si\(r_2-r_1>0\), entonces por el Teorema 2.56, debe ser el caso que\(r_2-r_1\geq d\). No obstante, lo sabemos\(0\leq r_2-r_1<d\), y así debemos haberlo hecho\(r_2-r_1=0\). Por lo tanto\(r_1=r_2\),, lo que a su vez implica\(q_1=q_2\). Eso lo hemos demostrado\(q\) y\(r\) somos únicos.

En el Algoritmo de División, llamamos\(n\) al dividendo,\(d\)\(q\) al divisor, al cociente y\(r\) al resto. Cabe señalar que el Algoritmo de División sostiene de manera más general donde no\(d\) se requiere que el divisor sea positivo. En este caso, debemos\(0\leq r<n\) sustituir por\(0\leq r<|n|\).

Contrariamente a su nombre, nuestra afirmación del Algoritmo de División no es en realidad un algoritmo, sino que este es el nombre tradicional del teorema. Sin embargo, hay un algoritmo enterrado en este teorema. Si no\(n\) es negativo, restar repetidamente\(d\) de\(n\) hasta obtener un valor entero que se encuentra entre 0 (inclusive) y\(d\) (exclusivo). El valor resultante es el resto\(r\) mientras que el número de veces que\(d\) se resta es el cociente\(q\). Por otro lado, si\(n\) es negativo, sumamos repetidamente\(d\) a\(n\) hasta que obtengamos un valor entero que se encuentra entre 0 (inclusivo) y\(d\) (exclusivo). Nuevamente, el valor resultante es\(r\). No obstante, en este caso, tomamos\(-q\) para ser el número de veces que\(d\) se agrega, de manera que\(q\) (un valor negativo) es el cociente.

Problema 6.8. Supongamos\(n=27\) y\(d=5\). Encuentra el cociente y el resto que están garantizados para existir por el Algoritmo de División. Es decir, encontrar lo único\(q,r\in\mathbb{Z}\) tal que\(0\leq r<n\) y\(n=dq+r\).

Es un poco más difícil de determinar\(q\) y\(r\) cuándo\(n\) es negativo.

Problema 6.9. Supongamos\(n=-26\) y\(d=3\). Encuentra el cociente y el resto que están garantizados para existir por el Algoritmo de División. Es decir, encontrar lo único\(q,r\in\mathbb{Z}\) tal que\(0\leq r<n\) y\(n=dq+r\).

Es útil tener alguna terminología adicional.

Definición 6.10. Que\(m,n\in\mathbb{Z}\) tal que al menos uno de\(m\) o\(n\) sea distinto de cero. El mayor divisor común (gcd) de\(m\) y\(n\), denotado\(\gcd(m,n)\), es el mayor entero positivo que divide ambos\(m\) y\(n\). Si\(\gcd(m,n)=1\), decimos eso\(m\) y\(n\) son relativamente primos.

Problema 6.11. Encontrar\(\gcd(54,72)\).

Problema 6.12. Proporcione un ejemplo de dos números naturales que son relativamente primos.

El siguiente resultado es un caso especial de un teorema conocido como Lema de Bézout (o Identidad de Bézout). En última instancia, necesitaremos este teorema para probar el Lema de Euclides (Teorema 6.15), que luego usamos para demostrar la singularidad para el Teorema Fundamental de la Aritmética (Teorema 6.17). Para probar nuestro caso especial del Lema de Bézout, considera el conjunto\(S:= \{ps+at> 0\mid s,t\in \mathbb{Z}\}\). Primero, observa eso\(p\in S\) (elige\(s=1\) y\(t=0\)). De ello se deduce que no\(S\) está vacío. Por el Principio Bien Ordenado (Teorema 4.38),\(S\) contiene un elemento mínimo, digamos\(d\). Esto implica que existe\(s_1,t_1\in \mathbb{Z}\) tal que\(d=ps_1+at_1\). Nuestro objetivo es demostrarlo\(d=1\). Ahora, elige\(m\in S\). Entonces existe\(s_2,t_2\in \mathbb{Z}\) tal que\(m=ps_2+at_2\). Por la definición de\(d\), sabemos\(d\leq m\). Por el Algoritmo de División, existe único\(q,r\in \mathbb{N}\cup\{0\}\) tal que\(m=qd+r\) con\(0\leq r < d\). Ahora, resolver para\(r\) y luego reemplazar\(m\) y\(d\) con\(ps_1+at_1\) y\(ps_2+at_2\), respectivamente. Deberías terminar con una expresión por\(r\) involucrar\(p, a, s_1, s_2, t_1\), y\(t_2\). A continuación, reorganice esta expresión para obtener\(r\) como una combinación lineal de\(p\) y\(a\) (es decir, una suma de un múltiplo de\(p\) y un múltiplo de\(a\)). ¿Qué\(d\) implica la minimalidad de\(r\)? Deberías poder concluir que\(m\) es un múltiplo de\(d\). Es decir, cada elemento de\(S\) es un múltiplo de\(d\). Sin embargo, recordemos que\(p\in S\),\(p\) es primo,\(p\) y\(a\) son relativamente primos. ¿De qué se puede concluir\(d\)?

Teorema 6.13. Si\(p,a\in\mathbb{Z}\) tal que\(p\) es primo y\(p\) y\(a\) son relativamente primos, entonces existe\(s,t\in\mathbb{Z}\) tal que\(ps+at=1\).

Problema 6.14. Considera los números naturales 2 y 7, que resultan ser relativamente primos. Encuentra enteros\(s\) y\(t\) garantiza que existen según el Teorema 6.13. Es decir, encontrar\(s,t\in\mathbb{Z}\) tal que\(2s+7t=1\).

El siguiente teorema se conoce como Lema de Euclides. Obsérvese que si\(p\) divide\(a\), la conclusión es ciertamente cierta. Entonces, supongamos lo contrario. Es decir, supongamos que\(p\) no divide\(a\), así que eso\(p\) y\(a\) son relativamente primos. Aplicar el Teorema 6.13 a\(p\)\(a\) y luego multiplicar la ecuación resultante por\(b\). Trate de concluir que\(p\) divide\(b\).

Teorema 6.15. Supongamos que\(p\) es primo. Si\(p\) divide\(ab\), dónde\(a,b\in\mathbb{N}\), entonces\(p\) divide\(a\) o\(p\) divide\(b\).

En el Lema de Euclides, es crucial que\(p\) sea primo como lo ilustra el siguiente problema.

Problema 6.16. Proporcionar un ejemplo de enteros\(a, b, d\) tales que\(d\) divide\(ab\) pero\(d\) no divide\(a\) y\(d\) no divide\(b\).

Bien, finalmente estamos listos para abordar la prueba del Teorema Fundamental de la Aritmética. Dejar\(n\) ser un número natural mayor a 1. Por Teorema 6.6, sabemos que se\(n\) puede expresar como un producto de primos. Todo lo que queda es demostrar que este producto es único (hasta el orden en que aparecen). En aras de una contradicción, supongamos\(p_1 p_2 \cdots p_k\) y\(q_1 q_2 \cdots q_l\) son ambas factorizaciones primordiales de\(n\). Tu objetivo es demostrarlo\(k=l\) y que cada uno\(p_i\) es igual a algunos\(q_j\). Hacer uso repetido del Lema de Euclides.

Teorema 6.17. Cada número natural mayor a 1 se puede expresar de manera única (hasta el orden en que aparecen) como producto de uno o más primos.

El Teorema Fundamental de la Aritmética es una de las muchas razones por las que 1 no se considera un número primo. Si 1 fuera primo, las factorizaciones de primos no serían únicas.