Teorema di Eulero - chiarimenti esempio

[duombo]

Ciao Ragazzi, studiando ho incontrato il teorema di Eulero che sembra abbastanza semplice, ma sul libro è riportato un esempio che non sono riuscito a capire, magari qualcuno di voi mi può aiutare. L'esempio è questo

Calcolare le ultime 2 cifre di \(\displaystyle 237^{250} \)
Si tratta di lavorare modulo 100. Ora, \(\displaystyle 237 \equiv 37(mod 100) \) e \(\displaystyle (37,100)=1 \). La funzione di eulero di 100 vale 40. In virtù del Teorema di Eulero \(\displaystyle 37^{40} \equiv 1 (mod 100) \).

fin qui è tutto chiaro

Allora \(\displaystyle 37^{242} = 37^{40*6+2}=(37^{40})^6*37^2=1369\equiv 69(mod100) \).

quello che non mi spiego, è questo pezzo, da dove viene fuori l'esponente 242?

Grazie a tutti in anticipo

[vict85]

In effetti dovrebbe essere \(250\). Cioè \(37^{250} = 37^{40\times 6 + 10} = (37^{40})^6\cdot 37^{10} = 37^{10}\) che è decisamente più difficile da calcolare del quadrato.

[duombo]

quindi potrebbe essere un errore sul libro?!

[duombo]

se prendo un altro esercizio in cui mi viene chiesto di trovare le ultime 2 cifre di \(\displaystyle 3^{950} \)
in base all'esempio precedente procedo in questo modo:
si tratta di trovare \(\displaystyle 3^{950} mod 100 \)
quindi: \(\displaystyle 3 \equiv 3 mod 100 \)
\(\displaystyle \varphi(100)=40 \)
il th di Eulero mi dice che: \(\displaystyle 3^{40}\equiv 1 mod 100 \)
quindi ottengo che \(\displaystyle 3^{40 \cdot 23} \cdot 3^{30}\equiv 1 \cdot 3^{30}\equiv x mod100 \)

alla fine dovrei risolvere \(\displaystyle 3^{30}\equiv x mod100 \)
ma essendo sempre \(\displaystyle 3^{30} \) un numero grande, come faccio?

grazie a tutti per l'aiuto

[Zero87]

"duombo":alla fine dovrei risolvere \(\displaystyle 3^{30}\equiv x mod100 \)
ma essendo sempre \(\displaystyle 3^{30} \) un numero grande, come faccio?

grazie a tutti per l'aiuto

L'avevo scritto non molto fa sempre in questa sezione. C'è un algoritmo semplice e pressoché sconosciuto (Lagrange???).

Sai che elevare al quadrato un numero - nell'aritmetica modulare - è una cosa "piuttosto" semplice perché elevi il resto modulo $n$ al quadrato (in genere piccolo e/o fattibile).

Ora
$30=15 \cdot 2=(14+1) \cdot 2=(7\cdot 2+1)\cdot 2=((6+1)\cdot 2+1)\cdot 2=(((3\cdot 2)+1)\cdot 2+1)\cdot 2=$
$=((((2+1)\cdot 2+1)\cdot 2+1)\cdot 2$

Questo è per l'esponente, ora sai che $a^(x+y)=a^x \cdot a^y$ e vale anche per l'aritmetica modulare.

Inizi con $3^2$ poi quello che ottieni lo moltiplichi per 3, poi elevi tutto al quadrato, poi quello che hai lo moltiplichi per 3, ...

Ok, l'ho spiegato in modo terribile, ci provo meglio.

- Hai l'esponente della potenza.
- Lo dividi sempre per 2 avendo cura del resto, come ho fatto io.
- Quando ottieni quell'espansione: in corrispondenza del $\cdot 2$ elevi al quadrato quello che hai, mentre in corrispondenza del $+1$ moltiplichi per la base. L'ordine da seguire è quello delle parentesi.

Il bello è che quando superi "n" lo sostituisci con il suo resto.

Ora, siccome lo chiedono in tanti e (tutte le volte) non lo so mai spiegare, può essere che non si trova da nessuna parte questo algoritmo (ce l'ho solo sugli appunti del corso di logica!)?

[duombo]

grazie mille Zero87, ora ho la suocera che chiama ma dopo pranzo provo ad applicare quello che hai scritto, grazie davvero tanto

[vict85]

I matematici lo studiano poco ma gli informatici lo usano spesso (su wiki per esempio). Da uno sguardo su Knuth sembra che fosse conosciuto sia da indiani che dagli arabi ben prima che Lagrange nascesse. Insomma ha valenza generale e può essere usato su qualsiasi gruppo.

[Zero87]

Grazie vict85... ecco perché non l'ho trovato da nessuna parte: ha un nome inglese e sulla wiki italiana non c'è.

[vict85]

Trovi qualcosa sulla storia anche qui http://mathoverflow.net/questions/10770 ... -algorithm

[duombo]

"Zero87":
... Ora, siccome lo chiedono in tanti e (tutte le volte) non lo so mai spiegare...

Invece ti sei spiegato benissimo, ho capito come fare, ed è anche piuttosto semplice, grazie mille di nuovo