domingo, 29 de abril de 2007

Potencias que se dividen

Enunciado

Para trabajar con números enteros que se dividen unos a otros, es conveniente pensar en los números factorizados, es decir, convertidos en un producto de números primos.

En el problema que nos ocupa, supongamos que tenemos un factor primo p que está en la descomposición en factores de a. Como a divide a b2, es evidente que p debe estar también en la descomposición de b (si no estuviese, tampoco podría estar en la de b2).

De forma similar, si q es un primo que está en la descomposición de b, como b2 divide a a3, y está claro que q estará en la descomposición de b2, también estará en la de a3, y por tanto no tendrá más remedio que estar también en a.

De esta forma, tanto a como b están formados por los mismos factores primos. Tal vez, elevados a potencias diferentes.

¿Qué les pasa a esas potencias de la factorización cuando elevamos los números a y b a una potencia? Pues lo que sucede es que se multiplica la potencia original por aquella a la que elevamos (recuerda que (pn)s = pn*s). Supongamos que uno de los primos p que forma parte de a está elevado a n, y que cuando forma parte de b, el mismo está elevado a m. En ese caso, el que a divida a b2, significa que n es menor o igual que 2m. De la misma forma, obtenemos que 2m es menor o igual que 3n, que 3n es menor o igual que 4m, que 4m es menor o igual que 5n, pero que, para al menos alguno de los primos, 5n es mayor que 6m, puesto que a5 no divide a b6.

Para trabajar con esas desigualdades, procuramos que uno de los números (m, por ejemplo) quede sin coeficiente, de forma que n/2 <= m, m <= 3n/2, 3n/4 <= m, m <= 5n/4 y m < 5n/6 (ojo, esta última desigualdad sólo es obligatoria para la potencia de algún primo de las descomposiciones).

Ahora bien, n/2 <= m y 3n/4 <= m son muy similares. En realidad, como 3n/4 siempre es mayor que n/2, sobra la primera desigualdad. De la misma forma, m <= 3n/2 y m <= 5n/4 son similares, pero en este caso, 5n/4 es menor que 3n/2, por lo que sobra también la primera desigualdad.

Si además, consideramos que al menos en un primo m < 5n/6 y que 5n/6 es menor que 5n/4, tendremos que un primo tendrá que cumplir que 3n/4 <= m < 5n/6, mientras que los demás podrán cumplir que 3n/4 <= m < 5n/4.

Probando con valores de n, vemos que (para el primo "especial") n tiene que ser por lo menos 4 (si es más pequeño, no hay enteros entre un valor y el otro). Y en ese caso, m tiene que valer 3 (se pide que busque un número, no que los encuentre todos, así que voy a por el más pequeño). Tomando el primo más pequeño, y suponiendo que no hay más primos en los números (de nuevo para que sean pequeños), podemos encontrar a = 24 = 16 y b = 23 = 8. Veamos que cumplen las condiciones:

a = 24 = 16 divide a 64 = 26 = b2

b2 = 26 = 64 divide a 4096 = 212 = a3

a3 = 212 = 4096 divide a 4096 = 212 = b4

b4 = 212 = 4096 divide a 1048576 = 220 = a5

pero a5 = 220 = 1048576 no divide a 262144 = 218 = b6

Se pueden encontrar muchos números como estos, multiplicando por otros primos (siempre que no sean 2), o encontrando otros valores para n y m, o usando otros primos de base.

Actualización

He corregido algunos valores erróneos