Con unos y ceros

Enunciado

Es sencillo probar que 101 es primo. Averiguar que es el único de esta familia de números que es primo no es sencillo, y requiere mucha paciencia.

El siguiente de la familia es el 10101. Está claro que es múltiplo de 3, pero nos va a interesar su factorización completa. Es 3*7*13*37, que podemos escribir de varias formas, es decir, como 21*481, o como 39*259, o como 111*91. Esto nos será de mucha utilidad más adelante, para encontrar un patrón.

El siguiente de la familia es el 1010101. En realidad, este nos da una pauta interesante. Es como si apareciese dos veces el 101, y por eso está claro que 101*10001 = 1010101.

Siguiendo esa idea, también el 10101010101 = 101*100010001, y está claro de esa manera que todos los que tengan un número par de unos (e impar de ceros), es múltiplo de 101, por lo que no puede ser primo.

Sin embargo, el que hemos visto antes no sigue esa pauta, y, por ejemplo, el 101010101, que tiene 5 unos, no es divisible entre 101. Para los que tienen un número impar de unos y un número par de ceros, habrá que buscar algún otro truco.

Recordad que no podemos usar calculadoras (si lo habéis probado, os habréis dado cuenta de que no es fácilmente factorizable). Hay un factorizador de números grandes (usa Java) muy interesante en Factorización usando curvas elípticas. Pero en este concurso, evidentemente, no es posible usarlo, por lo que tendremos que fijarnos en las factorizaciones del 10101, para ver si alguna nos sirve. Evidentemente, no es divisible entre ninguno de los mismos primos, pero hay algo que llama la atención: la factorización 10101 = 111*91. Es como si un factor fuese el mismo número sin ceros. Esta idea fue lo que me animó a probar a dividir 101010101 entre 11111, llevándome la sorpresa de que es divisible, y resulta 9091.

Si probamos con números más grandes, confirmaremos nuestra suposición: 1010101010101 = 1111111*909091, y es (relativamente) fácil probar que, para un cierto h, el número formado por h conjuntos 90 y un 91 al final, multiplicado por un número formado por 2*h + 3 unos, nos da un número formado por h + 2 conjuntos de 10 y un 1 al final. La idea es, sobre todo, gráfica, ya que multiplicamos por un número formado por unos, es decir, se trata de una gran suma.

De todas formas es un problema muy difícil, ya que no es fácil dar con el patrón para una cantidad impar de unos. Confieso que tuve que buscarlo con ayuda de una calculadora (pero sí usé diferentes factorizaciones, hasta encontrar una que me llamó la atención).

Actualización a 4 de mayo de 2009

Como propone el comentarista anónimo, hay otra solución que hace evidente la factorización. La idea, en efecto, es escribir el número como suma de potencias de 10, es decir N = 1 + 10² + 10⁴ + ... + 10²ⁿ para cierto valor de n, que coincide con el número de ceros que tiene el número.

Para convertir esto en una única expresión se emplea un sistema de tipo telescópico, similar al que se usa en la conversión de un número decimal periódico en fracción. Así, 100N = 10² + 10⁴ + ... + 10²ⁿ + 10^{2n + 2}. Está claro que las dos expresiones tienen la mayoría de términos iguales, por lo que 100N - N = 10^{2n + 2} - 1.

Sacando factor común, tenemos que N = (10^{2n + 2} - 1)/99. Usando la factorización de una diferencia de cuadrados, N = (10^{n + 1} - 1)(10^{n + 1} + 1)/99.

Está claro que 10^{n + 1} - 1 es múltiplo de 99 si N es mayor que 1 e impar, y si N es par, 10^{n + 1} - 1 es múltiplo de 9 y 10^{n + 1} + 1 es múltiplo de 11, por lo que N será producto de dos números mayores que 1 en el caso N > 1, y ya sabemos que el 101 es primo, con lo que se tiene el resultado.