Números del cubo que terminan en el número X

Question

Tengamos algún número X al que llamaremos "final" o "sufijo". ¿Cómo encontrar el número que al cubo tiene sufijo o final igual a nuestro X? Creo que una buena pista es que este número X siempre termina con el número impar ( 1, 3, 7 ,9 )- no 5 aquí.

Por ejemplo, tenemos X = 123 y el número más pequeño que buscamos es : 947, porque 947^3 849278*123*.

¿Cómo solucionar este problema y otros similares? Chris

Answer 1

Nota: en base 10 cualquier dígito puede ser la última cifra de un cubo.

Trabaja primero con los dígitos menos significativos.

$0^3=0; 1^3=1; 2^3=8; 3^3=27; 4^3=64, 5^3=125; 6^3=216; 7^3=343; 8^3=512; 9^3=729$

Elija un dígito $a$ para que $a^3$ termina con el dígito que necesitas, este será único.

A continuación, utilice $(10b+a)^3 = ... +30a^2b+a^3$ para elegir $b$ para fijar los dos últimos dígitos, lo que puede no ser posible, y es posible que haya más de un $b$ para probar.

Entonces $(100c+10b+a)^3= ... 300c(10b+a)^2+(10b+a)^3$ se ocupará del dígito de las centenas... etc.

Explorar las distintas posibilidades le dará algunas pistas sobre lo que funciona y por qué.

Answer 2

Supongamos que su sufijo $X$ es coprima de $10$ porque eso simplifica la teoría (¡y parece que quieres hacerlo de todos modos!). Básicamente estás buscando una manera de encontrar una raíz cúbica de $X$ modulo $10^n$ , donde $n$ es el número de dígitos del sufijo. Si sabe cómo hacer potencias modulares rápidamente (véase el ejemplo siguiente), entonces el siguiente método sencillo funciona. La estructura del grupo de unidades del anillo $\mathbf{Z}/10^n\mathbf{Z}$ es bien conocido. Utilizamos la siguiente información al respecto: el exponente del grupo es $e=2^t5^{n-1}$ donde el parámetro $t=\max\{2,n-2\}.$ El exponente tiene la propiedad de que $X^e\equiv 1\pmod{10^n}$ para todos $X$ coprima a $10$ . Así que si podemos encontrar un número entero $d$ tal que $3d\equiv 1 \pmod e$ , entonces el resto de $Y=X^d$ modulo $10^n$ es la raíz cúbica deseada. Esto se deduce del cálculo $$Y^3\equiv X^{3d} \equiv X^{ke+1}=(X^e)^kX\equiv X \pmod{10^n},$$ donde $k$ es el número entero tal que $3d=ke+1$ . Encontrar un número $d$ es fácil, porque siempre $e+1$ o $2e+1$ será divisible por $3$ .

Como ejemplo, considere los casos $n=2$ y $n=3$ . Cuando $n=2$ obtenemos $e=20$ y observamos que $d=7$ funciona, porque $3\cdot7=21\equiv 1\pmod{20}.$ Probemos. Elija $X=03$ . Entonces $3^7=2187\equiv 87 \pmod{100},$ por lo que la teoría dice que $87$ debería funcionar. De hecho, $87^3=658503$ . Cuando $n=3$ entonces $e=100$ y podemos elegir $d=67$ como $3\cdot67=201\equiv 1\pmod{100}.$ Así, podemos recuperar su caso de ejemplo calculando el resto de $123^{67}$ modulo $1000$ . Por cuadratura repetida (todas las congruencias módulo $1000$ ) obtenemos que $123^2\equiv 129$ , $123^4\equiv129^2\equiv641$ , $\ldots$ , $123^{64}\equiv241$ Así que al final obtenemos $$123^{67}\equiv 123^{64+2+1}\equiv 123\cdot129\cdot241\equiv 947\pmod{1000},$$ rederivando su respuesta.

Es perfectamente posible también encontrar la raíz cúbica (modular) un dígito a la vez como se indica en la respuesta de Mark Bennet.