ippaso

Aritmetica modulare

In Matematica, Uncategorized on dicembre 12, 2009 at 11:26 am

In questo post introduciamo un “linguaggio” estremamente utile nella teoria dei numeri ed in particolare nello studio dei numeri primi. Consideriamo l’insieme dei numeri interi. Vogliamo in qualche modo “restringerlo” per concentrarci su insiemi più piccoli. Vogliamo cioè accomunare un po’ di numeri interi che hanno una qualche particolarità in comune. Ci sono tanti modi per fare questo. Il più utile e semplice da considerare, dato un intero n, è dato dalle classi di resto modulo n. Ovvero ci concentriamo sull’insieme di tutti i possibili resti della divisione di un intero per n. Questo insieme che si indica con Z_n sarà composto da n elementi: 0, 1, 2,…,n-2,n-1. Tutti i numeri interi vengono così ristretti a n numeri, nel senso che ogni numero intero m corrisponderà al resto della divisione di m per n che si indica con la scrittura m mod n (m modulo n è appunto l’operazione che prende come risultato il resto della divisione di m per n).

Esempio. Consideriamo Z_7, i suoi elementi sono i numeri 0, 1, 2, 3, 4, 5, 6. Infatti dividendo un numero qualunque per 7 abbiamo uno di questi resti. 14 mod 7 = 0, 23 mod 7 = 2, 9 mod 7=2, 13 mod 7 = 6, 49 mod 7 =0, -2 mod 7 = 5, 12 mod 7 = 5, ecc… Tutti i numeri interi possono essere identificati in Z_7 con uno tra 0, 1, 2, 3, 4, 5, 6 semplicemente attribuendogli come valore il risultato dell’operazione modulo 7.

Come visto nell’esempio, alcuni numeri hanno lo stesso resto nella divisione per un certo intero n e quindi sono “rappresentati” in Z_n dallo stesso numero. Due numeri interi a, b che hanno lo stesso risultato nell’operazione modulo n si dicono congrui modulo n e si scrive: Vuol dire che a mod n = b mod n, che si può dire in altre maniere equivalenti, per esempio a congruo b modulo n vuol dire che n divide a-b, oppure a=b+kn per qualche intero k. Per ulteriori informazioni e motivazioni potete guardare qui e qui.

Introduciamo ancora una funzione molto importante in teoria dei numeri: la funzione di Eulero f. Dato un numero nf(n) è il numero di interi compresi tra 1 e n-1 coprimi con n. Per esempio f(6)=2, in quanto solo 1 e 5 non hanno fattori comuni con 6, mentre 2,3 e 4 sì. Analogamente f(7)=6, f(9)=6, ecc…

Terminiamo con due teoremi fondamentali nella teoria dei numeri.

Teorema di Eulero. Dati due interi a,n coprimi tra loro, allora: Piccolo Teorema di Fermat. Dato un numero intero a e un numero primo p, allora:

  1. …un intero a e un numero primo p!
    p
    p
    p!

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: