Los distintos criterios o reglas de divisibilidad de los números enteros "Z" son de sumo interés, especialmente de los números primos, ya que atajan el proceso de factorización permitiéndonos saber, si un número “N” mayor que éste “S”, es divisible por él, sin necesidad de pasar por dividir ambas cantidades y así ver si finalmente se obtiene, o no, residuo en dicha operación que nos indique que N no es divisible por S. Ésto supone mucho menos esfuerzo y tiempo a la hora de asegurar con certeza si dicho entero S es factor primo o no, de ése, o cualquier otro entero N.

Algunos criterios (o reglas) de divisibilidad, parecen más o menos eficientes, resulta más
o menos factible poder llevarlos a término, que otros, pero aún, que yo sepa, no se ha podido observar un único criterio o base metodológica que pueda emplearse con cualquier número primo, sin resultar su puesta en práctica, demasiado compleja o contraproducente a la hora de determinar la divisibilidad de N y S, en el transcurso del proceso de factorización de N.

He hallado un método matemático por el cual puedo determinar fácilmente si un número N es múltiplo de S, sin necesidad de dividir ambos términos. Ésto se consigue gracias a la obtención -mediante dicho método- de una serie numérica relativa a S, en cada caso, pudiendo ser S cualquier número primo.

A continuación mostraré, a modo de ejemplo, una lista de números que hacen, en su conjunto, una serie completa y ordenada, la cual nos permitirá saber si un número cualquiera N, sea éste de las cifras que sea, es múltiplo, o no, del número primo: 241.


Si queremos saber si N es divisible por 241, multiplicaremos uno a uno, comenzando por las unidades, el valor absoluto de cada cifra de N, por cada uno de los números de la serie, en el orden en que vienen determinados en la lista. Luego, los productos de dichas multiplicaciones se suman entre sí, para obtener un número entero “M” menor que N, el cual nos indicará si N es divisible por 241, según sea el caso de si M lo es, o no. Es decir:

En caso de que M siga siendo un número muy alto para saberlo con una operación suficientemente simple, repetiremos el proceso multiplicando las cifras de M, desde las unidades, por cada uno de los términos de la serie, nuevamente, hasta llegar a la primera cifra de M.

Por otro lado, si N es un número de más de -en este caso- 30 cifras (siempre en sistema decimal), la serie de la lista, se prolongará cíclicamente .ya que ésta contiene sólo 30 únicos números enteros distintos- continuando con el 1 nuevamente desde el 217, de modo que siempre, el valor absoluto de la última cifra de M multiplique al primer término de la lista, es decir, 1.

Pongámoslo a prueba con un par de números de distintas cifras, elegidos al azar, situándolos en el lugar de N, para ver si funciona en ambos los casos:

a) 9864378945521
b) 5633296




a) 1x1= 1 ;10x2= 20 ;100x5= 500 ;36x5= 180 ;119x4= 476 ;226x9= 2034 ;91x8= 728 ;
187x7= 1309 ;183x3= 549 ;143x4= 572 ;225x6= 1350 ;81x8= 648 ;87x9= 783 .

La suma de todos los productos es 9150. Un número (M), que aún podemos usar repitiendo el proceso nuevamente:

1x0= 0 ;10x5= 50 ;100x1= 100 ;36x9= 324

Sumamos los resultados y tenemos 474.

Si multiplicamos 241x2, el resultado es 482, demasiado alto, por lo que sabemos que:

El número 9864378945521 no es divisible por 241.

Si observamos bien, la diferencia entre el resultado del proceso y el primer múltiplo entero de 241 es 8 (482 – 474= 8 ), de modo que, ¿qué ocurriría si añado esas 8 unidades a N? ¿el número que resultara sería múltiplo de 241? Veamos:

9864378945521 + 8= 9864378945529

1x9= 9 ;10x2= 20 ;100x5= 500 ;36x5= 180 ;119x4= 476 ;226x9= 2034 ;91x8= 728 ;
187x7= 1309 ;183x3= 549 ;143x4= 572 ;225x6= 1350 ;81x8= 648 ;87x9= 783

Esta vez, la suma de todos los productos es 9158;

1x8= 8 ;10x5= 50 ;100x1= 100 ;36x9= 324

De la suma se obtiene 482, que es precísamente 241x2, de modo que deducimos que el número 9864378945529 sí es divisible por 241 y, de hecho así es, siendo que

9864378945529 / 241= 40931032969

- - - - - - - - - - - -

b) 1x6= 6 ;10x9= 90 ;100x2= 200 ;36x3= 108 ;119x3= 357 ;226x6= 1356 ;91x5= 455

Si sumamos los productos obtenemos 2572

1x2= 2 ;10x7= 70 ;100x5= 500 ;36x2= 72

De ahí se obtiene 644 que es menor que 723 (241x3) y mayor que 482 (241x2)

Deducimos, por tanto, que 5633296 no es divisible por 241.

Dado que 723 – 644= 79, añadimos dicha cantidad a N, quedando:

5633296 + 79 = 5633375

Dividimos 5633375 / 241 = 23375

El criterio de divisibilidad de 241 por el momento no falla.




Ahora mostraré otra lista de números, la que supone ser la serie con la que operar al hacer una prueba de divisibilidad del número primo 1093. Puesto que esta lista consiste en 273 números usaremos únicamente los 30 primeros, ya que los números que emplearemos a modo de dividendo en cada ejemplo no excederán en ningún caso las 30 cifras.

a) 66879740354082
b) 12338789


a) 1x2= 2 ;10x8= 80 ;100x0= 0 ;1000x4= 4000 ;163x5= 815 ;537x3= 1611 ;998x0= 0 ;
143x4= 572 ;337x7= 2359 ;91x9= 819 ;910x7= 6370 ;356x8= 2848 ;281x6= 1686 ; 624x6= 3744

La suma de los productos es 24906 que, como sigue siendo muy alto, situamos como M.

1x6= 6 ;10x0= 0 ;100x9= 900 ;1000x4= 4000 ;163x2=326

Sumamos y obtenemos 5232. Puesto que es menor a 5465 (1093x5) y mayor que 4372 (1093x4), deducimos que 66879740354082 no es divisible por 1093.

De 5465 – 5232 se obtiene 233 que, sumados a 66879740354082 serían 66879740354315

Dividimos ambos números y éste sí resulta ser divisible por 1093:

66879740354315 / 1093 = 61189149455

- - - - - - - - - - - -

b) 1x9= 9 ;10x8= 80 ;100x7= 700 ;1000x8= 8000 ;163x3= 489 ;537x3= 1611 ;998x2= 1996 ;
143x1= 143

Sumamos y obtenemos 13028

1x8= 8 ;10x2= 20 ;100x0= 0 ;1000x3= 3000 ;163x1= 163

Se obtiene 3191 que es menor que 3279 (1093x3) y mayor que 2186 (1093x2). Si restamos 3279 – 3191 obtenemos 88 que añadidos a 12338789 nos daría 12338877 el cual sí es múltiplo de 1093:

12338877 / 1093 = 11289

Como vemos, el criterio de divisibilidad del 1093 tampoco parece tener fallos.

- - - - - - - - - - - -

Es correcto. Las series son las potencias de 10 módulo S. Vale aunque S no sea primo.

Saludos.

¡Exacto! y gracias. El método del que hablo me sirve únicamente para hallar esos mismos términos con simples operaciones de multiplicación y resta, que es lo que se me ocurre que podría facilitar el proceso de factorización de números enteros, sobre todo aquellos de muchísimas cifras, ya que no implica dividir en ningún caso. ¡Yo es que no tenía ni idea de que estas series que se repiten cíclicamente, servían como regla de divisibilidad! Pero aún me queda la duda de si el hecho de poder obtener las potencias de 10 mod(x) a través de operaciones tan sencillas pueda ser interesante; me intriga la posibilidad de que incluir este proceso en un algoritmo de factorización de números enteros pueda ayudar a mejorar los tiempos o si implicaría resultados más fiables en la identificación de nuevos números primos. Gracias de nuevo por tu respuesta.

Es muy difícil mejorar los algoritmos de factorización de enteros porque es un problema muy estudiado, ya que muchos métodos criptográficos se basan en la dificultad de factorizar números grandes. Si se encontrara un algoritmo de factorización eficiente sería tremendo, la seguridad informática que ahora tenemos se caería.

Pero entonces, por lo que puedo deducir (corrígeme si me equivoco), de ser efectivo el método con el que he obtenido estos resultados, ¿al menos sí podría ayudar a simplificar o al menos resolvería en cierta forma el cálculo de la exponenciación modular?. Por lo que he podido comprobar, parece que funciona en los casos en los que la raíz primitiva del módulo de x es 10 ( 10^e mod(x) ) porque no me ha sido necesario resolver primero la potencia (por ejemplo) 10^271 para obtener el resultado de 10^271 mod 1093, a saber, 470. Se que aún tengo mucho que estudiar y poner a prueba detenidamente pero, como he dicho antes, muchísimas gracias Pedro Pablo, es un placer poder compartir y a la vez aprender, sobre todo aprender. Un saludo.

Claro, no hace falta calcular explícitamente las potencias, es más fácil generar la serie recursivamente, por ejemplo:

10^271 = 10 * 10^270 = 10 * 47 (mod 1093) = 470

Estúdiate la aritmética modular.

Un saludo.

No, eso está claro. Aquí lo único que hemos hecho ha sido averiguar el anterior número de la serie mediante A^(e-1)mod(n) , ¿no?. Para luego, a este resultado, multiplicarle A y obtener el siguiente en la serie, que es el que andábamos buscando. Pero, en realidad no hemos solucionado nada, seguimos teniendo que pasar por resolver una potencia con la misma base y casi el mismo exponente y una misma operación módulo para llegar al resultado.

Entiendo que no me he explicado bien; yo hablaba de transformar la expresión A^e mod(n)=Z a una de tipo N*x+y=A*Z mediante un método que, como digo, aún he de estudiar en mayor profundidad y poner a prueba detenidamente en cada uno de los casos para según que valores de A, o de N, y que es en sí mismo el objeto de todo este asunto.

Tengo un montón de nuevas preguntas, y ahí está la casi total seguridad de que no me lleve finalmente a nada que pueda aplicarse, o que si quiera trascienda lo más mínimo, pero a mi lo que me cabe esperar de todo esto es aprender así que seguiré tu consejo documentándome para abordar mejor el problema en su base.

Un saludo.