Teorema di Eulero
Da Wikipedia, l'enciclopedia libera.
Questa voce è solo un abbozzo (stub). Se puoi, contribuisci adesso a migliorarla secondo le convenzioni di Wikipedia. Per l'elenco completo degli stub di matematica, vedi la relativa categoria.
- Questa pagina non riguarda la formula di Eulero né l'identità di Eulero
Nella teoria dei numeri, il teorema di Eulero (detto anche teorema di Fermat-Eulero) dice che se n è un'intero positivo ed a è coprimo rispetto ad n, allora:
- aφ(n) ≡ 1 (mod n)
Dove φ(n) indica la funzione phi di Eulero.
Questo teorema è una generalizzazione del Piccolo Teorema di Fermat, ed è ulteriormente generalizzato dal teorema di Carmichael.
Indice |
[modifica] Dimostrazione
Consideriamo l'insieme delle classi di resto ( modulo n ) degli interi positivi minori o uguali ad n e primi con n:
![S_1 = \left\{[m_1], [m_2], \dots, [m_{\phi(n)}]\right\}](../../../math/0/2/a/02a9b01df5359cc0648c6063eb609a60.png)
Se moltiplichiamo ogni elemento di S1 per a otterremo un secondo insieme,
![S_2 = \left\{[am_1], [am_2], \dots, [am_{\phi(n)}]\right\}](../../../math/e/0/d/e0d403f2b911896f4796d1beb35e9174.png)
.
Si ha che S1 coincide con S2. Per mostrare cio' e' sufficiente verificare che ogni elemento dell'insieme 
è congruente ad uno e un solo elemento dell'insieme 
. Osserviamo innanzi tutto che se per un certo 
intero fosse 
, dove 
non è primo con n, allora neanche ami sarebbe primo con n (infatti si avrebbe ami = d + kn e se d ed n hanno un divisore comune, questo deve dividere anche il primo membro). Poiché a è primo con n, ne segue che mi ha un divisore non banale in comune con n: un assurdo per come sono stati defniti gli mi. Ciò basta a mostrare che 
.
Per verificare l'uguaglianza bisogna mostrare che gli elementi di S2 sono distinti tra loro. Siano 
due interi compresi tra 1 e n. Dobbiamo provare che ami non è equivalente a amj. Se lo fossero si avrebbe a(mi − mj) | n ed essendo a primo con n avremmo (mi − mj) | n ovvero 
, assurdo. Pertanto S2 ha la stessa cardinalità di S1, ed essendo segue l'uguaglianza.
Abbiamo quindi mostrato che S1 = S2, pertanto il prodotto di tutti gli elementi di S1 è congruente al prodotto di tutti gli elementi di S2:
.
Poiché ogni mi è primo con n, possiamo dividere per il loro prodotto, ottenendo
.
[modifica] Dimostrazione con i gruppi
sappiamo che se G è il gruppo moltiplicativo abeliano (Z/nZ)*(informalmente l'insieme dei naturali inferiori di n e coprimi con esso legati dall'operazione binaria di moltiplicazione), allora φ(n) è la sua cardinalità; poiché a ed n sono coprimi allora segue che a appartiene a G e
- [a]φ(n) ≡ e
secondo le proposizioni dei gruppi ciclici; quindi poiché in G si ha che e è equivalente a 1 ne consegue la tesi
[modifica] Esempi di utilizzo
Il teorema può essere usato per ridurre facilmente grandi potenze in modulo n. Ad esempio, prendiamo in considerazione la ricerca dell'ultima cifra di 7222, vale a dire di 7222 (mod 10). 7 e 10 sono coprimi, e φ(10) = 4. Quindi dal teorema di Eulero segue che 74 ≡ 1 (mod 10), quindi 7222 ≡ 74·55 + 2 ≡ (74)55·72 ≡ 155·72 ≡ 49 ≡ 9 (mod 10).
In generale, nella riduzione di una potenza di a modulo n (dove a ed n sono coprimi), bisogna ottenere a elevato al suo esponente originario in modulo φ(n):
- se x ≡ y (mod φ(n)), allora ax ≡ ay (mod n).
[modifica] Voci correlate
- Funzione di Eulero
- Piccolo Teorema di Fermat
- Teorema di Carmichael
