Nuestro propósito de hoy será hacer un algoritmo que nos devuelva la factorización de un entero positivo. Utilizando esta factorización resolveremos ejercicios planteados el pasado día.
La Criba de Eratóstenes
Este procedimiento es el más sencillo para determinar si un número es primo o no; sin, embargo, su eficiencia es escasa cuando el número es grande.
Ejercicio: Determinar un algoritmo que nos diga si un número es primo o no
(%i5)
n:13331$ out:1$ i:2$ while (i<floor(sqrt(n)) and out>0) do( if (mod(n,i)=0) then out:0, i:i+1 )$ if (out<1) then print(n, «no es primo») else print(n, «es primo»)$
Ejercicio: ¿Cuántos primos hay entre 5231 y 5331?
(%i1)
esprimo(n):=block([], … )$
(%i8)
n:5231$ m:5331$ if (mod(n,2)=0) then n:n+1$ if (mod(m,2)=0) then m:m–1$ id:0$ for i:n thru m step 2 do( if(esprimo(i)>0) then id:id+1 )$ id;
Algoritmo para encontrar divisores primos
Nuestro propósito es encontrar los divisores primos de un número compuesto, utilizando el teorema:
Teorema: Si un entero positivo es compuesto, entonces existe un primo \(p<\sqrt{n}\) que lo divide.
Ejercicio: Determinar un algoritmo que nos encuentre los divisores primos de un número compuesto.
(%i2)
div_primos(n):=block([d,j,m], d:[1], j:2, m:n, while (j<=floor(sqrt(m))) do( if (mod(m,j)=0) then ( d:append(d,[j]), m:m/j, j:1 ), j:j+1 ), d:append(d,[m]) )$ div_primos(13131);
Veamos ahora cómo determinar los divisores sin conocer su descomposición:
Ejercicio: Encontrar los divisores de 83853.
(%i2)
divisores(n):=block([d], d:[1], for i:2 thru n do if(mod(n,i)=0) then d:append(d,[i]), d )$ divisores(83853);
Como observamos el problema de este algoritmo es que es poco eficiente. El algoritmo será más eficiente si conseguimos la descomposición en factores primos del número.
Factorización con Casio
La calculadora Casio fx-991 permite factorizar números. Veamos un ejemplo:
Sin embargo, como nos dice, en el modo COMP, puede factorizar un entero positivo de no más de 10 dígitos en factores primos. Veamos el procedimiento para resolver algunos de los ejercicios cuando tenemos más de 10 dígitos
Sea \(N=(d_kd_{k-1}d_{k-2}\cdots d_{1}d_{0})_{10}\) expresado en base decimal. Así \(N\) se puede poner en formato \[N=(d_kd_{k-1}d_{k-2}\cdots d_{m+1})_{10}\, 10^{m}+ (d_{m}d_{m-1}\cdots d_{0})_{10}\]
Por la propiedades de divisibilidad que conocemos, si \[a|(d_kd_{k-1}d_{k-2}\cdots d_{m+1})_{10}\] y \[a|(d_{m}d_{m-1}\cdots d_{0})_{10},\] entonces \(a|N\), y por tanto \(a\) es un factor de \(N\). De este modo podemos buscar factores que nos faciliten reducir los dígitos hasta que quepan en la calculadora.
Ejercicio: Encontrar la factoriación de 930823188559.
Observemos que \[930823188559=93082\cdot 10^7+3188559.\] Si buscamos la descomposición de 93082 y de 3188559 de manera independiente y tienen factores comunes, entonces dichos factores también lo serán de 930823188559.
\[\begin{array}{l}
93082= 2\cdot 11 \cdot 4231 \\
3188559=3\cdot 11 \cdot 23 \cdot 4201
\end{array}
\] Luego \[\begin{align*}
930823188559&=11\cdot (8462\cdot10^7+289869) \\
&=11\cdot 84620289869
\end{align*}\]
Ahora tenemos un número más pequeño que factorizar, 84620289869, dando \[930823188559=11\cdot 41\cdot 73\cdot 2551\cdot 11083.\]
Ejercicio: Evalúese la siguiente afirmación: «Dos números enteros positivos impares y consecutivos son siempre coprimos.»