Factorización		Geovany Sanabria  B..

Inicio  1  2  3  4  5	Versión PDF

 

Métodos de Factorización prima.

 

Los métodos de factorización prima son algoritmos que permiten hallar los factores primos de un número. Dichos algoritmos se puede clasificar en: factorización por factores primos y por factores compuestos. Para el desarrollo de estos algoritmos es indispensable identificar los números primos, por ello, al final del presente trabajo se brinda una tabla con los números primos menores que 200. Seguidamente se explican cada una de estos tipos de métodos de factorización prima.

 

Métodos de factorización por factores primos.

Estos métodos son la aplicación directa del teorema de factorización prima, pues da un número natural $n$ consisten en hallar de manera ascendente cada uno de los factores primos de $n.$ En forma general estos algoritmos siguen los siguientes pasos:

 

Paso 1.

 

$k=1,$ $n_{k}=n$

Paso 2.

 

Determinar el número primo más pequeño que divide a $n_{k}.$ Este sera llamado $p_{k}.$

Paso 3.

 

Se define $n_{k+1}=\dfrac{n_{k}}{p_{k}}.$

Paso 4.

 

Si $n_{k+1}$ es primo entonces finaliza el procedimiento y se obtiene que

$$n=p_{1}\cdot p_{2}\cdot...\cdot p_{k}\cdot n_{k+1},$$

donde $p_{1},p_{2},...$ $p_{k}$ y $n_{k+1}$ son primos y además $p_{1}\leq p_{2}\leq...\leq$ $p_{k}\leq n_{k+1}.$ Si no se pasa al paso 5

 

Paso 5.

 

Incrementar $k$ en una unidad y pasar al paso 2.

 

Básicamente, estos métodos siguen un procedimiento de búsquedad lineal, es decir no se puede determinar el k-ésimo primo, $p_{k},$ si no se han determinado todos los anteriores: $p_{1},p_{2},...,p_{k-1},$ lo que provoca que estos métodos sea muy ineficientes para números grandes. A continuación se presentan los dos métodos que obedecen este procedimiento.

Método de ensayo y error.

En este método, para el paso 2 se procede realizando la división de $n_{k}$ entre $2,3,5,7,11,...$ hasta obtener el primer primo divisor de $n_{k},$ veamos el siguiente ejemplo.

Ejemplo 1.

 

Determine la factorización prima de $1638.$

 

Solución.

 

Los resultados del método ensayo y error se presentan en la siguiente tabla

$$\begin{tabular}[c]{\vert c\vert c\vert ccccc}\hline \multico... ...}[c]{ll} & \\ & \end{tabular}& & \\ \cline{1-2}% \end{tabular}$$

Así, en este caso se obtiene que $n=1638=p_{1}\cdot p_{2}\cdot p_{3}\cdot p_{4}\cdot n_{5}=2\cdot9\cdot7\cdot13 \medskip \medskip$

 

Método por reglas de divisibilidad.

Este método es una variación del anterior y consiste en sustituir algunas de las divisiones por reglas de divisibilidad. Para efectos de dicha presentación se enumeran seguidamente.

Dado un número $n,$ se dice que

1. $n$ es divisible entre $2$ si su último digito es $0,2,4,6$ $o$ $8$

2. $n$ es divisible entre $3$ si la suma de sus dígitos es múltiplo de $3.$

3. $n$ es divisible entre $5$ si su último digito es 0 $o$ $5$

4. $n$ es divisible entre $7$ si el número que queda suprimiendo el dígito de de las unidades, disminuido en el doble de las unidades es 0 o múltiplo de $7.$

5. $n$ es divisible entre $11,$ si la suma de los dígitos de las posiciones pares menos la suma de los dígitos de las posiciones impares es 0 o múltiplo de $11.$

Ejemplo 2.

 

Determine la factorización prima de $45\,885.$

 

Solución.

 

Los resultados del método por reglas de divisibilidad se observan en la siguiente tabla.

$$\begin{tabular}[c]{\vert c\vert c\vert ccccccccc}\hline \multicol... ...\begin{tabular}[c]{ll} & \\ & \end{tabular}& & & \\ \cline{1-2}% \end{tabular}$$

Por lo tanto se realiza $\allowbreak45\,885\allowbreak=p_{1}\cdot p_{2}\cdot p_{3}\cdot p_{4}\cdot n_{5}=3\cdot5\cdot7\cdot19\cdot23.\medskip\medskip$

 

Nota: Esta tabla como la del ejemplo anterior, es una manera de exhibir los resultados del método posterior a su aplicación, pues una vez aplicado el método, se sabe cuantas columnas se requieren.

Si bien este método es más eficiente que el anterior, se puede mejorar. En efecto, la idea consiste en romper el orden de menor a mayor de los primos y verificar primero si el $n_{k}$ es divisible por 5 y luego por 2, que es fácil de comprobarlo. Esto permitirá obtener luego un $n_{k}$ más cómodo para determinar si es divisible por $3,7,11,13...\medskip \medskip$

Hasta el momento se han presentado en los ejemplos, unas tablas que ilustran muy bien el procedimiento de los algoritmos utilizados. Sin embargo, en secundaria se utiliza una tabla donde se suele omitir el paso 2 de los algoritmos, las cuales tienen la ventaja de que se puede utilizar para ir presentado los datos conforme el método avanza, y no como en las anteriores, en donde no se podía construir la tabla hasta que el algoritmo finalice. El docente puede optar en un primer momento, por utilizar tablas similares a las expuestas en los ejemplos, permitiendo que los alumnos se familiaricen con los algoritmos, y posteriormente, utilizar la tradicional tabla que se expone en el siguiente ejemplo.

Ejemplo 3.

 

Determine la factorización prima de $40\,950.$

 

Solución.

 

Aplicando el algoritmo se tiene que

$$\begin{tabular}[c]{c\vert c}% $n_{k}$\ & $p_{k}$\\ \hline $40950$... ...rac{91}{7}=$\ $13$\ & \begin{tabular}[c]{ll} & \\ & \end{tabular}\end{tabular}$$

Por lo tanto $40950=2\cdot3^{2}\cdot5^{2}\cdot7\cdot13.\medskip\medskip$

 

Desventajas de los métodos por factores primos.

Como se han mencionado anteriormente, una de las mayores desventajas de estos métodos de factorización de un número natural $n$ es que utilizan un procedimiento de búsquedad lineal para hallar los factores primos de $n.$ Otras desventajas que tienen estos métodos son:

1. Funcionan sólo para números "pequeños". Para números muy grandes estos algoritmos requieren mucho tiempo.

2. Se cuenta con pocas reglas de divisibilidad. Estás son sólo para los primeros primos.

3. Es complicado saber si un número mayor que 100 es primo. La mayoría de personas conocen a lo sumo los veinte primeros números. Esto provoca que si $n$ esta compuesto con primos mayores que 100, se une al algoritmo la dificultad de tener que ir determinando los primos en el orden que se sigue.

 

Métodos de factorización por factores compuestos.

Estos métodos consisten en, dado un número natural $n,$ hallar dos números $m$ y $k$ (no necesariamente primos) que cumplan $n=mk.$ De manera general, estos algoritmos siguen los siguientes pasos para la factorización de $n$ :

Paso 1.

 

Hallar dos números naturales $m$ y $k$ que cumplan que $mk=n.$

Paso 2.

 

Factorizar $m$ y $k$ utilizando algunos de los métodos de factorización.

 

Si se continúa aplicando este mismo tipo de método, se puede apreciar que se sigue un procedimiento de búsqueda de árbol, pues se va simultáneamente hallando los factores primos de $n:$

Veamos el siguiente ejemplo.

Ejemplo 4.

 

Determine la factorización prima de $6400.$

 

Solución.

 

Se tiene que $6400=64\cdot100$ y como $64=8^{2}=2^{6}$ y $100=10^{2}=2^{2}5^{2},$ entonces $6400=2^{8}5^{2}. \medskip$

No siempre es tan fácil determinar para un número natural $n$ dos números que multiplicados entre sí den como resultado $n.$ Es fácil cuando el número es divisible por $2,$ $3$ o $5.$ Por lo tanto, en los métodos que presentaremos en las secciones siguientes se asumirá que el número $n$ a factorizar es impar y no es divisible por 3 ni por 5, pues, en caso contrario, es mejor aplicar inicialmente algunos de los métodos vistos, hasta obtener factores (un valor $n_{k})$ que cumplan dicho supuesto.

 

Método de factorización de Fermat

Sea $n$ un número natural impar, se quiere hallar dos naturales $m$ y $k$ que cumplan

$$n=mk$$

Como $n$ es impar entonces tanto $m$ como $k$ son impares y suponiendo sin pérdida de generalidad que $m\geq k$ entonces, $\dfrac{m-k}{2}$ y $\dfrac{m+k}{2}$ son números naturales. Tómese

$$x=\dfrac{m+k}{2} \,\in \, \mathbb{N}, \; \; \; y=\dfrac{m-k}{2} \, \in \, \mathbb{N}$$

Note que $x+y=m\quad$ y $\quad x-y=k,$ por lo tanto

$$n=mk=\left( x+y\right) \left( x-y\right) =x^{2}-y^{2}.\quad\quad\left( \ast\right)$$

Así, nuestro problema se reduce ha hallar dos números naturales $x,$ $y$ que cumplan $n=x^{2}-y^{2}.$

Note que de $\left( \ast\right)$ se tiene que $x^{2}=n+y^{2},$ entonces $x^{2}\geq n$ y se sigue que

$$x\geq n\quad\quad\left( 1\right)$$

Por otro lado, de $\left( \ast\right)$ se deduce que $x^{2}-n$ debe ser un cuadrado perfecto, que se denotará por $\Delta\left( x\right) ,$ por lo tanto

$$\Delta\left( x\right) =x^{2}-n$$ debe ser un cuadrado perfecto$$% \quad\quad\left( 2\right) .$$

En resumen a partir de $\left( 1\right)$ y $\left( 2\right) ,$ el Método de Fermat sigue los siguientes pasos, para determinar los factores $m$ y $k$ de un número natural $n$ :

 

Paso 1.

 

Si $\sqrt{n} \, \in \, \mathbb{N}$ tome $m=k=\sqrt{n}$ y finaliza el algoritmo. Sino pase al paso $2$

 

Paso 2.

 

Sea k el número natural entre $\sqrt{n}$ y $\sqrt{n}+1,$ pase al paso siguiente

 

Paso 3.

 

Si $\Delta\left( k\right)$ es cuadrado perfecto tome $x=k,$ $y=\sqrt{\Delta\left( x\right) }$ , $m=x+y$ , $k=x-y,$ y finaliza el algoritmo. Si no, pase al paso siguiente.

 

Paso 4.

 

Incremente $k$ en una unidad y pase al paso anterior.

 

Ejemplo 5.

 

Determine la factorización prima de $14\,647.$

 

Solución.

 

En este caso se tiene que $\sqrt{n}=\sqrt{14647}% =\allowbreak121.\,\allowbreak02$ por lo tanto se debe buscar un número $x\geq122$ que cumpla: $\Delta\left( x\right)$ se un cuadrado perfecto. Por lo tanto se procede de manera inductiva sobre $k$ a partir de $k=122$ hasta obtener que $\Delta\left( k\right)$ sea un cuadrado perfecto:

$$\begin{tabular}[c]{\vert c\vert c\vert c\vert}\hline \multicolumn... ... & $482$\ & $21,9544984$\\ \hline $124$\ & $729$\ & $27$\\ \hline \end{tabular}$$

Por lo tanto $x=124$ , $y=27,$ y se obtiene que el número $n=14647$ puede ser factorizado por

$$14647=\left( 124+27\right) \left( 124-27\right) =151\cdot97.$$

Como $151$ y $97$ son primos, entonces dicha factorización es la factorización prima de $14647. \medskip\medskip$

Ahora bien, este método se puede mejorar si se halla una fórmula recursiva para $\Delta\left( k\right) .$ En efecto, note que

$$\Delta\left( k+1\right) =\left( k+1\right) ^{2}-n=k^{2}+2k+1-n=\Delta \left( k\right) +2k+1.$$

Dicha fórmula facilita el cálculo de $\Delta\left( k\right) .$

El siguiente ejemplo muestra que a pesar de que el Método de Fermat requiere menos tiempo que los anteriores, no es tan rápido. $\medskip \medskip$

 

Ejemplo 6.

 

Determine la factorización prima de $31\cdot19\cdot101\cdot107\cdot5=31\,826\,615$

 

Solución.

Note que este número es divisible entre $5,$ por lo tanto nos interesa factorizar $\dfrac{31\,826\,615}{5}=6365\,323.$ Sea $n=6365\,323,$ se tiene que $\sqrt{n}=2522,959175.$ Por lo tanto, se obtiene que

$$\begin{tabular}[c]{\vert c\vert c\vert c\vert}\hline \multicolumn... ...8$\ & $544,2775028$\\ \hline $2582$\ & $301401$\ & $549$\\ \hline \end{tabular}$$

Así, $x_{1}=2582,$ $y_{1}=549,$ $m_{1}=x_{1}+y_{1}=3131$ y $k_{1}% =x_{1}-y_{1}=2033,$ por lo tanto

$$6365\,323=3131\cdot2033\quad\quad\quad\left( 1\right)$$

Ahora, factoricemos $3131,$ note que

$$3131=31\cdot100+31=31\left( 100+1\right) =31\cdot101\quad\left( 2\right)$$

Por otro lado, utilicemos el método de Fermat para factorizar $k=2033,$ donde $\sqrt{2033}=45.089$ . Se sigue que

$$\begin{tabular}[c]{\vert c\vert c\vert c\vert}\hline \multicolumn... ... $1811$\ & $42,55584566$\\ \hline $63$\ & $1936$\ & $44$\\ \hline \end{tabular}$$

Así, se obtiene que $x_{2}=63,y_{2}=44$ , $m_{2}=x_{2}+y_{2}=107$ y $k_{2}=x_{2}-y_{2}=19,$ entonces

$$2033=107\cdot19\quad\quad\left( 3\right)$$

Por $\left( 1\right) ,\left( 2\right)$ y $\left( 3\right) ,$ se concluye que

$$31\,826\,615=5\cdot6365\,323=5\cdot31\cdot19\cdot101\cdot107.$$

 

Método de Factorización de Euler

Suponga que el número impar $n$ a factorizar puede ser representado en dos formas distintas, como la suma de dos cuadrados perfectos:

$$n=a^{2}+b^{2}=c^{2}+d^{2},$$ con $$a,b,c,d \, \in \, \mathbb{N}$$

Como $n$ es impar, entonces solo puede ser expresado como la suma de un impar y un par, por lo tanto, supongamos sin perdida de generalidad que $a$ y $c$ son números impares, en tanto, $b$ y $d$ son pares, y además $a>c,$ por lo tanto $b<d.$ Debido a esto, note que $a^{2}$ es de la forma $4m,$ mientras $b^{2}$ es de la forma $4m+1,$ por lo tanto, $n$ es de la forma $4m+1.$

Por otro lado, de $\left( 1\right)$ se tiene que $d^{2}-b^{2}=a^{2}-c^{2},$ y se sigue que

$$\left( d-b\right) \left( d+b\right) =\left( a+c\right) \left( a-c\right) \quad\quad\left( 2\right)$$

Sea $m=\left( a-c,d-b\right) ,$ por lo tanto existen dos números naturales $l$ y $k$ que cumplen:

$$a-c=km,\quad d-b=lm\quad y\quad\left( k,l\right) =1.\quad\quad\left( 3\right)$$

Note que $m$ es par, pues $a-c$ y $d-b$ son pares. Sustituyendo $\left( 3\right)$ en $\left( 2\right)$ se obtiene que

$$l\left( d+b\right) =k\left( a+c\right) \quad\quad\left( 4\right)$$

Como $\left( l,k\right) =1$ entonces $l$ es divisor de $\left( a+c\right) ,$ y entonces existe un número natural $j$ que cumple

$$a+c=lj\quad\quad\left( 5\right)$$

Sustituyendo $\left( 5\right)$ en $\left( 4\right)$ se sigue

$$d+b=kj\quad\quad\left( 6\right)$$

Debido a $\left( 5\right) ,\left( 6\right)$ y $\left( l,k\right) =1,$ se obtiene que $j=\left( a+c,b+d\right) ,$ y como $a+c$ y $b+d$ son pares se concluye que $j$ es par.

Dado que $m$ y $j$ son números pares, verifiquemos que una factorización de $n$ está dada por

$$\left[ \left( \dfrac{m}{2}\right) ^{2}+\left( \dfrac{j}{2}\right)... ...ft[ \left( l\right) ^{2}+\left( k\right) ^{2}\right] \quad\quad\left( 7\right)$$

En efecto, expandiendo $\left( 7\right)$ se obtiene que

$$\left[ \left( \dfrac{m}{2}\right) ^{2}+\left( \dfrac{j}{2}\right)... ...t) ^{2}+\left( km\right) ^{2}+\left( lj\right) ^{2}+\left( kj\right) ^{2}}{4},$$

aplicando $\left( 3\right) ,\left( 5\right)$ y $\left( 6\right)$ se deduce que $\left( 7\right)$ es equivalente a

$$\dfrac{\left( d-b\right) ^{2}+\left( a-c\right) ^{2}+\left( a+c\r... ...t( d+b\right) ^{2}}{4}=\dfrac{2\left( a^{2}+b^{2}+c^{2}% +d^{2}\right) }{4}=n.$$

Lo anterior justifica el Método de Euler que se enuncia en las siguientes líneas.

En resumen, para poder factorizar un número impar $n$ con el Método de Euler, este debe cumplir:

1. Es de la forma $4m+1$ .

2. Se puede representar como la suma de dos cuadrados perfectos: $n=a^{2}+b^{2}$ , con $a$ impar y $b$ par.

3. Posee otra representación como la suma de dos cuadrados perfectos: $n=c^{2}+d^{2}$ , con $c$ impar y $d$ par.

Así para un $n$ que cumple con las reglas anteriores, se puede factorizar siguiendo los siguientes pasos:

 

Paso 1.

 

Calcular $m=\left( a-c,d-b\right)$

 

Paso 2.

 

Hallar $k=\dfrac{a-c}{m},\quad l=\dfrac{d-b}{m}$

 

Paso 3.

 

Determinar $j=\dfrac{a+c}{l}$

Paso 4.

La factorización de $n$ esta dada por $\left[ \left( \dfrac{m}{2}\right) ^{2}+\left( \dfrac{j}{2}\right) ^{2}\right] \left[ \left( l\right) ^{2}+\left( k\right) ^{2}\right] \medskip\medskip .$

 

Ejemplo 7.

 

Determine la factorización prima de $901$

 

Solución.

 

Dado que $901=30^{2}+1^{2}=15^{2}+26^{2},$ se tiene que

$$\begin{tabular}[c]{lllll}% $a=$\ & $15$\ & & $m=$\ & $\left( 14,4... ...\ $c=$\ & $1$\ & & $l=$\ & $2$\\ $d=$\ & $30$\ & & $j=$\ & $8$% \end{tabular}$$

Por lo tanto,

$$n=\left[ 1^{2}+4^{2}\right] \left[ 2^{2}+7^{2}\right] =17\cdot 53.$$

El principal inconveniente de este método es la determinación de 2 representaciones del número $n$ a factorizar como la suma de dos cuadrados. Sin embargo, al igual que en el Método de Fermat, se puede buscar por medio de una tabla, dos valores enteros de $x$ entre $1$ y $\sqrt{n},$ para los cuales $T\left( x\right) =n-x^{2}$ es un cuadrado perfecto$.$ En caso de que existan dichos valores de $x$ , digamos $x_{0}$ y $x_{1},$ se obtiene que $n$ tiene 2 representaciones como la suma de dos cuadrados:

$$n=x_{0}^{2}+\left( \sqrt{T\left( x_{0}\right) }\right) ^{2}=x_{1}% ^{2}+\left( \sqrt{T\left( x_{1}\right) }\right) ^{2}.$$

Además, se puede establecer una fórmula recursiva para $T\left( x\right) :$

$$T\left( x+1\right) =n-\left( x+1\right) ^{2}=T\left( x\right) -2x-1.$$

Ejemplo 8.

 

Determine la factorización prima de $10001.$

 

Solución.

 

En la siguiente tabla se aprecian los valores de $x$ y $\sqrt{T\left( x\right) }:$

$$\begin{tabular}[c]{\vert c\vert c\vert c\vert}\hline \multicolumn... ...\ & $\vdots$\ & $\vdots$\\ \hline $76$\ & $4225$\ & $65$\\ \hline \end{tabular}$$

Así, se tiene que $a=65,b=76,c=1$ y $d=100,$ además $m=\left( a-c,d-b\right) =\left( 64,24\right) =\left( 2^{6},2^{3}\cdot3\right) =2^{3}=8,$ con estos valores se obtiene: $k=\dfrac{a-c}{m}=8,\quad l=\dfrac{d-b}{m}=3$ y $j=\dfrac{a+c}{l}=\dfrac{66}{3}=22.$ Por lo tanto, la factorización prima de 10001 es

$$10001=\left[ \left( \dfrac{m}{2}\right) ^{2}+\left( \dfrac{j}{2}\... ...{2}\right] =\left( 4^{2}+11^{2}\right) \left( 3^{2}+8^{2}\right) =137\cdot 73.$$

Ejemplo 9.

 

Determine la factorización prima de $6970697$

 

Solución.

 

Note que $6970697=697+10000\cdot697=697\cdot10001,$ y por el ejercicio anterior se sabe que la factorización prima de $10001=137\cdot73,$ por lo que solo resta factorizar $n=697,$ para el cual se tiene los siguientes valores de $x$ y $T\left( x\right) :$

$$\begin{tabular}[c]{\vert c\vert c\vert c\vert}\hline \multicolumn... ...$\ & $\vdots$\ & $\vdots$\\ \hline $16$\ & $441$\ & $21$\\ \hline \end{tabular}$$

Así, se obtiene que

$$\begin{tabular}[c]{lllll}% $a=$\ & $21$\ & & $m=$\ & $\left( 10,8... ... $c=$\ & $11$\ & & $l=$\ & $4$\\ $d=$\ & $24$\ & & $j=$\ & $8$% \end{tabular}$$

Por lo tanto $697=\left( 1+4^{2}\right) \left( 4^{2}+5^{2}\right) =17\cdot41.$ Se concluye que la factorización prima de $6970697$ es

$$6970697=17\cdot41\cdot73\cdot137$$

Con este ejemplo se finaliza esta presentación, esperamos que esta sea de utilidad al lector.

 

Revista digital Matemática, Educación e Internet.
Derechos Reservados