De ce contează?
Privește un ceas cu ace. După ora 12 nu urmează 13 — acul sare înapoi la 1. Numerele nu cresc niciodată la nesfârșit: se „înfășoară" și o iau de la capăt. Dacă acum e ora 10 și mai trec 5 ore, nu spui „ora 15", ci „ora 3". Tocmai ai făcut, fără să-ți dai seama, o operație modulo: ai luat restul împărțirii la 12. Aritmetica modulară este matematica lucrurilor care se repetă în cerc.
Ideea-cheie
Până acum ai învățat cum se calculează cu resturi: adunare, scădere și înmulțire modulo ((a + b) % m, (a * b) % m și restul corectat la scădere). Lecția asta nu adaugă nicio formulă nouă. Răspunde la o întrebare diferită și mai importantă: când te uiți la o problemă și îți spui „aici e modulo"?
Aritmetica modulară apare din trei motive concrete. Învață să le recunoști și jumătate din muncă e gata.
1. Ca să ții rezultatele uriașe sub control. Unele probleme cer „numărul de moduri în care poți face X". Acel număr poate avea sute sau mii de cifre — nu încape în niciun tip de date. De aceea enunțul spune „afișați rezultatul modulo 1000000007". Tu nu calculezi numărul adevărat, ci doar restul lui; și, ca să nu depășești pe drum, reduci la fiecare pas.
2. Ca să modelezi lucruri care se repetă în cerc. Ceasul, zilele săptămânii, pozițiile pe o pistă circulară, rotațiile unui șir — orice se întoarce la început. Poziția de după k pași pe un cerc cu m căsuțe este pur și simplu un rest la m.
3. Ca să răspunzi la întrebări de divizibilitate sau de grupare. „Este a divizibil cu m?" înseamnă a % m == 0. „Împarte obiectele în m grupe" se traduce prin resturi. Iar cazul cel mai mic, % 2, îți spune paritatea: par sau impar.
Modulo nu este o tehnică pe care o aplici la sfârșit. Este o lentilă prin care privești problema de la început: „valorile mele trăiesc pe un cerc cu m căsuțe, nu pe o linie infinită." Odată ce vezi cercul, regulile de adunare, scădere și înmulțire modulo se aplică singure.