Teorema di Eulero: dimostrazione

Il Teorema di Eulero (chiamato anche Teorema di Fermat-Eulero) dimostra che se è un intero positivo e un coprimo (interi che non hanno nessun divisore a eccezione di 1 e -1, se il loro massimo comune divisore è 1) rispetto a. In questo modo ?() ? 1(mod ()), come detto in precedenza. Poiché ogni [m (i)] è primo con, si possono moltiplicare entrambi i membri per l'inversa di ottenendo così che [^?() ? 1]. In questa guida vediamo insieme la dimostrazione del Teorema di Eulero.

Il teorema afferma che se è un numero intero positivo ed è coprimo di allora ^?() ? 1(mod ()) dove ?() indica la funzione totiente detta anche funzione di Eulero. La funzione di Eulero è una funzione definita come il numero degli interi compresi tra 1 e che sono comprimi con. A questa funzione gli è stato dato il nome di colui che la descrissi per la prima volta, ovvero il matematico Eulero.

Iniziamo ora a delineare la dimostrazione del teorema. Consideriamo l'insieme delle classi di resto aventi modulo degli interi positivi minori o uguali a e primi con: S1 = {[m1], [m2], ..., [m?()]}. Per verificare il teorema di Eulero bisogna dimostrare che tutti gli elementi dell'insieme S2 sono distinti tra loro. Quindi, siano i?j due numeri interi positivi compresi tra 1 e. Bisogna quindi provare che [*m (i)] non equivale a [*m (j)], in quanto se lo fossero si avrebbe {*[m (i)-m (j)]|} ed essendo a primo con avremmo {[m (i)-m (j)]|}, cioè [m (i) ?m (j)]. Quindi S2 ha la stessa cardinalità di S1 ed essendo S1?S2, segue che S1=S2. Pertanto il prodotto di ogni elemento di S1 è congruente con il prodotto di ogni elemento di S2.

In parole povere, se si moltiplica per ogni elemento di S1 si otterrà un secondo insieme: S2= {[*m1], [a*m2], ..., [*m?()]}. In questo modo si ottiene che S1 coincide con S2 e per mostrare questo basta semplicemente verificare che ogni elemento dell'insieme {[m1], [m2], ..., [m?()]} sia congruente a uno e un solo elemento dell'insieme {[*m1], [*m2], ..., [*m?()]}.

In conclusione, se per 0?i??, dove "i" è semplicemente un numero intero, fosse [*m (i) ? d], dove 0?d? non è primo con, allora neanche *m (i) sarebbe primo con, in quanto si avrebbe [*m (i)=d+k*n], e se "d" e avessero un divisore in comune, questo dovrebbe dividere anche il primo membro. Siccome è primo con, ne segue che "m (i)" ha un divisore in comune con. Questo è necessario a dimostrare che S1?S2.

Il Teorema di Eulero può essere utilizzato per ridurre grandi potenze in modulo e la sua dimostrazione aritmetica può essere applicata ai gruppi abeliani finiti. Nel gruppo abeliamo, l'operazione binaria (ovvero la funzione che richiede due argomenti dello stesso insieme X, per restituire un elemento di X) si avvalla della proprietà commutativa. Utilizzano questo teorema, non si ricorre a quello di Lagrange.