Piccolo Teorema di Fermat e teorema di Eulero Fermat

[giusibrunelli]

Buongiorno, sto studiando il Piccolo Teorema di Fermat e il Teorema di Eulero Fermat, dal punto di vista teorico i due teoremi sono piuttosto chiari, però non capisco come vengono applicati negli esercizi come questi:

1) Determinare il resto della divisione per 7 del numero $4526^236$
2)Calcolare le ultime due cifre di $237^242$
3)calcola il resto della divisione per 21 del numero $15^748374949292$
4)calcola il resto della divisione per 15 del numero $2^3394849204839$
Inoltre non mi è chiaro come si riduce un espressione come questa x$-=$ $32^511$(mod5)
Grazie in anticipo!

[Antimius]

Ti faccio vedere, ad esempio, come usarlo per l'esercizio numero 3: vuoi calcolare $15^{748374949292 } \mod 21$. La funzione di Eulero di $21$ è $\phi(21)=\phi(3)\phi(7)=2 \cdot 6 =12$. L'idea fondamentale è che, poiché $a^{\phi(n)} = 1 \mod n$ quando $(a,n)=1$, cerchiamo di calcolare il resto della divisione dell'esponente per $12$. Infatti se $748374949292 = 12h + r$, abbiamo che $a^{748374949292 }= a^{12 h + r} = (a^12)^h a^r = 1^h a^r=a^r \mod n$ e dunque l'espressione si semplifica notevolmente.

Adesso bisogna risolvere due problemi:
- $15$ non è coprimo con $21$
- Dobbiamo calcolare $748374949292 \mod 12$

Per il secondo problema, basta osservare che il numero è divisibile per $4$ ed è congruo a $2 \mod 3$. Allora, applicando il teorema cinese del resto: $$\begin{cases} x = 0 \mod 4 \\ x = 2 \mod 3 \end{cases} \implies x = 8 \mod 12$$

Per il primo, scomponiamo $15 = 5 \cdot 3$ e scriviamo $15^{748374949292} = 5^{748374949292 } \cdot 3^{748374949292 }$. Poiché $(5,21)=1$, possiamo applicare il teorema di Eulero e quindi possiamo semplificare l'espressione come ti ho spiegato su (dove $r=8$ l'abbiamo appena trovato): $5^{748374949292 } = 5^8 = 25^4 = 4^4 = 16^2 = (-5)^2 = 25 = 4 \mod 21$

Come facciamo a calcolare $3^{748374949292 } \mod 21$? Scomponiamo $21$ per liberarci del fattore che ci dà fastidio, e poi applichiamo il teorema cinese del resto.
Poiché $21 = 3 \cdot 7$, abbiamo che $3^{748374949292 } = 0 \mod 3$, mentre $3^{748374949292 } = c \mod 7$. Dobbiamo calcolare $c$: $\phi(7)=6$. Allora facciamo come abbiamo fatto prima e osserviamo che $748374949292 = 2 \mod 6$. Allora, applicando il teorema di eulero: $3^{748374949292 } = 3^{6h+2} = 3^2 = 9 = 2 \mod 7$

Per il teorema cinese del resto, $$\begin{cases} x = 0 \mod 3 \\ x = 2 \mod 7 \end{cases} \implies x = 9 \mod 21$$
Ma allora $3^{748374949292 } = 9 \mod 21$.

Adesso possiamo scrivere la soluzione dell'esercizio: $15^{748374949292 } = 4 \cdot 9 = 36 = 15 \mod 21$.

Probabilmente, se avessi scomposto da subito $21$ applicando il teorema cinese del resto all'inizio e poi il teorema di eulero alle due congruenze derivanti, sarebbe venuto un po' più corto di così. In ogni caso, spero sia chiaro quando applicare il teorema

[giusibrunelli]

Grazie mille, credo di aver capito come si applica il teorema.
Però potresti gentilmente mostrarmi anche il metodo più veloce applicando direttamente il teorema cinese dei resti? perchè questo metodo è molto lungo e difficile da memorizzare, temo che all'esame possa poi saltare qualche passaggio.
grazie ancora

[Antimius]

Calcoliamo $15^{748374949292} \mod 7$ e $\mod 3$ e poi applichiamo il teorema cinese del resto. Il secondo è nullo poiché è un multiplo di $3$, quindi dobbiamo calcolare solo il primo.
Poiché $\phi(7)=6$, calcoliamo $748374949292 \mod 6$ come prima e troviamo che è uguale a $2$. Allora, per il teorema di Eulero-Fermat: $15^{748374949292} = 15^{6h+2}= 15^2 = 1 \mod 7$
Allora per il teorema cinese del resto:
$$\begin{cases} x = 0 \mod 3 \\ x = 1 \mod 7 \end{cases} \implies x = 15 \mod 21$$
che è la soluzione cercata.

In effetti, scomponendo dall'inizio viene molto più veloce, perché ti liberi subito del $3$

[giusibrunelli]

ok perfetto! grazie ancora!
ultima domanda, questo metodo lo posso utilizzare per qualsiasi esercizio di questo tipo?
sto provando ad applicarlo all'esercizio numero 4 che ho scritto sopra ma non mi ritrovo con la soluzione data dal professore, potresti aiutarmi?

[Antimius]

Intanto semplifica la base $32^{511} = 2^{511} \mod 5$. Dopodiché, poiché $\phi(5)=4$ e $511 = 3 \mod 4$, per il teorema di Eulero-Fermat: $$2^{511} = 2^{4h+3} = 2^3 = 8 = 3 \mod 5$$

[giusibrunelli]

"giusibrunelli":Buongiorno, sto studiando il Piccolo Teorema di Fermat e il Teorema di Eulero Fermat, dal punto di vista teorico i due teoremi sono piuttosto chiari, però non capisco come vengono applicati negli esercizi come questi:

4)calcola il resto della divisione per 15 del numero $2^3394849204839$

Grazie in anticipo!

in realtà mi riferivo a questo esercizio potresti farmi vedere come si risolve con il teorema cinese dei resti?
in ogni caso grazie perchè anche l'altro non mi era chiaro

[Antimius]

Ops, avevo visto direttamente l'ultimo :p Comunque in quel caso non serve il teorema cinese del resto perché $2$ e $15$ sono coprimi, quindi puoi applicare direttamente il teorema di Eulero-Fermat. Osserva che $\phi(15) = 8$ e quindi devi calcolare $3394849204839 \mod 8$ che, se ho fatto bene i conti, è congruo a $7$.
Allora il risultato è $2^7= 2^4 \cdot 2^3 = 16 \cdot 8 = 1 \cdot 8 = 8$

[giusibrunelli]

ahh ok perfetto, quindi ricapitolando applico Eulero Fermat se i numeri sono co-primi, mentre se non sono coprimi scompongo in più cogruenze e applico il teorema di eulero fermat ad ognuna e poi con il teorema cinese dei resti trovo la x.
Grazie mille il tuo aiuto è stato fondamentale!!

[Antimius]

Esattamente