Migliore risposta
Per prima cosa, dobbiamo guardare il modulo (o il numero che stiamo cercando di dividere per). In questo caso, è 1818. Quindi, inserisci 1818 nella funzione totiente di Eulero , per ottenere ϕ (18) ϕ (18) In particolare, per tutti gli interi nn, abbiamo
ϕ (n) = n∏p | n (1−1p), ϕ (n) = n∏p | n (1−1p),
dove il prodotto attraversa tutti i univoci fattori primi di nn. Quindi, in questo caso,
ϕ (18) = (18) (1/2) (2/3) = 6.ϕ (18) = (18) (1/2) (2/3) = 6.
Ok, quindi il passaggio successivo è il teorema di Eulero , che dice che per qualsiasi altro intero aa che è relativamente primo a nn, abbiamo che aa alla potenza ϕ (n) ϕ (n) lascia un resto di 11 quando diviso per nn. Cioè,
aϕ (n) ≡1 (modn) .aϕ (n) ≡1 (modn).
Dato che 1717 è effettivamente primo rispetto al 1818, sappiamo che 176176 foglie un promemoria di 1. Ciò significa che possiamo continuare a dividere 176176 da 1720017200 senza modificare il resto. Un altro modo per dirlo è che 17 a qualsiasi potenza che “un multiplo di 6 lascerà un resto di 1. Quindi, alla fine, poiché 200 è 2 più di un multiplo di 6, sappiamo che
17200≡172 (mod18) .17200≡172 (mod18).
Questo rende il problema molto più semplice: ci siamo quasi! Una scorciatoia qui per concludere il problema è rendersi conto che 1717 lascia un resto di −1−1 quando diviso per 1818 (cioè 17≡ − 1 (mod18) 17≡ − 1 (mod18)), quindi 172172 lascia un resto di (- 1) 2 = 1. (- 1) 2 = 1.
Quindi la nostra risposta è 1 . La prossima volta che hai un problema con il resto di grande potenza, puoi usare questa bella soluzione generalizzata e suonare in modo intelligente allo stesso tempo :). Se non hai già visto la notazione modmod, vedi Aritmetica modulare .
PS Potresti aver sentito parlare di un caso speciale di questo teorema chiamato piccolo teorema di Fermat , che funziona quando hai un modulo che “è un numero primo (non è il caso qui). Il teorema dice che per ogni primo pp e intero aa che non è un multiplo di pp,
ap − 1≡1 (modp) .ap − 1≡1 (modp).
Questo è un trucco interessante ma è fondamentalmente lo stesso di quello “s sopra poiché ϕ (p) = p − 1ϕ (p) = p − 1 per ogni primo pp. Questi tipi di domande diventano davvero semplici se capisci il concetto di resto negativo . Cerca sempre di ridurre il dividendo a 1 o -1.
Rem [17 ^ 200/18] = Rem [(-1) ^ 200/18] = Rem [1/18] = 1
Risposta
Background importante necessario per risolvere il problema :
Sappiamo che il resto ottenuto quando r divide pq è il prodotto dei resti ottenuti quando r divide pe qseparatamente. Questo si chiama lemma sui resti. Puoi dimostrarlo con il teorema di divisione di Euclide.
La soluzione
17 quando divisa per 18 lascia il resto -1 (è conveniente lavorare con -1 rispetto a 17)
Applicando il lemma del resto a 17 × 17 × 17 … × 17 (2000 volte) quando diviso per 18 si otterrà il resto quando il i singoli resti vengono moltiplicati es. -1 × -1 .. × -1 (2000 volte) il resto è 1 \ blacksquare
Se fosse 17 elevato a un numero dispari, il resto sarebbe -1 o 17 .