Bästa svaret
I uttrycket från 1! till 200 !, kommer alla siffror att delas med 14 utom de första 6 termerna. Varför?
- 14 = 2 \ gånger 7
- Nu är 7 inte där upp till 6 !.
Så, 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 ( Svar )
Svar
Det finns många frågor av detta slag på Quora. De kräver i allmänhet ingen djup insikt för att bemästra.
Det primära att komma ihåg är att exponentiering är cyklisk under en modul. Vi måste bara ta reda på hur stor den cykeln är, vilket kan göras genom att bara testa den.
2 ^ 1 = 2 2 ^ 2 = 4 2 ^ 3 = 8 2 ^ 4 = 16 ( vid denna punkt kunde vi notera att 16 = -1 modulo 17 och stoppa, men låt oss fortsätta.) 2 ^ 5 = 32 = 15 2 ^ 6 = 2 * 15 = 30 = 13 2 ^ 7 = 2 * 13 = 26 = 9 2 ^ 8 = 2 * 9 = 18 = 1
Det andra faktum vi behöver är att x ^ {ab + c} = (x ^ a) ^ bx ^ c. Eftersom 2017 = 8 * 252 + 1, 2 ^ {2017} = (2 ^ 8) ^ {252} * 2. Med hjälp av beräkningen ovan, 2 ^ 8 = 1 mod 17, så 2 ^ {2017} = 1 ^ {252} * 2 = 2 mod 17.
Sedan lägger vi till en för att få slutresultatet, vilket är 3.
Antag att vi bara vill beräkna svaret ”direkt”. Det är möjligt att gör detta med upprepad kvadrering — vilket är användbart i applikationer där modulen kan vara tillräckligt stor för att vi inte klarar ens en enda cykel. Grunden för denna teknik är att x ^ {2k} = (x ^ k) ^ 2. Representera exponenten i binär. Varje gång den binära siffran längst till vänster är en kommer vi att multiplicera med x. Varje gång vi går vidare till nästa siffra, kvadrerar du det aktuella värdet.
I det här fallet 2017 = 11111100001b. Tar varje siffra i tur och ordning (och börjar med startvärdet ”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
Detta överensstämmer med vår tidigare beräkning att 2 ^ {2017} = 2 mod 17.