Mulțimea claselor de resturi modulo n; adunarea claselor

Este ora $21$ și vrei să știi cât e ceasul peste $8$ ore. Nu răspunzi „ora $29$", ci „ora $5$", pentru că ceasul nu numără la nesfârșit: după $24$ o ia de la capăt. Ai făcut, fără să-i spui pe nume, o adunare cu clase de resturi modulo $24$ — operația pe care o construim riguros în lecția aceasta, prima structură concretă și finită din programa de clasa a 12-a, mate-info. Clasele de resturi modulo $n$ sunt cele $n$ grămezi în care se împart numerele întregi după restul împărțirii cu $n$; mulțimea lor se notează ${\mathbb{Z}}_n$ și se adună element cu element, exact ca orele pe cadran.

Ideea e neașteptat de folositoare. În loc să lucrăm cu numere întregi, lucrăm cu grămezile în care le împarte restul la $n$: toți întregii care dau restul $0$, toți cei care dau restul $1$, și așa mai departe. Se obține o mulțime cu exact $n$ elemente, pe care adunarea funcționează la fel de bine ca pe $\mathbb{Z}$ — dar pe care se poate scrie o tablă completă, se pot număra elementele și se pot verifica proprietățile una câte una, așa cum am făcut cu tablele din Tabla unei legi de compoziție pe o mulțime finită. Este exemplul-etalon al întregii unități, iar la Bacalaureat M1 el revine an de an, în Subiectul al II-lea. Lecția aceasta se ocupă numai de adunare; înmulțirea claselor vine imediat după, în Înmulțirea claselor de resturi modulo n.

Ce vei învăța

• Vei ști să definești clasa de resturi $\hat{a}$ ca mulțime de numere întregi și să scrii câțiva dintre elementele ei.
• Vei ști să decizi când două clase sunt egale, folosind criteriul $\hat{a}=\hat{b}⟺n\mid (a-b)$.
• Vei ști să scrii mulțimea ${\mathbb{Z}}_n$ și să explici de ce are exact $n$ elemente.
• Vei ști să aduni două clase și să demonstrezi că definiția nu depinde de reprezentanții aleși.
• Vei ști să alcătuiești și să citești tabla adunării pe ${\mathbb{Z}}_n$, pentru $n\le 8$.
• Vei ști să determini opusul unei clase și să rezolvi ecuații de gradul întâi cu clase de resturi.

Hai să descoperim împreună

1. Ce este o clasă de resturi modulo $n$?

Clasa de resturi $\hat{a}$ modulo $n$ este mulțimea tuturor numerelor întregi care dau același rest ca $a$ la împărțirea cu $n$, adică $\hat{a}=\{a+kn\mid k\in \mathbb{Z}\}$; numărul $a$ se numește un reprezentant al clasei, iar $n$ este un număr natural fixat, $n\ge 2$. Punctul de plecare este teorema împărțirii cu rest: pentru orice $a\in \mathbb{Z}$ există numerele întregi $q$ și $r$, unic determinate, cu $a=nq+r$ și $0\le r<n$.

Să vedem clasele modulo $3$, scrise ca mulțimi:

$$\hat{0}=\{\dots ,-6,-3,0,3,6,\dots \},\hat{1}=\{\dots ,-5,-2,1,4,7,\dots \},\hat{2}=\{\dots ,-4,-1,2,5,8,\dots \}.$$

Observă unde stau numerele negative. Numărul $-7$ se scrie $-7=3\cdot (-3)+2$, deci restul lui este $2$, nu $-1$: restul din teorema împărțirii cu rest este întotdeauna nenegativ și mai mic decât $n$. Așadar $-7\in \hat{2}$. Este cea mai frecventă greșeală de început, iar la Bacalaureat M1 costă imediat punctajul.

O clasă are infinit de multe nume. Mulțimea $\hat{2}$ modulo $3$ este aceeași cu $\hat{5}$, cu $\hat{8}$ sau cu $\widehat{-1}$ — sunt aceeași grămadă de numere, descrisă prin reprezentanți diferiți. Prin convenție, scriem clasele cu reprezentantul din $\{0,1,\dots ,n-1\}$, adică chiar cu restul.

2. Când sunt egale două clase de resturi?

Criteriul este simplu și se demonstrează în trei rânduri. Propoziție. Pentru orice $a,b\in \mathbb{Z}$ are loc echivalența

$$\hat{a}=\hat{b}⟺n\mid (a-b).$$

Demonstrație. Dacă $\hat{a}=\hat{b}$, atunci, cum $a\in \hat{a}$, avem $a\in \hat{b}$, deci $a=b+kn$ pentru un $k\in \mathbb{Z}$, adică $a-b=kn$ și $n\mid (a-b)$. Invers, dacă $n\mid (a-b)$, scriem $a=b+kn$. Atunci orice element $a+tn$ al lui $\hat{a}$ se scrie $b+(k+t)n$, deci aparține lui $\hat{b}$, și reciproc; prin urmare cele două mulțimi coincid. $■$

Criteriul se folosește în ambele sensuri. De pildă, $\widehat{17}=\hat{5}$ în ${\mathbb{Z}}_n$ exact pentru acei $n$ care divid $17-5=12$, adică pentru $n\in \{2,3,4,6,12\}$. Iar în ${\mathbb{Z}}_6$ avem $\widehat{47}=\hat{5}$, pentru că $47-5=42=6\cdot 7$; același lucru se vede și direct, din $47=6\cdot 7+5$.

O consecință imediată: $\hat{a}=\hat{r}$, unde $r$ este restul împărțirii lui $a$ la $n$, pentru că $a-r=nq$ se divide cu $n$. Reducerea la reprezentantul standard este, deci, exact împărțirea cu rest.

(În alte cărți relația $n\mid (a-b)$ se scrie $a\equiv b(\mathrm{mod}n)$ și se citește „$a$ este congruent cu $b$ modulo $n$". Noi nu vom folosi notația aceasta: tot ce ne trebuie se exprimă prin egalitatea claselor.)

3. Ce este mulțimea ${\mathbb{Z}}_n$ și cum se împarte $\mathbb{Z}$ în clase?

Notăm cu ${\mathbb{Z}}_n$ mulțimea tuturor claselor de resturi modulo $n$:

$${\mathbb{Z}}_n=\left\{\hat{0},\hat{1},\hat{2},\dots ,\widehat{n-1}\right\}.$$

Mulțimea are exact $n$ elemente, și merită spus de ce. Pe de o parte, orice clasă $\hat{a}$ este egală cu $\hat{r}$, unde $r$ este restul lui $a$, deci lista de mai sus le epuizează pe toate. Pe de altă parte, clasele din listă sunt distincte două câte două: dacă $\hat{i}=\hat{j}$ cu $0\le i,j\le n-1$, atunci $n\mid (i-j)$, iar cum diferența are modulul strict mai mic decât $n$, singura posibilitate este $i=j$.

Mai mult, cele $n$ clase sunt disjuncte și acoperă tot $\mathbb{Z}$:

$$\mathbb{Z}=\hat{0}\cup \hat{1}\cup \cdots \cup \widehat{n-1},\hat{i}\cap \hat{j}=\varnothing \text{ pentru }i\ne j.$$

Fiecare număr întreg cade într-o clasă și numai în una — cea dată de restul lui. Așa arată, în cea mai curată formă, împărțirea unei mulțimi infinite într-un număr finit de grămezi. Pentru $n=2$ obținem exact numerele pare și impare, iar pentru $n=12$, cadranul ceasului.

Merită observat cât de mult câștigăm prin această trecere. Mulțimea $\mathbb{Z}$ este infinită, deci despre ea nu se poate spune nimic prin verificarea tuturor cazurilor; despre ${\mathbb{Z}}_n$, în schimb, se poate spune totul, pentru că are un număr finit de elemente. Afirmația „suma a două numere impare este pară" devine, în ${\mathbb{Z}}_2$, o singură egalitate: $\hat{1}+\hat{1}=\hat{2}=\hat{0}$, iar $\hat{0}$ este exact clasa numerelor pare. Aceasta este metoda pe care o folosesc problemele de divizibilitate rezolvate cu clase de resturi: în loc să lucrezi cu toți întregii, lucrezi cu cei $n$ reprezentanți și acoperi astfel toate situațiile posibile. Noutatea lui ${\mathbb{Z}}_n$ nu este, deci, faptul că putem scrie tabla unei operații — asta am făcut și pe alte mulțimi finite — ci că o mulțime infinită a fost strânsă, fără pierdere de informație, în $n$ elemente.

4. Adunarea claselor: o definiție prin reprezentanți

Vrem o operație pe ${\mathbb{Z}}_n$, deci o lege de compoziție $+:{\mathbb{Z}}_n\times {\mathbb{Z}}_n\to {\mathbb{Z}}_n$. Cel mai natural este să adunăm reprezentanții:

$$\hat{a}+\hat{b}=\widehat{a+b}.$$

Cu alte cuvinte: iei un număr din prima clasă, unul din a doua, le aduni ca numere întregi și te uiți în ce clasă a căzut suma. În ${\mathbb{Z}}_5$, de pildă, $\hat{3}+\hat{4}=\hat{7}=\hat{2}$, pentru că $7=5\cdot 1+2$.

Definiția are însă o slăbiciune care sare în ochi dacă privești atent: rezultatul pare să depindă de reprezentanții aleși. Clasa $\hat{3}$ este aceeași cu $\widehat{13}$, iar $\hat{4}$ este aceeași cu $\widehat{-1}$. Dacă adunăm noii reprezentanți obținem $13+(-1)=12$, iar $\widehat{12}=\hat{2}$, pentru că $12=5\cdot 2+2$. Am obținut același rezultat — dar coincidența trebuie transformată în teoremă.

5. De ce trebuie demonstrată buna definire a adunării?

Pentru că o „definiție" care depinde de alegeri arbitrare nu este o definiție. Dacă doi elevi ar alege reprezentanți diferiți și ar obține clase diferite, operația nu ar fi o funcție, iar tot ce am construi peste ea s-ar prăbuși. Proprietatea care ne salvează se numește buna definire și se demonstrează, nu se presupune.

Teoremă (buna definire a adunării). Fie $a,a_1,b,b_1\in \mathbb{Z}$ cu $\hat{a}=\widehat{a_1}$ și $\hat{b}=\widehat{b_1}$. Atunci $\widehat{a+b}=\widehat{a_1+b_1}$.

Demonstrație. Din $\hat{a}=\widehat{a_1}$ rezultă, prin criteriul de la punctul 2, că $n\mid (a-a_1)$, deci $a-a_1=kn$ cu $k\in \mathbb{Z}$. Analog, $b-b_1=ln$ cu $l\in \mathbb{Z}$. Adunând cele două egalități obținem

$$(a+b)-(a_1+b_1)=(a-a_1)+(b-b_1)=kn+ln=(k+l)n,$$

deci $n\mid [(a+b)-(a_1+b_1)]$, adică $\widehat{a+b}=\widehat{a_1+b_1}$. $■$

Prin urmare adunarea claselor este o lege de compoziție bine definită pe ${\mathbb{Z}}_n$: rezultatul depinde numai de clase, nu de reprezentanți. Verificarea numerică din ${\mathbb{Z}}_5$ de mai sus era, deci, obligatorie să iasă.

Ca să vezi că grija nu e formală, iată o „operație" care nu este bine definită. Definim, tot pe reprezentanți, $\hat{a}\ast \hat{b}=\widehat{\max (a,b)}$. În ${\mathbb{Z}}_5$, cu reprezentanții $1$ și $2$ obținem $\widehat{\max (1,2)}=\hat{2}$; dar $\hat{1}=\hat{6}$, iar cu reprezentanții $6$ și $2$ obținem $\widehat{\max (6,2)}=\hat{6}=\hat{1}$. Două rezultate diferite pentru aceleași două clase — deci $\ast$ nu este o operație pe ${\mathbb{Z}}_5$. Diferența dintre cele două situații stă în faptul că adunarea se „împacă" cu divizibilitatea cu $n$, iar maximul nu.

6. Ce proprietăți moștenește adunarea claselor de la numerele întregi?

Toate proprietățile se obțin din cele ale adunării pe $\mathbb{Z}$, trecute prin definiție. Fie $\hat{a},\hat{b},\hat{c}\in {\mathbb{Z}}_n$.

Asociativitatea:

$$\left(\hat{a}+\hat{b}\right)+\hat{c}=\widehat{a+b}+\hat{c}=\widehat{(a+b)+c}=\widehat{a+(b+c)}=\hat{a}+\widehat{b+c}=\hat{a}+\left(\hat{b}+\hat{c}\right).$$

Pasul din mijloc este singurul care „lucrează": el folosește asociativitatea adunării pe $\mathbb{Z}$. Restul sunt aplicări ale definiției.

Comutativitatea: $\hat{a}+\hat{b}=\widehat{a+b}=\widehat{b+a}=\hat{b}+\hat{a}$, din comutativitatea adunării întregilor.

Elementul neutru: $\hat{a}+\hat{0}=\widehat{a+0}=\hat{a}$, deci $\hat{0}$ este element neutru, în sensul fixat în Elementul neutru al unei legi de compoziție.

Opusul: pentru orice $\hat{a}$ avem $\hat{a}+\widehat{-a}=\widehat{a+(-a)}=\hat{0}$, deci fiecare clasă este simetrizabilă, iar opusul ei este $-\hat{a}=\widehat{-a}$. Scris cu reprezentantul standard, pentru $a\in \{1,2,\dots ,n-1\}$ obținem

$$-\hat{a}=\widehat{n-a},\text{iar}-\hat{0}=\hat{0}.$$

În ${\mathbb{Z}}_7$, de pildă, opusele sunt, în ordine, $\hat{0},\hat{6},\hat{5},\hat{4},\hat{3},\hat{2},\hat{1}$: fiecare clasă și opusa ei dau împreună $\hat{7}=\hat{0}$.

Punând totul cap la cap: $({\mathbb{Z}}_n,+)$ este un monoid comutativ în care toate elementele sunt simetrizabile — structura pe care am descris-o în Semigrupuri și monoizi și căreia îi vom da un nume în unitatea următoare. Notația simetricului este cea aditivă, $-\hat{a}$, iar numele este „opusul", pentru că legea se scrie cu $+$; regula este cea din Elemente simetrizabile și simetricul unui element.

7. Tabla adunării: cum se citește?

Pe o mulțime cu $n\le 8$ elemente tabla se scrie complet și se citește dintr-o privire. Iată tabla lui $({\mathbb{Z}}_4,+)$, exemplul-etalon al capitolului — este exact tabla pe care ai întâlnit-o, fără nume, drept „ceasul cu patru ore" în lecția despre tabla unei legi de compoziție: acolo scriam resturile $0,1,2,3$, aici scriem clasele $\hat{0},\hat{1},\hat{2},\hat{3}$, iar operația e aceeași.

Trei citiri, toate imediate. Comutativitatea: tabla este simetrică față de diagonala principală. Elementul neutru: linia lui $\hat{0}$ și coloana lui $\hat{0}$ reproduc antetul. Opusele: cauți $\hat{0}$ pe fiecare linie — pe linia lui $\hat{1}$ îl găsești în coloana lui $\hat{3}$, deci $-\hat{1}=\hat{3}$; pe linia lui $\hat{2}$ îl găsești în coloana lui $\hat{2}$, deci $-\hat{2}=\hat{2}$; clasa $\hat{2}$ este propriul ei opus.

Se vede și un tipar: fiecare linie este linia dinainte, deplasată cu un pas la stânga, cu elementul ieșit reintrat la capăt. Tabla se completează, deci, fără niciun calcul, iar același tipar apare la orice $n$. Pentru $({\mathbb{Z}}_5,+)$:

Aici $\hat{0}$ apare exact o dată pe fiecare linie și pe fiecare coloană, ceea ce confirmă că fiecare clasă are un opus și numai unul. Pentru $n$ mai mare de $8$ nu se mai scrie tabla; se lucrează cu formula $\hat{a}+\hat{b}=\widehat{a+b}$ și cu reducerea restului.

8. Multipli și ecuații în ${\mathbb{Z}}_n$

Legea fiind notată aditiv, puterile unui element se numesc multipli și se scriu $k\hat{a}$, adică $\hat{a}$ adunată de $k$ ori cu ea însăși. Din definiția adunării rezultă imediat

$$k\hat{a}=\underset{k\text{ termeni}}{\underbrace{\hat{a}+\hat{a}+\cdots +\hat{a}}}=\widehat{ka},k\in {\mathbb{N}}^{\ast }.$$

De pildă, în ${\mathbb{Z}}_6$ avem $4\hat{3}=\widehat{12}=\hat{0}$, iar în ${\mathbb{Z}}_7$, $5\hat{2}=\widehat{10}=\hat{3}$. Observă lucrul surprinzător din primul exemplu: adunând de patru ori o clasă nenulă am obținut clasa nulă — ceva ce nu se întâmplă niciodată cu numerele întregi.

Ecuațiile de gradul întâi se rezolvă adunând opusul, exact ca la numere. Pentru $\hat{x}+\hat{a}=\hat{b}$ adunăm $-\hat{a}$ în ambii membri și obținem $\hat{x}=\hat{b}+\widehat{n-a}$. În ${\mathbb{Z}}_7$, ecuația $\hat{x}+\hat{5}=\hat{2}$ dă $\hat{x}=\hat{2}+\hat{2}=\hat{4}$; verificare: $\hat{4}+\hat{5}=\hat{9}=\hat{2}$, corect.

Există și ecuații în care necunoscuta apare de mai multe ori, și atunci adunarea opusului nu mai ajunge. În ${\mathbb{Z}}_6$, ecuația $\hat{x}+\hat{x}+\hat{4}=\hat{1}$ devine $2\hat{x}=\hat{3}$, iar aici cea mai sigură metodă este verificarea celor $6$ clase: pentru $\hat{x}=\hat{0},\hat{1},\dots ,\hat{5}$ obținem $2\hat{x}\in \{\hat{0},\hat{2},\hat{4},\hat{0},\hat{2},\hat{4}\}$, iar $\hat{3}$ nu apare niciodată. Ecuația nu are soluții — un răspuns perfect valabil, care nu are corespondent în $\mathbb{R}$ și care apare des la Bacalaureat M1.

Aceleași unelte rezolvă și probleme de divizibilitate. Vrei restul împărțirii sumei $1+2+\cdots +100$ la $7$? Poți calcula suma, $\frac{100\cdot 101}{2}=5050$, și să o reduci: $5050=7\cdot 721+3$, deci clasa sumei este $\hat{3}$, iar restul căutat este $3$. Dar poți lucra și direct cu clasele, adunându-le în ${\mathbb{Z}}_7$ — și obții același rezultat, tocmai pentru că adunarea este bine definită. Iar dacă vrei să arăți că suma a cinci numere întregi consecutive se divide cu $5$, treci în ${\mathbb{Z}}_5$: suma claselor lor este $\hat{a}+\widehat{a+1}+\widehat{a+2}+\widehat{a+3}+\widehat{a+4}=\widehat{5a+10}=\hat{0}$, iar clasa nulă înseamnă exact rest zero. Demonstrația ține trei rânduri, față de calculul obișnuit cu paranteze, și este exact tipul de aplicație pe care programa îl cere la clasele de resturi.

Exemple rezolvate

Exemplul 1 — Clase scrise ca mulțimi

Scrie elementele lui ${\mathbb{Z}}_6$ ca mulțimi de numere întregi, apoi determină clasele lui $47$ și ale lui $-23$ în ${\mathbb{Z}}_6$.

Cele șase clase sunt $\hat{0}=\{\dots ,-6,0,6,12,\dots \}$, $\hat{1}=\{\dots ,-5,1,7,13,\dots \}$, $\hat{2}=\{\dots ,-4,2,8,\dots \}$, $\hat{3}=\{\dots ,-3,3,9,\dots \}$, $\hat{4}=\{\dots ,-2,4,10,\dots \}$, $\hat{5}=\{\dots ,-1,5,11,\dots \}$. Pentru $47$ împărțim: $47=6\cdot 7+5$, deci $\widehat{47}=\hat{5}$. Pentru $-23$ avem $-23=6\cdot (-4)+1$, cu restul $1$ nenegativ și mai mic decât $6$, deci $\widehat{-23}=\hat{1}$.

Exemplul 2 — Tabla lui $({\mathbb{Z}}_3,+)$ și citirea ei

Alcătuiește tabla adunării pe ${\mathbb{Z}}_3$ și citește din ea comutativitatea, elementul neutru și opusele.

Tabla e simetrică față de diagonala principală, deci legea este comutativă. Linia și coloana lui $\hat{0}$ reproduc antetul, deci $\hat{0}$ este element neutru. Pe linia lui $\hat{1}$, clasa $\hat{0}$ apare în coloana lui $\hat{2}$, deci $-\hat{1}=\hat{2}$; simetric, $-\hat{2}=\hat{1}$. Singura clasă egală cu opusa ei este $\hat{0}$.

Exemplul 3 — Buna definire, verificată pe numere

În ${\mathbb{Z}}_9$, verifică pe reprezentanți diferiți că $\hat{4}+\hat{7}$ dă același rezultat.

Cu reprezentanții standard: $4+7=11$, iar $11=9\cdot 1+2$, deci $\hat{4}+\hat{7}=\hat{2}$. Alegem alți reprezentanți: $\widehat{22}=\hat{4}$, pentru că $22=9\cdot 2+4$, și $\widehat{-2}=\hat{7}$, pentru că $-2=9\cdot (-1)+7$. Adunăm: $22+(-2)=20$, iar $20=9\cdot 2+2$, deci clasa este tot $\hat{2}$. Rezultatul coincide, exact cum garantează teorema bunei definiri.

Exemplul 4 — Opusele și clasele egale cu opusul lor

În ${\mathbb{Z}}_8$, determină opusul fiecărei clase și clasele egale cu propriul opus.

Opusul lui $\hat{a}$ este $\widehat{8-a}$ pentru $a\ne 0$, iar $-\hat{0}=\hat{0}$. Obținem $-\hat{1}=\hat{7}$, $-\hat{2}=\hat{6}$, $-\hat{3}=\hat{5}$, $-\hat{4}=\hat{4}$, $-\hat{5}=\hat{3}$, $-\hat{6}=\hat{2}$, $-\hat{7}=\hat{1}$. Condiția $-\hat{a}=\hat{a}$ înseamnă $\hat{a}+\hat{a}=\hat{0}$, adică $\widehat{2a}=\hat{0}$, deci $8\mid 2a$: pentru $a\in \{0,1,\dots ,7\}$ rămân $a=0$ și $a=4$. Clasele căutate sunt $\hat{0}$ și $\hat{4}$.

Exemplul 5 — Ecuații de gradul întâi

Rezolvă în ${\mathbb{Z}}_6$ ecuația $\hat{x}+\hat{4}=\hat{1}$, iar în ${\mathbb{Z}}_8$ ecuația $\hat{x}+\hat{3}=\hat{0}$.

Prima: adunăm opusul lui $\hat{4}$, adică $\widehat{6-4}=\hat{2}$, în ambii membri. Obținem $\hat{x}=\hat{1}+\hat{2}=\hat{3}$. Verificare: $\hat{3}+\hat{4}=\hat{7}=\hat{1}$, corect. A doua: soluția este chiar opusul lui $\hat{3}$, adică $\hat{x}=\widehat{8-3}=\hat{5}$. Verificare: $\hat{5}+\hat{3}=\hat{8}=\hat{0}$, corect.

Exemplul 6 — Exemplu tip Bacalaureat M1

Se consideră mulțimea ${\mathbb{Z}}_8$ cu adunarea claselor de resturi.

a) Calculează $\hat{3}+\hat{5}+\hat{7}$.

Adunăm reprezentanții: $3+5+7=15$, iar $15=8\cdot 1+7$, deci $\hat{3}+\hat{5}+\hat{7}=\hat{7}$. (Adunarea fiind asociativă, ordinea grupării nu contează.)

b) Determină opusul clasei $\hat{6}$.

Opusul lui $\hat{6}$ este $\widehat{8-6}=\hat{2}$. Verificare: $\hat{6}+\hat{2}=\hat{8}=\hat{0}$, elementul neutru.

c) Rezolvă în ${\mathbb{Z}}_8$ ecuația $\hat{x}+\hat{x}+\hat{2}=\hat{0}$.

Ecuația se scrie $2\hat{x}=-\hat{2}=\hat{6}$. Necunoscuta apare de două ori, deci adunarea opusului nu izolează pe $\hat{x}$; verificăm cele opt clase. Valorile lui $2\hat{x}$ sunt, pentru $\hat{x}=\hat{0},\hat{1},\dots ,\hat{7}$: $\hat{0},\hat{2},\hat{4},\hat{6},\hat{0},\hat{2},\hat{4},\hat{6}$. Clasa $\hat{6}$ apare de două ori, pentru $\hat{x}=\hat{3}$ și $\hat{x}=\hat{7}$. Verificare: $\hat{3}+\hat{3}+\hat{2}=\hat{8}=\hat{0}$ și $\hat{7}+\hat{7}+\hat{2}=\widehat{16}=\hat{0}$, ambele corecte. Așa arată subpunctul c) al problemei de clase de resturi din Subiectul al II-lea de la Bacalaureat M1: două soluții, nu una, pentru că nu lucrăm în $\mathbb{R}$.

Să exersăm

1. Scrie elementele lui ${\mathbb{Z}}_5$ ca mulțimi de numere întregi, cu câte cinci elemente fiecare.

2. Determină clasa lui $38$ în ${\mathbb{Z}}_7$.

3. Determină clasa lui $-19$ în ${\mathbb{Z}}_5$.

4. Pentru ce valori ale lui $n$ are loc egalitatea $\widehat{17}=\hat{5}$ în ${\mathbb{Z}}_n$?

5. Alcătuiește tabla adunării pe ${\mathbb{Z}}_3$ și citește din ea elementul neutru.

6. Calculează $\hat{4}+\hat{5}$ în ${\mathbb{Z}}_6$.

7. Determină opusul fiecărei clase din ${\mathbb{Z}}_7$.

8. (Adevărat/Fals cu motivare.) „Clasa $\hat{7}$ nu există în ${\mathbb{Z}}_5$."

9. Rezolvă în ${\mathbb{Z}}_6$ ecuația $\hat{x}+\hat{4}=\hat{1}$.

10. Rezolvă în ${\mathbb{Z}}_8$ ecuația $\hat{x}+\hat{3}=\hat{0}$.

11. (Problemă aplicată.) Este ora $21$. Ce oră va fi peste $8$ ore, dacă lucrăm cu un ceas de $24$ de ore? Scrie răspunsul ca operație în ${\mathbb{Z}}_{24}$.

12. Calculează $5\hat{2}$ în ${\mathbb{Z}}_7$, adunând clasa $\hat{2}$ de cinci ori.

13. Determină clasele din ${\mathbb{Z}}_{10}$ egale cu opusul lor.

14. În ${\mathbb{Z}}_9$, verifică faptul că $\hat{4}+\hat{7}$ dă același rezultat dacă folosești reprezentanții $22$ și $-2$.

15. (Exercițiu tip Bacalaureat M1.) În ${\mathbb{Z}}_8$: a) calculează $\hat{3}+\hat{5}+\hat{7}$; b) determină opusul clasei $\hat{6}$; c) rezolvă ecuația $\hat{x}+\hat{x}+\hat{2}=\hat{0}$.

16. Determină restul împărțirii sumei $1+2+\cdots +50$ la $6$, folosind clasele de resturi.

17. Arată, lucrând în ${\mathbb{Z}}_3$, că suma a trei numere întregi consecutive se divide cu $3$.

18. (Provocare.) Câte clase din ${\mathbb{Z}}_n$ sunt egale cu opusul lor? Discută după paritatea lui $n$ și justifică răspunsul.

Răspunsuri și explicații

1. $\hat{0}=\{\dots ,-10,-5,0,5,10,\dots \}$, $\hat{1}=\{\dots ,-9,-4,1,6,11,\dots \}$, $\hat{2}=\{\dots ,-8,-3,2,7,12,\dots \}$, $\hat{3}=\{\dots ,-7,-2,3,8,13,\dots \}$, $\hat{4}=\{\dots ,-6,-1,4,9,14,\dots \}$ — fiecare clasă conține numerele care diferă între ele prin multipli de $5$.

2. $38=7\cdot 5+3$, deci $\widehat{38}=\hat{3}$.

3. $-19=5\cdot (-4)+1$, cu $0\le 1<5$, deci $\widehat{-19}=\hat{1}$. Atenție: restul nu este $-4$.

4. Condiția este $n\mid (17-5)$, adică $n\mid 12$. Cu $n\ge 2$, obținem $n\in \{2,3,4,6,12\}$.

5. Tabla este cea din Exemplul 2. Linia și coloana lui $\hat{0}$ reproduc antetul, deci elementul neutru este $\hat{0}$.

6. $4+5=9=6\cdot 1+3$, deci $\hat{4}+\hat{5}=\hat{3}$.

7. $-\hat{0}=\hat{0}$, $-\hat{1}=\hat{6}$, $-\hat{2}=\hat{5}$, $-\hat{3}=\hat{4}$, $-\hat{4}=\hat{3}$, $-\hat{5}=\hat{2}$, $-\hat{6}=\hat{1}$.

8. Fals. Scrierea $\hat{7}$ are perfect sens în ${\mathbb{Z}}_5$ și desemnează clasa lui $7$, care este $\hat{2}$, pentru că $7=5\cdot 1+2$. Nu este o clasă nouă, ci un alt nume pentru una dintre cele cinci.

9. Adunăm opusul lui $\hat{4}$, care este $\hat{2}$: $\hat{x}=\hat{1}+\hat{2}=\hat{3}$. Verificare: $\hat{3}+\hat{4}=\hat{7}=\hat{1}$.

10. $\hat{x}$ este opusul lui $\hat{3}$, adică $\hat{x}=\widehat{8-3}=\hat{5}$. Verificare: $\hat{5}+\hat{3}=\hat{8}=\hat{0}$.

11. În ${\mathbb{Z}}_{24}$: $\widehat{21}+\hat{8}=\widehat{29}=\hat{5}$, pentru că $29=24+5$. Va fi ora $5$.

12. $5\hat{2}=\widehat{5\cdot 2}=\widehat{10}=\hat{3}$, pentru că $10=7+3$.

13. Condiția $\hat{a}+\hat{a}=\hat{0}$ înseamnă $10\mid 2a$, adică $5\mid a$. Pentru $a\in \{0,1,\dots ,9\}$ obținem $\hat{0}$ și $\hat{5}$.

14. Cu reprezentanții standard: $4+7=11=9+2$, deci rezultatul este $\hat{2}$. Cu ceilalți: $22+(-2)=20=9\cdot 2+2$, deci tot $\hat{2}$. Coincidența este garantată de teorema bunei definiri.

15. a) $3+5+7=15=8+7$, deci rezultatul este $\hat{7}$. b) Opusul lui $\hat{6}$ este $\widehat{8-6}=\hat{2}$. c) Ecuația devine $2\hat{x}=\hat{6}$; verificând cele opt clase obținem soluțiile $\hat{x}=\hat{3}$ și $\hat{x}=\hat{7}$.

16. Suma este $\frac{50\cdot 51}{2}=1275$, iar $1275=6\cdot 212+3$, deci $\widehat{1275}=\hat{3}$ în ${\mathbb{Z}}_6$ și restul căutat este $3$.

17. Fie numerele $a$, $a+1$, $a+2$. Trecând la clase în ${\mathbb{Z}}_3$, suma lor este $\hat{a}+\widehat{a+1}+\widehat{a+2}=\widehat{3a+3}=\hat{0}$, pentru că $3\mid (3a+3)$. Clasa nulă înseamnă rest zero, deci suma se divide cu $3$.

18. Condiția $-\hat{a}=\hat{a}$ revine la $n\mid 2a$, cu $a\in \{0,1,\dots ,n-1\}$. Dacă $n$ este impar, din $n\mid 2a$ rezultă $n\mid a$, deci singura soluție este $a=0$: o singură clasă. Dacă $n$ este par, soluțiile sunt $a=0$ și $a=\frac{n}{2}$: două clase. De pildă, în ${\mathbb{Z}}_7$ doar $\hat{0}$, iar în ${\mathbb{Z}}_{10}$ clasele $\hat{0}$ și $\hat{5}$.

De reținut

• Clasa de resturi $\hat{a}$ modulo $n$ este mulțimea $\{a+kn\mid k\in \mathbb{Z}\}$, adică mulțimea tuturor întregilor care dau același rest ca $a$ la împărțirea cu $n$.
• Două clase sunt egale dacă și numai dacă reprezentanții lor diferă printr-un multiplu de $n$, adică $\hat{a}=\hat{b}⟺n\mid (a-b)$.
• Mulțimea ${\mathbb{Z}}_n=\{\hat{0},\hat{1},\dots ,\widehat{n-1}\}$ are exact $n$ elemente, iar cele $n$ clase sunt disjuncte și acoperă întreg $\mathbb{Z}$.
• Adunarea claselor se definește prin $\hat{a}+\hat{b}=\widehat{a+b}$ și este bine definită, adică rezultatul nu depinde de reprezentanții aleși — proprietate care se demonstrează, nu se presupune.
• Adunarea pe ${\mathbb{Z}}_n$ este asociativă și comutativă, are elementul neutru $\hat{0}$, iar fiecare clasă are opusul $-\hat{a}=\widehat{n-a}$, deci toate elementele sunt simetrizabile.

Greșeli frecvente

• Restul negativ. La împărțirea lui $-19$ la $5$ restul este $1$, nu $-4$: teorema împărțirii cu rest cere $0\le r<n$. Scrie întotdeauna împărțirea completă, $-19=5\cdot (-4)+1$, înainte de a numi clasa.
• Confuzia dintre clasă și reprezentant. $\hat{2}$ nu este numărul $2$, ci mulțimea infinită a întregilor care dau restul $2$. De aceea $\hat{2}=\hat{7}=\widehat{-3}$ în ${\mathbb{Z}}_5$, deși numerele $2$, $7$ și $-3$ sunt diferite.
• Sărirea peste buna definire. A spune „adun reprezentanții" fără a demonstra că rezultatul nu depinde de ei este o lacună de raționament, nu o economie de timp. Contraexemplul cu $\max$ arată că nu orice formulă pe reprezentanți definește o operație.
• Rezolvarea unei ecuații ca în $\mathbb{R}$. În ${\mathbb{Z}}_n$, o ecuație în care necunoscuta apare de mai multe ori poate avea zero soluții sau mai multe. Verificarea tuturor celor $n$ clase este metoda sigură; „împărțirea la $2$" nu are sens aici.
• Scrierea claselor cu altă notație. Se scrie $\hat{a}$, cu accent circumflex, și $\widehat{n-1}$ pentru expresii lungi. Bara, $\bar{a}$, este rezervată conjugatului unui număr complex, iar parantezele drepte nu se folosesc la clase.

Aplică acasă

1. Ceasul ca tablă de operație. Desenează cadranul unui ceas de $12$ ore și scrie tabla adunării pe ${\mathbb{Z}}_{12}$ doar pentru orele $0,3,6,9$. Verifică dacă mulțimea acestor patru clase este parte stabilă și găsește opusul fiecăreia. Compară rezultatul cu tabla lui $({\mathbb{Z}}_4,+)$.

2. Calendarul. Zilele săptămânii se numerotează de la $0$ (luni) la $6$ (duminică). Dacă azi este ziua $2$, în ce zi cade a $100$-a zi de acum înainte? Rezolvă în ${\mathbb{Z}}_7$, apoi verifică pe un calendar real.

3. Tabla generată automat. Într-o foaie de calcul, scrie pe prima linie și pe prima coloană numerele $0,\dots ,7$, iar în interior formula care dă restul sumei la $8$. Vei obține tabla lui $({\mathbb{Z}}_8,+)$. Colorează celulele care conțin $0$ și explică de ce apar exact o dată pe fiecare linie.

Pentru părinți și profesori

Lecția introduce primul obiect algebric „construit", nu preluat din aritmetică: elementele lui ${\mathbb{Z}}_n$ sunt mulțimi, nu numere. Această trecere este obstacolul principal, iar reușita ei se vede în felul în care elevul vorbește: „clasa lui $7$" în loc de „numărul $7$". A doua miză este obișnuința cu ideea de bună definire — primul loc din liceu în care o definiție trebuie verificată că e legitimă înainte de a fi folosită.

De verificat în caiet: (1) împărțirea cu rest este scrisă complet, inclusiv pentru numere negative; (2) demonstrația bunei definiri pleacă de la $n\mid (a-a_1)$ și $n\mid (b-b_1)$; (3) opusul este scris $\widehat{n-a}$, nu $\widehat{-a}$ ca rezultat final; (4) la ecuații se face verificarea. Întrebări de control: „Ce este $\hat{3}$ în ${\mathbb{Z}}_5$?"; „De ce $\widehat{-1}=\hat{4}$?"; „Ce înseamnă că adunarea e bine definită?"; „Câte elemente are ${\mathbb{Z}}_{12}$?".

La BAC, clasele de resturi apar în Subiectul al II-lea, singure sau împreună cu înmulțirea lor: calcule de sume, determinarea opuselor, rezolvarea unor ecuații, uneori numărarea soluțiilor. Semn că elevul a înțeles: reduce automat orice clasă la reprezentantul dintre $0$ și $n-1$ și verifică soluțiile ecuațiilor înlocuindu-le în ecuația inițială.

Întrebări frecvente

Ce este o clasă de resturi modulo $n$? Clasa de resturi $\hat{a}$ modulo $n$ este mulțimea tuturor numerelor întregi care dau același rest ca $a$ la împărțirea cu $n$, adică $\hat{a}=\{a+kn\mid k\in \mathbb{Z}\}$. Ea este o mulțime infinită, iar numărul $a$ este doar unul dintre reprezentanții ei posibili.

Câte elemente are mulțimea ${\mathbb{Z}}_n$? Exact $n$ elemente: clasele $\hat{0},\hat{1},\dots ,\widehat{n-1}$. Orice clasă este egală cu una dintre acestea, pentru că se reduce la clasa restului, iar cele $n$ clase din listă sunt distincte, fiindcă diferența a doi reprezentanți din $\{0,\dots ,n-1\}$ nu se poate divide cu $n$ decât dacă este nulă.

Cum se adună două clase de resturi? Se adună reprezentanții și se ia clasa sumei: $\hat{a}+\hat{b}=\widehat{a+b}$. Apoi rezultatul se reduce la reprezentantul standard, împărțind cu rest la $n$. De pildă, în ${\mathbb{Z}}_5$ avem $\hat{3}+\hat{4}=\hat{7}=\hat{2}$, pentru că $7=5\cdot 1+2$.

Ce înseamnă că adunarea claselor este bine definită? Înseamnă că rezultatul nu depinde de reprezentanții aleși: dacă $\hat{a}=\widehat{a_1}$ și $\hat{b}=\widehat{b_1}$, atunci $\widehat{a+b}=\widehat{a_1+b_1}$. Demonstrația scade cele două egalități de divizibilitate și obține $n\mid [(a+b)-(a_1+b_1)]$. Fără această verificare, definiția nu ar fi o funcție.

Care este opusul unei clase de resturi? Opusul clasei $\hat{a}$ este clasa $\widehat{n-a}$, pentru $a$ între $1$ și $n-1$, iar opusul lui $\hat{0}$ este $\hat{0}$. Verificarea e imediată: $\hat{a}+\widehat{n-a}=\hat{n}=\hat{0}$. Prin urmare fiecare element al lui ${\mathbb{Z}}_n$ este simetrizabil față de adunare.

De ce restul lui $-19$ la împărțirea cu $5$ este $1$ și nu $-4$? Pentru că teorema împărțirii cu rest cere ca restul să satisfacă $0\le r<n$. Scrierea corectă este $-19=5\cdot (-4)+1$, cu câtul $-4$ și restul $1$. Scrierea $-19=5\cdot (-3)-4$ are un rest negativ, deci nu respectă condiția și nu dă clasa.

Cum se rezolvă o ecuație de gradul întâi în ${\mathbb{Z}}_n$? Se adună opusul termenului liber în ambii membri: din $\hat{x}+\hat{a}=\hat{b}$ obții $\hat{x}=\hat{b}+\widehat{n-a}$. Dacă necunoscuta apare de mai multe ori, metoda sigură este verificarea tuturor celor $n$ clase, pentru că ecuația poate avea mai multe soluții sau niciuna.

Cum apar clasele de resturi în subiectele de Bacalaureat M1? În Subiectul al II-lea, ca problemă de sine stătătoare: se cer calcule de sume în ${\mathbb{Z}}_n$, opusele unor clase, rezolvarea sau discuția unei ecuații și, uneori, alcătuirea tablei. Punctajul se pierde cel mai des la reducerea greșită a claselor negative și la ecuațiile cu mai multe soluții.