Cel mai bun răspuns
În expresia de la 1! la 200 !, toate numerele vor fi divizibile cu 14, cu excepția primilor 6 termeni. De ce?
- 14 = 2 \ ori 7
- Acum 7 nu este până la 6 !.
Deci, 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 ( Răspuns )
Răspuns
Există multe întrebări de acest fel pe Quora. În general, nu necesită nicio înțelegere profundă pentru a stăpâni.
Principalul lucru de reținut este că exponențierea este ciclică sub un modul. Trebuie doar să ne dăm seama cât de mare este ciclul respectiv, ceea ce se poate face prin simpla încercare.
2 ^ 1 = 2 2 ^ 2 = 4 2 ^ 3 = 8 2 ^ 4 = 16 ( în acest moment am putea observa că 16 = -1 modul 17 și opriți, dar să continuăm.) 2 ^ 5 = 32 = 15 2 ^ 6 = 2 * 15 = 30 = 13 2 ^ 7 = 2 * 13 = 26 = 9 2 ^ 8 = 2 * 9 = 18 = 1
Acum celălalt fapt de care avem nevoie este că x ^ {ab + c} = (x ^ a) ^ bx ^ c. Deoarece 2017 = 8 * 252 + 1, 2 ^ {2017} = (2 ^ 8) ^ {252} * 2. Folosind calculul de mai sus, 2 ^ 8 = 1 mod 17, deci 2 ^ {2017} = 1 ^ {252} * 2 = 2 mod 17.
Apoi adăugăm unul pentru a obține rezultatul final, care este 3.
Să presupunem că dorim doar să calculăm răspunsul „direct”. Este fezabil să faceți acest lucru cu quadrarea repetată — ceea ce este util în aplicații în care modulul ar putea fi suficient de mare încât să nu finalizăm nici măcar un singur ciclu. Baza acestei tehnici este că x ^ {2k} = (x ^ k) ^ 2. Reprezentați exponentul în binar. De fiecare dată când cifra binară din stânga este una, vom înmulți cu x. Apoi, ori de câte ori trecem la următoarea cifră, pătrat valoarea curentă.
În acest caz 2017 = 11111100001b. Luând fiecare cifră pe rând (și începând cu valoarea inițială „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
Acest lucru este de acord cu calculul nostru anterior că 2 ^ {2017} = 2 mod 17.