Definición

Es el proceso inverso de la multiplicación , la factorización de enteros o factorización de primos consiste en descomponer un número compuesto (no primo) en divisores no triviales, que cuando se multiplican dan el número original.

Descomposición en factores primos

La imagen demuestra la descomposición en primos del número 864. Un método rápido de escribir el resultado en números primos es $2^{5}\times 3^{3}$ .

Por el teorema fundamental de la aritmética, cada entero positivo tiene una única descomposición en números primos (factores primos). La mayor parte de los algoritmos de factorización elementales son de propósito general, es decir, permiten descomponer cualquier número introducido, y solo se diferencian sustancialmente en el tiempo de ejecución.

{\begin{array}{r|l}72&2\\36&2\\18&2\\9&3\\3&3\\1&\end{array}}

72=2^{3}\cdot 3^{2}\,

Algoritmo de Euclides

Un algoritmo es una secuencia de pasos para conseguir un resultado.

El algoritmo de Euclides es un procedimiento para calcular el m.c.d. de dos números. Los pasos son:

1 Se divide el número mayor entre el menor.

2 Si:

1 La división es exacta, el divisor es el m.c.d.

2 La división no es exacta, dividimos el divisor entre el resto obtenido y se continúa de esta forma hasta obtener una división exacta, siendo el último divisor el m.c.d.

Ejemplos

Se busca el máximo común divisor de a = 945 y b = 651, números escogidos al azar: 945 = 1×651 + 294 651 = 2×294 + 63 294 = 4×63 + 42

63 = 1×42 + 21
42 = 2×21 + 0        entonces mcd(951; 294) = 21 (el último resto no nulo).

Como segundo ejemplo, tomemos números de tamaños parecidos a los anteriores: a = 987 y b = 610: 987 = 1×610 + 377 610 = 1×377 + 233 233 = 1×144 + 89 144 = 1×89 + 55

89 = 1×55 + 34
34 = 1×21 + 13
21 = 1×13 + 8
13 = 1×8 + 5
 8 = 1×5 + 3
 5 = 1×3 + 2
 3 = 1×2 + 1        entonces mcd(987; 610) = 1