Clasele de resturi în aritmetică: divizibilitate și ecuații în numere întregi

Care este ultima cifră a numărului $7^{2026}$? Nimeni nu-l scrie: are peste o mie șapte sute de cifre. Și totuși răspunsul se obține în trei rânduri, dacă renunți la număr și păstrezi doar clasa lui de resturi modulo $10$. Aceasta este ideea lecției de față din programa de clasa a 12-a. Clasele de resturi modulo $n$ sunt, în aritmetică, instrumentul care înlocuiește o infinitate de numere întregi cu doar $n$ clase: cu el se demonstrează divizibilități, se află resturi de puteri uriașe și se arată că anumite ecuații în numere întregi nu au nicio soluție.

Programa de matematică-informatică cere explicit, la competența XII.CS.6.1, „rezolvarea cu ajutorul claselor de resturi modulo $n$ a unor probleme de divizibilitate și a unor ecuații în mulțimea numerelor întregi". Vom folosi tot ce s-a construit până acum: operațiile din ${\mathbb{Z}}_n$, grupul claselor inversabile și, ca unealtă principală, Consecința 2 a teoremei lui Lagrange. Metoda seamănă cu cea de la transferul de structură prin izomorfism: muți problema într-o mulțime mică, unde poți verifica toate cazurile, și citești acolo răspunsul.

Ce vei învăța

• Vei ști să treci de la o afirmație despre numere întregi la una despre clase de resturi și să te întorci corect.
• Vei ști să demonstrezi divizibilități de tipul $6\mid n^3+5n$ verificând un număr finit de clase.
• Vei ști să determini ultima cifră, ultimele două cifre sau restul unei puteri mari, folosind ordinul clasei bazei.
• Vei ști să aplici Consecința 2 a teoremei lui Lagrange în grupul claselor inversabile din ${\mathbb{Z}}_n$.
• Vei ști să arăți că o ecuație în numere întregi nu are soluții, alegând modulul potrivit.
• Vei ști să rezolvi ecuații liniare în numere întregi trecând prin ecuații cu clase de resturi.

Hai să descoperim împreună

1. Ce înseamnă să lucrezi „modulo $n$"?

Reducerea modulo $n$ este operația prin care fiecărui număr întreg $a$ i se asociază clasa lui de resturi $\hat{a}$ din ${\mathbb{Z}}_n$, adică mulțimea tuturor întregilor care dau același rest ca $a$ la împărțirea cu $n$; ea păstrează atât adunarea, cât și înmulțirea, iar $n$ divide $a$ exact atunci când $\hat{a}=\hat{0}$.

Cele trei proprietăți pe care se sprijină toată lecția au fost demonstrate deja, la adunarea claselor de resturi și la înmulțirea claselor de resturi:

$$\widehat{a+b}=\hat{a}+\hat{b},\widehat{ab}=\hat{a}\cdot \hat{b},\hat{a}=\hat{b}⟺n\mid (a-b).$$

Prima dintre ele spune, în limbajul unității noastre, că funcția $\pi :\mathbb{Z}\to {\mathbb{Z}}_n$, $\pi (a)=\hat{a}$, este morfism surjectiv de la $(\mathbb{Z},+)$ la $({\mathbb{Z}}_n,+)$. A doua spune că ea se poartă la fel de frumos și cu înmulțirea. Împreună, ele dau regula practică: orice expresie polinomială cu coeficienți întregi se poate reduce modulo $n$ termen cu termen.

De aici, procedeul: dacă vrei să dovedești ceva despre toate numerele întregi și afirmația e „polinomială", e destul s-o verifici pe cele $n$ clase din ${\mathbb{Z}}_n$ — un număr finit de cazuri, în locul unei infinități.

⚠️ Atenție la sensul de întoarcere: din $\hat{a}=\hat{b}$ nu rezultă $a=b$, ci doar $n\mid (a-b)$. Clasele uită totul în afară de rest, iar asta e și puterea, și limita metodei.

2. Cum se demonstrează o divizibilitate cu clase de resturi?

Problemă-etalon. Arătați că $6\mid n^3+5n$ pentru orice $n\in \mathbb{Z}$.

Ar fi de ajuns să verificăm cele șase clase din ${\mathbb{Z}}_6$, dar e mai comod să spargem problema: $6=2\cdot 3$, iar $2$ și $3$ sunt prime între ele, deci un număr divizibil și cu $2$, și cu $3$, e divizibil cu $6$.

Modulo 2. În ${\mathbb{Z}}_2$ avem $\hat{5}=\hat{1}$, deci expresia devine ${\hat{n}}^3+\hat{n}$. Pentru $\hat{n}=\hat{0}$: $\hat{0}+\hat{0}=\hat{0}$. Pentru $\hat{n}=\hat{1}$: $\hat{1}+\hat{1}=\hat{0}$. În ambele cazuri clasa e nulă, deci $2\mid n^3+5n$.

Modulo 3. În ${\mathbb{Z}}_3$ avem $\hat{5}=\hat{2}$, deci expresia devine ${\hat{n}}^3+\hat{2}\hat{n}$:

(Am folosit ${\hat{2}}^3=\hat{8}=\hat{2}$ și $\hat{2}\cdot \hat{2}=\hat{4}=\hat{1}$.) Toate cele trei clase dau $\hat{0}$, deci $3\mid n^3+5n$.

Cum $(2,3)=1$, rezultă $6\mid n^3+5n$ pentru orice $n$ întreg. $■$

De ce e corect procedeul? Pentru că teorema împărțirii cu rest spune că fiecare număr întreg aparține exact uneia dintre cele $n$ clase, iar reducerea păstrează operațiile: valoarea expresiei într-un număr oarecare are aceeași clasă ca valoarea expresiei în restul lui. Verificând cele $n$ clase, ai verificat, de fapt, toate numerele întregi — nu un eșantion, ci întreaga infinitate, împărțită în $n$ pachete. Este singura metodă din programă care demonstrează o proprietate a tuturor numerelor întregi fără inducție; comparat-o cu metoda inducției matematice, care merge din aproape în aproape, aici se verifică un număr finit de cazuri și gata.

Reține rețeta. (1) Scrii ce trebuie demonstrat sub forma „$d$ divide expresia". (2) Descompui $d$ în factori primi între ei doi câte doi, dacă asta ușurează calculul. (3) Pentru fiecare factor, reduci expresia modulo el și verifici toate clasele. (4) Reunești concluziile.

⚠️ Pasul (4) cere ca factorii să fie primi între ei. Din $4\mid k$ și $2\mid k$ nu rezultă $8\mid k$: numărul $4$ e un contraexemplu.

3. Cum se află ultima cifră a unei puteri mari?

Ultima cifră a unui număr este restul lui la împărțirea cu $10$, deci întrebarea se pune în ${\mathbb{Z}}_{10}$. Calculăm puterile lui $\hat{7}$:

$${\hat{7}}^1=\hat{7},{\hat{7}}^2=\widehat{49}=\hat{9},{\hat{7}}^3=\hat{9}\cdot \hat{7}=\widehat{63}=\hat{3},{\hat{7}}^4=\hat{3}\cdot \hat{7}=\widehat{21}=\hat{1}.$$

Am ajuns la $\hat{1}$, deci $\mathrm{ord}(\hat{7})=4$ în grupul claselor inversabile, iar de aici încolo puterile se repetă din patru în patru. Împărțim exponentul la $4$:

$$2026=4\cdot 506+2⟹{\hat{7}}^{2026}={\left({\hat{7}}^4\right)}^{506}\cdot {\hat{7}}^2={\hat{1}}^{506}\cdot \hat{9}=\hat{9}.$$

Deci ultima cifră a lui $7^{2026}$ este $9$. Aceeași metodă dă ultima cifră a lui $3^{2026}$: puterile lui $\hat{3}$ sunt $\hat{3},\hat{9},\hat{7},\hat{1}$, ordinul e tot $4$, iar ${\hat{3}}^{2026}={\hat{3}}^2=\hat{9}$. Prin urmare ultima cifră a sumei $3^{2026}+7^{2026}$ este cifra unităților lui $9+9=18$, adică $8$.

Rețeta generală, în trei pași: (1) determini ordinul clasei bazei, calculând puterile până obții $\hat{1}$; (2) împarți exponentul la ordin și reții restul $r$; (3) răspunsul este puterea a $r$-a a bazei (cu convenția că restul $0$ înseamnă $\hat{1}$).

Pentru ultimele două cifre procedezi identic, dar în ${\mathbb{Z}}_{100}$: de pildă, ${\hat{7}}^4=\widehat{2401}=\hat{1}$ în ${\mathbb{Z}}_{100}$, deci ${\hat{7}}^{2026}={\hat{7}}^2=\widehat{49}$ și ultimele două cifre ale lui $7^{2026}$ sunt $49$.

4. Consecința 2 a teoremei lui Lagrange, la lucru

Calculul ordinului nu e mereu rapid. Există însă o scurtătură, pe care ne-o dă structura de grup. Reamintim, de la grupurile claselor de resturi modulo n, că mulțimea claselor inversabile

$$U({\mathbb{Z}}_n)=\left\{\hat{a}\in {\mathbb{Z}}_n\mid (a,n)=1\right\}$$

este grup față de înmulțirea claselor. Aplicăm acum Consecința 2 a teoremei lui Lagrange, demonstrată la grupuri finite și teorema lui Lagrange: într-un grup finit $G$, orice element verifică $x^{\mathrm{card}G}=e$.

Consecință aritmetică. Dacă $(a,n)=1$ și $m=\mathrm{card}U({\mathbb{Z}}_n)$, atunci ${\hat{a}}^m=\hat{1}$, adică $n\mid a^m-1$.

Iată câteva cazuri utile, cu cardinalele calculate direct:

Aplicație. Care este restul împărțirii lui $5^{2026}$ la $7$? Cum $(5,7)=1$ și $\mathrm{card}U({\mathbb{Z}}_7)=6$, avem ${\hat{5}}^6=\hat{1}$. Împărțim: $2026=6\cdot 337+4$, deci

$${\hat{5}}^{2026}={\left({\hat{5}}^6\right)}^{337}\cdot {\hat{5}}^4={\hat{5}}^4.$$

Calculăm ${\hat{5}}^2=\widehat{25}=\hat{4}$ și ${\hat{5}}^4={\hat{4}}^2=\widehat{16}=\hat{2}$. Restul căutat este $2$.

Observă avantajul: nu am avut nevoie de ordinul exact al lui $\hat{5}$, ci doar de un exponent despre care știm că dă $\hat{1}$. Ordinul divide oricum acest cardinal, conform Consecinței 1 a aceleiași teoreme, deci reducerea funcționează.

⚠️ Condiția $(a,n)=1$ este esențială. Pentru $\hat{2}$ în ${\mathbb{Z}}_{10}$, care nu e inversabilă, nicio putere nu dă $\hat{1}$; acolo se lucrează direct cu ciclul puterilor: $\hat{2},\hat{4},\hat{8},\hat{6},\hat{2},\dots$, care se repetă din patru în patru începând de la exponentul $1$. Cum $2026=4\cdot 506+2$, ultima cifră a lui $2^{2026}$ este $4$.

5. Cum arăți că o ecuație în numere întregi nu are soluții?

Trecem la a doua jumătate a lecției. Dacă o ecuație are soluții întregi, atunci ea are soluții și „modulo $n$", oricare ar fi $n$. Contrapoziția e metoda:

Principiul reducerii. Dacă există un număr natural $n\ge 2$ pentru care ecuația redusă modulo $n$ nu are soluții în ${\mathbb{Z}}_n$, atunci ecuația inițială nu are soluții în $\mathbb{Z}$.

Exemplul 1. Ecuația $x^2+y^2=2023$ nu are soluții întregi. Reducem modulo $4$ și calculăm întâi pătratele: ${\hat{0}}^2=\hat{0}$, ${\hat{1}}^2=\hat{1}$, ${\hat{2}}^2=\hat{0}$, ${\hat{3}}^2=\hat{1}$. Deci un pătrat perfect este, modulo $4$, fie $\hat{0}$, fie $\hat{1}$, iar suma a două pătrate este $\hat{0}$, $\hat{1}$ sau $\hat{2}$ — niciodată $\hat{3}$. Dar $2023=4\cdot 505+3$, deci membrul drept este $\hat{3}$. Contradicție, deci ecuația nu are soluții.

Exemplul 2. Ecuația $x^2-5y^2=2$ nu are soluții întregi. Reducem modulo $5$: termenul cu $y$ dispare, pentru că $\hat{5}=\hat{0}$, și rămâne ${\hat{x}}^2=\hat{2}$. Pătratele în ${\mathbb{Z}}_5$ sunt $\hat{0},\hat{1},\hat{4},\hat{4},\hat{1}$, adică mulțimea $\{\hat{0},\hat{1},\hat{4}\}$, care nu-l conține pe $\hat{2}$. Deci ecuația nu are soluții.

Exemplul 3. Ecuația $15x+21y=100$ nu are soluții întregi. Reducem modulo $3$: membrul stâng devine $\hat{0}$, pentru că $3\mid 15$ și $3\mid 21$, iar membrul drept este $\widehat{100}=\hat{1}$. Contradicție.

Cum alegi modulul. Nu la întâmplare, ci după ce vrei să obții:

• vrei să elimini un termen — alegi un divizor al coeficientului lui (exemplele 2 și 3);
• ai pătrate — încearcă $n\in \{3,4,5,8\}$, unde mulțimea pătratelor e mică: în ${\mathbb{Z}}_3$ e $\{\hat{0},\hat{1}\}$, în ${\mathbb{Z}}_4$ tot $\{\hat{0},\hat{1}\}$, în ${\mathbb{Z}}_8$ e $\{\hat{0},\hat{1},\hat{4}\}$;
• ai cuburi — încearcă $n=7$ sau $n=9$: cuburile în ${\mathbb{Z}}_7$ sunt doar $\hat{0},\hat{1},\hat{6}$;
• ai ultima cifră în enunț — lucrezi în ${\mathbb{Z}}_{10}$.

⚠️ Metoda este doar un criteriu de respingere. Dacă ecuația redusă are soluții modulo $n$, nu poți conchide nimic despre ecuația inițială: trebuie fie alt modul, fie altă metodă.

6. Ecuații liniare în numere întregi, rezolvate în ${\mathbb{Z}}_n$

Aceeași unealtă rezolvă, nu doar respinge. Fie ecuația $7x-10y=3$, cu $x,y\in \mathbb{Z}$. Reducând modulo $10$, termenul cu $y$ dispare și rămâne

$$\hat{7}\cdot \hat{x}=\hat{3}\text{ıˆn }{\mathbb{Z}}_{10}.$$

Clasa $\hat{7}$ este inversabilă, cu ${\hat{7}}^{-1}=\hat{3}$, pentru că $\hat{7}\cdot \hat{3}=\widehat{21}=\hat{1}$. Înmulțind ecuația cu $\hat{3}$, obținem $\hat{x}=\hat{3}\cdot \hat{3}=\hat{9}$, adică $x=9+10k$ cu $k\in \mathbb{Z}$. Înlocuind în ecuația inițială:

$$y=\frac{7(9+10k)-3}{10}=\frac{60+70k}{10}=6+7k.$$

Soluțiile sunt perechile $(9+10k,6+7k)$, $k\in \mathbb{Z}$. Verificare pentru $k=1$: $7\cdot 19-10\cdot 13=133-130=3$. ✓

Când coeficientul nu e inversabil, procedezi prin verificarea tuturor claselor, așa cum ai învățat la elementele inversabile din mulțimea claselor de resturi. De pildă, în ${\mathbb{Z}}_6$, ecuația $\hat{4}\cdot \hat{x}=\hat{2}$ are două soluții, $\hat{x}=\hat{2}$ și $\hat{x}=\hat{5}$, în vreme ce $\hat{4}\cdot \hat{x}=\hat{3}$ nu are niciuna — pentru că multiplii lui $\hat{4}$ sunt doar $\hat{0},\hat{4},\hat{2}$.

7. Cum se demonstrează criteriile de divizibilitate în două rânduri?

Regulile pe care le folosești din gimnaziu primesc acum o demonstrație. Fie $N$ un număr natural cu cifrele $c_0$ (unitățile), $c_1$, …, $c_p$, adică

$$N=c_0+c_1\cdot 10+c_2\cdot 10^2+\cdots +c_p\cdot 10^p.$$

Modulo 9 avem $\widehat{10}=\hat{1}$, deci $\widehat{10^k}={\hat{1}}^k=\hat{1}$ pentru orice $k$, iar reducerea dă

$$\hat{N}=\widehat{c_0}+\widehat{c_1}+\cdots +\widehat{c_p}=\widehat{c_0+c_1+\cdots +c_p}.$$

Adică: un număr și suma cifrelor lui dau același rest la împărțirea cu $9$ (și, cu același argument, la împărțirea cu $3$).

Modulo 11 avem $\widehat{10}=\widehat{-1}$, deci $\widehat{10^k}=\widehat{(-1{)}^k}$, iar reducerea dă suma alternantă a cifrelor: $\hat{N}=\widehat{c_0-c_1+c_2-\dots }$. De aici criteriul de divizibilitate cu $11$.

Merită observat cât de puțin s-a folosit: doar faptul că reducerea păstrează adunarea și înmulțirea. Aceasta este, în fond, toată lecția.

8. Recapitularea rețetelor, într-un singur loc

Tabelul nu înlocuiește gândirea, dar scurtează primul minut al fiecărei probleme, care e și cel mai scump: alegerea drumului. Odată ales modulul, restul calculului e mecanic și se face în cinci-șase rânduri. Aceste șase rânduri acoperă aproape tot ce se cere la Bacalaureat M1 din acest capitol; le vei regăsi, alături de restul unității, în sinteza unității de legi de compoziție și grupuri.

Exemple rezolvate

Exemplul 1 — O divizibilitate clasică

Arătați că $3\mid n^3-n$ pentru orice $n\in \mathbb{Z}$ și deduceți că produsul a trei numere naturale consecutive se divide cu $3$.

Rezolvare. Reducem modulo $3$: pentru $\hat{n}=\hat{0}$ obținem $\hat{0}-\hat{0}=\hat{0}$; pentru $\hat{n}=\hat{1}$, $\hat{1}-\hat{1}=\hat{0}$; pentru $\hat{n}=\hat{2}$, $\hat{8}-\hat{2}=\hat{2}-\hat{2}=\hat{0}$. Toate clasele dau $\hat{0}$, deci $3\mid n^3-n$.

Cum $n^3-n=(n-1)n(n+1)$, rezultatul spune exact că produsul a trei numere consecutive se divide cu $3$.

Exemplul 2 — Ultima cifră a unei sume de puteri

Determinați ultima cifră a numărului $3^{2026}+7^{2026}$.

Rezolvare. Lucrăm în ${\mathbb{Z}}_{10}$. Puterile lui $\hat{3}$ sunt $\hat{3},\hat{9},\hat{7},\hat{1}$, deci $\mathrm{ord}(\hat{3})=4$; puterile lui $\hat{7}$ sunt $\hat{7},\hat{9},\hat{3},\hat{1}$, deci $\mathrm{ord}(\hat{7})=4$. Din $2026=4\cdot 506+2$ obținem

$${\hat{3}}^{2026}={\hat{3}}^2=\hat{9},{\hat{7}}^{2026}={\hat{7}}^2=\hat{9},{\hat{3}}^{2026}+{\hat{7}}^{2026}=\hat{9}+\hat{9}=\widehat{18}=\hat{8}.$$

Ultima cifră este $8$.

Exemplul 3 — Un rest, obținut cu Consecința 2 a teoremei lui Lagrange

Determinați restul împărțirii numărului $2^{2026}+5^{2026}$ la $7$.

Rezolvare. Ambele baze sunt prime cu $7$, iar $\mathrm{card}U({\mathbb{Z}}_7)=6$, deci ${\hat{2}}^6={\hat{5}}^6=\hat{1}$. Din $2026=6\cdot 337+4$ rămâne de calculat puterea a patra a fiecăreia:

$${\hat{2}}^4=\widehat{16}=\hat{2},{\hat{5}}^4={\left({\hat{5}}^2\right)}^2={\hat{4}}^2=\widehat{16}=\hat{2}.$$

Prin urmare ${\hat{2}}^{2026}+{\hat{5}}^{2026}=\hat{2}+\hat{2}=\hat{4}$, iar restul căutat este $4$.

(Pentru $\hat{2}$ se putea merge și mai repede: ${\hat{2}}^3=\hat{8}=\hat{1}$, deci $\mathrm{ord}(\hat{2})=3$, iar $2026=3\cdot 675+1$ dă tot $\hat{2}$.)

Exemplul 4 — O ecuație fără soluții

Arătați că ecuația $x^2+y^2=2023$ nu are soluții în $\mathbb{Z}\times \mathbb{Z}$.

Rezolvare. Reducem modulo $4$. Pătratele claselor sunt $\hat{0},\hat{1},\hat{0},\hat{1}$, deci ${\hat{x}}^2,{\hat{y}}^2\in \{\hat{0},\hat{1}\}$ și ${\hat{x}}^2+{\hat{y}}^2\in \{\hat{0},\hat{1},\hat{2}\}$. Pe de altă parte, $2023=4\cdot 505+3$, deci $\widehat{2023}=\hat{3}$, clasă care nu apare printre valorile posibile ale membrului stâng. Ecuația nu are soluții întregi. $■$

Exemplul 5 — O ecuație liniară rezolvată complet

Rezolvați în $\mathbb{Z}\times \mathbb{Z}$ ecuația $5x+12y=7$.

Rezolvare. Reducem modulo $5$, ca să dispară primul termen: $\widehat{12}\cdot \hat{y}=\hat{7}$, adică $\hat{2}\hat{y}=\hat{2}$ în ${\mathbb{Z}}_5$. Clasa $\hat{2}$ este inversabilă, cu ${\hat{2}}^{-1}=\hat{3}$ (fiindcă $\hat{2}\hat{3}=\hat{6}=\hat{1}$), deci $\hat{y}=\hat{3}\cdot \hat{2}=\hat{6}=\hat{1}$, adică $y=1+5k$.

Înlocuim: $5x=7-12(1+5k)=-5-60k$, deci $x=-1-12k$. Soluțiile sunt perechile $(-1-12k,1+5k)$, $k\in \mathbb{Z}$. Verificare pentru $k=0$: $5\cdot (-1)+12\cdot 1=7$. ✓

Exemplul 6 — Exemplu tip Bacalaureat M1

Se consideră mulțimea ${\mathbb{Z}}_7$ a claselor de resturi modulo $7$.

a) Determinați mulțimea $U({\mathbb{Z}}_7)$ a claselor inversabile și cardinalul ei.

b) Arătați că ${\hat{a}}^6=\hat{1}$ pentru orice $\hat{a}\in U({\mathbb{Z}}_7)$ și deduceți că $7\mid a^6-1$ pentru orice întreg $a$ nedivizibil cu $7$.

c) Determinați restul împărțirii numărului $3^{2026}$ la $7$.

Rezolvare. a) O clasă $\hat{a}$ este inversabilă dacă și numai dacă $(a,7)=1$; cum $7$ este prim, toate clasele nenule sunt inversabile:

$$U({\mathbb{Z}}_7)=\left\{\hat{1},\hat{2},\hat{3},\hat{4},\hat{5},\hat{6}\right\},\mathrm{card}U({\mathbb{Z}}_7)=6.$$

b) $(U({\mathbb{Z}}_7),\cdot )$ este grup finit cu $6$ elemente. Conform Consecinței 2 a teoremei lui Lagrange, $x^{\mathrm{card}G}=e$ pentru orice element al unui grup finit, deci ${\hat{a}}^6=\hat{1}$ pentru orice $\hat{a}\in U({\mathbb{Z}}_7)$. Revenind la numere întregi: dacă $7\nmid a$, atunci $\hat{a}\in U({\mathbb{Z}}_7)$, deci $\widehat{a^6}=\hat{1}$, adică $\widehat{a^6-1}=\hat{0}$ și $7\mid a^6-1$.

c) Cum $(3,7)=1$, punctul b) dă ${\hat{3}}^6=\hat{1}$. Din $2026=6\cdot 337+4$ obținem ${\hat{3}}^{2026}={\hat{3}}^4$. Calculăm: ${\hat{3}}^2=\hat{9}=\hat{2}$, deci ${\hat{3}}^4={\hat{2}}^2=\hat{4}$. Restul împărțirii lui $3^{2026}$ la $7$ este $4$.

Să exersăm

La fiecare problemă, scrie întâi în ce mulțime ${\mathbb{Z}}_n$ lucrezi și de ce ai ales acel $n$. La divizibilități, verifică toate clasele, nu doar câteva.

1. Determină ultima cifră a numărului $9^{2026}$.

2. Determină restul împărțirii lui $4^{2026}$ la $9$.

3. Arată că $2\mid n^2+n$ pentru orice $n$ întreg.

4. (Adevărat/Fals cu motivare.) „Dacă $\hat{a}=\hat{b}$ în ${\mathbb{Z}}_n$, atunci $a=b$."

5. Arată că $5\mid n^5-n$ pentru orice $n$ întreg.

6. Determină toate clasele $\hat{x}$ din ${\mathbb{Z}}_9$ pentru care ${\hat{x}}^2=\hat{0}$.

7. Arată că un pătrat perfect nu se poate termina cu cifra $2$, $3$, $7$ sau $8$.

8. Determină mulțimea $U({\mathbb{Z}}_{12})$ și verifică pe două dintre elementele ei că ${\hat{a}}^4=\hat{1}$.

9. Rezolvă în ${\mathbb{Z}}_{10}$ ecuația $\hat{7}\cdot \hat{x}=\hat{3}$ și deduce soluțiile întregi ale ecuației $7x-10y=3$.

10. (Adevărat/Fals cu motivare.) „Dacă o ecuație are soluții modulo $5$, atunci ea are soluții și în numere întregi."

11. Arată că ecuația $x^2=3y+2$ nu are soluții în numere întregi.

12. (Problemă aplicată.) Un plan de întreținere a unui utilaj se repetă din $6$ în $6$ zile, iar astăzi, în ziua $0$, s-a făcut revizia mare. În ce zi a ciclului va cădea ziua a $2026$-a? Rezolvă folosind clase de resturi.

13. Determină ultimele două cifre ale numărului $3^{2026}$.

14. Arată că $n^2+1$ nu se divide cu $3$, oricare ar fi $n$ întreg.

15. (Exercițiu tip Bacalaureat M1.) Se consideră ${\mathbb{Z}}_{10}$. a) Determină $U({\mathbb{Z}}_{10})$ și cardinalul ei. b) Arată că ${\hat{3}}^4=\hat{1}$ și determină $\mathrm{ord}(\hat{3})$. c) Determină ultima cifră a numărului $3^{2026}+3^{2027}$.

16. Rezolvă în $\mathbb{Z}\times \mathbb{Z}$ ecuația $3x+7y=5$.

17. Arată că ecuația $x^3=7y+2$ nu are soluții în numere întregi.

18. (Provocare.) Arată că, pentru orice $n$ întreg, numărul $n^{13}-n$ se divide cu $2$, cu $3$, cu $5$, cu $7$ și cu $13$, deci se divide cu $2730$.

Răspunsuri și explicații

1. În ${\mathbb{Z}}_{10}$: ${\hat{9}}^2=\widehat{81}=\hat{1}$, deci $\mathrm{ord}(\hat{9})=2$. Cum $2026$ este par, ${\hat{9}}^{2026}=\hat{1}$ și ultima cifră este $1$.

2. În ${\mathbb{Z}}_9$: ${\hat{4}}^2=\widehat{16}=\hat{7}$, ${\hat{4}}^3=\hat{7}\hat{4}=\widehat{28}=\hat{1}$, deci $\mathrm{ord}(\hat{4})=3$. Din $2026=3\cdot 675+1$ rezultă ${\hat{4}}^{2026}=\hat{4}$, deci restul este $4$.

3. Modulo $2$: pentru $\hat{n}=\hat{0}$, $\hat{0}+\hat{0}=\hat{0}$; pentru $\hat{n}=\hat{1}$, $\hat{1}+\hat{1}=\hat{0}$. Ambele clase dau $\hat{0}$. (Este și evident: $n^2+n=n(n+1)$, produs de numere consecutive.)

4. Fals. Egalitatea $\hat{a}=\hat{b}$ înseamnă doar $n\mid (a-b)$, adică cele două numere dau același rest la împărțirea cu $n$. De pildă, în ${\mathbb{Z}}_5$ avem $\hat{2}=\hat{7}$, dar $2\ne 7$. Clasa reține doar restul, nu numărul.

5. Modulo $5$: ${\hat{0}}^5-\hat{0}=\hat{0}$; ${\hat{1}}^5-\hat{1}=\hat{0}$; ${\hat{2}}^5=\widehat{32}=\hat{2}$, deci diferența e $\hat{0}$; ${\hat{3}}^5=\widehat{243}=\hat{3}$; ${\hat{4}}^5=\widehat{1024}=\hat{4}$. Toate cele cinci clase dau $\hat{0}$.

6. Calculăm pătratele: ${\hat{0}}^2=\hat{0}$, ${\hat{3}}^2=\hat{0}$, ${\hat{6}}^2=\widehat{36}=\hat{0}$, iar celelalte clase dau pătrate nenule ($\hat{1},\hat{4},\hat{7},\hat{7},\hat{4},\hat{1}$). Deci $\hat{x}\in \{\hat{0},\hat{3},\hat{6}\}$.

7. Ultima cifră a lui $n^2$ este clasa lui ${\hat{n}}^2$ în ${\mathbb{Z}}_{10}$. Calculând pătratele celor zece clase, obținem mulțimea $\{\hat{0},\hat{1},\hat{4},\hat{9},\hat{6},\hat{5}\}$, adică cifrele $0,1,4,5,6,9$. Cifrele $2,3,7,8$ nu apar niciodată.

8. $U({\mathbb{Z}}_{12})=\{\hat{1},\hat{5},\hat{7},\widehat{11}\}$, cu $4$ elemente. Verificare: ${\hat{5}}^2=\widehat{25}=\hat{1}$, deci ${\hat{5}}^4=\hat{1}$; ${\hat{7}}^2=\widehat{49}=\hat{1}$, deci ${\hat{7}}^4=\hat{1}$.

9. ${\hat{7}}^{-1}=\hat{3}$, pentru că $\widehat{21}=\hat{1}$. Deci $\hat{x}=\hat{3}\cdot \hat{3}=\hat{9}$ și $x=9+10k$. Atunci $y=\frac{7x-3}{10}=6+7k$, iar soluțiile sunt $(9+10k,6+7k)$, $k\in \mathbb{Z}$.

10. Fals. Contraexemplul e chiar ecuația din Exemplul 4: $x^2+y^2=2023$. Modulo $5$, pătratele sunt $\hat{0},\hat{1},\hat{4}$, iar $2023=5\cdot 404+3$, deci membrul drept e $\hat{3}$; alegerea $\hat{x}=\hat{y}=\hat{2}$ dă $\hat{4}+\hat{4}=\hat{8}=\hat{3}$, deci ecuația are soluții modulo $5$. Cu toate acestea, am arătat prin reducere modulo $4$ că nu are nicio soluție întreagă. Reducerea respinge, dar nu confirmă.

11. Reducem modulo $3$: ${\hat{x}}^2=\hat{2}$. Pătratele în ${\mathbb{Z}}_3$ sunt $\hat{0}$ și $\hat{1}$, deci $\hat{2}$ nu poate fi pătrat. Ecuația nu are soluții.

12. Zilele ciclului sunt clasele din ${\mathbb{Z}}_6$. Cum $2026=6\cdot 337+4$, avem $\widehat{2026}=\hat{4}$: ziua a $2026$-a cade în a patra zi a ciclului. Reviziile mari, în ziua $\hat{0}$, cad la zilele $0,6,12,\dots$, iar $2026$ nu e printre ele.

13. În ${\mathbb{Z}}_{100}$: ${\hat{3}}^4=\widehat{81}$, ${\hat{3}}^5=\widehat{243}=\widehat{43}$, ${\hat{3}}^{10}={\widehat{43}}^2=\widehat{1849}=\widehat{49}$, ${\hat{3}}^{20}={\widehat{49}}^2=\widehat{2401}=\hat{1}$. Deci $\mathrm{ord}(\hat{3})=20$ și, cum $2026=20\cdot 101+6$, avem ${\hat{3}}^{2026}={\hat{3}}^6=\widehat{729}=\widehat{29}$. Ultimele două cifre sunt $29$.

14. Modulo $3$, pătratele sunt $\hat{0}$ și $\hat{1}$, deci ${\hat{n}}^2+\hat{1}\in \{\hat{1},\hat{2}\}$, niciodată $\hat{0}$. Prin urmare $3\nmid n^2+1$.

15. a) $U({\mathbb{Z}}_{10})=\{\hat{1},\hat{3},\hat{7},\hat{9}\}$, cu $4$ elemente. b) ${\hat{3}}^2=\hat{9}$, ${\hat{3}}^3=\widehat{27}=\hat{7}$, ${\hat{3}}^4=\widehat{21}=\hat{1}$; niciun exponent mai mic nu dă $\hat{1}$, deci $\mathrm{ord}(\hat{3})=4$. c) $2026=4\cdot 506+2$, deci ${\hat{3}}^{2026}=\hat{9}$ și ${\hat{3}}^{2027}={\hat{3}}^3=\hat{7}$; suma este $\hat{9}+\hat{7}=\widehat{16}=\hat{6}$. Ultima cifră este $6$.

16. Reducem modulo $3$: $\hat{7}\hat{y}=\hat{5}$, adică $\hat{1}\hat{y}=\hat{2}$, deci $\hat{y}=\hat{2}$ și $y=2+3k$. Atunci $3x=5-7(2+3k)=-9-21k$, deci $x=-3-7k$. Soluțiile: $(-3-7k,2+3k)$, $k\in \mathbb{Z}$. Verificare pentru $k=0$: $3\cdot (-3)+7\cdot 2=5$. ✓

17. Reducem modulo $7$: ${\hat{x}}^3=\hat{2}$. Cuburile în ${\mathbb{Z}}_7$ sunt $\hat{0},\hat{1},\hat{1},\hat{6},\hat{1},\hat{6},\hat{6}$, adică mulțimea $\{\hat{0},\hat{1},\hat{6}\}$, care nu-l conține pe $\hat{2}$. Ecuația nu are soluții.

18. Pentru fiecare dintre numerele prime $p\in \{2,3,5,7,13\}$, observăm că $p-1$ divide $12$: anume $1,2,4,6,12$. Dacă $p\nmid n$, atunci $\hat{n}\in U({\mathbb{Z}}_p)$, care are $p-1$ elemente, deci ${\hat{n}}^{p-1}=\hat{1}$ (Consecința 2 a teoremei lui Lagrange) și, cum $p-1\mid 12$, rezultă ${\hat{n}}^{12}=\hat{1}$, adică ${\hat{n}}^{13}=\hat{n}$. Dacă $p\mid n$, atunci $\hat{n}=\hat{0}$ și egalitatea ${\hat{n}}^{13}=\hat{n}$ e imediată. Deci $p\mid n^{13}-n$ pentru toate cele cinci numere prime; fiind distincte, produsul lor $2\cdot 3\cdot 5\cdot 7\cdot 13=2730$ divide și el $n^{13}-n$.

De reținut

• Reducerea modulo $n$ păstrează adunarea și înmulțirea, deci orice expresie polinomială cu coeficienți întregi se poate calcula direct pe clase, iar $n$ divide un număr exact când clasa lui este $\hat{0}$.
• O divizibilitate valabilă pentru orice număr întreg se demonstrează verificând un număr finit de clase, iar pentru un modul compus se lucrează separat cu factorii lui primi între ei.
• Ultima cifră a unei puteri se află în ${\mathbb{Z}}_{10}$: se determină ordinul clasei bazei, se împarte exponentul la acest ordin și se păstrează restul.
• Consecința 2 a teoremei lui Lagrange, aplicată grupului claselor inversabile, dă ${\hat{a}}^m=\hat{1}$ pentru orice clasă inversabilă, unde $m$ este cardinalul acestui grup — de aici toate calculele de resturi ale puterilor mari.
• O ecuație în numere întregi nu are soluții dacă există un modul pentru care ecuația redusă nu are soluții; reciproca este falsă, deci metoda respinge, dar nu confirmă.

Greșeli frecvente

• Se verifică doar câteva clase. O divizibilitate „pentru orice $n$" cere toate cele $n$ clase; două-trei valori particulare nu demonstrează nimic, oricât de convingătoare ar părea.
• Se combină factori care nu sunt primi între ei. Din $4\mid k$ și $6\mid k$ nu rezultă $24\mid k$: numărul $12$ e un contraexemplu. Regula funcționează numai când factorii sunt primi între ei doi câte doi.
• Se aplică ${\hat{a}}^m=\hat{1}$ unei clase neinversabile. Condiția $(a,n)=1$ trebuie verificată explicit; pentru $\hat{2}$ în ${\mathbb{Z}}_{10}$ nicio putere nu dă $\hat{1}$, iar formula devine falsă.
• Se confundă criteriul de respingere cu unul de existență. Faptul că o ecuație are soluții modulo $n$ nu spune nimic despre soluțiile ei întregi; concluzia se trage doar când ecuația redusă nu are soluții.
• Se simplifică nepermis într-o ecuație cu clase. Din $\hat{4}\hat{x}=\hat{4}\hat{y}$ în ${\mathbb{Z}}_6$ nu rezultă $\hat{x}=\hat{y}$, pentru că $\hat{4}$ nu e inversabilă; simplificarea e permisă numai prin înmulțire cu inversa, deci numai când clasa e inversabilă.

Aplică acasă

1. Tabelul puterilor. Alege trei numere de o cifră și scrie, pentru fiecare, ciclul puterilor lui modulo $10$, până se repetă. Notează lungimea fiecărui ciclu și verifică apoi, pe calculator, ultima cifră a puterii a $50$-a a fiecărui număr.

2. Vânătoarea de ecuații imposibile. Scrie cinci ecuații de forma $x^2+y^2=N$ cu $N$ ales de tine și decide, doar prin reducere modulo $4$, care dintre ele sigur nu au soluții. Pentru cele rămase, caută efectiv o soluție cu numere mici.

3. Criteriul cu $11$. Ia zece numere de câte cinci cifre și verifică, prin suma alternantă a cifrelor, care dintre ele se divid cu $11$. Confirmă apoi împărțind efectiv și explică, în două rânduri, de ce funcționează criteriul.

Pentru părinți și profesori

Lecția este aplicația aritmetică a întregii unități: structura algebrică construită abstract în lecțiile precedente devine aici un instrument de calcul pentru probleme de divizibilitate și pentru ecuații în numere întregi, exact cum cere programa la competența XII.CS.6.1. Este și una dintre puținele lecții din clasa a XII-a care leagă direct materia de gimnaziu (criteriile de divizibilitate) de teoria grupurilor.

De verificat în caiet: (1) la fiecare divizibilitate sunt scrise toate clasele, într-un tabel, nu doar cele „interesante"; (2) înainte de a folosi ${\hat{a}}^m=\hat{1}$ este verificată condiția $(a,n)=1$; (3) la calculul unui rest se scrie explicit împărțirea exponentului la ordin, cu cât și rest; (4) la ecuațiile fără soluții se precizează de ce a fost ales tocmai acel modul. Întrebări de control: „De ce e destul să verifici $n$ cazuri?"; „Ce grup are $\mathrm{card}U({\mathbb{Z}}_{10})=4$ și ce spune Consecința 2 despre el?"; „De ce reducerea nu poate demonstra că o ecuație are soluții?".

La BAC M1, materialul apare în Subiectul al II-lea, la problema de structuri algebrice, de obicei sub forma: se dă ${\mathbb{Z}}_n$, se cer clasele inversabile, apoi o ecuație cu clase și, la punctul c), un rest sau o ultimă cifră. Semn că elevul a înțeles: în fața unui exponent uriaș, prima lui mișcare este să caute ordinul clasei bazei, nu să încerce calcule directe.

Întrebări frecvente

Ce înseamnă să rezolvi o problemă „modulo n" la clasa a 12-a? Înseamnă să înlocuiești fiecare număr întreg cu clasa lui de resturi din ${\mathbb{Z}}_n$ și să lucrezi acolo. Fiindcă adunarea și înmulțirea claselor se fac exact ca la numere, orice egalitate între expresii întregi rămâne adevărată după reducere. Câștigul e uriaș: o infinitate de cazuri devine un număr finit, cel mult $n$.

Cum se află ultima cifră a unei puteri mari? Se lucrează în ${\mathbb{Z}}_{10}$, unde ultima cifră este chiar clasa numărului. Se calculează puterile succesive ale clasei bazei până se ajunge iar la ea, obținând ordinul; apoi se împarte exponentul la acest ordin și se păstrează restul. Puterea cu exponentul rest dă răspunsul.

Care este formula care dă restul unei puteri mari? Dacă $(a,n)=1$ și $m$ este numărul claselor inversabile din ${\mathbb{Z}}_n$, atunci ${\hat{a}}^m=\hat{1}$, ceea ce este Consecința 2 a teoremei lui Lagrange aplicată grupului claselor inversabile. Se împarte exponentul la $m$ și rămâne de calculat doar puterea cu exponentul rest, un calcul scurt.

Cum arăți că o ecuație nu are soluții în numere întregi? Se alege un modul $n$ potrivit și se reduce ecuația: dacă mulțimea valorilor posibile ale membrului stâng nu conține clasa membrului drept, ecuația nu are soluții. Pentru ecuații cu pătrate se încearcă $n$ egal cu $3$, $4$, $5$ sau $8$; pentru cuburi, $7$ sau $9$; pentru a elimina un termen, un divizor al coeficientului lui.

De ce nu se poate demonstra astfel că o ecuație are soluții? Pentru că reducerea pierde informație: două numere foarte diferite pot avea aceeași clasă. Existența unei soluții modulo $n$ înseamnă doar că nu apare o contradicție la acel modul, nu că există numere întregi care verifică efectiv ecuația. Metoda este, prin natura ei, doar un criteriu de respingere.

Când se poate simplifica într-o ecuație cu clase de resturi? Numai când clasa cu care simplifici este inversabilă, adică atunci când reprezentantul ei este prim cu $n$; simplificarea înseamnă, de fapt, înmulțirea cu inversa. În ${\mathbb{Z}}_6$, de pildă, din $\hat{4}\hat{x}=\hat{4}\hat{y}$ nu rezultă $\hat{x}=\hat{y}$, fiindcă $\hat{4}$ nu are invers.

De ce un număr și suma cifrelor lui dau același rest la împărțirea cu 9? Pentru că, modulo $9$, avem $\widehat{10}=\hat{1}$, deci orice putere a lui $10$ are clasa $\hat{1}$. Scriind numărul ca sumă de cifre înmulțite cu puteri ale lui $10$ și reducând, toate puterile devin $\hat{1}$ și rămâne exact suma cifrelor. Același argument, cu $\widehat{10}=\widehat{-1}$, dă criteriul pentru $11$.