Matemáticas de cuchufleta

11.9.06

cuéntame

¿Cuántos divisores tiene un número natural dado? Primero, observemos que si un número n divide a otro número m, entonces tambiénel opuesto -n del número n divide a m, así que nos basta contar los divisores positivos y, si gusta (no, no le estoy invitando a comer) multiplicar el resultado por dos para tener en cuenta los divisores positivos y negativos. Empecemos con el caso más simple en el que el número es primo: ¿cuántos divisores tiene un número primo p? ¡pues dos!...¿cuántos quiere que tenga? uno es el uno (valga la redundancia) y el otro el propio p. Ahora pongámoslo un poco más difícil: ¿cuántos divisores tiene un producto de dos primos distintos p y q? En este caso la respuesta es 4: los 4 divisores de pq son 1,p,q y pq. Ahora supondrá usted que voy a tratar el caso de un producto de tres primos, ya casi me lo puedo imaginar cerrando el navegador y lanzando improperios contra mi humilde persona. ¡¡¡Pues NO!!!, pasaremos a analizar de un golpe el caso general en el que el número se descompone como producto de primos en la forma m=p1i1 ... pnin. Los divisores de dicho número se descompondrán a su vez, como ocurre con todos los números naturales, como producto de primos. En dicha descomposición el exponente del primo p1 no puede pasar de i1, pues si en en un divisor de m el exponente de p1 sobrepasara i1, entonces al ser m igual a ese divisor multiplicado por algo, el exponente de p1 en m también sobrepasaría i1, pero dicho exponente es exactamente i1, sin que sobre ni falte nada, así que no puede ocurrir que el exponente de p1 en dicho divisor exceda i1. Análogamente se demuestra que el exponente de p2 no puede sobrepasar i2 y así sucesivamente hasta el final. Es decir, que los divisores de m son de la forma p1j1 ... pnjn donde j1 está entre 0 e i1, j2 está entre 0 e i2, etcétera, etcétera, y finalmente, después de unos cuantos etcéteras, jn está entre 0 e in. ¿Y cuántas formas posibles hay de elegir los "jotas"? Hay i1+1 formas de elegir j1, hay i2+1 formas de elegir j2 ... hay in+1 formas de elegir jn, y el número de formas de elegir conjuntamente los "jotas" es el producto de dichas cantidades, es decir, (i1+1)(i2+1)...(in+1), que es el número de divisores que estamos buscando.
Veamos un ejemplo: ¿cuántos divisores tiene 320? Como 320=26.5, en este caso el número de divisores es 7.2=14 Dichos divisores son de la forma 2i.5j con i entre 0 y 6 y j entre 0 y 1. Ahora, con un poco de paciencia, se puede decir cuáles son los divisores: 1 (20.50),2 (21.50),4 (22.50),8 (23.50),16 (24.50),32 (25.50),64 (26.50),5 (20.51),10 (21.51),20 (22.51),40 (23.51),80 (24.51),160 (25.51) y 320 (26.51).
Para dar una de cal y otra de arena hay que reconocer que el problema de descomponer un número en producto de primos no es sencillo de resolver para números grandes (por "grandes" quiero decir realmente grandes, del orden de varios centenares de dígitos o cuando menos del orden de mis deudas con el banco) y, hoy por hoy, no se conoce ningún algoritmo que permita factorizar un número sin emplear una cantidad indecentemente grande de tiempo.
Moraleja: la bonita fórmula que hemos encontrado para la cantidad de divisores de un número, en la práctica no mejora mucho el método de ir probando con todos los números menores que él e ir contando cuántos lo dividen, ¿pero y lo que nos hemos divertido?
Por último, un ejercicio para que no se aburran: ¿cuántos divisores tiene el número 68992000?

2 Comments:

  • porner las respuestas

    By Anonymous Anónimo, at 7:52 p. m.  

  • Gracias por el algoritmo de parte de un Ingeniero Informático en proyecto !
    Ya se sabe, mates e informatica son primos hermanos !

    By Anonymous Anónimo, at 9:19 p. m.  

Publicar un comentario en la entrada

<< Home


 
Contigo han caí­do ya   pardillos que han visitado este blog.