1.12: Factorización Única
- Page ID
- 117419
Nuestro objetivo en este capítulo es probar el siguiente teorema fundamental.
Cada entero se\(n>1\) puede escribir de forma única en la forma\[n=p_1p_2\dotsm p_s,\nonumber \] donde\(s\) es un entero positivo y\(p_1,p_2,\dotsc,p_s\) son primos satisfactorios\[p_1\le p_2\le\dotsb\le p_s.\nonumber \]
Si\(n=p_1p_2\dotsm p_s\) donde cada uno\(p_i\) es primo, llamamos a esto la factorización prima de\(n\). Teorema a veces\(\PageIndex{1}\) se afirma de la siguiente manera:
Cada entero\(n>1\) puede expresarse como un producto\(n=p_1p_2\dotsm p_s\), para algún entero positivo\(s\), donde cada uno\(p_i\) es primo y esta factorización es única excepto por el orden de los primos\(p_i\).
Tenga en cuenta por ejemplo que\[\begin{split} 600 &=2\cdot 2\cdot 2\cdot 3\cdot 5\cdot 5 \\ &=2\cdot 3\cdot 2\cdot 5\cdot 2\cdot 5 \\ &=3\cdot 5\cdot 2\cdot 2\cdot 2\cdot 5 \\ &\quad\text{etc.} \end{split}\]
Quizás la mejor manera de escribir la factorización principal de\(600\) es\[600=2^3\cdot 3\cdot 5^2.\nonumber \]
En general es claro que se\(n>1\) puede escribir de manera única en la forma\[n=p_1^{a_1}p_2^{a_2}\dotsm p_s^{a_s}\text{, some }s\ge 1,\nonumber \] donde\(p_1<p_2<\dotsb<p_s\) y\(a_i\ge 1\) para todos\(i\). A veces el producto se escribe como\[n=\prod_{i=1}^s p_i^{a_i}\,.\nonumber \] Aquí\(\displaystyle\prod\) significa producto, así como\(\displaystyle\sum\) significa suma.
Para probar el Teorema\(\PageIndex{1}\) necesitamos establecer primero algunos lemmas.
Si\(a\mid bc\) y\(\gcd(a,b)=1\) entonces\(a\mid c\).
Prueba
Ya que\(\gcd(a,b)=1\) por el Lema de Bezout hay\(s\),\(t\) tal que\[1=as+bt.\nonumber \] Si multiplicamos ambos lados\[c=cas+cbt=a(cs)+(bc)t.\nonumber \] por\(c\) obtenemos Por suposición\(a\mid bc\). Claramente\(a\mid a(cs)\) así, por el Teorema 1.4.1,\(a\) divide la combinación lineal\(a(cs)+(bc)t=c\).
Eso decimos\(a\) y\(b\) son relativamente primos si\(\gcd(a,b)=1\).
Entonces podemos reafirmar Lemma de la\(\PageIndex{1}\) siguiente manera: Si\(a\mid bc\) y\(a\) es relativamente primo para\(b\) entonces\(a\mid c\).
No es cierto generalmente que cuando\(a\mid bc\) entonces\(a\mid b\) o\(a\mid c\). Por ejemplo,\(6\mid 4\cdot 9\), pero\(6\nmid 4\) y\(6\nmid 9\). Tenga en cuenta que Lemma\(\PageIndex{1}\) no aplica aquí desde\(\gcd(6,4)\ne 1\) y\(\gcd(6,9)\ne 1\).
Si\(p\) es un primo y\(p\mid ab\), entonces\(p\mid a\) o\(p\mid b\).
Prueba
Asumir eso\(p\mid ab\). Si\(p\mid a\) hemos terminado. Supongamos\(p\nmid a\). Vamos\(d=\gcd(p,a)\). Tenga en cuenta que\(d>0\) y\(d\mid p\) y\(d\mid a\). Ya\(d\mid p\) que tenemos\(d=1\) o\(d=p\). Si\(d\ne 1\) entonces\(d=p\). Pero esto dice eso\(p\mid a\), lo que suponíamos que no era cierto. Entonces debemos tener\(d=1\). De ahí\(\gcd(p,a)=1\) y\(p\mid ab\). Entonces por Lemma\(\PageIndex{1}\),\(p\mid b\).
\(p\)Déjese ser prime. Dejemos\(a_1,a_2,\dotsc,a_n\)\(n\ge 1\),, ser enteros. Si\(p\mid a_1a_2\dotsm a_n\), entonces\(p\mid a_i\) para al menos uno\(i\in\{1,2,\dotsc,n\}\).
Prueba
Utilizamos inducción on\(n\), el número de enteros multiplicados en el producto. El resultado es claro si\(n=1\). Supongamos que el lema se sostiene para\(n\) tal que\(1\le n\le k\). Demostremos que se mantiene para\(n=k+1\). Entonces\(p\) asumamos que es un primo y\(p\mid a_1a_2\dotsm a_ka_{k+1}\). Dejar\(a=a_1a_2\dotsm a_k\) y\(b=a_{k+1}\). Entonces\(p\mid a\) o\(p\mid b\) por Lema\(\PageIndex{2}\). Si\(p\mid a=a_1\dotsm a_k\), por la hipótesis de inducción,\(p\mid a_i\) para algunos\(i\in\{1,\dotsc,k\}\). Si\(p\mid b=a_{k+1}\) entonces\(p\mid a_{k+1}\). Entonces podemos decir\(p\mid a_i\) para algunos\(i\in\{1,2,\dotsc,k+1\}\). Entonces el lema aguanta para\(n=k+1\). De ahí por PMI se sostiene para todos\(n\ge 1\).
Si\(n>1\) entonces existen primos\(p_1,\dotsc,p_s\) para algunos\(s\ge 1\) tales que\[n=p_1p_2\dotsm p_s\nonumber \] y\(p_1\le p_2\le\dotsb\le p_s\).
Prueba
Prueba por inducción encendido\(n\), con valor inicial\(n=2\): Si\(n=2\) entonces ya que\(2\) es primo podemos tomar\(p_1=2\),\(s=1\). Asumir el lema sostiene para\(n\) tal que\(2\le n\le k\). Demostremos que se mantiene para\(n=k+1\). Si\(k+1\) es prime podemos tomar\(s=1\) y\(p_1=k+1\) y ya terminamos. Si\(k+1\) es compuesto podemos escribir\(k+1=ab\) dónde\(1<a<k+1\) y\(1<b<k+1\). Por la hipótesis de inducción hay primos\(p_1,\dotsc,p_u\) y\(q_1,\dotsc,q_v\) tales que\[a=p_1\dotsm p_u\text{ and }b=q_1\dotsm q_v.\nonumber \] Esto nos da es\[k+1=ab=p_1p_2\dotsm p_uq_1q_2\dotsm q_v,\nonumber \] decir,\(k+1\) es un producto de primos. Vamos\(s=u+v\). Al reordenar y volver a etiquetar cuando sea necesario, tenemos\[k+1=p_1p_2\dotsm p_s,\nonumber \] donde\(p_1\le p_2\le\dotsb\le p_s\). Entonces el lema aguanta para\(n=k+1\). De ahí que por PMI, se sostiene para todos\(n>1\).
Dejar\[n=p_1p_2\dotsm p_s \mbox{ for some } s\ge 1,\nonumber \] y\[n=q_1q_2\dotsm q_t \mbox{ for some } t\ge 1,\nonumber \] dónde\(p_1,\dotsc,p_s,q_1,\dotsc,q_t\) están los primos satisfactorios\[p_1\le p_2\le\dotsb\le p_s\nonumber \] y\[q_1\le q_2\le\dotsb\le q_t.\nonumber \] Entonces,\(t=s\) y\(p_i=q_i\) para\(i=1,2,\dotsc,t\).
Prueba
Nuestra prueba es por inducción en\(s\). Supongamos\(s=1\). Entonces\(n=p_1\) es primo y tenemos\[p_1=n=q_1q_2\dotsm q_t.\nonumber \] Si\(t>1\), esto contradice el hecho de que\(p_1\) es primo. Entonces\(t=1\) y tenemos\(p_1=q_1\), como se desee. Ahora supongamos que el resultado se mantiene para todos\(s\) tales que\(1\le s\le k\). Queremos demostrar que se sostiene para\(s=k+1\). Así que\[n=p_1p_2\dotsm p_kp_{k+1}\nonumber \] asumamos y\[n=q_1q_2\dotsm q_t\nonumber \] dónde\(p_1\le p_2\le\dotsb\le p_{k+1}\) y\(q_1\le q_2\le\dotsb\le q_t\). Claramente\(p_{k+1}\mid n\) así\(p_{k+1}\mid q_1\dotsm q_t\). Entonces por Lemma\(\PageIndex{3}\)\(p_{k+1}\mid q_i\) para algunos\(i\in\{1,2,\dotsc,t\}\). Del Ejercicio 1.11.3 se desprende que\(p_{k+1}=q_i\). De ahí\(p_{k+1}=q_i\le q_t\).
Por un argumento similar\(q_t\mid n\) así\(q_t\mid p_1\dotsm p_{k+1}\) y\(q_t=p_j\) para algunos\(j\). De ahí\(q_t=p_j\le p_{k+1}\). Esto demuestra que\[p_{k+1}\le q_t\le p_{k+1}\nonumber \] así\(p_{k+1}=q_t\). Tenga en cuenta que\[p_1p_2\dotsm p_kp_{k+1}=q_1q_2\dotsm q_{t-1}q_t\nonumber \] ya\(p_{k+1}=q_t\) podemos cancelar este prime desde ambos lados y tenemos\[p_1p_2\dotsm p_k=q_1q_2\dotsm q_{t-1}.\nonumber \] Ahora por la hipótesis de inducción\(k=t-1\) y\(p_i=q_i\) para\(i=1,\dotsc,t-1\). Así tenemos\(k+1=t\) y\(p_i=q_i\) para\(i=1,2,\dotsc,t\). Entonces el lema se sostiene para\(s=k+1\) y por el PMI, sostiene para todos\(s\ge 1\).
Ahora la prueba del Teorema\(\PageIndex{1}\) sigue inmediatamente de Lemmas\(\PageIndex{4}\) y \(\PageIndex{5}\).
Si\(a\) y\(b\) son enteros positivos podemos encontrar primos\(p_1,\dotsc,p_k\) y enteros\(a_1,\dotsc,a_k,b_1,\dotsc,b_k\) cada uno\(\ge 0\) tal que\[\label{eq11-2ast} \begin{cases} a=p_1^{a_1}p_2^{a_2}\dotsm p_k^{a_k} \\ b=p_1^{b_1}p_2^{b_2}\dotsm p_k^{b_k} \end{cases}\] Por ejemplo, si\(a=600\) y\(b=252\) tenemos\[\begin{aligned} 600 &=2^3\cdot 3^1\cdot 5^2\cdot 7^0 \\ 252 &=2^2\cdot 3^2\cdot 5^0\cdot 7^1.\end{aligned}\] Sigue que\[\gcd(600,252)=2^2\cdot 3^1\cdot 5^0\cdot 7^0 \quad \text{ and } \quad \operatorname{lcm}(600,252)=2^3\cdot 3^2\cdot 5^2\cdot 7^1.\nonumber \] en general, si\(a\) y\(b\) están dadas por ecuaciones\(\eqref{eq11-2ast}\) se puede probar que\[\boxed{\gcd(a,b)=p_1^{\min(a_1,b_1)}p_2^{\min(a_2,b_2)}\cdots p_k^{\min (a_k,b_k)}}\nonumber \] y\[\boxed{\operatorname{lcm}(a,b)=p_1^{\max(a_1,b_1)}p_2^{\max(a_2,b_2)}\cdots p_k^{\max (a_k,b_k)}}\nonumber \] (¡pruébalo!). Esto da una manera de calcular el gcd o lcm siempre que pueda factorizar ambos números. ¡Pero en términos generales la factorización es muy difícil! Por otro lado, el algoritmo euclidiano es relativamente rápido.
Ejercicios
Encuentra las factorizaciones principales de\(1147\) y\(1716\) probando todos los primos\(p\le\sqrt{1147}\) (\(p\le\sqrt{1716}\)) en sucesión.
Determinar la factorización principal de\(15! = 1307674368000\).
- Usando la factorización prima de\(100!\), determine cuántos 0 aparecen al final de la representación base 10.
- ¿Cuántos 0 aparecen al final de la representación binaria de\(100!\)?
La factorización prima de un entero\(n\) se\(n\) expresa como el producto de uno o más números primos, y por el Teorema Fundamental de la Aritmética, la factorización es única cuando los primos están ordenados por tamaño.
Examinemos la idea de factorizaciones en un conjunto diferente. Dejar\(S\) ser el conjunto de todos los múltiplos positivos de 3. Para cada uno\(n \in S\), defina\(n\) ser\(S\) -prime si\(n\) no se puede escribir como producto de dos elementos menores de\(S\).
- Anote los 10 números enteros\(S\) primos más pequeños.
- Encuentra una factorización de\(18\) números\(S\) primos.
- Explique cómo sabemos que cada elemento de\(S\) puede escribirse como producto de uno o más números\(S\) primos.
- ¿Es única la factorización de un elemento de unidades\(S\) en\(S\) -prime? Si es así, explique por qué. Si no, da un ejemplo de un elemento de\(S\) que se puede factorizar en números\(S\) primos de al menos dos formas diferentes (junto con las dos factorizaciones).
\(\mathbb{N}^*\)Déjese ser el conjunto\(\{4,5,6,7,\dots\}\). Este conjunto\(\mathbb{N}^*\) sería el conjunto de enteros positivos si por alguna razón cambiamos de opinión y declaramos que no\(1,2,3\) eran enteros.
- Si definimos un número en\(\mathbb{N}^*\) como “primo\(^*\)” si no puede escribirse como producto de dos o más elementos más pequeños en\(\mathbb{N}^*\), entonces ¿qué números del conjunto\(\{4,5,\dots,25\}\) son primos\(^*\)?
- Expresar\(32\) como producto de dos\(^*\) números primos.
- Encuentra un número en el\(\mathbb{N}^*\) que se pueda escribir como producto de\(^*\) números primos de al menos dos formas diferentes. (Como desafío adicional, trate de encontrar el número más pequeño de ese tipo).
La mayoría de los estudiantes han visto el Teorema Fundamental de la Aritmética hace tanto tiempo que parece de alguna manera obvio o poco notable. Con base en los dos ejercicios anteriores, ¿crees que el Teorema\(\PageIndex{1}\) es para nada sorprendente? Explica tu respuesta en al menos un breve párrafo.
Notas al pie
[1] Este resultado se demuestra en la Proposición 30 del Libro VII de los Elementos de Euclides.