Migliore risposta
Nellespressione da 1! a 200!, tutti i numeri saranno divisibili per 14 tranne i primi 6 termini. Perché?
- 14 = 2 \ volte 7
- Ora 7 non arriva a 6 !.
Quindi, 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 ( risposta )
Risposta
Ci sono molte domande di questo tipo su Quora. Generalmente non richiedono alcuna conoscenza approfondita per padroneggiarli.
La cosa principale da ricordare è che lelevazione a potenza è ciclica sotto un modulo. Dobbiamo solo capire quanto è grande quel ciclo, che può essere fatto semplicemente provandolo.
2 ^ 1 = 2 2 ^ 2 = 4 2 ^ 3 = 8 2 ^ 4 = 16 ( a questo punto potremmo notare che 16 = -1 modulo 17 e fermiamoci, ma continuiamo.) 2 ^ 5 = 32 = 15 2 ^ 6 = 2 * 15 = 30 = 13 2 ^ 7 = 2 * 13 = 26 = 9 2 ^ 8 = 2 * 9 = 18 = 1
Ora laltro fatto di cui abbiamo bisogno è che x ^ {ab + c} = (x ^ a) ^ bx ^ c. Perché 2017 = 8 * 252 + 1, 2 ^ {2017} = (2 ^ 8) ^ {252} * 2. Utilizzando il calcolo sopra, 2 ^ 8 = 1 mod 17, quindi 2 ^ {2017} = 1 ^ {252} * 2 = 2 mod 17.
Quindi ne aggiungiamo uno per ottenere il risultato finale, che è 3.
Supponiamo di voler solo calcolare la risposta “direttamente”. È possibile farlo con squadratura ripetuta — che è utile nelle applicazioni in cui il modulo potrebbe essere abbastanza grande da non completare nemmeno un singolo ciclo. La base di questa tecnica è che x ^ {2k} = (x ^ k) ^ 2. Rappresenta lesponente in binario. Ogni volta che la cifra binaria più a sinistra è una, la moltiplicheremo per x. Quindi ogni volta che andiamo alla cifra successiva, piazza il valore corrente.
In questo caso 2017 = 11111100001b. Prendendo ciascuna cifra a turno (e iniziando dal valore iniziale “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
Ciò concorda con il nostro calcolo precedente secondo cui 2 ^ {2017} = 2 mod 17.