Aritmetica modulară, explicată
Toată lumea folosește deja aritmetica modulară: la 10 ore după ora 8 este ora 6, iar ziua de după duminică este luni. Numărarea care o ia de la 0 după n pași se dovedește a avea propria ei aritmetică completă, cu reguli, surprize și un loc central în teoria numerelor și în criptografia care protejează internetul.
Resturi și congruență
Împarte a la n și păstrează doar restul: acesta este a mod n, un număr de la 0 la n − 1. 26 mod 7 = 5, deoarece 26 = 3 × 7 + 5. Numerele cu același rest se comportă la fel mod n, așa că le numim congruente: 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauss a introdus această notație în Disquisitiones Arithmeticae, din 1801, iar ea a transformat vechile observații ale lui Fermat și Euler într-o aritmetică de sine stătătoare. Pe un ceas cu n poziții, fiecare număr întreg ajunge pe restul său; turele complete sunt uitate.
Adunare, scădere și înmulțire
Cele trei operații obișnuite funcționează ca de obicei și poți reduce mod n oricând vrei: restul unei sume este restul sumei resturilor, iar același lucru e valabil pentru diferențe și produse. Ca să afli ultima cifră a lui 37 × 48, înmulțește doar ultimele cifre: 7 × 8 = 56, deci rezultatul se termină în 6. Asta face aritmetica modulară atât de utilă pentru calculatoare: oricât de mari ar fi numerele, valorile intermediare nu depășesc niciodată n².
Împărțirea are nevoie de un invers
Împărțirea este excepția. 2 × 3 ≡ 2 × 8 (mod 10), pentru că ambele sunt 6 mod 10, și totuși 3 și 8 sunt diferite, deci nu poți pur și simplu să simplifici cu 2. A împărți la a înseamnă a înmulți cu inversul lui, numărul x cu a × x ≡ 1, care există exact când a și n nu au niciun factor comun. Algoritmul lui Euclid extins îl găsește: efectuează pașii de împărțire ai lui Euclid pentru cel mai mare divizor comun și ține evidența unui multiplicator la fiecare pas, astfel încât, când restul ajunge la 1, multiplicatorul este inversul. Când n este prim, orice număr în afară de 0 are un invers, iar împărțirea funcționează mereu.
Puteri, Fermat și Euler
Puterile se repetă. Ia puterile lui 3 mod 7: 3, 2, 6, 4, 5, 1, apoi din nou 3. Lungimea acestui ciclu este ordinul lui 3. În 1640, Pierre de Fermat a observat că pentru un număr prim p, a^(p − 1) ≡ 1 (mod p) ori de câte ori p nu îl divide pe a, deci orice ordin îl divide pe p − 1. Leonhard Euler a demonstrat acest lucru și l-a extins la orice n, înlocuind p − 1 cu numărul valorilor prime cu n. Puterile uriașe se calculează prin ridicări repetate la pătrat: a, a², a⁴, a⁸ …, fiecare fiind pătratul celei dinainte, redus mod n, apoi înmulțite după cifrele binare ale exponentului.
Cifre de control și calendare
Aritmetica modulară prinde greșelile. Ultima cifră a unui ISBN-10 este aleasă astfel încât o sumă ponderată a tuturor celor zece cifre să fie multiplu de 11, așa că orice cifră greșită și orice inversare a două cifre vecine sunt detectate. Numerele cardurilor bancare folosesc verificarea Luhn mod 10, iar codurile IBAN o verificare mod 97. Calendarele merg mod 7: ziua săptămânii pentru orice dată se poate calcula cu câteva resturi, iar așa funcționează calendarele perpetue și regula doomsday.
Criptografie
Criptografia modernă se bazează pe puteri modulare ușor de calculat și greu de inversat. În schimbul de chei Diffie–Hellman din 1976, două persoane convin asupra unui secret comun pe o linie deschisă, schimbând puteri modulo un număr prim mare. RSA, publicat în 1977 de Rivest, Shamir și Adleman, criptează un mesaj m ca m^e mod n, unde n este produsul a două numere prime mari, și decriptează cu un al doilea exponent d pe care îl poate calcula doar cineva care cunoaște cele două numere prime. În exemplul din manuale, n = 3233 = 61 × 53, e = 17 și d = 413: 65 devine 2790, iar 2790 redevine 65.
Explorează
Deschide ceasul modular ca să calculezi a mod n, sume, diferențe, produse, puteri, inverse și câturi mod n, pentru numere de până la 30 de cifre. Fiecare răspuns vine cu pașii lui: împărțirea cu rest, puterile din ridicarea repetată la pătrat sau tabelul algoritmului lui Euclid extins. Ceasul desenează cum se ajunge la răspuns, de la spirala unei adunări la ciclul puterilor, iar pentru n mic tabelul operației arată toate răspunsurile deodată.
Întrebări frecvente
Ce înseamnă simbolul ≡?
a ≡ b (mod n) spune că a și b dau același rest la împărțirea la n sau, echivalent, că n îl divide pe a − b. 38 ≡ 2 (mod 12), deoarece 38 − 2 = 36 este multiplu de 12.
Este mod același lucru cu operatorul % din programare?
Pentru numere pozitive, da. Pentru numere negative, multe limbaje, precum C, Java și JavaScript, întorc un rest negativ: acolo −7 % 3 este −1, în timp ce −7 mod 3 = 2. Operatorul % din Python urmează convenția matematică pentru un n pozitiv.
Ce este ordinul unui număr mod n?
Cel mai mic k > 0 cu a^k ≡ 1 (mod n). El există doar când a și n nu au niciun factor comun. Ordinul lui 2 mod 7 este 3, deoarece 2³ = 8 ≡ 1, iar ordinul lui 3 mod 7 este 6, așa că puterile lui 3 trec prin toate resturile nenule: 3 este o rădăcină primitivă mod 7.
Cine a inventat aritmetica modulară?
Resturile erau folosite cu mult înainte, de exemplu în teorema chineză a resturilor, din secolele III–V, precum și de Fermat și Euler. Gauss a transformat-o într-o aritmetică sistematică, cu notația congruențelor, în 1801.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Deschide ceasul modular