Las reglas de divisibilidad son criterios que sirven para determinar si un número es divisible por otro. Un número es divisible por otro si al dividirlo por ese número el resultado es una división exacta con residuo cero.

Por ejemplo, 30 es divisible por 5 porque al dividirlo por 5 el resto es cero, y como resultado da un número exacto que es 6.

Definición: Dados dos números enteros n y d, con la condición de que d ≠ 0. Se dice que d divide a n si existe un entero q que satisface la siguiente igualdad

Si d divide a n, se escribe d|n. Caso contrario si d no divide a n, se escribe

Ejemplo. Sabemos que 15 = 3∙5, por lo tanto, podemos afirmar que 3 divide a 15, de igual forma 5 divide a 15, por lo tanto 3 y 5 son factores de 15.

Teorema: Sean m, n y d números enteros, entonces

Definición: Un entero mayor que 1 cuyos únicos divisores positivos son 1 y él mismo número se llama primo. Un entero mayor que 1 que no es primo se llama compuesto.

Ejemplo. El número 29 es primo porque sus únicos divisores son 29 y 1. El número entero 24 es compuestos ya que es divisible entre 1, 2, 3, 4, 6 y 24.

Dado un número entero n > 1. El número n es compuesto, si tiene un divisor positivo d diferente de 1 y diferente de él mismo. Como d es positivo y d ≠ 1, d > 1. Luego d es un divisor de n, d ≤ n.

Dado que d ≠ n y d < n. Para determinar si n es compuesto, es suficiente con probar si alguno de los enteros

2, 3, . . . , n – 1

divide a n. Si algún entero en esta lista divide a n, entonces n es compuesto. Si no hay un divisor en esa lista, entonces n es primo.

Ejemplo. Mostrar si el número 29 es primo.

Por inspección, se puede verificar que ningún número de la lista

2, 3, 4, 5, 6, 7, …, 27, 28

divide a 29; por lo tanto, se concluye que 29 es primo.

Ejemplo. Verificar si el número 1353 es primo.

Se puede verificar que ningún número de la lista siguiente divida a 1353

2, 3, 4, 5, 6, 7, …, 1351, 1352

Buscando los posibles divisores, encontramos que 3 divide a 1353, además (1-3+5-3=0), por lo tanto 11 divide a 1353.

Teorema. Un entero positivo n mayor que 1 es compuesto si y sólo si n tiene un divisor d que satisface

Con base en el teorema anterior para determinar si un número es primo, es suficiente con verificar en la lista 

Algoritmo

Definimos el siguiente algoritmo que determina si un número entero n > 1 es primo. Si n es primo, el algoritmo retorna como salida 0. Si n es compuesto, el algoritmo retorna el primer divisor d que se encuentra en la lista acotada por los límites 2 y la raíz cuadrada de n.

Para probar si d divide a n, el algoritmo verifica si el residuo al dividir n entre d, n mod d, es cero.

Entrada: n

Salida: d

es_primo(n)

{

      Para d = 2 hasta

      Si (n mod d == 0)

           Escriba “Es primo”

      Escriba “No es primo”

}

Código C++

Teorema fundamental de la aritmética

Cualquier entero mayor que 1 se puede expresar como un producto de primos. Más aún, si los primos se escriben en orden no decreciente, la factorización es única. Simbólicamente, si

Ejemplo

Los divisores de 30 son

Los factores primos de 30 son

La factorización completa de 30 es

Código C++

Máximo común divisor

El máximo común divisor de dos números enteros p y q (diferentes de cero) es el entero positivo más grande que divide a los dos: p y q.

Ejemplo

El máximo común divisor de 4 y 6 es 2 y el máximo común divisor de 3 y 8 es 1 (no tienen divisores en común mayores que 1).

Si el máximo común divisor de p y q es 1, significa que la fracción p/q está simplificada; en caso contrario, la fracción p/q sería factible de ser simplificada.

Ejemplo, 4/6 no está simplificada porque el máximo común divisor de 4 y 6 es 2. (Dividiendo 4 y 6 entre 2), obtendríamos la fracción canónica correspondiente. 

La fracción 3/8 está simplificada porque el máximo común divisor de 3 y 8 es 1.

Definición. Sean m y n enteros diferentes de cero. Un divisor común de m y n es un entero que divide tanto a m como a n. El máximo común divisor, escrito mcd(m, n), es el mayor divisor común de m y n.

Ejemplo. Los divisores enteros y positivos de 30 están dados por conjunto

D₃₀ = {1, 2, 3, 5, 6, 10, 15, 30}

y los divisores enteros y positivos de 105 están en el conjunto

D₁₀₅={1, 3, 5, 7, 15, 21, 35, 105}

Por lo tanto, los divisores comunes de 30 y 105 son 1, 3, 5, 15.

y el máximo común divisor de 30 y 105, mcd(30, 105), es 15.

Código C++

Mínimo común múltiplo

Definición:  Sean p y q enteros positivos. Un múltiplo común de p y q es un entero que es divisible tanto entre p como entre q. El mínimo común múltiplo, escrito mcm(p, q), es el menor múltiplo común positivo de p y q.

Ejemplo:  Obtener el mcm de 2940 y 3150

La factorización completa de 2940 = 2∙2∙3∙5∙7∙7

La factorización completa de 3150 = 2∙3∙3∙5∙5∙7

Luego los factores primos comunes son: 2∙2∙3∙3∙5∙5∙7∙7= 44100

Teorema: Para cualquier par de números enteros positivos p y q, se cumple que: 

Usando el teorema anterior, si tenemos un algoritmo para calcular el máximo común divisor de dos números enteros positivos, es posible calcular el mínimo común múltiplo.

Ejemplo:  Obtener el mcm de 315 y 825

La factorización completa de 315 = 3∙3∙5∙7

La factorización completa de 825 = 3∙5∙5∙11

Luego el mcd(315, 825) = 3∙5 = 15