¿Hay alguna manera fácil de encontrar los dos últimos dígitos de [math] x ^ {y} [/ math], por ejemplo, [math] 2013 ^ {2013} [/ math]?

Answer 1

La función mod ‘a% b’ le da el resto de dividir a por b. Los dos últimos dígitos de x son x% 100.

Desea encontrar (2013 ^ 2013)% 100.

Esto es (2013 * 2013 * 2013 *…. * 2013)% 100.

Un teorema importante que se puede usar aquí es:

(a * b)% n = ((a% n) * (b * n))% n.

Esto significa que podemos usar la función mod después de cada multiplicación y obtener la misma respuesta que tendríamos al hacerlo una vez al final. Esto reduce el problema a encontrar 13 ^ 2013.

Para el resto de esta respuesta, suponga que cada multiplicación es realmente una multiplicación seguida de% 100.

Por ejemplo: 13 * 13 = 69.

que podemos escribir como 13 ^ 2 = 69.

Como 69 * 69 = 61, tenemos:

13 ^ 4 = 61

Continuando de esta manera:

13 ^ 8 = 21

13 ^ 16 = 41

13 ^ 32 = 81

13 ^ 64 = 61

En este punto vemos que habrá un patrón repetitivo. Podemos calcular rápidamente las potencias hasta 1024:

13 ^ 128 = 21

13 ^ 256 = 41

13 ^ 512 = 81

13 ^ 1024 = 61

Ahora podemos escribir 13 ^ 2013 usando los poderes que tenemos. Dado que el producto de dos potencias se encuentra sumando los exponentes, solo necesitamos encontrar exponentes que ya tenemos que suman hasta 2013.

2013 = 1024 + 512 + 256 + 128 + 64 + 16 + 8 + 4 + 1.

Lo que significa que x ^ 2013 = x ^ 1024 * x ^ 512 * x ^ 256 * x ^ 128 * x ^ 64 * x ^ 16 * x ^ 8 * x ^ 4 * x ^ 1.

Entonces 13 ^ 2013 = 61 * 81 * 41 * 21 * 61 * 41 * 21 ^ 61 * 13

= 53 .

Esta técnica se llama “exponenciación por cuadratura” y se usa para calcular exponentes ridículamente grandes rápidamente. (por ejemplo: en criptografía, donde el exponente puede tener cientos de dígitos). Sorprendentemente, funciona sin importar lo que defina como multiplicación, siempre que sea asociativo. Por lo tanto, puede usarlo para encontrar poderes de matrices, permutaciones o concatenación de cadenas. He usado esta técnica para descubrir los efectos de aplicar repetidamente una operación de Cubo de Rubik. De hecho, si definimos la multiplicación como suma, los poderes son realmente multiplicación y obtenemos un nuevo método de multiplicación.

Answer 2

Buena pregunta. Nos gustaría proyectar una perspectiva de informática aplicada sobre esto; otros ya se están ocupando de los enfoques teóricos de números generales, pero han sugerido con razón que 20 multiplicaciones pueden o no ser tan fáciles.

intenta encontrar periodicidad en los dígitos finales

Si. Vea cosas como {Orden de grupo – MathWorld}. Solo hay 100 posibles “últimos 2 dígitos”, así que después de un cierto número de veces (hasta 100), multiplicar por 2013 nos llevará de regreso a los “últimos 2 dígitos” con los que comenzamos, y luego el patrón se repetirá.

Específicamente en su situación, el ciclo tiene 20 números de largo. No estoy seguro si considera que 20 multiplicaciones son una manera fácil o no, pero después de conocer este hecho, resulta fácil calcular la respuesta. Entonces esos números son:

Las computadoras hacen muchas cosas rutinarias, que solían ser difíciles en su tedio (en lugar de difíciles en su desafío intelectual), mucho más fáciles. Si vamos a utilizar los problemas para evaluar a los estudiantes, es nuestra responsabilidad como educadores cumplir con este nuevo paradigma actualizando nuestros problemas, de modo que los estudiantes aún estén siendo desafiados.

Las características principales de nuestro script serán: solo los últimos 2 dígitos importan significa que todo funciona en el módulo 100; y 2013 es un número lo suficientemente grande como para implementar una rutina de exponenciación ligeramente optimizada.

var bin_exp_mod = función (base, exponente, divisor) {

resultado var = 1;
var cuadrado = divisor base%;

para (; exponente> 0; exponente >> = 1) {

if (exponente & 1) {
resultado * = cuadrado;
resultado% = divisor;
}

cuadrado * = cuadrado;
cuadrado% = divisor;
}

resultado de retorno;
};

Breve explicacion:

• podemos hacer cualquier número entero positivo (como el exponente) sumando potencias de 2, y desglosamos el exponente de esta manera
• cada vez que cuadramos la base, obtenemos base-al-poder-de-un-poder-de-2 (línea 13)
• Si necesitamos sumar esa potencia de 2 para formar el exponente, debemos multiplicar por ese cuadrado correspondiente (líneas 8 a 11)
• en cada etapa, solo necesitamos mantener el residuo (resto)

Para obtener la respuesta deseada, simplemente llamamos

bin_exp_mod(2013,2013,100);

pero podríamos usarlo con cualquier otro número entero que sea compatible con el sistema en el que lo ejecutamos.

Answer 3

Lo único que me viene a la mente después de leer esto es tratar de encontrar la periodicidad en los dígitos finales. No puede ser más largo que 100 números, porque en algún momento están obligados a comenzar a repetirse.

Específicamente en su situación, el ciclo tiene 20 números de largo. No estoy seguro si considera que 20 multiplicaciones son una manera fácil o no, pero después de conocer este hecho, resulta fácil calcular la respuesta. Entonces esos números son:

13, 69, 97, 61, 93, 9, 17, 21, 73, 49, 37, 81, 53, 89, 57, 41, 33, 29, 77, 1, 13 (comienza la repetición).

Habiendo aprendido que podemos decir que el módulo 20 de 2013 es 13, entonces deberíamos mirar el número 13 en esta lista, que es 53. Entonces debería ser la respuesta.

Answer 4

Usa el teorema de Euler

a ^ k = 1 (mod 100), donde k es la función totient de Euler, k = 40.

13 ^ 2013 es lo suficientemente bueno.

Entonces 13 ^ 40 = 1 (mod 100)

13 ^ 2000 = 1 (mod 100)

Entonces solo tienes que descubrir los dos últimos de 13 ^ 13, lo que te da 53.