Beste svaret
I uttrykket fra 1! til 200 !, vil alle tallene kunne deles med 14 bortsett fra de første 6 vilkårene. Hvorfor?
- 14 = 2 \ ganger 7
- Nå er 7 ikke der opptil 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 er mange spørsmål av denne typen på Quora. De krever vanligvis ikke noe dyp innsikt for å mestre.
Det primære å huske er at eksponentiering er syklisk under en modul. Vi må bare finne ut hvor stor den syklusen er, noe som kan gjøres ved å bare prøve den.
2 ^ 1 = 2 2 ^ 2 = 4 2 ^ 3 = 8 2 ^ 4 = 16 ( på dette punktet kunne vi merke oss at 16 = -1 modulo 17 og stopp, men la oss fortsette.) 2 ^ 5 = 32 = 15 2 ^ 6 = 2 * 15 = 30 = 13 2 ^ 7 = 2 * 13 = 26 = 9 2 ^ 8 = 2 * 9 = 18 = 1
Nå er det andre faktum vi trenger at x ^ {ab + c} = (x ^ a) ^ bx ^ c. Fordi 2017 = 8 * 252 + 1, 2 ^ {2017} = (2 ^ 8) ^ {252} * 2. Bruk beregningen ovenfor, 2 ^ 8 = 1 mod 17, så 2 ^ {2017} = 1 ^ {252} * 2 = 2 mod 17.
Så legger vi til en for å få det endelige resultatet, som er 3.
Anta at vi bare vil beregne svaret «direkte». Det er mulig å gjør dette med gjentatt kvadrat — som er nyttig i applikasjoner der modulen kan være stor nok til at vi ikke fullfører enda en syklus. Grunnlaget for denne teknikken er at x ^ {2k} = (x ^ k) ^ 2. Representere eksponenten i binær. Hver gang det binære sifferet til venstre er ett, multipliserer vi med x. Hver gang vi går videre til neste siffer, kvadrat nåværende verdi.
I dette tilfellet 2017 = 11111100001b. Tar hvert siffer etter tur (og begynner med startverdien «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
Dette stemmer overens med vår tidligere beregning at 2 ^ {2017} = 2 mod 17.