Aritmetica modulare
Ciao a tutti,
ho un dubbio riguardo un esercizio, dovrei calcolare 2015^(2015) mod 1000 per scoprire quali sono le ultime 3 cifre decimali. Per risolverlo ho prima calcolato il MCD(2015,1000) che chiaramente è diverso da 0 quindi ho escluso il teorema di Eurelo. Allora ho fattorizzato 1000, 8*125=1000 , e per il teorema cinese del resto so che 2015^(2015) è congruo a x sia mod 128 che mod 8. Poi ho calcolato e ho notato che 2015 è congruo a 7 mod 8 cioè è congruo a -1 mod 8 e questo va bene, quello che non riesco a calcolare è 2015^(2015) mod 125 o 15^(2015) mod 125 dato che non riesco ad applicare nessuna proprietà delle congruenze, il mio prof mi ha detto che questa congruenza viene 0 e difatti proseguendo i conti la soluzione finale mi viene . Ma come ha fatto a dirmi subito che 2015^(2015) è congruo a 0 mod 125?
ho un dubbio riguardo un esercizio, dovrei calcolare 2015^(2015) mod 1000 per scoprire quali sono le ultime 3 cifre decimali. Per risolverlo ho prima calcolato il MCD(2015,1000) che chiaramente è diverso da 0 quindi ho escluso il teorema di Eurelo. Allora ho fattorizzato 1000, 8*125=1000 , e per il teorema cinese del resto so che 2015^(2015) è congruo a x sia mod 128 che mod 8. Poi ho calcolato e ho notato che 2015 è congruo a 7 mod 8 cioè è congruo a -1 mod 8 e questo va bene, quello che non riesco a calcolare è 2015^(2015) mod 125 o 15^(2015) mod 125 dato che non riesco ad applicare nessuna proprietà delle congruenze, il mio prof mi ha detto che questa congruenza viene 0 e difatti proseguendo i conti la soluzione finale mi viene . Ma come ha fatto a dirmi subito che 2015^(2015) è congruo a 0 mod 125?
Risposte
Beh, $2015$ è multiplo di $5$.
Quindi $2015^3$ è multiplo di $125$. A maggior ragione, $2015^(2015)$ è multiplo di $125$
Quindi $2015^3$ è multiplo di $125$. A maggior ragione, $2015^(2015)$ è multiplo di $125$
Ah capito, era più facile del previsto! Grazie mille comunque
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo