venerdì 16 aprile 2010

Alice, Bob e Eva — Qualche proprietà

“Abbiamo dato la definizione di congruenza in modulo, cioè abbiamo spiegato cosa significa la scrittura mn mod p”.

“Sì, significa che m diviso per p dà resto n”.

“Bene. Ora studiamo qualche proprietà. Per capire come funzionano le cose, prendiamo ad esempio p = 7. Tieni presente che tutto quello che diciamo sarà poi valido per ogni p”.

“Va bene”.

“Allora, per prima cosa: come possiamo scrivere, in un altro modo, la congruenza mn mod 7?”.

“In che senso, in un altro modo?”.

“Utilizzando simboli già noti in precedenza. In pratica, ti sto chiedendo la definizione in formule”.

“Ah, ok. Bè, vorrebbe dire che quando divido m per 7 ottengo un quoziente che non conosco (e che non mi interessa) e resto n”.

“Puoi chiamare h il quoziente”.

“Allora, potrei scrivere che m = 7h + n”.

“Esatto. Facciamo un esempio, prendiamo due numeri m e n che siano entrambi congrui a 2 modulo 7. Ti scrivo le formule qua, riesci a tradurle?”.

m ≡ 2 mod 7,
n ≡ 2 mod 7.

“Allora, i due quozienti non saranno necessariamente uguali, giusto?”.

“Giustissimo. Uno lo possiamo chiamare h, l'altro k”.

“Allora le due congruenze diventano:”.

m = 7h + 2,
n = 7k + 2.

“Bene. Ora calcola la differenza m-n”.

“Uhm, m-n è uguale a 7h - 7k + 2 - 2. Dato che i 2 si eliminano, risulta che m-n è uguale a 7h - 7k. Ehi, posso raccogliere un 7, quindi ottengo che m-n = 7(h-k). In pratica m-n è un multiplo di 7”.

“Perfetto. Non ti sarà difficile generalizzare in un teorema questa idea di dimostrazione”.

“Mh, no, direi di no. Credo che funzioni così: se due numeri sono congruenti modulo p, allora la loro differenza è un multiplo di p”.


“Giusto, anche se non abbiamo dimostrato proprio questa affermazione. In realtà nell'esempio non abbiamo preso due numeri congruenti tra loro, ma entrambi congruenti a 2”.

“Ah. E quindi?”.

“Quindi va bene lo stesso, perché la congruenza è una relazione di equivalenza”.

“Non ti seguo. Le relazioni di equivalenza sono quelle per le quali valgono quelle tre proprietà: riflessiva, simmetrica e transitiva?”.

“Esatto, sono loro, vedo che ti ricordi qualcosa”.

“E il fatto che la congruenza in modulo è una relazione di equivalenza lo dimostriamo?”.

“Direi di no, non è difficile una volta che hai capito un concetto importante: la congruenza vale anche coi numeri negativi”.

“In che senso?”.

“Possiamo dire che -5 è congruente a 2 modulo 7, perché -5 è uguale a -7 + 2”.

“Ah, non ci avevo pensato. È come se andassimo indietro con l'orologio”.

“Esatto. Se tieni presente questa cosa, puoi dimostrare facilmente che la congruenza è una relazione di equivalenza, e quindi se hai due numeri entrambi congruenti a 2, tanto per fare un esempio, allora essi sono congruenti tra loro”.

“In pratica è come se dicessi che, non so, 15 e 22 sono congruenti tra loro modulo 7 perché entrambi sono congruenti a 1?”.

“Giustissimo, è così. Ora proviamo ad analizzare la somma di due numeri modulo il nostro 7. Prendi questi due:”.

m ≡ 3 mod 7,
n ≡ 5 mod 7.

“Allora, la prima uguaglianza significa che m = 7h + 3, mentre la seconda significa che n = 7k + 5. Se faccio la somma ottengo che m + n = 7(h + k) + 8. Quindi m + n ≡ 8 mod 7. Non mi piace.”.

“Perché?”.

“Perché 8 è maggiore di 7, come fa a venire un resto maggiore del divisore?”.

“Giusto. Ma dato che 8 è uguale a 7+1, puoi togliere 7 da 8 e sommarlo a 7(h + k)”.

“Quindi verrebbe m + n = 7(h + k + 1) + 1”.

“Esatto. In pratica, se nella somma ti risulta un risultato maggiore di 7, puoi farne di nuovo la divisione per 7 e tenere sempre il resto. E poi ricordati che abbiamo esteso il concetto di congruenza: quella relazione ci dice che sia m + n che 8 hanno lo stesso resto quando vengono divisi per 7 (cioè 1)”.

“Ho capito. Quindi questo secondo teorema diventerebbe così: se ab mod p e cd mod p, allora a + cb + d mod p”.

“Sì. Detto in termini meno rigorosi: possiamo fare le somme come ci pare”.

“Oh, mi piacciono questi enunciati decisi”.

“Già che ci siamo, facciamo anche la moltiplicazione. Prendiamo per esempio m ≡ 3 e n ≡ 5”.

“Vado, provo a fare tutti i conti. Allora, prima di tutto le tue uguaglianze significano questo:”.

m = 7h + 3,
n = 7k + 5.

“Bene. Io non l'avevo specificato, ma stiamo sempre immaginando che p sia uguale a 7”.

“Sì. Ora moltiplico:”.

mn = (7h + 3)(7k + 5) = … + 15.

“Come mai hai messo i puntini?”.

“Perché tanto l'espressione sottointesa dai puntini contiene sempre multipli di 7”.

“Quindi?”.

“Quindi posso scriverla così: mn = 7t + 15. In fondo a me interessa il 15, non ciò che moltiplica 7”.

“Molto bene. Quindi alla fine abbiamo capito come funziona la moltiplicazione?”.

“Sì, il teorema dovrebbe essere questo: se ab mod p e cd mod p, allora acbd mod p”.

“Oppure, in termini non rigorosi?”.

“Possiamo fare le moltiplicazioni come ci pare”.

“Caso particolare: a = c. Che succede?”.

“Uh, le potenze. Bè, se a = c allora posso sostituire e dire che a2b2 mod p”.

“Bene, e naturalmente possiamo moltiplicare a per sé stesso più volte, e generalizzare la regola sulle potenze in questo modo:”.

se ab mod p, allora anbn mod p, per ogni n naturale.

“Bello, anche le potenze si comportano bene”.

“Sì, anche loro. Per oggi basta, ti lascio un esercizio: che resto si ottiene dividendo per 5 la seguente espressione?”.

914 + 924 + 934 + 944 + 954.

·

4 commenti:

Unknown ha detto...

Bellissimo anche questo dialogo. A dire il vero non avevo pensato di partire da due numeri congrui ad un terzo ed usare la proprietà transitiva. Ero partito facendo vedere da casi particolari che il numero di ore dell'orologio divide la differenza dei due numeri congrui fra loro. Anzi, l'ho fatto dire ai ragazzi, mostrandogli degli esempi.
Invece per i numeri negativi abbiamo ragionato proprio sull'orologio percorso al contrario, con buoni risultati direi.

Grande davvero per questi dialoghi! Pensi di farne una specie di libro come per gli infiniti?

zar ha detto...

Mah, vedremo, l'intenzione è quella di arrivare a spiegare come funziona RSA.

Unknown ha detto...

Immaginavo. Buon lavoro allora!

Unknown ha detto...

Ah dimenticavo di rispondere alla questione degli argomenti che faccio al liceo. Il mio è un progetto che porto in aula da esterno, non fa parte del programma che svolgono normalmente i ragazzi, ma la prof è stata ben lieta di permettere che si dedicassero alcune ore a qualcosa di diverso.

Ho concluso oggi l'intero percorso parlando di crittografia quantistica...