"¿Por qué las cosas son como son y no de otra manera?"  Johannes Kepler

	Divisibilidad	Breve esquema teórico

Índice

• Introducción
• División entera y exacta
• Múltiplos y divisores
• Criterios de divisibilidad
• MCD y MCM
• Números primos y compuestos
• Descomposición en factores primos
• Fórmula de Polignac
• Conjunto de divisores de un número
• Números perfectos, amigos, etc.
• Funciones importantes en Teoría de Números
• Conjeturas

Introducción

El tema de divisibilidad se trata sobre los números naturales, aunque se sabe que sus resultados son válidos en Z. Sin embargo, para cuestiones de unicidad es más claro restringir el estudio a los números naturales. En las propiedades en las que intervengan números enteros se advertirá sobre este carácter.

No se demuestra ningún resultado, ya que el objetivo de esta página es tan solo mostrar un recorrido breve por los aspectos teóricos más interesantes.

División entera y exacta

División entera

Dados dos números naturales a y b, llamaremos división entera entre ellos a la operación de encontrar otros dos números q (cociente) y r (resto), tales que se cumpla:

a = b.q + r con r<b, o lo que es lo mismo, b.q<= a < b(q+1)

Se demuestra que q y r son únicos y que siempre existen.

Si esta situación la expresamos como a =b.q+r, llamaremos a q cociente por defecto y a r resto por defecto.

También podemos expresarla como a=b(q+1)-r'. llamando a r' resto por exceso.

Propiedades

• Se cumple siempre que r + r' = b
• Si el dividendo y el divisor se multiplican (o dividen) por un mismo número, el cociente no varía, pero el resto queda multiplicado (o dividido) por ese número.

En la división entera podemos definir la operación "módulo". Dados dos números a y b naturales llamaremos a MOD b al resto por defecto que resulta al dividir a entre b.

División exacta

Dados dos números naturales a (dividendo) y b (divisor), llamaremos división exacta entre ellos a la operación de encontrar otro número q (cociente) tal que se cumpla a=b.q

Si esta operación es posible, diremos que b es divisor de a, o bien que a es múltiplo de b.

Múltiplos y divisores

Divisor

Divisor de un número

Diremos que un número natural a es divisor de b cuando existe otro número natural k que multiplicado por a da por resultado b. Expresado de otra forma, la división entre b y a ha de ser exacta.

La relación de "ser divisor" o de divisibilidad se representa con el símbolo |. Así, "a divide a b" se escribe como a|b

Propiedades

• Todo número natural es divisor de sí mismo. a|a "aÎN
• La unidad es divisor de todos los números naturales  1|a  "aÎN
• El cero no es divisor de ningún número.
• Si un número es divisor de otros dos, también lo es de suma y diferencia: a|a y a|b  → a|(a+b)
• Si a es divisor de b, y b es divisor de c, entonces a es divisor de c. a|b y b|c  → a|c
• Si a divide a b, también divide a bx, siendo x natural.
• Si a|b y ambos son positivos (naturales), a≤b

La relación de divisibilidad como orden parcial

La relación ‌ por cumplir las tres propiedades

Reflexiva:  a|a "aÎN
Antisimétrica: a|b y b|a, ambos positivos  → a=b
Transitiva:  a|b y b|c  → a|c

es una relación de orden. Al existir elementos no comparables (7 no divide a 8, ni 8 divide a 7), este orden es parcial, por lo que los elementos se pueden ordenar mediante diagramas de árbol.

Diremos que un número natural a es múltiplo de b cuando existe otro número natural k que multiplicado por b da por resultado a.

Propiedades

• Todo n es múltiplo de sí mismo y de la unidad.
• Cero es múltiplo de todos los números.
• La suma o diferencia de dos múltiplos de un número también es múltiplo de dicho número.
• Si a es múltiplo de b, y b es múltiplo de c, entonces a es múltiplo de c.

La relación de "ser múltiplo" representa el orden parcial inverso al de la relación de "ser divisor".

Criterios de divisibilidad

Criterios más comunes

Llamaremos criterio de divisibilidad a toda regla u operación que nos permita conocer si un número es múltiplo (o divisible) entre otro dado. Los criterios que todos conocemos se basan en los restos potenciales del la base 10 respecto al número fijado. Puedes consultar esta relación en la página de Teoría de las Congruencias.

Se recogen aquí los más populares:

Divisibilidad entre 2: Un número es divisible entre 2 si termina en cifra par: 0,2,4,6,8.
Entre 5: Si termina en 0 o 5
Entre 10, 100, 1000, ...: Si termina respectivamente en 0, 00, 000, ...
Entre 4: Si las dos últimas cifras del número forman otro número divisible entre 4. Por ejemplo 236, 132, 448,...
Entre 25: Similar al anterior: si termina en 00, 25, 50 o 75.
Entre 8 o 125: Son similares a los dos anteriores, pero observando las tres últimas cifras.
Entre 3 o 9: Un número es divisible entre 3 o 9 cuando también lo sea la suma de sus cifras.
Entre 11: Se suman las cifras de orden par y las de orden impar por separado. Se restan después ambas sumas y ha de resultar un múltiplo de 11 (incluido el cero).

Otros criterios menos eficientes

Divisibilidad entre 7 o 13: Este criterio también es válido para el 11, aunque no es útil. Consiste en separar el número en bloques consecutivos de tres cifras, e ir sumando cada bloque con signos alternados + y -. El resultado ha de ser múltiplo de 7 o de 13 en su caso (o entre 11 si se estudia este número). Por ejemplo, el número 1707069 es múltiplo de 13, porque 1-707+069 = -637 = -13*49

Divisibilidad entre números compuestos: Para ver si un número es divisible entre otro compuesto, basta estudiar la divisibilidad respecto a sus factores primos. Así, un número es divisible entre 6 si lo es entre 2 y 3.

Criterios recursivos

Últimamente se han hecho populares los criterios de tipo recursivo, en los que se reitera una misma operación varias veces hasta conseguir la seguridad de si es divisible o no. Vemos un ejemplo para el 7:

Para ver si un número es divisible entre 7 se apartan su última cifra de la derecha, se multiplica por 2 y se resta el resultado del resto de número formado por las cifras que quedan. Si se obtiene un número múltiplo de siete, el número primitivo también lo es. Podemos probarlo con el número 191548, que se transforma en 19154 - 2*8 = 19138. Si no sabemos si es múltiplo de 7, reiteramos la operación: 1913 - 2*8 = 1897, Podemos continuar: 191 - 2*3 = 175, que es múltiplo de 7 por ser 7*15. Según este criterio, también será múltiplo de 7 el primitivo número.

En las Propuestas de Divisibilidad se sugiere una demostración de este criterio.

Criterios para ordenador

Todo lo anterior ha perdido eficacia ante el uso de las funciones ENTERO, COCIENTE y RESIDUO de las hojas de cálculo y programas similares.

ENTERO: Todos los programas de cálculo y lenguajes de programación disponen de la función parte entera, que, en los números positivos, que son los que nos interesan ahora, truncan los decimales de un número y devuelven la parte entera. Según la herramienta usada, se puede representar como ENTERO, ENT, E, INT, etc.

Para ver si un número A es divisible entre un número B, basta plantear esta condición:

Si   A/B = ENTERO(A/B) es divisible, y en caso contrario, no.

En hoja de cálculo se puede representar así:

=SI(A/B=ENTERO(A/B);"Es divisible";"No es divisible")

COCIENTE: La función COCIENTE, a veces representada con el signo \, devuelve el cociente entero entre dos números. Por tanto, el criterio de divisibilidad es similar al anterior:

=SI(A/B=COCIENTE(A;B);"Es divisible";"No es divisible")

RESIDUO: Esta función devuelve el resto de la división entera de A entre B. También se usan los símbolos MOD, MÓDULO, %, según los programas o lenguajes. Con esta función basta averiguar si el RESIDUO es igual a cero para decidir si es divisible un número entre otro:

=SI(RESIDUO(A;B)=0;"Es divisible";"No es divisible")

Máximo común divisor y Mínimo común múltiplo

Divisores y múltiplos comunes

Un número natural k es divisor común de otros cuando es divisor de todos ellos. Igualmente se define el múltiplo común.

Máximo común divisor (MCD)

El máximo común divisor de varios números naturales es el mayor de sus divisores comunes.

Si su valor es 1, diremos que los números son primos entre sí.

Propiedades:

• Si a es múltiplo de b, entonces el MCD de ambos es b.
• El MCD de dos números a y b coincide con el MCD de b y el resto de la división de a entre b.En esta propiedad se basa el Algoritmo de Euclides.

Practica el algoritmo de Euclides con hojas de cálculo

• Si varios números naturales se multiplican (o dividen exactamente) por otro natural m, su MCD queda también multiplicado ( o dividido exactamente) por m. En concreto, si se dividen entre su MCD, los resultados son priomos entre sí.
• Si m es el MCD de dos números a y b y n su MCM, se cumple la igualdad: m.n = a.b
• Igualmente, si m es el MCD de a y b, existen dos números enteros p y q tales que se verifica: m = p.a+q.b (Teorema de Bezout)

Números primos entre sí

Son aquellos números naturales (no necesariamente primos) que no tienen divisores comunes. Su MCD es 1. También se les llama extraños, primos relativos o coprimos.

Según el Teorema de Bezout, si a y b son primos entre sí, existirán dos números enteros p y q tales que se verifique: p.a+q.b = 1

Números primos entre sí dos a dos

Los elementos de un conjunto de números naturales se dicen primos entre sí dos a dos, cuando tomados por parejas, son siempre primos entre sí. Los números 5,15 y 9 son primos entre sí, pero no dos a dos. Sin embargo 4, 9, 25 y 49 sí lo son.

Mínimo común múltiplo (MCM) de varios números es el menor de sus múltiplos comunes.

Propiedades:

• Si a es múltiplo de b, entonces el MCM de ambos es a.
• Si varios números naturales se multiplican (o dividen exactamente) por otro natural m, su MCM queda también multiplicado ( o dividido exactamente) por m.
• Si m es el MCD de dos números a y b y n su MCM, se cumple la igualdad: m.n = a.b

Puedes efectuar estos cálculos con hoja de cálculo

Números primos y compuestos

Número primo

Un número natural mayor que 1 se llama primo si sólo es divisible entre sí mismo y la unidad. En caso contrario le llamaremos compuesto.

Existen infinitos números primos (se sabe desde Euclides), aunque su densidad es cada vez menor y se ha demostrado que converge de la siguiente forma:

Si denominamos p (x) al número de números primos inferiores o iguales a x, se cumple el teorema:

Teorema de los números primos

El cociente p(x)/x  es asintóticamente equivalente al cociente 1/ln(x) para valores de x muy grandes (versión de Gauss) o bien a 1/(ln(x)- 1.08366)  (versión de Legendre). Este teorema lo expresó Gauss como conjetura. Un tiempo más tarde sustituyó estas funciones por el logaritmo integral Li(x), conjeturando que p(x) se aproxima asintóticamente a esta función:

El matemático ruso Chebychev acotó mediante dos constantes esta aproximación.

Riemann usó la función zeta x (s) = 1 + 1/2^s + 1/3^s+ 1/4^s + 1/5^s … para lograr una gran aproximación entre p(x) y Li(x), aunque no llegó a demostrar su su convergencia, cosa que lograron por separado los matematicos De la Vallée Pousin y Hadamard, al final del siglo XIX, y en el siguiente siglo (1949), demostraron el teorema Selberg y Erdös usando técnicas elementales.

La serie S (1/p) , donde p recorre todos los números primos, es divergente.

No obstante, si limitamos la serie a una suma parcial de todos los números primos inferiores o iguales a 5.10⁷, dicha suma es menor o igual que 4.

La función p(x) la puedes obtener en la calculadora de Divisibilidad

Criba de Eratóstenes

Algoritmo que encuentra la serie de números primos inferiores a uno dado mediante supresiones ordenadas de números compuestos: En primer lugar se tachan los pares a partir del 4 Después, a partir del 9, se tachan de 3 en 3 Desde el 25, de 5 en 5 Y así sucesivamente. En la figura se observa un modo muy atractivo de tachado de números compuestos entre 1 y 100, debido a K.P.Swallow. En este esquema se comprueba que todos los números primos son de la forma 6n+1 o 6n-1. También se ve fácilmente que son de la forma 4n+1 o 4n-1.

Criterio para saber si un número es primo

Un número es primo si no es divisible entre ninguno de los números primos menores o iguales a su raíz cuadrada. Como el número de esos primos es finito, esto proporciona un algoritmo para descubrir si un número es primo o no.

Algunas propiedades de los números primos

- Hay infinitos números primos de la forma 4n+3
- Si p_n es el n-ésimo primo, será menor o igual que 2 elevado a 2^n-1
- Todo número primo mayor que 3 es de la forma 6n+1 o de la forma 6n-1
- Todo número primo mayor que 2 es de la forma 4n+1 o de la forma 4n-1

Un número primo tiene las siguientes propiedades respecto a una suma de cuadrados:

1. Un número primo es suma de cuadrados de dos números naturales si y sólo si es de la forma 4n+1.
2. El producto de dos números que son suma de cuadrados también es otra suma de cuadrados, en virtud de la identidad
3. (a² + b²)(c² + d²) = (ac-bd)² + (ad+bc)²
4. Por tanto el producto de potencias de números del tipo 4n+1 también equivale a una suma de cuadrados.
5. Si una suma de cuadrados se multiplica por otro cuadrado, resulta una nueva suma de cuadrados:
6. (a² + b²)c² = (ac)² + (bc)²
7. De las propiedades anteriores se deduce que son suma de cuadrados los números que contienen factores primos del tipo 4n+1 y factores de otro tipo cualquiera pero con potencia par.

Puedes estudiar estas propiedades con el Buscador de Naturales

Descomposición en factores primos

La descomposición en factores primos se basa en en siguiente teorema

Teorema Fundamental de la aritmética

Sea n un número mayor que 1. Entonces existen números primos p₁, p₂, p₃, ... y unos exponentes a1, a2, a3, ... tales que

n = p₁^a1.p₂^a2. p₃^a3...

A estos números primos les llamaremos factores primos de n y siempre existen y son únicos, así como sus exponentes.

Las potencias del tipo p₁^a1 , potencias de un número primo, reciben el nombre de números primarios.

Consulta un modelo de Hoja de Cálculo que encuentra los factores primos de un número.

Criterio de divisibilidad

Un número natural a divide a otro b si todos los factores primos de a lo son también de b con exponentes iguales o mayores

Cálculo del MCD y el MCM mediante factores primos

Una vez descompuestos dos números a y b en factores primos, su MCD se obtiene como producto de los factores comunes tomados con el menor exponente y el MCM como producto de todos los factores con el mayor exponente.

Como consecuencia, dos números serán primos entre sí si no tienen factores primos comunes.

Fórmula de Polignac

Es relativamente sencillo encontrar los divisores primos del factorial de un número natural n. Simplemente son todos los primos inferiores o iguales a n. El problema reside en calcular los exponentes a los que están elevados. Por ejemplo, la descomposición factorial de 22! Es

Para obtener los exponentes Polignac propuso esta fórmula

En la que el exponente r de cada factor primo p viene dado por la suma de los cocientes enteros del número n entre las sucesivas potencias de p.

Puedes usar esta fórmula para resolver las cuestiones siguientes:
¿Cuál es el mayor divisor del factorial 12! que es cuadrado perfecto? (Solución 2073600, cuadrado de 1440)
¿En cuántos ceros termina el cociente 100!/50!? (Solución en 12 ceros)
¿Cuál es la máxima potencia de 56 que divide a 56!? (Solución 56 elevado a 9)
 

La fórmula de Polignac la tienes implementada en hojas de cálculo

Conjunto de divisores de un número

Número de divisores

Es el conjunto formado por todos los divisores de ese número. Generalmente sólo se consideran los positivos. En nuestro caso lo haremos así, por restringirnos a los números naturales.

Para obtener todos los divisores de un número cuya descomposición es n = p₁^a1.p₂^a2 .p₃^a3... basta considerar que son los términos del producto

(1 + p₁ + p₁²+...p₁^a1)(1 + p₂ + p₂²+...p₂^a2)(1 + p₃ + p₃²+...p₃^a3)

Logaritmo entero

Llamaremos logaritmo entero de un número natural a la suma de todos sus factores primos, contando sus repeticiones. Se suele representar por la función sopfr(n). Así, sopfr(28)=2+2+7=11. El valor más pequeño corresponde a sopfr(1)=0 y los mayores coinciden con los números primos, como es evidente. Aquí tienes la gráfica de esta función para los primeros números, en la que se perciben los máximos correspondientes a los primos:

Se le llama logaritmo porque posee la propiedad aditiva: sopfr(a*b)=sopfr(a)+sopfr(b). Se cumple por el hecho de contar las repeticiones de los factores primos. Si se contaran una sola vez, esta propiedad sólo se verificaría si los números fueran primos entre sí y daría lugar a otra función que se representa por sopf(n).

Números perfectos, amigos,etc.

Puedes consultar los siguientes tipos interesantes de números

Números perfectos, abundantes o deficientes

Número perfecto

Diremos que un número es perfecto cuando equivale a la suma de todos sus divisores propios (menores que él).

Los primeros números perfectos son 6, 28, 496 y 8128, ya conocidos en la antigüedad.

Todos los números perfectos son también triangulares y todos los conocidos hasta ahora son son pares. Se ignora si existe algún número perfecto impar, aunque se sabe que de existir debería ser mayor que 10¹⁵⁰.

Tampoco se sabe si existen infinitos números perfectos.

Euclides demostró que si el número 2^k-1 es primo (número de Mersenne), el número N=2^k-1(2^k-1) es perfecto.

Ver propuesta de demostración

Euler demostró el recíproco (evidentemente, sólo para perfectos pares), con lo que quedó establecida una correspondencia biunívoca entre los números perfectos pares y los números de Mersenne primos.

Número abundante

Un número es abundante si es menor que la suma de todos sus divisores propios, por ejemplo el 12.

Todos los números múltiplos de 6 mayores que 6 son abundantes. Intenta demostrarlo.

El menor abundante impar es 945. Puedes comprobarlo con el Buscador de Naturales.

Todo número abundante mayor que 83.160 es suma de otros dos abundantes.

Número deficiente

Un número se llama deficiente cuando es mayor que la suma de sus divisores propios. Por ejemplo: 21 > 1+3+7

Curiosidades numéricas sobre números perfectos, abundantes o deficientes

Los inversos de los divisores de un número perfecto suman siempre 2:

Divisores del 6: 1/1 +1/2 +1/3 + 1/6 = 2

Divisores del 28: 1/1 + 1/2 +1/4 + 1/7 + 1/14 + 1/28 = 2

Todos los números perfectos, salvo el 6, coinciden con sumas parciales de la serie

1³ + 3³ +5³ +7³ +9³ + …

Así: 28 = 1³ + 3³ ; 496 = 1³ + 3³ +5³ +7³

Números amigos

Dos números naturales son amigos si cada uno de ellos es igual a la suma de todos los divisores propios del otro.

Así, son amigos los pares 220 y 284 (conocido por los griegos), 17296 y 18416 (Fermat) y 9363584 con 9437056 (Descartes).

Euler encontró 64 pares, entre ellos 2620 y 2924, y 5020 con 5564

Paganini descubrió un par relativamente pequeño que había permanecido inadvertido durante siglos: 1184 y 1210

Parece que su cociente tiende a 1

No se conocen pares de amigos uno par y otro impar ni se ha podido demostrar que no existan.

Todas las parejas de números amigos impares son múltiplos de 3.

No hay fórmulas para encontrar todos los números amigos, aunque existen para construir algunos (Ver Thabit idn Qurra)

No se sabe si su número es finito o infinito.

Los primeros pares de números amigos son:

Número de Mersenne

Son los números del tipo 2^p -1 con p primo.

Si 2ⁿ -1 es primo, n también es primo, pero no al revés. Por ejemplo, 2⁶⁷-1 es divisible entre 193.707.221. También 2¹¹ – 1 es compuesto e igual a 23*89

Mersenne afirmó que son primos tan sólo los correspondientes a los valores de p 2, 3, 5, 7, 13, 19, 31, 67, 127 y 257, pero falló en el 61, que también es primo, y en el 67, que no lo es (Cole 1903).

Se ignora si hay infinitos números primos de Mersenne.

Los primeros números de Mersenne primos son:

Y algunos de los últimos descubiertos hasta ahora:

Número de Fermat

Es aquel que es de la forma

Todo primo de la forma 2^k +1 es de Fermat, pues es fácil demostrar que si k es impar, o contiene un factor impar, el resultado es un número compuesto.

Pero cualquier número de Fermat no es necesariamente primo.

Los primeros números de Fermat, para n=0,1,2,3 y 4, los números 3, 5, 17, 257, 65537, ...son primos.

Euler demostró que para n=5 El número resultante no es primo, sino divisible entre 641: 4.294.967.297 = 641*6.700.417

Next, en 1880 demostró que el número de Fermat correspondiente a n=6 se descompone en los factores 18.446.744.073.709.551.617 = 274.177 * 67.280.421.310.721

No se sabe si existen más números de Fermat primos.

Gauss relacionó estos números con los polígonos regulares que se pueden dibujar con regla y compás.

Funciones importantes en teoría de números
 

f(n) (Indicador de Euler) Representa cuántos números naturales inferiores a n son primos con él, contando el 1.

Si n es primo, f(n)= n-1. Si es primario (tipo p^r con p primo), su indicador viene dado por la fórmula f(n)=p^r-1(p-1) = p^r(1-1/p)

El indicador de un producto de números primos dos a dos es el producto de los indicadores de éstos.
Con esta propiedad podemos calcular el indicador de cualquier número compuesto

Si un número natural m se descompone en factores primos:  m=p^a.q^b.r^s.... su indicador de Euler vendrá dado por:

f(m) = m (1- 1/p)(1 - 1/q)(1- 1/r)....

Por ejemplo, si 12 = 2²*3, su indicador será  f(12) = 12*(1-1/2)*(1-1/3) = 4, y , efectivamente los 4 números 1, 5, 7 y 11 son primos con él

El indicador de Euler coincide con el número de elementos inversibles de un grupo cíclico de orden n

Una curiosa propiedad de esta función es que si sumamos su valor en los divisores de N, esa suma coincide con N.

s (n) (Suma de divisores) Representa la suma de todos los divisores de n incluido él mismo.

Si n es primo, s (n)=n+1. Si es perfecto, s (n)=2n. Si es un número primario, la función s (n) tiene como fórmula:
s (p^r)= (p^r+1-1)/(p-1) que nos permite evaluar la función s (n) para un número compuesto si se conocen sus factores primos, en virtud del resultado:

Si a y b son primos entre sí se verifica que s (a.b)=s (a).s (b)

p (n) (Primos hasta n) Representa cuántos números primos hay no superiores a n.

Para n tendiendo a infinito, coincide asintóticamente con la expresión n/ln(n) (Teorema de los números primos).

D(n) (Distancia al próximo primo) Su valor es la distancia entre un número cualquiera y el número primo más pequeño que es mayor o igual que él.

M(n) (Función de Möbius)

Se define para todos los números naturales según sean múltiplos o no de números cuadrados. A cada uno se le hace corresponder uno de los valores -1, 0 o +1,de la siguiente forma:

M(n)= 1 si n no es múltiplo de cuadrados y tiene un número par de factores primos distintos
M(n)=-1 si n no es múltiplo de cuadrados y tiene un número impar de factores primos distintos
M(n)=0 si n es divisible entre algún cuadrado.

Es una función es muy importante en Teoría de Números y Combinatoria.

Conjeturas

Conjetura de Girard

Todo número primo de la forma 4n+1 se puede expresar de forma única como suma de dos cuadrados

Conjeturas de Goldbach

Todo número par mayor que 2 es suma de dos primos

Fue propuesta por Goldbach el 7 de Junio de 1742, en una carta dirigida a Euler.  En realidad, su propuesta se refería a la conjetura ternaria: " Todo número impar es la suma de tres primos" y Euler le respondió con la propuesta binaria que todos conocemos.

Ha sido comprobada hasta 10¹⁴, pero no se ha podido demostrar.

No obstante, se han logrado resultados provisionales:

Cualquier número par es suma de 6 o menos números primos.(Ramaré 1995)

Todo número par suficientemente grande es suma de un primo y del producto de dos primos.(Chen 1966)

Todo número impar N mayor que 5 es suma de tres primos. (Demostración de la conjetura ternaria a cargo de Vinogradov en 1937).

Es consecuencia de la anterior.

(Demostrada por Vinogradov (para un número suficientemente grande), tiene como consecuencia que todo número par suficientemente grande es suma de a lo sumo cuatro primos)

Otras conjeturas

Algunas están incluidas en el Diccionario como problemas no resueltos.

Ver propuestas