[Risolto] Calcolare le ultime due cifre

Lo farei con piacere se solo avessi la minima idea di come c'entri il totiens coi resti modulo 100.
Se scrivi un commento con "@exProf" nella prima linea e nella seconda un link agli appunti del tuo insegnante che "vuole che usiamo la funzione di Eulero", così vedo COME vuole che la usiate, poi cercherò di capirlo e di spiegarlo a te su quest'esempio.

------------------------------
AGGIORNAMENTO delle 17h 30'
@Daniele11000
Ok, ho capito che devo cercarmi e capire quel Teorema di Eulero-Fermat ("Corollario 2.7", pag. 7) sui numeri primi e poi vedere come lo si applica al problema 12 (che è lo svolgimento precedente a quello che tu hai riprodotto). Intanto ti anticipo una cosa che ho osservato al volo.
Nello "Svolgimento Esercizio 12" a pag. 9 c'è scritto "Il problema è che non sappiamo calcolare
direttamente φ(100).": ma come! Basta contare: in una precedente risposta te li ho elencati i primi minori di 100, mi pare.
Quando avrò una qualsiasi conclusione, anche negativa, ti scriverò un secondo aggiornamento.
Saluti, per ora.

------------------------------

AGGIORNAMENTO delle 19h
@Daniele11000
Ma è una cavolata! Si tratta solo di un riferimento all'indietro che t'è sfuggito.
Lo "Svolgimento Esercizio 12" si basa sulle conclusioni successive ai corollarii 2.7 e 2.8 con la "Osservazione 2.9" che sta subito dopo.
* φ(100) = 40
* divisori(40) = {1, 2, 4, 5, 8, 10, 20, 40}
* {k, 7^k mod 100} in {{0, 1}, {1, 7}, {2, 49}, {3, 43}, {4, 1}, {5, 7}, {6, 49}, {7, 43}, ...}
cioè il periodo delle potenze d'interesse è un divisore del totiens di cento (Lo so che Sylvester aveva scritto "totient", ma ho sempre pensato che fu un lapsus: lui il Latino lo sapeva e aveva pensato "totiens", ispirandosi alla massima "quotiens doces, totiens disce". Non me lo dire, lo so da me che questa è superbia!).
------------------------------
CONCLUSIONI (pag. 7)
... consentono di effettuare efficacemente la riduzione modulo n della potenza di un intero,
SEMPRE CHE la base della potenza sia relativamente prima con "n":
per ridurre modulo "n" (cioè: per calcolare il resto della divisione per "n") la potenza "a^e" del numero "a" relativamente primo ad "n" basta
1) ridurre la base "a" modulo "n";
2) ridurre l'esponente "e" modulo "φ(n)";
3) infine, calcolare direttamente il resto della divisione della risultante potenza
per "n".
---------------
Poi la "Osservazione 2.9" dice che nel passo 2 si può sostituire a "φ(n)" il periodo delle potenze di "a", se è minore di "φ(n)".
------------------------------
"Svolgimento Esercizio 12"
Ultime due cifre decimali ("07") di
* 5607^38402475948201
---------------
0) SEMPRE CHE
* MCD(38402475948201, 5607) =
= MCD(5607, 38402475948201 mod 5607 = 624) =
= MCD(624, 5607 mod 624 = 615) =
= MCD(615, 624 mod 615 = 9) =
= MCD(9, 615 mod 9 = 3) = 3
Non va bene, la procedura non è applicabile.
Però gli appunti la applicano alla base ridotta, dopo il passo 1, perché
* MCD(38402475948201, 7) = 1
---------------
1) 5607 mod 100 = 7
---------------
2) d = periodo[7^k mod 100] = 4
* 38402475948201 mod 4 = 1
---------------
3) risultante potenza = 7^1 = 7
* calcolare direttamente ...: 7 mod 100 = 7
---------------
CONCLUSIONE
* 5607^38402475948201 mod 100 = 7
* Ultime due cifre decimali = "07"
Saluti e alla prossima.