Teorema chineză a resturilor explicată
Un număr dă restul 2 la împărțirea la 3, restul 3 la împărțirea la 5 și restul 2 la împărțirea la 7. Ce număr este? Încercați numerele unul câte unul și după o vreme ajungeți la 23, dar întrebarea ascunde o teoremă: atâta timp cât împărțitorii nu au un factor comun, există mereu exact un răspuns sub produsul lor și el se găsește fără să încercați nimic. Teorema are circa 1.500 de ani și lucrează încă în calendare, în aritmetica calculatoarelor și în criptografia care protejează internetul.
O problemă din Sunzi Suanjing
Sunzi Suanjing, o carte de aritmetică chinezească din secolele III–V, întreabă de un număr de lucruri care, numărate câte trei, lasă 2, câte cinci lasă 3 și câte șapte lasă 2. Răspunsul ei este 23, iar metoda este cea care se predă și azi: luați 70 pentru fiecare lucru rămas la numărarea câte trei, 21 pentru fiecare rămas la numărarea câte cinci și 15 pentru fiecare rămas la numărarea câte șapte, adunați și scădeți 105 de câte ori se poate. 2 × 70 + 3 × 21 + 2 × 15 = 233, iar 233 − 2 × 105 = 23. Un vers din epoca Ming a păstrat în memorie numerele 70, 21, 15 și 105 timp de secole. Qin Jiushao a dat o metodă generală în 1247, aceeași problemă apare în Liber Abaci al lui Fibonacci din 1202, iar Carl Friedrich Gauss a enunțat teorema în forma ei modernă în Disquisitiones Arithmeticae din 1801.
Ce spune teorema
Luați moduli n₁, n₂, …, nₖ dintre care niciun doi nu au un factor comun și resturi oarecare a₁, a₂, …, aₖ. Atunci există exact un număr întreg x de la 0 la N − 1, unde N = n₁ × n₂ × … × nₖ, care dă restul aᵢ la împărțirea la nᵢ, pentru fiecare i. Toate celelalte soluții diferă de el printr-un multiplu de N. În notația aritmeticii modulare: sistemul x ≡ aᵢ (mod nᵢ) are o soluție, unică mod N. Altfel spus, un număr de la 0 la N − 1 și lista resturilor sale poartă exact aceeași informație: 3 × 5 × 7 = 105 numere și 3 × 5 × 7 = 105 liste posibile de resturi, fiecare folosită o dată.
Construirea soluției
Numerele 70, 21 și 15 nu sunt magice. Fiecare dă restul 1 la împărțirea la propriul modul și restul 0 la împărțirea la celelalte: 70 = 2 × 35 este multiplu de 5 și de 7 și dă restul 1 la împărțirea la 3. În general se ia Nᵢ = N / nᵢ, multiplu al fiecărui modul în afară de nᵢ, și se înmulțește cu yᵢ, inversul lui Nᵢ mod nᵢ. Inversul există pentru că Nᵢ și nᵢ nu au un factor comun, iar algoritmul lui Euclid extins îl găsește: face împărțirile lui Euclid pentru cel mai mare divizor comun și se întoarce până la identitatea lui Bézout 1 = s × nᵢ + t × Nᵢ, astfel încât t este inversul. Atunci x = a₁N₁y₁ + a₂N₂y₂ + …, redus mod N, se potrivește fiecărei ecuații, pentru că fiecare termen se potrivește propriei ecuații și dispare în toate celelalte.
Câte o ecuație pe rând
Există o a doua cale, care nu are nevoie de produsul tuturor modulilor. Orice soluție a lui x ≡ 2 (mod 3) are forma x = 2 + 3t. Înlocuind în ecuația următoare, obțineți 2 + 3t ≡ 3 (mod 5), deci 3t ≡ 1 (mod 5), iar înmulțind cu 2, inversul lui 3 mod 5, rezultă t ≡ 2 (mod 5). Atunci x = 2 + 3 × 2 = 8, iar primele două ecuații împreună spun x ≡ 8 (mod 15). Repetând cu a treia ecuație, 8 + 15t ≡ 2 (mod 7) dă t ≡ 1, deci x ≡ 23 (mod 105). Această substituție păstrează numerele mai mici, este felul în care un calculator rezolvă de obicei astfel de sisteme și merge și când modulii au un factor comun.
Moduli cu un factor comun
Dacă doi moduli au un factor comun, ecuațiile lor se suprapun: x ≡ 1 (mod 4) spune deja că x este impar, iar x ≡ 4 (mod 6) spune că x este par, deci niciun x nu le satisface pe amândouă. În general, x ≡ a (mod m) și x ≡ b (mod n) pot fi adevărate în același timp exact când a și b dau același rest la împărțirea la g = gcd(m, n), adică atunci când g divide a − b. Soluția este atunci unică mod lcm(m, n) = m × n / g, nu mod m × n. Vechea ghicitoare a coșului cu ouă, din care rămâne 1 când sunt scoase câte 2, 3, 4, 5 sau 6 și niciunul când sunt scoase câte 7, are răspunsul 301, care se repetă la fiecare 420 = lcm(2, 3, 4, 5, 6, 7). Un sistem are soluție exact când fiecare pereche de ecuații ale sale se potrivește, deci un sistem imposibil conține mereu o pereche care se contrazice.
Calendare, calculatoare și RSA
În 1583, Joseph Scaliger a combinat trei cicluri calendaristice, ciclul solar de 28 de ani, ciclul lunar de 19 ani și indictionul de 15 ani, în perioada iuliană de 28 × 19 × 15 = 7.980 de ani. Conform teoremei, fiecare an are propria combinație a celor trei numere de ciclu, iar perioada începe în 4713 î.Hr., ultimul an în care toate trei erau 1; astronomii numără și azi zilele iuliene de acolo. Calculatoarele folosesc teorema pentru a lucra cu numere uriașe sub formă de liste de resturi mici, care pot fi adunate și înmulțite separat și în paralel, apoi unite la sfârșit. Decriptarea RSA funcționează la fel: c^d mod n cu n = p × q se calculează ca două puteri mod p și mod q unite prin teoremă, de circa patru ori mai repede decât o putere mod n. Schemele de partajare a secretelor, precum cele ale lui Mignotte și ale lui Asmuth și Bloom, ascund un secret în resturi, astfel încât doar suficient de multe dintre ele împreună îl dezvăluie.
Încercați
Deschideți calculatorul pentru a scrie orice sistem de congruențe, până la 20 de ecuații și numere de cel mult 200 de cifre, sau alegeți unul dintre exemplele rezolvate: problema lui Sunzi, coșul cu ouă, perioada iuliană, două orare de autobuz, decriptarea RSA și un sistem fără soluție. Calculul este scris cu numerele dumneavoastră, prin construcție sau prin substituție, cu algoritmul lui Euclid extins pentru fiecare invers. Imaginea marchează numerele care satisfac fiecare ecuație, ca să vedeți singura coloană în care se întâlnesc toate, sau așază resturile a două ecuații într-un tabel în care fiecare număr are celula lui.
Întrebări frecvente
Soluția unui sistem de congruențe este unică?
Doar până la un multiplu al modulului. Dacă x = 23 rezolvă problema lui Sunzi, o rezolvă și 23 + 105 = 128, 233 și −82, pentru că adunarea lui 105 nu schimbă niciun rest. Teorema spune că există exact o soluție de la 0 la 104; cu moduli care au factori comuni, exact una sub cel mai mic multiplu comun al lor.
De ce trebuie modulii să fie primi între ei?
Pentru construcție, pentru că Nᵢ trebuie să aibă un invers mod nᵢ, iar acesta există doar când nu au un factor comun. Pentru teorema însăși, pentru că factorii comuni fac unele ecuații să se suprapună: atunci un sistem fie nu are soluție, fie are mai puține soluții diferite, iar soluțiile se repetă la fiecare cel mai mic multiplu comun în loc de fiecare produs.
Cum găsesc de mână un invers modular?
Cu algoritmul lui Euclid extins. Pentru inversul lui 15 mod 7: 15 = 2 × 7 + 1, deci 1 = 15 − 2 × 7, iar 15 × 1 ≡ 1 (mod 7): inversul este 1. Pentru 35 mod 3: 35 = 11 × 3 + 2 și 3 = 1 × 2 + 1, deci 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, iar inversul lui 35 mod 3 este −1 ≡ 2. Pentru moduli mici puteți și pur și simplu să încercați 1, 2, 3, … până când produsul dă restul 1.
Ce legătură are teorema cu ceasurile?
Un rest mod n este o poziție pe un ceas cu n ore. Două ceasuri cu 3 și 5 ore, pornite împreună și avansate câte o oră, arată fiecare dintre cele 15 perechi de poziții o dată înainte să revină la început, pentru că 3 și 5 nu au un factor comun. Ceasurile cu 4 și 6 ore revin după 12 pași și arată doar 12 din cele 24 de perechi: o poziție impară și una pară nu apar niciodată împreună.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Deschideți calculatorul pentru teorema chineză a resturilor