Aritmetica modulare

Questo sito utilizza cookie, anche di terze parti. Se vuoi saperne di più leggi la nostra Cookie Policy. Scorrendo questa pagina o cliccando qualunque suo elemento acconsenti all’uso dei cookie.I testi seguenti sono di proprietà dei rispettivi autori che ringraziamo per l'opportunità che ci danno di far conoscere gratuitamente a studenti , docenti e agli utenti del web i loro testi per sole finalità illustrative didattiche e scientifiche.

Le informazioni di medicina e salute contenute nel sito sono di natura generale ed a scopo puramente divulgativo e per questo motivo non possono sostituire in alcun caso il consiglio di un medico (ovvero un soggetto abilitato legalmente alla professione).

Aritmetica modulare

DAI “NUMERI DELL’OROLOGIO” ALL’ARITMETICA MODULARE

Tutti noi in genere, anziché dire “ ci vediamo oggi alle ore 15,00 ” diciamo più sbrigativamente “ci vediamo alle tre del pomeriggio”, 3 ore cioè dopo le ore 12,00 di mezzogiorno.

Se 6 ore dopo dobbiamo ricevere una telefonata il calcolo è per tutti istantaneo: alle nove di sera, ovvero alle 21,00. Ma se ci chiedono a bruciapelo che ora sarà 17 ore dopo, forse indugiamo a contare quante ore mancano alla mezzanotte e poi ad aggiungere la differenza da 17 e ancora più laborioso sarebbe il calcolo se dovessimo ad es. stabilire a che ora - ma prima ancora tra quanti giorni - presumibilmente brucerà una lampadina accesa in quel momento (senza più spegnerla) che dura 1000 ore.Un ulteriore problema si pone poi, se oggi è ad es.venerdì 20 gennaio 2006), nel determinare quale sarà il giorno della settimana e infine nel determinare la data di tale giorno.

L’algoritmo risolutivo è sempre lo stesso e non cambierebbe se dovessimo stabilire la 1000° cifra di un numero periodico noto (ad es. 2, 354721347213…) oppure calcolare a quale angolo del primo angolo giro corrisponde una rotazione (destrorsa a partire dal semiasse x positivo) di 1000°.

Se in quest’ultimo caso basta infatti, com’è noto, eseguire la divisione con resto (non cioè quella con la virgola) tra 1000° e il periodo di 360° corrispondente all’angolo giro, assumendo poi come risultato non il quoziente 2 (che è un numero puro) ma il resto 280°, altrettanto si farà nel primo caso dividendo 32 = 15+ 17 indifferentemente (in questo caso) per 12 o 24 e ottenendo resto 8;

così pure per la lampadina, dividendo 1015 per 24 si trova resto 7 e quoziente 42. Ciò significa che se la lampadina durasse effettivamente 1000 ore esatte si spegnerebbe alle 8 del mattino del 42° giorno successivo. Per stabilire il giorno della settimana basta poi attribuire a ciascun suo giorno (indipendentemente ora dal giorno di data) un numero progressivo, ad es. 1 al lunedì, 2 al martedì e così via sino ad arrivare a sabato 6 mentre alla domenica si fa corrispondere lo 0. Divendo questa volta per 7 – numero dei giorni della settimana – si perviene subito alla risposta.

Meno immediato è invece il calcolo della data, non avendo infatti i vari mesi lo stesso numero di giorni (tenuto conto anche dell’eventuale bisestile per febbraio) mentre per la cifra del numero periodico di nuovo non ci sono particolari difficoltà per cui lasciamoa chi legge il facile calcolo.

Passiamo ora dai singoli problemi alla teoria risolutiva.

In ciascuno dei casi esaminati escluso l’ultimo, quello della data (di cui diremo a parte più avanti), fondamentale è la nozione di modulo, cioè del periodo temporale o puramente numerico inerente al problema stesso. Per esso – e supponiamo che sia n il valore considerato - sempre si divide ed ad ogni numero naturale considerato viene associato il resto di tale divisione.

E’ allora facile convincersi che esso determina una suddivisione (o partizione) di tutto l’insieme N dei numeri naturali in n (infiniti) insiemi numerici che chiameremo classi di resto modulo n e per comodità indicheremo con i primi n numeri naturali in grassetto a partire da 0: 0, 1, 2, … n –1 oppure con scrittura più elaborata, ma che evidenzia anche il modulo: [0]n, [1]n, [2]n, …[n-1]n .

Ogni classe di resto modulo n viene in tal modo individuata mediante un numero, rappresentante della classe (quello scritto in parentesi) che ad essa appartiene e che per maggiore semplicità può sempre scegliersi, come si è fatto, tra i primi n numeri naturali a partire da zero (quindi da 0 a n-1),

così come al posto di 27/45 si preferisce scrivere semplificando, 3/5 (o il numero decimale 0,6).

Ciò significa che, tornando al modello dei giorni della settimana, risulta ad es.: [25]7 = [39]7 = [4]7

in quanto sia 25 che 39 divisi per 7 danno resto 4 o, il che è lo stesso, 39 –25 è multiplo di 7 e che quindi 39° e 25° giorno a partire da una certa data prefissata come lunedì sono entrambi giovedì.

Possiamo quindi dire, senza dover eseguire due volte la divisione per il modulo, che due numeri naturali a e b appartengono alla stessa classe di resto modulo n - e li diremo allora equivalenti modulo n, scrivendo a = b (mod n), in quanto rappresentanti di una stessa classe - se e solo se la loro differenza (per ora in valore assoluto) risulta multipla del modulo n, in modo ancora del tutto analogo a quanto si fa con le frazioni quando, per stabilire che a/b e a’/b’ sono equivalenti (individuano cioè lo stesso numero razionale) basta verificare la proporzione a/b =a’/b’ ó ab’ = a’b.

La nozione di equivalenza appena introdotta, così come quella tra frazioni, non va però intesa in matematica in senso generico, così come si fa nel linguaggio comune, e meno che mai come sinonimo di uguaglianza, come usualmente ma a rigore in modo improprio si fa con le frazioni. Essa sta infatti ad indicare che la relazione R così denominata è riflessiva (cioè xRx per ogni x considerato), simmetrica (xRy => yRx) e transitiva (xRy & yRz => xRz). Ciò si verifica facilmente (lasciamo la dimostrazione per esercizio) sia per le classi di resto che per le frazioni, ma se si vuole evitare di parlare di differenza in valore assoluto basta estendere l’equivalenza modulare a tutto Z. Essa diventa così una relazione tra interi relativi per cui potremo anche scrivere ad es. [-3]7 = [4]7 .

D’ora in poi per indicare l’insieme delle n classi di resto mod n useremo non a caso il simbolo Z n

che meglio evidenzia, come subito vedremo, le maggiori affinità strutturali con Z anziché con N.

L’insieme Z n non è infatti un semplice insieme di insiemi (le classi di equivalenza mod n) così come, continuando con il nostro confronto con le frazioni, non lo è l’insieme Q dei numeri razionali, intesi quest’ultimi come insiemi (o classi) a loro volta di frazioni equivalenti.

Come con le frazioni (anzi in modo ancora più semplice, lo vedremo subito) è infatti possibile introdurre tra le classi di resto le quattro operazioni verificando che per addizione e moltiplicazione continuano a valere le proprietà formali (associativa, commutativa e distributiva, esistenza di elementi neutri o annullatori rispetto ad esse) nonché l’esistenza dell’opposto per ogni elemento (in ogni caso) grazie al quale diventa sempre eseguibile la sottrazione e dell’inverso (in casi particolari oppure per ciascuna classe, quando n è un numero primo) grazie al quale può eseguirsi la divisione, che giustificano anche per esse l’appellativo di “numeri”, sia pur speciali.

Somma, differenza e prodotto come già in parte si è visto nei primi esempi parlando dei numeri dell’orologio, vengono introdotte nel modo più ovvio mediante somma, differenza e prodotto dei loro proprietà

[a]n + [b]n = [a+b]n [a]n - [b]n = [a - b]n [a]n · [b]n = [a · b]n

Così ad es. risulta:

[5]7 + [4]7 = [9]7 = [2]7 ; [2]7 - [6]7 = [- 4]7 = [3]7 ; [4]7 · [4]7 = [16]7 = [2]7

In base a tali definizioni le varie proprietà prima indicate risultano automaticamente verificate e così pure risulta che [1]n è elemento neutro della moltiplicazione e [0]n dell’addizione, nonchéelemento assorbente (annullatore) del prodotto e inoltre che – [a]n = [- a]n , cioè che l’opposto di una classe coincide con la classe dell’opposto del rappresentante.

Tale apparente semplicità non deve però trarre in inganno. Essendo i nostri oggetti non dei singoli numeri ma delle classi di numeri equivalenti, le definizioni delle diverse operazioni non devono dipendere dalla scelta dei loro rappresentanti, così come un patto elettorale tra due partiti per essere veramente tale deve prescindere dall’accordo finale dei pochi funzionari che lo firmano.

In altri termini chi ci assicura che, essendo ad es. [47]7 = [5]7 e [102]7 = [4]7 risulti poi [149]7 = [2]7 ? Analoghe considerazioni valgono ovviamente anche per le altre operazioni ma possono essere tralasciate per la sottrazione riconducibile per quanto prima osservato alla somma dell’opposto.

Occorre pertanto dimostrare che, in generale, se [a]n = [a’]n ed inoltre [b]n = [b’]n risulta pure:

[a + b]n = [a’ + b’]n ó (a+b) – (a’ +b’) = kn ; [a · b]n = [a’ · b’]n ó a · b – a’ · b’ = kn

Al solito lasciamo le facili dimostrazioni per esercizio. Osserviamo ancora per quanto riguarda il prodotto che ogniqualvolta n non è un numero primo si presenta un caso del tutto nuovo rispetto a quanto accade non solo in N e Z ma anche tra i numeri razionali o reali. Sia ad es. n = 12.

Risulta allora che: [2]12 · [6]12 = [12]12 = [3]12 · [4]12 = [12]12 = [0]12 . Esistono cioè delle classi non nulle che moltiplicate tra loro danno come risultato lo zero di Z12 . Proprio per questa strana loro proprietà tali elementi vengono detti divisori dello zero.

Passiamo ora a considerare l’ultima operazione, la divisione. E’ questa la più interessante in quanto, anziché intenderla come operazione inversa del prodotto (come avviene in N) può essere trasformata (come avviene in Q) nel prodotto del dividendo con l’inverso del divisore. Tale inverso, diversamente da quanto accade in Z (dove gli elementi invertibili sono solo 1 e –1), esiste sempre (per la dimostrazione si veda più avanti) a condizione che il numero da invertire sia primo con n; gli altri hanno infatti divisori dello zero tra i loro fattori e tali divisori chiaramente (solita dimostazione lasciata come es.) non sono invertibili. Se in particolare n è un numero primo p i divisori dello zero non sono presenti e quindi ogni elemento non nullo di Z p è invertibile. Ovviamente poi l’inverso dell’inverso è l’elemento iniziale. Così ad es. in Z 7, com’è facile verificare, 2 e 4; 3 e 5 sono uno l’inverso dell’altro mentre, essendo sempre 1 l’inverso di se stesso, anche 6 deve fare altrettanto. In Z 12 invece 2, 4, 3, 6, 8, 9, 10 non hanno inverso in quanto non primi con 12 mentre 5, 7, 11 hanno tutti per inverso se stessi; lo stesso accade in Z 24 mentre invece in Z10 sono inversi tra loro 3 e 7 e soltanto 9 è inverso di se stesso.

Concludiamo questo paragrafo introducendo alcuni termini di strutture fondamentali dell’algebra moderna aventi riferimento con le classi di resto:

Si dice gruppo un qualsiasi insieme G, finito o no, dotato di un’operazione binaria interna * sempre eseguibile in G e associativa (ma non necessariamente commutativa) dotato di elemento neutro u (g*u=u*g=g, "gÎG) e tale che ogni elemento di G ammette simmetrico g’: g*g’= g’*g =u. Risultano allora gruppi commutativi Z, Q, R (infiniti) e ogni Z n rispetto a + ma non N (mancano gli opposti).

Si dice invece campo un qualsiasi insieme K, finito o no, dotato di due operazioni (che indicheremo ora con + e · ) che sia gruppo commutativo rispetto a + e tale che pure K - {0} lo sia rispetto a ·, avendo indicato con 0 l’elemento neutro della prima operazione. Risultano allora campi gli insiemi Q, R (infiniti) e ogni Z p , ma solo se p è primo. Non è invece un campo Z (mancano gli inversi).

TEOREMA DI eulero – fermat (“piccolo” teorema di fermat)

Esso afferma che, per ogni numero p primo e per ogni x intero non suo multiplo vale:

x p = x (mod p) ó x p -1 = 1 (mod p) cioè: (x p – x) e (x p -1 – 1) sono multipli di p.

Dimostrazione:

Il modo più semplice per dimostrarlo consiste nel considerare il campo Z p = { 0, 1, … , p-1}

formato dalle p classi di resto modulo p che come sappiamo formano un campo rispetto alle due solite operazioni di somma e prodotto tra classi di resto modulo p in quanto, essendo p primo, ogni classe diversa dalla classe nulla ammette inverso: "x {(x Î Z p ) & (x ¹ 0) Þ $! x -1 [ x ×x –1 = 1] }.

Se ora consideriamo le p -1 classi non nulle 1, …, p-1 è chiaro che se x è una qualsiasi di esse esiste sempre un opportuno minimo esponente k ¹ 0 tale che: x k = 1 (mod p). Questo perché ogni volta che x ¹ 1 (se x = 1 vale ovviamente x 1 = 1, quindi k = 1) moltiplica due elementi distinti a e b, i risultati sono ancora distinti e così pure il prodotto di due classi non nulle e non unitarie è diverso da ciascuno dei suoi fattori, il tutto esattamente come vale per i numeri naturali :

1) "x ¹ 0: a ¹ b Þ a×x ¹ b×x 2) "a, x ¹ 0,1 : a×x ¹ a ¹ x

Se infatti per assurdo così non fosse, moltiplicando ambo i membri nel caso 1) per x –1 e nel caso 2) per x –1 o per a –1 si otterrebbe rispettivamente a = b e a = 1 o x = 1, contro l’ipotesi. (Si noti

che il risultato 0 è invece escluso in quanto, essendo p primo, mancano i divisori dello zero).

Si può pertanto affermare che moltiplicando le p -1 classi non nulle 1, …, p-1 per una qualsiasi di esse, x ¹ 1, si ottiene sempre una permutazione non identica degli elementi iniziali.

Ripetendo quindi successivamente più volte il prodotto, sempre per lo stesso x ¹ 1 prefissato, si otterranno via via permutazioni ogni volta diverse dalla precedente e quindi, prima o poi, la permutazione 1, …, p-1 dovrà ripetersi, al più dopo (p-1)! iterazioni, essendo tale il numero delle possibili diverse permutazioni su p –1 oggetti distinti.

Se però si considera non una qualsiasi classe 1, …, p-1 ma proprio la classe x per cui si moltiplica, dovendo il suo trasformato anch’esso cambiare ad ogni passaggio, dovrà coincidere con x stesso al più dopo p – 1 passaggi, quindi l’ x potrà moltiplicarsi per se stesso al più p-1 volte per potersi ripresentare, il che significa che al massimo si avrà proprio: x p = x (mod p) ó x p -1 = 1 (mod p).

Si può quindi affermare che l’equazione: x k = 1 (mod p) è verificata una prima volta con k < p-1.

A titolo di chiarimento si consideri ad es. il caso p = 7 e x =2 . Allora, come facilmente si verifica, si ottengono le seguenti successive tre trasformazioni:

1 2 3 4 5 6 risulta pertanto: 2 ×2 = 4; 4 ×2 = (2 ×2) ×2 = 1; 1 × 2 = (2 ×2 ×2) ×2 = 2

2 4 6 1 3 5 cioè: 2 3 = 1 ó 2 4 = 2

4 1 5 2 6 3

1 2 3 4 5 6

Se invece, sempre per p = 7, si considerasse x = 6, si avrebbero solo due trasformazioni:

1 2 3 4 5 6 si avrebbe cioè: 6 ×6 = 1; 1×6 = (6 ×6) ×6 = 6

6 5 4 3 2 1 cioè: 6 2 = 1 ó 6 3 = 6

1 2 3 4 5 6

(si noti che questo risultato non è casuale ma vale sempre per ogni p primo, ogniqualvolta cioè si considera x = p -1. Infatti vale allora: p -1 = -1 (mod p) Þ (p – 1) 2 = (- 1) 2 = 1 (mod p) ).

Per dimostrare il teorema basta allora verificare che k vale p-1 oppure è un divisore di p – 1, cioè:

p -1 = s × k, con s intero > 1, in quanto vale poi: (xs)k = x sk, quindi x p-1 = x sk =(x k)s =1s =1 (mod p).

Ciò è derivabile dalle proprietà generali dei gruppi finiti (vedi prima), particolari strutture algebriche simili ai campi ma con una sola operazione *(sempreassociativa ma in genere non commutativa) che per semplicità continueremo a chiamare moltiplicazione . Sappiamo che ogni campo Z n

– anche per n non primo - è un gruppo commutativo rispetto alla somma di classi di resto, con 0 elemento neutro e – x simmetrico di x; così pure G = {1, …, p-1} = Z p - {0} (p: primo) è un gruppo commutativo rispetto al prodotto di classi di resto, con 1 elemento neutro e x –1 simmetrico di x .

Se ora si considera nel gruppo G l’insieme: Px = {x, x2, …, xk } (dove k è, come sappiamo, il più piccolo intero positivo tale che xk = 1) di un qualsiasi suo elemento x, si dimostra facilmente che anche Px costituisce un gruppo rispetto al prodotto. Tale gruppo, essendo Px sottoinsieme di G (ed essendo l’operazione in Px la stessa che vale in G) è detto allora sottogruppo di G.

Affinché un sottinsieme H (non vuoto) di un gruppo G sia un suo sottogruppo basta e occorre che, contenendo due qualsiasi elementi contenga anche il prodotto del primo per l’inverso del secondo, come facilmente si verifica, tenuto conto che per essere sottogruppo deve contenere l’elemento neutro di G e inoltre tutti prodotti e tutti gli inversi dei suoi elementi.

Vale allora il fondamentale teorema Di Lagrange: In ogni gruppo finito G ogni suo sottogruppo H

ha sempre come ordine #H (numero dei suoi elementi) un divisore dell’ordine #G del gruppo.

Applicato al caso nostrorisulta: #H = #Px = k e #G = p-1. Dunque k divide p-1 C.V.D.

Vediamo ora la dimostrazione del teorema di Lagrange (per semplicità scriveremo ab anziché a*b).

Se si moltiplicano tutti gli elementi del sottogruppo H di G per un qualsiasi gÎG si trova un insieme, che indicheremo con Hg, detto laterale (destro). Hg è in genere diverso da gH laterale sinistro, a meno che G sia commutativo, come ad es.nel caso nostro. Limitandoci ancora a considerare i soli laterali destri (ma per i sinistri è la stessa cosa) valgono allora le seguenti proprietà:

1) ogni elemento g di G sta in un laterale di H e in uno soltanto

2) H è laterale di se stesso ed è l’unico sottogruppo tra i laterali di H (gli altri sono solo insiemi)

2) tutti i laterali hanno lo stesso ordine # H

La 1) è evidente nella sua prima parte: g sta certamente in Hg, visto che uÎH e quindi gu =g ÎHg.

Per la seconda parte chiediamoci quale relazione L intercorrre tra due elementi x e y che stanno in uno medesimo laterale L = Hg. Dovendo essere x = h1g ; y = h1g si avrà allora:

xLy ó x = h1g & y = h2g ó h1-1 x = g = h2-1 y ó x = h1 h2-1 y ó x y -1 = h1 h2-1 . Ciò significa che, risultando h1 h2-1 un certo elemento h di H, xLy ó x y -1 = h ó x y -1 ÎH (ma non x,y ÎH se L ¹ H).

E’ facile a questo punto dimostrare che la relazione L è una relazione di equivalenza in quanto:

è riflessiva: xLx ó x x -1 = u ÎH
è simmetrica: xLy ó x y -1 ÎH ó (x y -1 ) -1 =y x -1 Î H ó yLx
è transitiva xLy ó x y -1 = h ; yLz ó y z -1 = h’ Þ (x y -1 ) (y z -1 ) = x z -1 ÎH ó xLz

Essendo L una relazione di equivalenza, come già e avvenuto per le classi resto a partire da Z

(individute allora dal numero n del modulo e ciascuna contenente infiniti interi) essa permette di suddividere G in classi disgiunte (individuate ora da H) e non vuote, i diversi laterali di H;ciascun elemento di G sta quindi in una e una sola classe.

La 2) è evidente, osservato che H altro non è che un laterale Hh, essendo ciascun laterale L = Hg individuato oltre che dal sottogruppo H da un qualsiasi suo rappresentante g che gli appartiene.

H è poi l’unico laterale ad essere un sottogruppo in quanto è l’unico contenente l’elemento neutro u

Vale infine la 3) in quanto due qualsiasi elementi hg e h’g di ciascun laterale sono distinti essendo distinti i due elementi h e h’: hg ¹ h’g ó hgg-1 ¹ h’gg-1 ó h ¹ h’

In conclusione se m è il numero dei diversi laterali L di un qualsiasi sottogruppo H di G, essendo tutti tra loro disgiunti e tutti di ordine #H, vale chiaramente la formula #G = m #H, il che significa che l’ordine di H è un sottomultiplo dell’ordinedi G. Il teorema di Lagrange è così dimostrato.

In particolare se l’ordine #G è un numero primo G non posside sottogruppi propri.

CONSEGUENZE DEL TEOREMA E SUA ESTENSIONE AL CASO GENERALE.

FUNZIONE j DI EULERO.

Il piccolo teorema di Fermat può interpretarsi anche come un’equazione in Z p : x p – x = 0.

Tale equazione, essendo soddisfatta da tutti gli elementi di Z p - compreso lo 0, a differenza di

x p-1 – 1 = 0 - è quindi un’identità non banale, come lo sono invece quelle in N, Z,Q, R e C dove

gli unici polinomi sempre nulli sono quelli a coefficienti tutti nulli (o ad essi equivalenti, ad es. x=x).

Osserviamo ancora, più in generale, che in Z p anche molte equazioni impossibili in N, Z,Q, R (ma non in C, dove ogni equazione algebrica ammette sempre soluzioni, eventualmente multiple) ammettono soluzioni – innanzitutto, com’è evidente, tutte quelle del tipo: x k(p-1) – 1 = 0, con k intero qualsiasi – ma pure altre più interessanti, come ad es. : x 2 + 1 = 0 in Z 5 (2, 5) e in Z 13 (5, 8) ma non in Z 3, Z 7; x 3 + 2 = 0 in Z 3 (1, 2), Z 5 (2), Z 11 (4) ma non in Z 7 e così via.

Passiamo ora ad esaminare il caso in cui il numero p non è più primo. Dimostriamo che, nel caso in cui è sostituito dal prodotto p ×q di due primi, per ogni x primo con il prodotto p×q vale:

x (p-1)(q-1) = 1 (mod p×q) o , più in generale: x k (p-1)(q-1) = 1 (mod pq), k Î Z

Osservato subito che Z pq non è più un campo (p , q ,divisori dello zero, non hanno inverso), se si scrive il teorema nella forma x k(p-1) – 1 = 0 con k = q-1 e x k(q-1) – 1 = 0 con k = p-1, risulta:

1) "x ¹ mp: x(q-1)(p-1) = 1 (mod p) ó "x ¹ mp $ r tale che: x (q-1)(p-1) – 1 = r p

2) "x ¹ nq: x(q-1)(p-1) = 1 (mod q) ó "x ¹ nq $ s tale che: x (q-1)(p-1) – 1 = s q

Ne deriva rp = sq Þ (essendo p e q primi) $ t tale che: r = t q; s = t p da cui segue infine:

"x ¹ mp, nq (cioè primo con p, q): $ t tale che: x (q-1)(p-1) – 1 = t (pq) ó x(q-1)(p-1) = 1 (mod pq) C.V.D.

Anche questa generalizzazione del teorema può scriversi a sua volta nella forma col k generico:

"x Î N (primo con pq) : xk(q-1)(p-1) = 1 (mod pq), così come, generalizzando ulteriormente si ottiene:

"x Î N (primo con p1 p2 … pf) : xk(P1-1)(P2-1)…(Pf-1) = 1 (mod p1 p2 … pf).

Se invece - riprendendo il caso iniziale di due soli fattori – fosse p= q, in modo altrettanto semplice

Si potrebbe verificare che la formula va così modificata:

"x Î N (primo con p2) : xkp(p-1) = 1 (mod p2) e se p2 è sostituito da ph+1 dalla formula più generale:

"x Î N (primo con p h+1) : xk(p^h) (p-1) = 1 (mod p h+1) (dove p^h indica appunto p h+1).

E’ possibile a questo punto prendere in esame il caso più generale in assoluto, riassumente tutti i precedenti, in cui l’unico originario numero primo p viene sostituito da un qualsiasi numero naturale n = 2 F1 × 3 F2 × … × p Fn . Indicato allora con j (n) il numero dei numeri naturali minori di n e primi con n stesso (contando tra questi anche il numero 1, quindi j (1) = 1 ) vale allora la formula :

"x Î N (primo con n ) : x j (n) = 1 (mod n) . (formula di Eulero)

La funzione j(n) - detta quindi non a caso funzione di Eulero - riassumendo quanto detto in precedenza risulta avere le seguenti proprietà:

1) se n è primo, n = p, allora: j (p) = p-1 Così ad es. se n = 24 = 2 3× 3 risulta

2) se n = p h+1 allora: j (n) = p h(p-1) j (24) = j (23) ×j (3) = 2 2× j (2) ×j (3) = 2 2×1×2 = 8,

3) vale: j (n m) = j (n) j (m) quando essendo 8 i numeri :1, 5, 7, 11, 13, 17, 19, 23.

n ed m sono primi tra loro

La 1) è ovvia, contando tra i divisori primi con n numero primo tutti suoi predecessori, 1 compreso.

Per la 2) basta togliere dall’insieme A = {1, 2, 3, …, p h+1} l’insieme B = {p, 2p, 3p, …, pp,…, pp h} .

Vale infatti j (p h+1) = # (A –B) e # (A – B) è proprio p h+1 - p h = p h(p-1) = p h+1(1-1/p ).

Si noti che la 2) può anche scriversi : j (p h+1) = p h j (p) (formula che ricorda un po’ le derivate).

Per la 3) procediamo in modo analogo. Consideriamo ancora i numeri da escludere dall’insieme

A = {1, 2, 3, …, m·n} i cui termini formano una tabellina moltiplicativa di m righe ed n colonne.

Gli elementi formanti l’insieme B da escludere saranno allora innanzitutto quelli delle n - j (n) colonne che hanno in prima riga i divisori di n (tutti questi elementi diventano infatti divisori di nm)

e poi, tra le rimanenti colonne, i residui elementi da aggiungere a B saranno analogamente quelli che stanno sulle m - j (m) righe corrispondenti ai divisori di m. Si osservi che così facendo nessun escluso è contato due volte, essendo n ed m primi tra loro, per ipotesi. L’insieme B conterrà quindi

m [n - j (n)] + j (n) [m - j (m)] = mn - m j (n) + m j (n) - j (n) j (m) = mn - j (n) j (m) e pertanto

si avrà: j (n) j (m) = # (A – B ) = nm – [mn - j (n) j (m)] = j (n) j (m) C.V.D.

APPLICAZIONI DEL TEOREMA ALLA CRITTOGRAFIA

Il teorema di Eulero–Fermat, da sempre considerato come un esempio di matematica pura con scarse se non nulle applicazioni pratiche, per quanto pregevole esso sia, ha non da molto trovato un significativo impiego nel campo della moderna crittografia telematica “a chiave pubblica”.

Sia N = pq il prodotto di due numeri primi molto grandi, ad es. con più di 200 cifre decimali ciascuno. Se un destinatario D desidera ricevere pubblici messaggi criptati da un qualsiasi mittente MM, proponendosi che ciascuno possa inviarli ma nessuno, al di fuori di lui, possa decifrarli, può:

rendere di pubblico dominio il numero N ma non p e q
fare altrettanto con un secondo numero e , a sua scelta, che sia però primo con (p-1)(q-1)
calcolarsi, ma senza renderlo noto, il numero d tale che sia: d ×e = 1 (mod (p -1) ×(q -1)

A questo punto MM può inviare un qualsiasi numero M (ad es. uno alla volta i numeri M di codice ASCII corrispondenti a ciascuna lettera del suo messaggio) trasmettendo il seguente numero C:

C = Me (mod N). M è quindi, come si dice, il messaggio in chiaro, C il messaggio criptato.

Dopo aver ricevuto C , per risalire ad M, al destinatario D non resta che calcolare il seguente X:

X = Cd (mod N). Vale infatti X = M in quanto d×e =1 mod (p-1)(q-1) ó d×e= 1+n(p-1)(q-1) e quindi:

Xe = (Cd )e (mod N) = Cd e (mod N) ó Xe = C 1+k(p-1)(q-1) (mod N) = C 1 = C (mod N)

in quanto, per il teorema precedente, C k(p-1)(q-1) = 1(mod N).

Avendosi in definitiva C = Me (mod N) e così pure C = Me (mod N), X si trasforma quindi come M

e pertanto coincide con esso, essendo biunivoca la corrispondenza tra il numero M (sicuramente primo con N e minore di N stesso, visto che N >> M) e il suo trasformato C.

L’assoluta sicurezza del metodo è garantita dal fatto che la chiave decifrante d può calcolarsi solo se si conoscono p e q, ma la scomposizione di N in questi due enormi numeri primi richiede

– come si può facilmente calcolare – tempi superiori all’età dell’universo, anche supponendo di procedere utilizzando in parallelo miliardi dei più potenti computer oggi esistenti nel mondo.

ULTERIORI PROPRIETA’ E DIMOSTRAZIONI DELL’ARITMETICA MODULARE

Nei precedenti paragrafi abbiamo detto che ogni Z p è sempre un campo quando p è primo in quanto ogni suo elemento non nullo ammette inverso. Negli esempi proposti abbiamo infatti agevolmente calcolato tali inversi ma, come ben si comprende, occorre una dimostrazioni che ci assicuri della loro esistenza quale che sia p (grande cioè a piacere).

Come subito vedremo tale questione è strettamente connessa alla risoluzione con numeri interi dell’equazione: ax + by = c, la più celebre delle equazioni diofantee, così chiamata perché di essa (e altre ancora) si occupò il massimo algebrista dell’antica Grecia, Diofanto.

Se infatti ci chiediamo ad es. qual è in Z19 l’inverso di 9, ciò equivale a risolvere in Z19 l’equazione 9x =1 (mod 19) che in Z diventa (indicando per comodità con – y il multiplo del modulo risolvente):

9x –1 = -19y e quindi: 9 x +19 y = 1. Più in generale ogni equazione di primo grado mx = c in Z n qualunque sia n, anche non primo, si traduce nell’equazione diofantea: mx + n y = c e come sappiamo, quando m non è un numero primo esistono sicuramente in Z n dei divisori dello zero che entrano in gioco nell’equazione se e solo se m non è primo con n. In tali casi l’equazione modulare non può avere soluzioni (i divisori dello zero non hanno infatti inverso) e conseguentemente anche la corrispondente equazione diofantea. Così ad es. l’equazione modulare 3x = 7 (mod 12) risulta impossibile in quanto 3×4 = 0 (mod 12) e quindi non esistono in Z12 gli inversi di 3 e di 4 (e così pure di 2 e di 6, gli altri due divisori dello 0) altrimenti si avrebbe: 3-1 (3×4) = 3-1× 0 e quindi, usando la proprietà associativa e ricordando che 0 è sempre annulatore, ( 3-1 ×3)×4 = 0 cioè 1×4 = 4 = 0.

D’altra parte la corrispondente equazione diofantea dell’equazione modulare proposta: 3x +12y = 7 è chiaramente impossibile in quanto il suo 1° membro è comunque multiplo di 3 ma non così il 2°.

Invece l’equazione: 11x = 6 (mod 12) ammette soluzioni (l’inverso di 11, numero primo, esiste e vale anch’esso 11 poiché 11× 11= 121 cioè 1 mod 12) e quindi: 11×11x = 11×6, cioè x = 11×6 = 6

(in quanto 66 = 12×5 + 6, si noti che 11 si comporta da elemento neutro, ma solo in questo caso)

e quindi l’equazione:11x+12y = 6 ammette la corrispondente soluzione x=6; y=-5 (e infinite altre).

E’ poi chiaramente possibile procedere in senso opposto, partire cioè da un’equazione diofantea

e pervenire a una modulare equivalente ma solo a condizione che i coefficienti e il termine noto dell’equazione siano primi tra loro, come si può sempre scrivere in forma ridotta se già non lo è.

Così ad es.l’equazione: 3x + 4y = 5, soddisfatta da x=7; y= -4, può diventare 3x = 5 (mod 4) cioè, e meglio ancora 3x = 1 (mod 4)] con soluzione 7 ma anche 4y = 5 (mod 3) ovvero y = 2 (mod 3) corrispondente alla nuova soluzione y=2; x =-1. Se però l’equazione diofantea iniziale fosse stata scritta in forma non ridotta: 6x + 8y = 10, non potremmo associarle 6x = 10 (mod 8) che non può a rigore (senza cioè inopinatamente semplificarla) essere risolta mancando l’inverso di 6 (mod 12).

Ciò premesso meglio si comprende il seguente fondamentale teorema sulle equazioni diofantee:

Teorema: Condizione necessaria e sufficiente affinche l’equazione diofantea ax + by = c ammetta soluzioni (e se queste esistono sono allora infinite) è che, scritta in forma ridotta, risultino primi tra loro i coefficienti a e b ovverosia risulti MCD(a,b) = 1.

Dimostrazione: supponiamo che l’equazione ax + by = c sia già scritta in forma ridotta e siano a e b primi tra loro. Se c=0 si verifica subito che essa ammette le infinite soluzioni: x =kb; y= -ka, "kÎZ.

Se c¹0 possiamo sempre supporre che sia c=1, in quanto se aa + bb = 1 allora, come subito si verifica, x=ca; y=cb è soluzione di ax + by = c. Per risolvere l’equazione ax + by =1 applichiamo al calcolo del massimo comun divisore di a e b il ben noto algoritmo euclideo. Ricordiamo che esso consiste nel dividere a per b (supponendo ad es. che sia a>b) e poi, se il resto r0 non è nullo, nel dividere b per il resto r0 trovando un nuovo quoziente q1 e resto r1 e quindi, sempre che r1¹0,

nel dividere r0 per r1 e poi r1 per r2 ecc. sino a quando non si trova un resto nullo, condizione che sicuramente prima o poi si verifica essendo i resti successivi in ordine decrescente. Il MCD è allora b (se b|q) o l’ultimo rf ¹ 0 (cosi ad es. con a=12 e b=8 si trova 12 = 8×1 + 4 ; 8= 4×2 + 0 => MCD=2),

in quanto, come subito si verifica “risalendo” verso a e b, tale divisore divide sia a che b

Nel caso nostro, essendo MCD (a,b) =1 si avrà allora rf = 1 (quindi q f+1 = r f-1) e pertanto:

a = b q0 + r0 ; b = r0 q1 + r1 ; r0 = r1 q2 + r2 ; r1 = r2 q3 + r3 ; … r f-2 = r f -1 q f + 1 (ed r f-1 = 1×r f-1 + 0).

Ricavando allora dalla 1° equazione r0 = a -bq0 e sostituendo nella 2° si avrà: b =( a -bq0) q1 + r1 cioè a (-q1) + b (1+ q0 q1) = r1 . Ricavando poi r1 da questa equazione e sostituendolo nella 3° e ripetendo il procedimento sino ad avere rf = 1 a secondo membro si troverà alla fine un’equazione anch’essa del tipo: a ( …) + b (…) =1, dove in parentesi si troveranno, come appunto nell’ultima equazione trovata, due espressioni u e v contenenti i successivi quozienti q0, q1, q2 … che costituiscono pertanto una delle soluzioni cercate dell’equazione ax + by =1: x’0 = u; y’0 = v.

Una soluzione particolare dell’equazione data: ax + by =c è pertanto: x0 = cu; y0 = cv.

Per avere poi la soluzione generale di tale equazione basta aggiungere la generica soluzione

x* =kb; y*= -ka dell’equazione omogenea associata (quella cioè con c=0). Essa, al variare di k in Z è infatti ancora soluzione dell’equazione data (basta sommare membro a membro per verificarlo)

e non ce ne sono altre perché se (x1; y1 ) è una qualsiasi soluzione di ax+by = c diversa da (x0; y0 )

come subito si verifica (sottraendo questa volta membro a membro) (x1- x0; y1-y0 ) risulta allora soluzione dell’omogenea associata, e quindi x1- x0 = kb; y1- y0 = - ka, cioè x1=x0 + kb; y1= y0 – ka.

Lasciamo come esercizio la ricerca delle eventuali soluzioni con numeri naturali, quindi x, y >0.

Abbiamo quindi dimostrato che, se nell’equazione diofantea ridotta ax + by = c vale MCD(a,b)=1 essa ammette infinite soluzioni intere: x = x0 + kb; y = y0 – ka dove (x0 ;y0) è una qualsiasi soluzione dell’equazione data, in particolare quella prima indicata: x0 = cu;y0 =cv fornita dalla dimostrazione.

Resta da dimostrare, per completare il teorema, la condizione necessaria. La dimostrazione è immediata. Se infatti l’equazione diofantea ridotta ax + by = c ammette una soluzione x= U; y = V e fosse m= MCD(a,b) ¹1 allora avremmo a= hm; b=km (con h, kÎZ ) e quindi : hmU+ kmV = c ó m(hU + kV) = c. Ci sarebbe cioè un fattore m¹1 comune ad a, b, c, contro l’ipotesi che essi siano primi tra loro in quanto l’equazione ridotta.

Come abbiamo già detto, grazie all’equivalenza tra equazioni modulari ed equazioni diofantee, il teorema precedente ci assicura che ogni Z p, con p primo, è un campo e conseguentemente che vale il teorema di Eulero –Fermat. A sua volta però questo secondo teorema può rendere più agevole la ricerca degli inversi di Z p, troppo lunga e laboriosa con il metodo di euclideo. La formula infatti può scriversi " x ¹0 : x ×x p-2 = 1. Questo ci dice che l’inverso di una qualsiasi classe di resto (mod p) x vale x p-2 e ci permette quindi, almeno in teoria (in pratica non è molto agevole se p è grande) di calcolare l’inverso di una qualsiasi classe modulo un numero primo. Così ad es. considerando ancora una volta le classi modulo 7 si ottiene subito che l’inverso di [2]7 vale:[2]7 -1 = [2]7 5 = [32]7 = [4]7 come già si è visto. Analogamente [3]7 -1 = [3]7 5 = [243]7 = [5]7 .

Concludiamo questo breve excursus sull’aritmetica modulare con due interessanti applicazioni.

La prima riguarda i criteri di divisibilità per 3, 9 e 11 di un numero n. Com’è noto per i primi due basta fare la somma s delle cifre, eventualmente ripetendo lo stesso calcolo sulle cifre di S appena calcolato: s è divisibile per 3 o per 9 ó il numero dato n è divisibile per 3 o 9.

La dimostrazione, usando l’aritmetica modulare, è semplicissima e molto elegante. Basta infatti trasformare s in base 9 e ricordare che [a+b] =[a] + [b] e [ab] = [a] [b] per qualunque base.

Osservato poi che ogni numero naturale intero decimale ( scritto cioè usualmente in base 10) altro non è che un polinomio P(x) avente per coefficienti le dieci cifre 0, 1, 2, …, 9 calcolato per x=10 e che [10]9 = [1]9 segue subito che [n]9 = [s]9 . Osservato che 9 non è primo e quindi [3]9 è divisore dello zero (l’unico, essendo 9 un quadrato) ne deriva subito che:

9|s ó [s]9 = [0]9 ó [0]9 = [n]9 ó n|9 cioè n è divisibile per 9 se e solo se s è divisibile per 9.

Così pure con n divisibile per 3 e non per 9,cioè n =3k ma k non multiplo di 3 vale:

[n]9 ¹ [0]9 = [3k]9 = [3]9 [k]9 ó[s]9 ¹ [0]9 = [3k]9 = [3]9 [k]9 cioè n è multiplo di 3 e non di 9 se e solo

se s è multiplo di 3 e non di 9. Mettendo poi insieme questo risultato con il precedente segue poi il criterio generale quale che sia n : n è divisibile per 3 se e solo se s è divisibile per 3.

Si noti che per le potenze di 3 successive a 9 vale solo la condizione sufficiente dei due precedenti criteri di divisibilità, ad es. 999 è divisibile per 27, essendo tale la somma delle sue cifre, ma non viceversa (ad es. 54 è divisibile per 27 ma 5+4 non lo è).

Passando ora a considerare la divisibilità per 11 basta osservare che [10]11 = [-1]11 (infatti risulta 10 – (-1) =11 ) e quindi - scritto al solito il numero in forma polinomiale - risulta questa volta:

[n]11 = [p-d]11 avendo orai ndicato con p la somma delle cifre di posto pari e con d quella di posto dispari. Lasciamo al solito i dettagli della dimostrazione come esercizio.

Per concludere la divisibilità mediante i moduli accenniamo al problema in generale.

Com’è noto, a prescindere dai due ovvi criteri di divisibilità per 2 e per 5 – un numero è divisibile per essi se e solo se lo è la sua cifra delle unità – non esistono altri semplici criteri per altri fattori primi. Basterebbe però riscrivere i numeri in basi diversa da dieci (ad es. otto) per ottenere nuovi corrispondenti criteri di divisibilità. Lasciamo ancora una volta per esercizio le facili risposte.

Ricordiamo infine, in quanto argomento connesso, che il passaggio al modulo 9 permette un immediato controllo dell’esattezza di un calcolo eseguito manualmente, la famosa prova del nove, strumento prezioso prima del recenteavvento delle moderne calcolatrici. Per accertare se ad es. vale 125 x 379 = 47375 basta moltiplicare le somme (mod 9) delle cifre dei due fattori (8 e 19º1):

Ovviamente l’esito positivo della prova ora ottenuto non assicura l’esattezza del calcolo (esito che continua a valere cambiando ad es.l’ordine delle cifre) in quanto è solo una condizione necessaria.

Molto più sicura sarebbe invece la prova dell’undici. Al solito lasciamo i dettagli come esercizio.

Vediamo ora un’altra significativa applicazione dell’aritmetica modulare che generalizza quanto già accennato: la determinazione del giorno serttimanale di una data qualsiasi, passata o futura.

Per farlo basta calcolare il giorno g (lunedì:1, martedì: 2, … sabato: 6, domenica: 0) corrispondente al 1 marzo dell’anno in esame (successivo all’eventuale gioirno bisestile). Se la data fa parte dell’attuale calendario gregoriano (entrato in vigore il 15/10/ 1582) bisogna ricordare che, a differenza del precedente impreciso calendario giuliano (introdotto da Giulio Cesare nel 44 A.C.) non sono bisestili gli anni secolari: 1700,1800, 1900, il futuro 2100 ecc. mentre lo sono quelli divisibili per 400 (quindi il 1600, il recente 2000, il 2400 ecc.). Sappiamo che il conteggio dei giorni settimanali non ha mai subito interruzioni, almeno dall’epoca romana. Sappiamo inoltre che, essendo 1 il resto della divisione di 365 per 7, se una data fissa dell’anno come il Natale cade di domenica un certo anno – e così è avvenuto nel 2005 – nell’anno successivo cadrà di lunedì se quell’anno non è bisestile, di martedì se lo è. Si può allora verificare che scritto l’anno a nella forma a = 100s + n (ad es. per l’anno della discesa sulla luna era: s =19; n = 69) valgono le due formule

(si osservi che 1secolo giuliano = (75×365+25×366)d mentre 1sec. gregoriano = (76×365+24×366)d ):

g = [1+ 6s + n + n\4]7 per il calendario giuliano (dal 44 A.C.fino al 1582 D.C.) (a\b è il quoziente

g = [3+ 5s + s\4 + n + n\4]7 per il calendario gregoriano (dal 1583 D.C. in poi). Intero tra a e b)

Cosi ad es. per il 1 marzo 1492 era d = [1+ 6×14 + 92 + 23]7 = [4]7 : giovedì e quindi il 12 ottobre

- 225 giorni dopo, data della scoperta dell’america - era venerdì, essendo [225]7 = [1]7 ; invece il 1 marzo 1789 era d = [3+ 5×17 + 4 + 89 + 22]7 = [0]7 : domenica e quindi il 14 luglio – 135 giorni dopo, data della presa della Bastiglia – era invece martedì.

La seconda applicazione che in conclusione vogliamo proporre riguarda la già citata questione dei numeri periodici. Com’è noto eseguendo la divisione con la virgola (quindi, per intenderci, quella indicata con il simbolo / e non con \ che indica invece il quoziente intero) tra due numeri interi a e b che supporremo primi tra loro, si possono ottenere tre diversi possibili risultati:

1) Il rapporto è decimale finito, ad es. 9 / 80 = 0, 1125. Questo accade se e solo se i fattori primi del denominatore b sono soltanto 2 e/o 5 (quindi i fattori di 10) quali che siano gli esponenti. Osserviamo che in questo caso, e solo in questo, la frazione a/b può sostituirsi (utilizzando la proprietà invariantiva della divisione) con una equivalente di tipo decimale, avente cioè una certa potenza di 10 al denominatore. Nell’es. risulta: 9/80 = 9 /24×5 = 9×53/ 24×54 = 1125 / 10000 = 0,1125.

2) Il rapporto è un decimale periodico semplice, ad es. 10 / 21 = 0,476190476190… = 0,(476190). Questo accade se e solo se i fattori primi del denominatore b sono diversi sia da 2 che da 5 (nell’es. 3 e 7). Si osservi che le cifre prima o poi si ripetono – nell’es. sono 7, una di meno del fattore più grande di 21 = 3×7 - in quanto sono in numero finito, al più b—1, i possibili resti della divisione di a per b, divesamente da quanto accade ad es. nell’estrazione di radice di un numero non quadrato, dove le cifre sono infinite ma non periodiche, essendo irrrazionale il risultato.

3)Il rapporto è un numero periodico misto, ad es. 8 / 35 = 0,2285714285714… = 0,2(285714), presenta cioè ancora un periodo di cifre che si ripete infinite volte precedeuto però da una o più cifre decimali che non si ripetono. Ciò si verifica se e solo se i fattori primi di b sono il 2 e/o il 5 assieme a qualche altro fattore (nell’es. il 5 assieme al 7).

La presenza di numeri periodici nel risultato di una divisione tra numeri interi – l’equivalenza cioè tra alcuni razionali a / b e i numeri periodici non è quindi un’eccezione, anzi volendo diventa la regola, potendosi sempre scrivere un numero decimale finito in forma periodica con periodo nove: ad es. 2,5 = 2,4999… (oltre che 2,500…) e così pure 2= 1,999…

Volendo tuttavia ogni frazione può al contrario scriversi in forma decimale finita cambiando in modo opportuno la base del sistema numerico. Ad es. 0,(3) =1/3 diventa decimale finito in base 3: infatti in tale base 3 diventa 10TRE (una terzina, zero unità) da cui: 0,(3) = 1 / 3 = 1 / 10TRE = 0,(1)TRE .

Naturalmente passando dal sistema decimale ad altre basi numeriche, se alcune frazioni cessano di generare numeri periodici, altre, prima decimali finite, lo diventano. Lasciamo come sempre a titolo di esercizio la determinazione dei criteri generali per la classificazione di una generica frazione in una base numerica qualsiasi.

A prescindere da ciò, com’è noto, ogni numero periodico può sempre sostituirsi con (una) sua frazione generatrice. Ricordiamo la regola semplice e immediata:

al numeratore si scrive la differenza tra il numero periodico (liberato dalle parentesi del periodo)

e la sua parte non periodica; al denominatore si scrivono tanti 9 quante sono le cifre del periodo seguiti da tanti zeri quante sono le cifre dell’antiperiodo.Vediamone brevemente la ragione con una dimostrazione semplice ed elegante (ce n’è un’altra che usa le progressioni geometriche, ma più complessa ed elaborata) procedendo su alcuni esempi particolari.

Sia ad es. s = 3,(45) = 3,454545…. Avendo allora anche 100s =345,454545… la stessa illimitata parte decimale periodica, basta sottrarre membro a membro per ottenere: 99s = 345 – 3 da cui si ricava subito: s = (345 –3) / 99, come indica la regola. Chiaramente se fossimo partiti da un altro numero periodico semplice di periodo tre avremmo moltiplicato per 1000 e diviso poi per 999 ecc.

Se invece il numero di partenza è periodico misto, ad es. m = 5, 83(216), s = 100m = 583,(216) risulta periodico semplice. Per quanto detto sopra vale allora: s = (583216 – 583) /999 da cui

m = s / 100 = (583216 – 583) / 99900, come ancora indica la regola.

Anche per questa regola non è difficile dare una formulazione generale valida per ogni base.

Osservato preliminarmente che dalle considerazioni precedenti deriva subito che al crescere del numero dei 9 e degli 0 finali i denominatori delle frazioni generatrici diventano multipli di un qualsiasi numero intero, ci chiediamoora se, data una qualsiasi frazione che genera un numero periodico, ad es. 8/11, sia possibile sapere il numero k di cifre del periodo senza doverle calcolare. Sappiamo già che al massimo k =10. Possiamo però immaginare di risalire da tale numero alla sua frazione generatrice che al denominatore presenterà un numero D con k cifre uguali a 9 e quindi anche: D= 10k – 1. Essendo poi tale frazione equivalente a quella data, 8 / 11 ne deriva subito che 10k – 1 deve essere multiplo di 11 ovvero 10k = 1 (mod 11). Il problema viene quindi subito ricondotto al teorema di Eulero –Fermat che come sappiamo afferma che vale: x j (n) = 1 (mod n) "x Î N (primo con n), in questo caso x=10; n=11. Esso però ci assicura solo che in questo caso esiste sempre – cosa che già sappiamo - la soluzione x=10 (essendo 11primo), senza però escludere che esista una soluzione k* < j (n) , la minima possibile, che soddisfa l’equazione modulare considerata. Tale minimo valore k* , sempre esistente quando n ed x sono primi tra loro, è detto anche gaussiano di n rispetto ad x e viene indicato con il simbolo gss(n, x). Nel caso nostro è facile verificare che gss(11, 10) = 2 in quanto 102 =100 = 1 + 11× 9 e infatti risulta:

8 / 11= 0,(72). Così pure si verifica che (essendo sempre x=10)risulta gss(3,10) =1; gss(13,10) = 6

mentre per n = 7 ed n = 17 assume invece i valori massimi, 6 e 16.

Più in generale, sulla base dell’esempio appena considerato e di quanto detto in precedenza, si può poi facilmente dimostrare che il numero delle cifre del periodo del numero periodico, semplice o misto che sia, generato da una qualsiasi frazione m /n (con m ed n sempre primi fra loro) non dipende dal numeratore m ma solo dal denominatore n e, scomposto parzialmente n in fattori in modo che si abbia: n = 2p × 5q × d (con p e/o q eventualmente nulli e d primo con 2 e con 5), è sempre pari al gaussiano gss(d,10) di d rispetto a 10 mentre il numero delle cifre dell’antiperiodo risulta uguale al massimo max(p,q) dei due esponenti.

La regola ora stabilita vale pure nel caso in cui la frazione m/n genera un numero non periodico ma decimale finito (d =1): in tal caso max(p,q) risulta il numero finito delle cifre dopo la virgola.

Ancora una volta lasciamo a titolo di esercizio l’immediata generalizzazione ad una base qualsiasi delle già di per sé ampie considerazioni appena enunciate.

Le cifre del periodo (ma anche dell’antiperiodo) nello sviluppo decimale di una imprecisata frazione, non essendo determinabili se non svolgendo il calcolo completo della divisione sino alla conclusione dell’eventuale periodo, sono quindi imprevedibili a priori e in quanto tali possono considerarsi a tutti gli effetti come se fossero dei numeri casuali. Come tali vengono oggi usate dalle calcolatrici e dai computer nelle costruzioni di modelli matematici o simulazioni statistiche (ad es. il metodo Montecarlo) e quindi ben si comprende quanto sia importante conoscere la lunghezza del periodo e dell’antiperiodo per vedere se vale la pena procedere nel calcolo successivo.

Fonte: http://www.ypsilon.altervista.org/Argomenti/Aritmetica.doc

Autore del testo: non indicato nel documento di origine

Parola chiave google : Aritmetica modulare tipo file : doc

Aritmetica modulare

L'aritmetica modulare si basa sul concetto di congruenza modulo n . Dati tre numeri interi a, b, n, con n ≠ 0, diciamo che a e b sono congruenti modulo n se la loro differenza (a − b) è un multiplo di n. In questo caso scriviamo

e diciamo che a è congruo a b modulo n. Per esempio, possiamo scrivere

poiché 38 − 14 = 24, che è un multiplo di 12.

Nel caso entrambi i numeri siano positivi, si può anche dire che a e b sono congruenti modulo n se hanno lo stesso resto nella divisione per n. Quindi possiamo anche dire che 38 è congruo a 14 modulo 12 poiché sia 38 sia 14 hanno resto 2 nella divisione per 12.

La congruenza è una relazione di equivalenza tra numeri interi come si evince dalle seguenti proprietà:

Proprietà riflessiva: ogni numero è congruo a sé stesso modulo n, per ogni n diverso da 0 fissato.

Dimostrazione: si ha a - a = 0. Ma come è noto, ogni intero non nullo è divisore di 0. Quindi n divide (a - a)

Proprietà simmetrica: se a è congruo a b modulo n allora b è congruo ad a modulo n

Dimostrazione: se n divide (a - b) , allora n divide anche l'opposto (b - a) = - (a - b)

Proprietà transitiva: se a è congruo a b modulo n e b è congruo a c modulo n allora anche a è congruo a c modulo n.

Dimostrazione: se n divide (a - b) e n divide (b - c) allora, per la proprietà distributiva della divisione rispetto alla somma, n divide anche [(a - b) + (b - c)]=[a - b + b - c] = (a - c).

Invarianza rispetto alle operazioni aritmetiche [modifica]

Un'altra importante caratteristica della relazione di congruenza è il fatto di essere preservata dalle usuali operazioni aritmetiche tra interi:

Invarianza per addizione: aumentando o diminuendo della stessa quantità due numeri congruenti modulo n, i nuovi numeri ottenuti sono ancora congruenti tra loro modulo n. Più sinteticamente

Dimostrazione: scriviamo (a - b) = (a - b + c - c) = (a + c) - (b + c)

Invarianza per moltiplicazione: moltiplicando per una stessa quantità due numeri congruenti modulo n, i nuovi numeri ottenuti sono ancora congruenti tra loro modulo n.

Dimostrazione: se n divide (a - b) allora n divide (a - b)×c

Nota: Questa proprietà si può invertire solo se MCD(n,c) = 1.

Invarianza rispetto all'elevamento a potenza: elevando due numeri congrui modulo n alla stessa potenza k, i numeri ottenuti sono ancora congrui tra loro modulo n.

Dimostrazione: se a ≡ b ≡ 0 (mod n) la proposizione è banale. Se a ≡ b (mod n) non sono nulli, supponiamo di sapere che .

Nota: Questa proprietà si può invertire solo se k è diverso da 0.

Fonte: https://2bclasse2-0.wikispaces.com/file/view/aritmetica+modulare.docx/312058544/aritmetica%20modulare.docx

Aritmetica modulare

Aritmetica modulare

Aritmetica modulare

Aritmetica modulare

Aritmetica modulare

Visita la nostra pagina principale

Aritmetica modulare

Termini d' uso e privacy

Aritmetica modulare