Euler contra Diderot

El pasado 28 de julio, apareció una entrada de Carlo Frabetti en la sección El Juego de La Ciencia del diario El País, que rezaba el mismo título: Euler contra Diderot. Su lectura es muy instructiva y me llamó la atención el problema que nos deja a los lectores. en determinado momento nos cuenta que Euler le dijo a Diderot: “Mi mujer escribió un número entero de menos de treinta cifras terminado en 2; yo borré el 2 del final y lo puse al principio, y el número resultante era el doble del que había escrito mi mujer. ¿Qué número escribió?”. Ahí arranca un interesante problema de la teoría de números. Independientemente de la originalidad o certeza de este reto, nos plantea un problema que podemos resolver con la herramientas de una teoría de números básica. Veámoslo.

Consideremos que el número que buscamos es $x$. Si lo expresamos en base decimal, será: $$d_n10^n +d_{n-1}10^{n-1}+\ldots+d_110+d_0=x.$$ El enunciado del problema nos dice que $d_0=2$, en consecuencia $x$ es par y se puede poner como $x=2y$. Además, por el enunciado, colocando el 2 en primer lugar (recordemos que seguimos teniendo las mismas $n+1$ cifras), resultará el doble del primero; es decir, $$2\cdot 10^n +d_{n}10^{n-1}+d_{n-1}10^{n-2}+\cdot+d_210+d_1=2x=4y (1)$$

Precisamente el hecho de que las cifras sean las mismas, salvo el orden, juega a nuestro favor. Por la propiedad de la divisibilidad del 3 y las congruencias $$2y=d_n10^n +d_{n-1}10^{n-1}+\ldots+d_110+2\equiv [d_n+d_{n-1}+\ldots+d_1+2](mod\, 3)$$ y $$4y=2\,10^n +d_{n}10^{n-1}+d_{n-1}*10^{n-2}+\ldots+d_210+d_1\equiv [2+d_n+d_{n-1}+…+d_1](mod\, 3).$$ Observemos que ambos términos de la congruencia son el mismo sumando $[d_n+d_{n-1}+\ldots+d_1+2]$, en consecuencia, $$2y\equiv 0(mod\, 3).$$

Ya tenemos la primera pista del número que buscamos: es un múltiplo de 6 que termina en 2.

Esta linea se puede continuar, aunque nos lleva a un camino peligroso. Me explico. Si consideramos el enunciado, $$2\,10^n +d_{n}10^{n-1}+d_{n-1}*10^{n-2}+\ldots+d_210+d_1=2(d_n10^n +d_{n-1}10^{n-1}+\ldots+d_110+2).$$

Si restamos nos dará: $$(2-2d_{n})\,10^n +(d_{n}-2d_{n-1})10^{n-1}+\ldots+(d_2-2d_1)10+(d_1-2d_0)=0$$

Lo que nos permite aventurar que nuestro número termina en 42, aún diría más, en 842, resultado que nos lo enseña la sucesión de diferencias: $d_1-2d_0=0;d_2-2d_1=0$. Sin embargo, debemos llevarnos cuidado, puesto que los números $d_i$ son dígitos entre 0 y 9, y en la siguiente,  $d_3-2d_2=0$, nos crea un problema un poco más difícil de entender, que lo utilizado hasta ahora. Dejemos esta línea, para afrontar otra más productiva y con la misma facilidad de entender. No sin antes, mostrar que si miramos al final de la recursión nos llevaría a $2-2d_{n}=0$, que nos indica que $d_n=1$ y, aún más, $d_{n-1}=0$. Así que esta línea nos da la pista de que el número que buscamos es de la forma: $$10\cdots\cdots\cdots\cdots 842.$$ Curioso, ¿verdad? No sabemos la cantidad de cifras, solo que es menor de 30 (por el enunciado).

Hasta aquí, a mis alumnos de Informática les sugiero que afronten el problema con una solución a fuerza bruta. Si utilizamos R y la librería de grandes enteros gmp, únicamente necesitamos un procedimiento de fuerza bruta que busque múltiplos de 6 que empiecen por 10 y terminen por 842, menores de 30 dígitos. Un problema finito.

Pero Euler no disponía de ordenador (salvo que su celebro fuese uno), con lo cual tenemos que seguir probando con la teoría de números, o en este caso un sencillo proceso de aritmética.  Sabemos (algoritmo de la división) que cualquier entero positivo, y nuestro $x$ en particular, que termine en 2 se puede escribir como: $x=10q+2.$ El enunciado no dice que el doble termina en el penúltimo dígito de $x$, luego $$x=10q+2\to 2x=2(10q+2)$$ Pero también, $$2x=2\cdot 10^{n}+q.$$

Veamos esto con un ejemplo. Supongamos el número $456872$, si quitamos el último 2 y lo pasamos al principio tendremos el $245687$. $456872=10 \cdot 45687+2$ y $245687=2 \cdot 10^{6}+45687$. En nuestro caso el equivalente a $q$ es $45687$.

Por tanto, de $2x=2(10q+2)$ y $2x=2\cdot 10^{n}+q$, obtenemos que $$20q+4=2\cdot 10^{n}+q$$ lo que nos lleva a $$2(10^n-2)=19q$$

Lo hemos escrito así para poder utilizar las propiedades de los números primos. En la ecuación diofántica que tratamos de resolver (como sabemos que tiene solución), es necesario que $19$ divida a $(10^n-2)$, por ser $19$ primo. Así que buscamos un número divisible por $19$ de la forma $(10^n-2)$. Esto es un problema de restos potenciales, estamos buscando resolver la ecuación $$10^a\equiv 2(mod\, 19).$$

De nuevo podemos utilizar R para obtener que el número $a$ que buscamos es $17$; $$10^{17}\equiv 2(mod\, 19).$$

En realidad, $$10^{17m}\equiv 2(mod\, 19),$$ para cualquier natural $m$ valdría, pero el enunciado nos dice que el número en cuestión es menor de 30 digítos, y $10^{17\cdot 2}$ supera los treinta. Por tanto la ecuación $$2(10^n-2)=19q$$ queda como $$2(10^{17}-2)=19q,$$ es $$2\cdot 99999999999999998=19q.$$

Dividiendo por 19 y multiplicando por 2, tendremos $$q=10526315789473684.$$ Pero recordad que el número que buscamos es $x=10q+2$, por tanto $$x=10q+2=105263157894736842.$$ Y ya está. Bonito número, ¿verdad? Observar que cumple las primeras propiedades que observamos: comienza por 10 y termina por 842, además de ser divisible por 6.