Teorema fundamental de la aritmética

Contenido

Teorema fundamental de la aritmética#

Introducción#

En este capítulo veremos el teorema fundamental de la aritmética, que es un resultado importante en el campo de la teoría de números. Este teorema establece que cualquier número entero positivo puede ser expresado de manera única como un producto de números primos. Aunque puede parecer una afirmación simple, su demostración es un resultado profundo y fundamental.
Además, este teorema tiene implicaciones importantes en muchas áreas de las matemáticas, cómo la criptografía, la cual veremos más adelante. Antes de enunciar el teorema formalmente, demostraremos algunos resultados previos que serán útiles en este capítulo.
Para finalizar, veremos cómo el teorema fundamental de la aritmética nos puede ser útil para calcular el máximo común divisor y el mínimo común múltiplo y mostraremos algunos ejemplos en los que hacemos uso de este teorema.

Primos que dividen productos de enteros#

Lema 3 (Euclides)

Si $p$ es un primo y $p |ab$, entonces $p |a$ o $p |b$.

Demostración. Sin perdida de generalidad supongamos que $p \nmid a$, entonces debemos demostrar que $p$ divide a $b$.
Notemos que como $p$ es primo y $a$ es un entero positivo tenemos que $(a,p)=1$, esto quiere decir que son primos relativos. Luego, por el Teorema 8, existen enteros $\alpha$ y $\beta$ tales que, el máximo común divisor se puede escribir como una combinación lineal, es decir, $\alpha p + \beta a = 1$.
Entonces, si esta igualdad la multiplicamos por $b$ obtenemos que,

\[\alpha pb + \beta ab = b.\]

Ya que $p|p$ y por hipótesis $p|ab$, entonces por la propiedad $4$ de la Proposición 2 tenemos que $p|(\alpha pb + \beta ab)=b$ y por lo tanto $p|b$. $\square$

El siguiente lema extiende el resultado anterior para tres o más factores.

Lema 4

Sea $p$ un primo y $p|a_1 a_2 \cdot \ldots \cdot a_n$, donde $a_1,a_2, \ldots ,a_n$ son enteros positivos. Entonces $p|a_i$ para alguna $i$, donde $1 \le i \le n$.

Demostración. Procedamos por inducción sobre el número de factores del producto que divide $p$.

Base inductiva. El caso cuando $n = 1$ se cumple directamente de la hipótesis ya que $p|a_1$. El caso cuando $n = 2$ ya lo demostramos en el Lema 3.

Hipótesis inductiva. Supongamos que es verdadero para un entero arbitrario $k$.

Es decir si $p|a_1 a_2 \cdot \ldots \cdot a_k$, entonces $p|a_i$ para alguna $i$, donde $1\le i \le k$.

Paso inductivo. Supongamos que $p|a_1 a_2 \cdot \ldots \cdot a_k a_{k+1}$.

Podemos reescribir la expresión como

\[p|(a_1 a_2\cdot \ldots \cdot a_k) \cdot a_{k+1},\]

haciendo que $p$ divida a dos elementos. Luego podemos aplicar el Lema 3 y tendríamos que $p|(a_1 a_2\cdot \ldots \cdot a_k)$ o $p|a_{k+1}$.

Si $p|a_1 a_2\cdot \ldots \cdot a_k$, entonces por la hipótesis inductiva tenemos que $p|a_i$ para alguna $i$, donde $1 \le i \le k$. Así $p|a_i$, donde $1\le i\le k$, o $p|a_{k+1}$. En cualquiera de los dos casos, $p|a_i$ para alguna $i$, donde $1\le i\le k+1$.
Así, por inducción, el resultado se cumple para todo entero positivo $n$. $\square$

El siguiente corolario es consecuencia del lema anterior.

Corolario 4

Si $p,q_1,q_2, \ldots ,q_n$ son primos tales que $p|q_1q_2 \cdot \ldots \cdot q_n$, entonces $p = q_i$ para alguna $i$, donde $1 \le i \le n$.

Demostración. Ya que $p|q_1q_2 \cdot \cdots \cdot q_n$, por el Lema 4 tenemos que $p|q_i$ para alguna $i$. Entonces tendríamos que $q_i=ap$ para algún entero $a$, pero $p$ y $q_i$ son primos. No queda otra opción más que $a=1$, por lo tanto $p=q_i$. $\square$

Enunciado y demostración del teorema fundamental de la aritmética.#

El resultado principal de este capítulo es el siguiente teorema.

Teorema 12 (Teorema fundamental de la aritmética)

Todo entero $n \ge 2$ es un número primo o puede ser expresado como un producto de primos. La factorización en primos es única excepto por el orden de los factores.

Demostración. Primero probaremos que $n$ es primo o puede ser expresado como un producto de primos.
Procederemos por inducción fuerte.

Sea $P(n)$ la proposición que afirma que el entero positivo $n$ es un número primo o puede ser expresado como un producto de primos.

Base inductiva. Ya que $2$ es un primo, resulta que $P(2)$ es verdadera.

Hipótesis inductiva. Supongamos que $P(2), P(3), P(4) \ldots ,P(k)$ son verdaderas, es decir, que todo entero de $2$ hasta $k$ o son primos o pueden ser expresados como un producto de primos.

Paso inductivo. Si $k+1$ es primo, entonces $P(k+1)$ es verdadera.

Si $k+1$ no es primo entonces, $k+1$ debe ser compuesto. Luego, tenemos que $k+1 = ab$ para algunos enteros $a$ y $b$, donde $1 < a,b < k+1$. Por la hipótesis de inducción, $a$ y $b$ o son primos o pueden ser expresados como un producto de primos, en cualquiera de los dos casos $k+1=ab$ puede ser expresado como un producto de primos. Así, $P(k+1)$ también es verdadera.
Por lo tanto, por inducción fuerte tenemos que $P(n)$ se cumple para todo entero $n \ge 2$.

Ahora, estableceremos la unicidad de dicha factorización.

Sea $n$ un número compuesto con dos diferentes factorizaciones en primos, es decir:

\[n = p_1p_2\cdot \ldots \cdot p_r = q_1q_2\cdot \ldots \cdot q_s.\]

Mostraremos que $r = s$ y que todo $p_i$ es igual a algún $q_j$, donde $1\le i \le r$ y $1 \le j \le s$. Esto es, que los primos $q_1q_2\cdot \ldots \cdot q_s$ son una permutación de los primos $p_1p_2\cdot \ldots \cdot p_r$.

Supongamos por conveniencia que $r\le s$. Ya que

\[p_1p_2\cdot \ldots \cdot p_r = q_1q_2\cdot \ldots \cdot q_s,\]

tenemos que $p_1|q_1q_2\cdot \ldots \cdot q_s$, luego por el Corolario 4 $p_1=q_i$ para algún $i$.

Si dividimos ambos lados de la igualdad por $p_1$, tenemos que

\[p_2\cdot \ldots \cdot p_r=q_1q_2 \cdot \ldots \cdot q_{i-1} \cancel{q_i} q_{i+1} \cdot \ldots \cdot q_s.\]

Como $p_2$ divide el lado derecho de la igualdad, nuevamente por el Corolario 4, tenemos que $p_2 = q_j$ y dividimos ambos lados de la igualdad por $p_2$ obteniendo:

\[p_3 \cdot \ldots \cdot p_r=q_1q_2\cdot \ldots \cdot q_{i-1} q_{i+1} \cdot \ldots \cdot q_{j-1} \cancel{q_j} q_{j+1} \cdot \ldots \cdot q_s.\]

Ya que $r \le s$, y continuando de esta forma, podemos cancelar cada $p_t$ con algún $q_k$. Siguiendo con este procedimiento obtendríamos $1$ en el lado izquierdo de la igualdad. Sin embargo, si $r<s$ en el lado derecho de la igualdad obtendríamos un producto de primos, y sabemos que ningún producto de primos podría dar $1$ como resultado, es decir, que deberíamos haber agotado todos los $q_k$. Entonces $r = s$ y por lo tanto los primos $q_1q_2\cdot \ldots \cdot q_s$ son los mismos primos que $p_1p_2\cdot \ldots \cdot q_r$ en algún orden diferente. Así, la factorización de $n$ es única, excepto por el orden en que los primos son escritos. $\square$

Descomposición canónica#

Con el Teorema 12 demostramos que todo número entero $n$ puede ser descompuesto en un producto de primos. Dicha factorización es llamada una factorización en primos de $n$. Puede haber muchas formas de escribir a un mismo número como producto de primos, por ejemplo, $12=2\cdot 3 \cdot 2 = 3\cdot 2 \cdot 2$. Una forma de poder darle un orden a está descomposición en producto de primos es la siguiente.

Definición 14 (Descomposición canónica)

La descomposición canónica de un entero positivo $n$ es la descomposición en primos de la forma

\[n=p_1^{a_1} p_2^{a_2} \cdot \ldots \cdot p_k^{a_k},\]

donde $p_1,p_2, \ldots ,p_k$ son números primos tales que $p_1<p_2<p_3< \ldots <p_k$ y cada $a_i$ es un entero positivo.

Ejemplo 38

Encuentra la descomposición canónica de $38220$.

Solución.

Vamos a dividir el número $38220$ entre los números primos de manera ordenada, comenzando por el primo más pequeño que es $2$ y continuando con $3,5,7,11, \ldots$. Si el número no es divisible por el primo en cuestión pasaríamos a probar si es divisible por el siguiente primo y continuamos así hasta terminar con un cociente de $1$.

Comenzamos dividiendo $38220$ entre $2$:

\[\begin{align*} 38220 \div 2 &= 19110, \\ & \\ 19110\div 2 &= 9555. \end{align*}\]

Ya que $2$ no divide a $9555$, procedemos a dividir entre $3$:
\[9555 \div 3 = 3185.\]
Como $3$ no divide a $3185$, procedemos a dividir entre $5$:
\[3185 \div 5 = 637.\]
Como $5$ no divide a $637$, procedemos a dividir entre $7$:

\[\begin{align*} 637 \div 7 &= 91, \\ & \\ 91\div 7 &= 13. \end{align*}\]

Para terminar, como $7$ ni $11$ dividen a $13$, solamente nos queda dividir entre $13$:
\[13 \div 13 = 1.\]

Así, obtenemos que la descomposición canónica de $38220$ es:

\[\begin{align*} 38220 &= 2\cdot 2\cdot 3\cdot 5\cdot 7 \cdot 7\cdot 13 \\ & \\ &=2^2 \cdot 3\cdot 5 \cdot 7^2 \cdot 13. \end{align*}\]

Como vimos en el teorema fundamental de la aritmética, la factorización en primos de un número entero positivo es única. Para las siguientes secciones y definiciones abusaremos de la notación y deformaremos esta factorización única para que la descomposición canónica de dos números enteros positivos puedan tener los mismos primos en su factorización, pero con diferentes exponentes cada una de ellas. En la siguiente observación veremos un ejemplo de esto.

Observación 5

Permitiendo algunos de los exponentes ser iguales a cero, podemos asumir que las descomposiciones en primos de dos enteros $a$ y $b$ contienen exactamente los mismos primos $p_i$ como bases, por ejemplo, los enteros $38220$ y $48552$ pueden ser expresados de la siguiente manera

\[\begin{align*} 38220 &= 2^2 \cdot 3\cdot 5 \cdot 7^2 \cdot 11^0 \cdot 13\cdot 17^0, \\ & \\ 48552 &= 2^3\cdot 3\cdot 5^0\cdot 7\cdot 11^0\cdot 13^0\cdot 17^2. \end{align*}\]

El siguiente lema nos muestra cuando un entero divide a otro.

Lema 5

Sean $a$ y $b$ dos números enteros positivos. Sean $p_1<p_2<\ldots<p_k$ todos los factores primos involucrados en la forma canónica de $a$ o $b$. Escribamos a los números $a$ y $b$ como sigue:

\[\begin{align*} a=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \\ b=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k}. \end{align*}\]

Se tiene que $a$ divide a $b$ si y sólo si para todo $i=1,\ldots, k$ se tiene que $\alpha_i\leq \beta_i$.

Demostración. Supongamos primero que $\alpha_i \leq \beta_i$. Notemos que en ese caso podemos tomar

\[c=p_1^{\beta_1-\alpha_1}p_2^{\beta_2-\alpha_2}\ldots p_k^{\beta_k-\alpha_k},\]

y que $c$ en efecto es un entero positivo. Además, tenemos que

\[\begin{align*} ac&=(p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k})(p_1^{\beta_1-\alpha_1}p_2^{\beta_2-\alpha_2}\ldots p_k^{\beta_k-\alpha_k})\\ & \\ &=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k}\\ & \\ &=b. \end{align*}\]

Esto muestra que $a$ divide a $b$.

Ahora supongamos que $a$ divide a $b$. En este caso, existe $c$ tal que $b=ac$. Si la factorización en primos de $b$ es

\[b = p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k},\]

entonces ésta también es la factorización en primos de $ac$. Por la unidad del Teorema 12, debe pasar entonces que todos los primos de $a$ están en $b$, y además, para cada primo $p_i$ de la factorización de $b$ es imposible que el exponente $\alpha_i$ en $a$ sea más grande que el exponente $\beta_i$ en $b$ pues se daría la contradicción de que en $b$ aparecen $\beta_i$ factores $p_i$, pero en $ac$ aparecerían por lo menos $\alpha_i>\beta_i$. $\square$

La descomposición canónica es muy útil si queremos encontrar el máximo común divisor de dos números enteros $a$ y $b$.

Teorema 13

Sean $a$ y $b$ enteros positivos con la siguiente descomposición canónica:

\[a=p_1^{a_1} p_2^{a_2} \cdots p_n^{a_n} \quad \text{y} \quad b=p_1^{b_1} p_2^{b_2} \cdots p_n^{b_n},\]

donde $a_i,b_i \ge 0$, entonces podemos escribir el máximo común divisor de los enteros $a$ y $b$ como,

\[(a,b) = p_1^{min\{a_1,b_1\}} p_2^{min\{a_2,b_2\}} \cdots p_n^{min\{a_n,b_n\}}.\]

Ejemplo 39

Dados los enteros $5544$ y $5940$, utiliza la descomposición canónica y haz que éstas tengan los mismos primos en sus bases para encontrar el máximo común divisor.

Solución.

Si utilizamos el método mostrado en el Ejemplo 38 para encontrar la descomposición canónica de los números $5544$ y $5940$ tendríamos lo siguiente

\[\begin{align*} 5544 &= 2^3 \cdot 3^2 \cdot 7 \cdot 11,\\ & \\ 5940 &= 2^2 \cdot 3^3 \cdot 5\cdot 11. \\ \end{align*}\]

Si hacemos que tengan los mismos primos en sus bases, tendríamos que

\[\begin{align*} 5544 &= 2^3 \cdot 3^2 \cdot 5^0 \cdot 7 \cdot 11,\\ & \\ 5940 &= 2^2 \cdot 3^3 \cdot 5 \cdot 7^0\cdot 11. \\ \end{align*}\]

Ahora, tomaremos el mínimo de cada uno de estos exponentes para encontrar el máximo común divisor.
Así, obtenemos que

\[\begin{align*} (5544,5940) &= 2^{min\{2,3\}} \cdot 3^{min\{2,3\}} \cdot 5^{min\{0,1\}} \cdot 7^{min\{0,1\}} \cdot 11^{min\{1,1\}} \\ & \\ &= 2^2 \cdot 3^2 \cdot 5^0 \cdot 7^0 \cdot 11^1 \\ & \\ &= 396. \end{align*}\]

Por lo tanto $(5544,5940) = 396$.

Con la descomposición canónica podemos calcular también el mínimo común múltiplo, pero primero veamos la definición.

Definición 15 (Mínimo común múltiplo)

Si $a$ y $b$ son enteros, entonces un múltiplo común de $a$ y $b$ es un entero $c$ tal que $a|c$ y $b|c$. El mínimo común múltiplo de $a$ y $b$, no ambos cero, es un entero positivo $l$ que satisface lo siguiente:

$a|l$ y $b|l$, es decir $l$ es un múltiplo en común.
Si $a|c$ y $b|c$, entonces $l|c$.

Usaremos la notación $[a,b]$ para denotar al mínimo común múltiplo.

Con esto en mente, podemos utilizar la descomposición canónica para calcular el mínimo común múltiplo como sigue.

Teorema 14

Sean $a$ y $b$ enteros positivos. Si $a = p_1^{a_1}p_2^{a_2}\cdot \ldots \cdot p_n^{a_n}$ y $b = p_1^{b_1}p_2^{b_2}\cdot \ldots \cdot p_n^{b_n}$, podemos expresar el mínimo común múltiplo de dos enteros $a$ y $b$ como,

\[[a,b] = p_1^{max\{ a_1,b_1 \} }p_2^{max\{ a_2,b_2 \} }\cdot \ldots \cdot p_n^{max\{ a_n,b_n \} }.\]

Ejemplo 40

Dados los enteros $252$ y $396$, utiliza la descomposición canónica y haz que éstas tengan los mismos primos en sus bases para encontrar el mínimo común múltiplo.

Solución.

Notemos que la descomposición canónica de ambos números es,

\[\begin{align*} 3276 &= 2^2\cdot 3^2\cdot 7\cdot 13, \\ & \\ 2904 &= 2^3\cdot 3^1\cdot 11^2. \end{align*}\]

Si hacemos que tengan los mismo primos en sus bases, tendríamos que

\[\begin{align*} 3276 &= 2^2\cdot 3^2\cdot 7\cdot 11^0\cdot 13, \\ & \\ 2904 &= 2^3\cdot 3^1\cdot 7^0\cdot 11^2\cdot 13^0. \end{align*}\]

Ahora, tendríamos que tomar el máximo de cada uno de estos exponentes. Entonces tendremos lo siguiente,

\[\begin{align*} (3276,2904) &= 2^{max\{2,3\}} \cdot 3^{max\{2,1\}} \cdot 7^{max\{1,0\}} \cdot 11^{min\{0,2\}} \cdot 13^{min\{1,0\}} \\ & \\ &= 2^3 \cdot 3^2 \cdot 7^1 \cdot 11^2\cdot 13^1 \\ & \\ &= 792792. \end{align*}\]

Por lo tanto, $[252,396] = 792792$.

Veamos un ejercicio en donde utilizamos la factorización en primos.

Ejemplo 41

Encuentra el número de ceros finales en el número 234!.

Solución.

Sabemos que cada cero al final del número $234!$ corresponde a que aparezca un $10$ en la factorización y cada $10$ es el producto de $2\cdot 5$. Entonces en la factorización nos interesa conocer cuántas veces aparece el producto $2\cdot 5$.
Por el Teorema 12 sabemos que el número $234!$ puede ser descompuesto como

\[234! = 2^a\cdot 5^b \cdot c,\]

donde $c$ es el producto de primos diferentes a $2$ y $5$. Luego, tendríamos que

\[\begin{align*} \text{No. de ceros finales en 234!} &= \text{No. veces que aparece el producto $2\cdot5$ en 234!} \\ & \\ &= \text{mínimo entre a y b}. \end{align*}\]

Ahora, busquemos cuántos números divisibles entre $5$ menores que $234$ hay. Esto lo podemos hacer de la siguiente manera.
Los números divisibles entre $5$ son de la forma $5n$ para algún entero $n$, entonces tenemos que

\[\begin{align*} 1 &< 5n < 234, \\ & \\ 0.2 &< n < 46.8,\text{ (dividiendo entre $5$)} \end{align*}\]

como $n$ es un número entero, tenemos $46$ números divisibles entre $5$ menores que $234$.

Hay que tener en cuenta que también nos interesan los números divisibles entre $25$ y $125$ ya que estos llevan en su factorización al número $5$ y contribuyen con otro $5$ extra en la factorización.
Sabemos que los números divisibles entre $25$ y $125$ son de la forma $25n$ y $125n$ respectivamente, entonces

\[\begin{align*} 1 &< 25n < 234, &\quad 1 &< 125n < 234, \\ & \\ 0.04 &< n < 9.36, &\quad 0.008 &< n < 1.872. \end{align*}\]

Por lo anterior, tenemos $9$ números divisibles entre entre $25$ y $1$ número divisible entre $125$ que son menores que $234$.

Procedemos de la misma forma con los números divisibles entre $2$ menores que $234$. Los números que son divisibles entre $2$ son de la forma $2n$, entonces tenemos que:

\[\begin{align*} 1 &< 2n \le 234 \\ & \\ 0.5 &< n \le 117, \text{ (dividiendo entre $5$)} \end{align*}\]

Por lo tanto tenemos $117$ números divisibles entre $2$ menores que $2324$.

Considerando esto, no es necesario seguir buscando números divisibles entre $2$, pues sólo con esta búsqueda ya tenemos más que los divisibles entre $5$. Por lo tanto, tenemos que el producto de $2\cdot 5$ aparece un total de $56$ veces y así sabemos que $234!$ tiene $56$ ceros al final.

Veamos un resultado en donde el Lema 5 es de ayuda.

Lema 6

Sean $m$ y $n$ enteros primos relativos positivos. Si $d$ es un divisor positivo de $mn$, hay un único par de divisores positivos $d_1$ de $m$ y $d_2$ de $n$ tales que $d = d_1d_2$. Conversamente, si $d_1$ y $d_2$ son divisores positivos de $m$ y $n$, respectivamente, entonces $d = d_1d_2$ es un divisor positivo de $mn$.

Demostración. Demostraremos las dos contenciones.

Primero demostremos que si $d$ es un divisor positivo de $mn$, hay un único par de divisores positivos $d_1$ de $m$ y $d_2$ de $n$ tales que $d = d_1d_2$.

Sean $m$ y $n$ primos relativos positivos. Por el Teorema 12 podemos escribir a $m$ y $n$ en su factorización de primos, es decir,

\[m = p_1^{m_1}p_2^{m_2} \ldots p_s^{m_s} \quad \text{ y } \quad n = q_1^{n_1}q_2^{n_2} \ldots q_t^{n_t}.\]

Ya que $(m,n) = 1$, los números primos que contiene $m$ en su factorización son diferentes a los números primos que contiene $n$ en su factorización. De aquí que la factorización en primos de $mn$ sea

\[mn = p_1^{m_1}p_2^{m_2} \ldots p_s^{m_s} \cdot q_1^{n_1}q_2^{n_2} \ldots q_t^{n_t}.\]

Luego como $d$ es un divisor positivo de $mn$, tenemos que

\[d = p_1^{e_1}p_2^{e_2} \ldots p_s^{e_s} \cdot q_1^{f_1}q_2^{f_2} \ldots q_t^{f_t}.\]

donde $m_i - e_i \ge 0$, es decir, $0 \le e_i \le m_i$ para todo valor de $i = 1,2,\ldots, s$ y $n_j - f_j \ge 0$, es decir $0 \le f_j \le n_j$ para todo valor de $j = 1,2,\ldots, t$.

Sean $d_1 = (d,m)$ y $d_2 = (d,n)$ por la Teorema 13, tenemos que

\[d_1 = p_1^{e_1}p_2^{e_2} \ldots p_s^{e_s} \quad \text{y} \quad d_2 = q_1^{f_1}q_2^{f_2} \ldots q_t^{f_t}.\]

Entonces tenemos que $d = d_1d_2$ y $(d_1,d_2) = 1$. Por lo tanto, tenemos la descomposición deseada de $d$. Además, ésta descomposición es única. Para ver esto, notemos que cada potencia de primos de $d$ debe estar en $d_1$ o en $d_2$ pero no en ambos, las potencias de primos que aparecen en $d$ que son potencias de primos de dividen a $m$ deben aparecer en $d_1$, y las potencias de primos que aparecen en $d$ que son potencias de primos que dividen a $n$ deben aparecer en $d_2$. Entonces tenemos que $d_1$ debe ser $(d,m)$ y que $d_2$ debe ser $(d,n)$.

Ahora demostremos que si $d_1$ y $d_2$ son divisores positivos de $m$ y $n$, respectivamente, entonces $d = d_1d_2$ es un divisor positivo de $mn$.

Por hipótesis tenemos que $m$ y $n$ son primos relativos positivos y tenemos su factorización de primos, es decir,

\[m = p_1^{m_1}p_2^{m_2} \ldots p_s^{m_s} \quad \text{ y } \quad n = q_1^{n_1}q_2^{n_2} \ldots q_t^{n_t}.\]

Como $d_1$ es un divisor positivo de $m$ tenemos que

\[d_1 = p_1^{e_1}p_2^{e_2} \ldots p_s^{e_s},\]

donde $0 \le e_i \le m_i$ para $i = 1,2,\ldots, s$.

Y como $d_2$ un divisor positivo de $n$ tenemos que

\[d_2 = q_1^{f_1}q_2^{f_2} \ldots q_t^{f_t},\]

donde $0 \le f_j \le n_j$ para $j = 1,2,\ldots, t$.

Luego, tenemos que el entero

\[d = p_1^{e_1}p_2^{e_2} \ldots p_s^{e_s} \cdot q_1^{f_1}q_2^{f_2} \ldots q_t^{f_t},\]

es un divisor de $mn$, es decir,

\[\begin{align*} \frac{mn}{d} &= \frac{p_1^{m_1}p_2^{m_2} \ldots p_s^{m_s} \cdot q_1^{n_1}q_2^{n_2} \ldots q_t^{n_t}}{p_1^{e_1}p_2^{e_2} \ldots p_s^{e_s} \cdot q_1^{f_1}q_2^{f_2} \ldots q_t^{f_t}} \\ & \\ &= p_1^{m_1 - e_1}p_2^{m_2 - e_2} \ldots p_s^{m_s - e_2} \cdot q_1^{n_1 - f_1}q_2^{n_2 - f_2} \ldots q_t^{n_t - f_t}. \end{align*}\]

Ya que $m_i - e_i \ge 0$ para toda $i = 1,2,\ldots, s$, y $n_i - f_i \ge 0$ para toda $j = 1,2,\ldots, t$, sucede que $d_1d_2 = d|mn$. $\square$

Código para descomponer un entero $n$ en primos#

El siguiente código nos dará una lista con los factores de la descomposición de un número entero $n$, en este caso utilizaremos el método descrito en el Ejemplo 38.

def factorizar_en_primos(n):
    lst = []
    for i in range(2, n+1):
        while n % i == 0:
            lst.append(i)
            n //= i
        if n == 1:
            break
    return lst

factorizar_en_primos(5940)

[2, 2, 3, 3, 3, 5, 11]

factorizar_en_primos(27720)

[2, 2, 2, 3, 3, 5, 7, 11]

factorizar_en_primos(2480863)

[7, 11, 11, 29, 101]

Explicación del código#

En esta ocasión mostramos una nueva sentencia, la sentencia break. Esta sentencia nos sirve para salir de los ciclos inmediatamente, e incondicionalmente termina la operación del ciclo.
Por ejemplo, el siguiente código inicia un ciclo for y recorre los valores en el rango de $1$ a $9$, pero cuando el valor de la variable «i» es igual a $3$ la condición del condicional if es True y se aplica la sentencia break terminando así el recorrido del ciclo for. Esto nos ayuda a que el código no recorra todos los valores en el rango y termine el ciclo cuando se satisfaga alguna sentencia lógica.

for i in range(1,10):
    if i = 3:
        break

Usamos una forma abreviada de escribir que una variable «n» sea dividida entre $i$ y «n» tome el nuevo valor. Las siguientes dos lineas de código son equivalentes.

n = n // i

n //= i 

Ahora, expliquemos cómo funciona el código para descomponer un entero $n$ en primos.

def factorizar_en_primos(n):
    lst = []
    for i in range(2, n+1):
        while n % i == 0:
            lst.append(i)
            n //= i
        if n == 1:
            break
    return lst

Definimos una función llamada «factorizar_en primos» la cual recibe como argumento un número entero $n$.

def factorizar_en_primos(n):

Creamos una lista vacía donde guardaremos los factores de la descomposición en primos.

    lst = []

Creamos un ciclo for para empezar a recorrer los valores de $2$ hasta $n$.

    for i in range(2,n+1):

Dentro del ciclo for iniciamos un bucle while, el cual repetirá el código dentro de él siempre que la condición de que el residuo al dividir la variable «n» entre la variable «i» sea cero. Mientras la condición del bucle while sea verdadera, el valor de la variable «i» se irá guardando en la lista. Después se actualizará el valor de la variable «n» dividiéndola entre la variable «i».

        while n % i == 0:
            lst.append(i)
            n //=i

Cuando el valor de la variable «n» es $1$, el código en lugar de regresar al ciclo for, pasa por el condicional if y se aplica la sentencia break obligando al código a salir de ciclo for sin haber recorrido todos los valores. El código nos arroja como resultado de salida la lista con todos los valores en la descomposición canónica.

        if n == 1:
            break
    return lst

Ejercicios de práctica#

Utilizando la descomposición canónica, encuentra el número de ceros que tienen al final los siguientes números:
- $234!$
- $1010!$
Demuestra el Teorema 14 y el Teorema 13.
Demuestra lo siguiente. Sean $a$ y $b$ enteros positivos, entonces $[a,b] = \frac{ab}{(a,b)}$.
Demuestra que todas las potencias en la descomposición canónica de un número entero $n$ son pares si y sólo si $n$ es un cuadrado perfecto.
¿Cuáles enteros tienen exactamente $3$ divisores positivos? ¿Y cuáles enteros tienes exactamente $5$ divisores positivos?
Dados $a$,$b$,$k$ y $l$ enteros positivos, donde $k \le l$, demuestra que si $a^l|b^k$, entonces $a|b$.

Teorema fundamental de la aritmética

Contenido

Teorema fundamental de la aritmética#

Introducción#

Primos que dividen productos de enteros#

Enunciado y demostración del teorema fundamental de la aritmética.#

Descomposición canónica#

Código para descomponer un entero \(n\) en primos#

Explicación del código#

Ejercicios de práctica#