Mejor respuesta
¡En la expresión de 1! ¡a 200 !, todos los números serán divisibles por 14 excepto los primeros 6 términos. ¿Por qué?
- 14 = 2 \ times 7
- ¡Ahora 7 no es hasta 6 !.
Entonces, R [\ dfrac {1! + 2! + 3! +… .. + 200!} {14}]
= R [\ frac {(1! + 2! +…. + 6!) + (7! + 8! +… .. + 200! )} {14}]
= R [\ frac {(1! + 2! +…. + 6!)} {14}] + R [\ frac {(7! + 8! + … .. + 200!)} {14}]
= R [\ dfrac {(1 + 2 + 6 + 24 + 120 + 720)} {14}] + 0
= R [\ dfrac {873} {14}]
= 5 ( Responder )
Responder
Hay muchas preguntas de este tipo en Quora. Por lo general, no requieren ningún conocimiento profundo para dominarlos.
Lo principal que hay que recordar es que la potenciación es cíclica bajo un módulo. Solo tenemos que averiguar qué tan grande es ese ciclo, lo cual se puede hacer simplemente probándolo.
2 ^ 1 = 2 2 ^ 2 = 4 2 ^ 3 = 8 2 ^ 4 = 16 ( en este punto podríamos notar que 16 = -1 módulo 17 y parar, pero sigamos adelante.) 2 ^ 5 = 32 = 15 2 ^ 6 = 2 * 15 = 30 = 13 2 ^ 7 = 2 * 13 = 26 = 9 2 ^ 8 = 2 * 9 = 18 = 1
Ahora, el otro hecho que necesitamos es que x ^ {ab + c} = (x ^ a) ^ bx ^ c. Porque 2017 = 8 * 252 + 1, 2 ^ {2017} = (2 ^ 8) ^ {252} * 2. Usando el cálculo anterior, 2 ^ 8 = 1 mod 17, por lo que 2 ^ {2017} = 1 ^ {252} * 2 = 2 mod 17.
Luego agregamos uno para obtener el resultado final, que es 3.
Supongamos que solo queremos calcular la respuesta «directamente». Es factible Haga esto con cuadratura repetida — lo cual es útil en aplicaciones donde el módulo puede ser lo suficientemente grande como para que no completemos ni un solo ciclo. La base de esta técnica es que x ^ {2k} = (x ^ k) ^ 2. Representa el exponente en binario. Siempre que el dígito binario más a la izquierda sea uno, lo multiplicaremos por x. Luego, siempre que pasemos al siguiente dígito, eleve al cuadrado el valor actual.
En este caso 2017 = 11111100001b. Tomando cada dígito por turno (y comenzando con el valor inicial «1»):
1: (1 * 2) ^ 2 = 4 1: (4 * 2) ^ 2 = 13 mod 17 1: (13 * 2) ^ 2 = 9 ^ 2 = 13 mod 17 1: (13 * 2) ^ 2 = 13 1: (13 * 2) ^ 2 = 13 0: 13 ^ 2 = 16 0: 16 ^ 2 = 1 0: 1 ^ 2 = 1 0: 1 ^ 2 = 1 1: 1 * 2 = 2
Esto concuerda con nuestro cálculo anterior de que 2 ^ {2017} = 2 mod 17.