Elementele inversabile din mulțimea claselor de resturi; ecuații cu clase de resturi

Într-o ecuație obișnuită, $5x=3$, gestul următor e automat: împarți la $5$. În mulțimea claselor de resturi modulo $n$ gestul acesta nu există — nu există împărțire — și totuși ecuația $\hat{5}\cdot \hat{x}=\hat{3}$ are, în ${\mathbb{Z}}_{12}$, exact o soluție. Lecția aceasta de clasa a 12-a explică de ce: pentru unele clase de resturi există un „invers", iar înmulțirea cu el ține locul împărțirii. Elementele inversabile din ${\mathbb{Z}}_n$ sunt subiectul cerut de programa de matematică-informatică, iar criteriul care le recunoaște este surprinzător de simplu. O clasă de resturi este inversabilă dacă există o altă clasă cu care, înmulțită, dă $\hat{1}$; în ${\mathbb{Z}}_n$ acest lucru se întâmplă exact atunci când reprezentantul clasei este prim cu $n$.

Deosebirea față de adunare e izbitoare. La adunarea claselor de resturi modulo n, orice clasă are opusul ei, anume $-\hat{a}=\widehat{n-a}$. La înmulțire, în schimb, unele clase au invers și altele nu: în ${\mathbb{Z}}_{12}$ clasa $\hat{5}$ are, clasa $\hat{4}$ nu. Vom afla exact care sunt cele „bune", vom învăța să calculăm inversul fără să scriem toată tabla și vom rezolva ecuații cu clase de resturi prin ambele metode pe care le acceptă baremele de Bacalaureat M1.

Ce vei învăța

• Vei ști ce înseamnă că o clasă de resturi este inversabilă și cum se notează inversul ei.
• Vei ști să demonstrezi teorema fundamentală: clasa $\hat{a}$ este inversabilă în ${\mathbb{Z}}_n$ dacă și numai dacă $(a,n)=1$.
• Vei ști să determini mulțimea $U({\mathbb{Z}}_n,\cdot )$ a elementelor inversabile și să explici de ce în ${\mathbb{Z}}_p$, cu $p$ prim, toate clasele nenule sunt inversabile.
• Vei ști să calculezi inversul unei clase fără să scrii tabla operației.
• Vei ști să rezolvi ecuații de forma $\hat{a}\cdot \hat{x}=\hat{b}$ prin înmulțire cu inversul și prin verificarea celor $n$ clase, alegând metoda potrivită.
• Vei ști să folosești clasele de resturi pentru probleme de divizibilitate în $\mathbb{Z}$.

Hai să descoperim împreună

1. Ce înseamnă că o clasă de resturi este inversabilă?

Noțiunea nu e nouă: la Elemente simetrizabile și simetricul unui element ai definit elementul simetrizabil față de o lege de compoziție cu element neutru. Aici legea este înmulțirea claselor, iar elementul neutru este $\hat{1}$, ca la Înmulțirea claselor de resturi modulo n; distributivitatea. Numele se schimbă odată cu notația: pentru o lege scrisă multiplicativ, elementul simetrizabil se numește inversabil, iar simetricul se numește invers și se notează ${\hat{a}}^{-1}$.

O clasă $\hat{a}\in {\mathbb{Z}}_n$ este inversabilă dacă există o clasă $\hat{b}\in {\mathbb{Z}}_n$ astfel încât $\hat{a}\cdot \hat{b}=\hat{b}\cdot \hat{a}=\hat{1}$. Clasa $\hat{b}$, atunci când există, se numește inversul lui $\hat{a}$ și se notează ${\hat{a}}^{-1}$. Mulțimea tuturor claselor inversabile ale monoidului $({\mathbb{Z}}_n,\cdot )$ se notează $U({\mathbb{Z}}_n,\cdot )$, iar elementele ei se mai numesc unitățile monoidului. Notația poartă și legea, pentru că pe ${\mathbb{Z}}_n$ trăiesc două legi de compoziție; în restul lecției, unde este vorba numai despre înmulțirea claselor, o vom scrie pe scurt $U({\mathbb{Z}}_n)$.

Două observații imediate. Prima: inversul, când există, este unic — proprietate demonstrată o dată pentru toate legile asociative cu element neutru și valabilă deci și aici. A doua: cum înmulțirea claselor este comutativă, e de ajuns să verifici una dintre cele două egalități.

Exemple în ${\mathbb{Z}}_{12}$: $\hat{5}\cdot \hat{5}=\widehat{25}=\hat{1}$, deci $\hat{5}$ este inversabilă și ${\hat{5}}^{-1}=\hat{5}$ — clasa este propriul ei invers. În schimb $\hat{4}$ nu este inversabilă: produsele $\hat{4}\cdot \hat{x}$ dau, pe rând, $\hat{0},\hat{4},\hat{8},\hat{0},\hat{4},\hat{8},\dots$ și clasa $\hat{1}$ nu apare niciodată.

2. Cum se citesc inversele din tabla înmulțirii?

Pe o tablă de operație, inversabilitatea se vede dintr-o privire: o clasă este inversabilă exact atunci când pe linia ei apare elementul neutru $\hat{1}$, iar coloana în care apare indică inversul. Iată tabla înmulțirii în ${\mathbb{Z}}_8$:

Clasa $\hat{1}$ apare pe liniile lui $\hat{1}$, $\hat{3}$, $\hat{5}$ și $\hat{7}$, în coloanele lui $\hat{1}$, $\hat{3}$, $\hat{5}$, respectiv $\hat{7}$. Așadar

$$U({\mathbb{Z}}_8)=\{\hat{1},\hat{3},\hat{5},\hat{7}\},{\hat{1}}^{-1}=\hat{1},{\hat{3}}^{-1}=\hat{3},{\hat{5}}^{-1}=\hat{5},{\hat{7}}^{-1}=\hat{7}.$$

Aici fiecare element inversabil este propriul său invers — o coincidență a lui $8$, nu o regulă. În ${\mathbb{Z}}_9$, de pildă, ${\hat{2}}^{-1}=\hat{5}$ (pentru că $\widehat{10}=\hat{1}$) și ${\hat{4}}^{-1}=\hat{7}$ (pentru că $\widehat{28}=\hat{1}$).

Privind tabla lui ${\mathbb{Z}}_8$, remarcă tiparul: inversabile sunt exact clasele impare, adică exact acelea al căror reprezentant nu are factor comun cu $8$. Următoarea subsecțiune arată că nu e o întâmplare.

3. Când este o clasă de resturi inversabilă?

Teoremă. Fie $n\in \mathbb{N}$, $n\ge 2$, și $a\in \mathbb{Z}$. Clasa $\hat{a}$ este inversabilă în $({\mathbb{Z}}_n,\cdot )$ dacă și numai dacă $(a,n)=1$, adică dacă $a$ și $n$ sunt prime între ele.

Demonstrație. „$\Rightarrow$" Presupunem că $\hat{a}$ este inversabilă, adică există $b$ cu $\hat{a}\cdot \hat{b}=\hat{1}$. Aceasta înseamnă $n\mid (ab-1)$, deci există $k\in \mathbb{Z}$ cu $ab-1=kn$, adică

$$ab-kn=1.$$

Fie $d=(a,n)$. Atunci $d\mid a$ și $d\mid n$, deci $d$ divide și membrul stâng al egalității de mai sus, adică $d\mid 1$. Prin urmare $d=1$.

„$\Leftarrow$" Presupunem $(a,n)=1$ și privim cele $n$ produse

$$\hat{a}\cdot \hat{0},\hat{a}\cdot \hat{1},\dots ,\hat{a}\cdot \widehat{n-1}.$$

Arătăm că sunt distincte două câte două. Dacă $\hat{a}\cdot \hat{x}=\hat{a}\cdot \hat{y}$, atunci $n\mid a(x-y)$. Cum $a$ și $n$ nu au niciun factor prim comun, toți factorii primi ai lui $n$, cu exponenții lor, se regăsesc în $x-y$; deci $n\mid (x-y)$, adică $\hat{x}=\hat{y}$. (Este proprietatea de divizibilitate din gimnaziu: dacă $n\mid ac$ și $(a,n)=1$, atunci $n\mid c$; ea se justifică prin descompunerea în factori primi.)

Așadar funcția ${\mathbb{Z}}_n\to {\mathbb{Z}}_n$, $\hat{x}\mapsto \hat{a}\cdot \hat{x}$, este injectivă. Cum pleacă dintr-o mulțime finită și ajunge în aceeași mulțime, ea este și surjectivă — proprietate pe care ai demonstrat-o la Funcții injective, surjective, bijective. În particular, clasa $\hat{1}$ este o valoare a funcției: există $\hat{b}\in {\mathbb{Z}}_n$ cu $\hat{a}\cdot \hat{b}=\hat{1}$, adică $\hat{a}$ este inversabilă. $■$

Demonstrația spune, de fapt, mai mult decât enunțul: când $(a,n)=1$, produsele $\hat{a}\cdot \hat{x}$ parcurg toate clasele din ${\mathbb{Z}}_n$, fiecare exact o dată. Este exact ce vezi pe linia lui $\hat{3}$ în tabla lui ${\mathbb{Z}}_8$: $\hat{0},\hat{3},\hat{6},\hat{1},\hat{4},\hat{7},\hat{2},\hat{5}$ — o rearanjare a întregii mulțimi. De aici va veni, în subsecțiunea a șasea, unicitatea soluției unei ecuații.

4. Câte clase inversabile are ${\mathbb{Z}}_n$?

Din teoremă, mulțimea elementelor inversabile se descrie complet:

$$U({\mathbb{Z}}_n,\cdot )=\{\hat{a}\mid 0\le a<n,(a,n)=1\}.$$

Câteva cazuri, obținute numărând clasele prime cu $n$:

Numărul elementelor inversabile din ${\mathbb{Z}}_n$ se notează în matematică $\phi (n)$ și se numește indicatorul lui Euler; îl menționăm doar, pentru că nu face parte din programă, iar la Bacalaureat M1 numărarea se face direct, listând clasele prime cu $n$.

Cazul cel mai important este $n=p$ prim. Dacă $p$ este prim, singurii divizori ai lui $p$ sunt $1$ și $p$, deci pentru orice $a$ cu $1\le a<p$ avem $(a,p)=1$. Prin urmare:

$$U({\mathbb{Z}}_p,\cdot )=\{\hat{1},\hat{2},\dots ,\widehat{p-1}\}={\mathbb{Z}}_p\setminus \{\hat{0}\}.$$

În ${\mathbb{Z}}_p$, toate clasele nenule sunt inversabile — proprietate pe care ${\mathbb{Z}}_n$ nu o are pentru $n$ compus și care apropie ${\mathbb{Z}}_p$ de mulțimile de numere cu care ești obișnuit. În ${\mathbb{Z}}_7$, de pildă, inversele sunt

$${\hat{1}}^{-1}=\hat{1},{\hat{2}}^{-1}=\hat{4},{\hat{3}}^{-1}=\hat{5},{\hat{4}}^{-1}=\hat{2},{\hat{5}}^{-1}=\hat{3},{\hat{6}}^{-1}=\hat{6},$$

lucru pe care îl verifici imediat: $2\cdot 4=8=7+1$, $3\cdot 5=15=2\cdot 7+1$, $6\cdot 6=36=5\cdot 7+1$. Observă și că $\hat{0}$ nu este niciodată inversabilă, în niciun ${\mathbb{Z}}_n$: produsul oricărei clase cu $\hat{0}$ este $\hat{0}\ne \hat{1}$.

5. Cum se calculează inversul unei clase fără tablă?

Pentru $n$ mare, scrierea tablei e nepractică. Metoda directă pornește chiar de la definiție: căutăm $b$ cu $ab\equiv 1$, adică un întreg de forma $1+kn$ care să se dividă cu $a$. Rețeta în trei pași:

1. verifici că $(a,n)=1$ — altfel inversul nu există și te oprești;
2. scrii numerele $1+n,1+2n,1+3n,\dots$ și te oprești la primul divizibil cu $a$;
3. împarți: câtul, redus modulo $n$, este ${\hat{a}}^{-1}$.

Exemplul 1: inversul lui $\hat{7}$ în ${\mathbb{Z}}_{15}$. Avem $(7,15)=1$, deci inversul există. Numerele $1+15k$ sunt $16,31,46,61,76,91,\dots$, iar primul divizibil cu $7$ este $91=7\cdot 13$. Deci ${\hat{7}}^{-1}=\widehat{13}$, ceea ce se verifică pe loc: $7\cdot 13=91=6\cdot 15+1$.

Exemplul 2: inversul lui $\widehat{11}$ în ${\mathbb{Z}}_{26}$. Cum $(11,26)=1$, inversul există. Numerele $1+26k$: $27,53,79,105,131,157,183,209$, iar $209=11\cdot 19$. Deci ${\widehat{11}}^{-1}=\widehat{19}$, cu verificarea $11\cdot 19=209=8\cdot 26+1$.

Un truc care scurtează des calculul: caută întâi un multiplu al lui $a$ aproape de un multiplu al lui $n$. În ${\mathbb{Z}}_{12}$, pentru $\hat{5}$, observi imediat că $5\cdot 5=25=2\cdot 12+1$, deci ${\hat{5}}^{-1}=\hat{5}$, fără să scrii niciun șir.

6. Cum se rezolvă ecuația $\hat{a}\cdot \hat{x}=\hat{b}$?

Aceasta este întrebarea centrală a lecției, iar programa cere ambele metode.

Metoda 1 — înmulțirea cu inversul. Se aplică atunci când $(a,n)=1$. Înmulțim ambii membri cu ${\hat{a}}^{-1}$ și folosim asociativitatea:

$$\hat{a}\cdot \hat{x}=\hat{b}⟹{\hat{a}}^{-1}\cdot (\hat{a}\cdot \hat{x})={\hat{a}}^{-1}\cdot \hat{b}⟹({\hat{a}}^{-1}\cdot \hat{a})\cdot \hat{x}={\hat{a}}^{-1}\cdot \hat{b}⟹\hat{x}={\hat{a}}^{-1}\cdot \hat{b}.$$

Ecuația are, în acest caz, exact o soluție — pentru că, așa cum am văzut în demonstrația teoremei, produsele $\hat{a}\cdot \hat{x}$ parcurg toate clasele, fiecare o singură dată.

Exemplu. Rezolvăm $\hat{5}\cdot \hat{x}=\hat{3}$ în ${\mathbb{Z}}_{12}$. Cum $(5,12)=1$ și ${\hat{5}}^{-1}=\hat{5}$, obținem $\hat{x}=\hat{5}\cdot \hat{3}=\widehat{15}=\hat{3}$. Verificare: $\hat{5}\cdot \hat{3}=\widehat{15}=\hat{3}$ ✓.

Metoda 2 — verificarea celor $n$ clase. Se aplică atunci când $\hat{a}$ nu este inversabilă, deci prima metodă e indisponibilă. Se calculează $\hat{a}\cdot \hat{x}$ pentru $x=0,1,\dots ,n-1$ și se rețin clasele pentru care rezultatul este $\hat{b}$.

Exemplu. Rezolvăm $\hat{4}\cdot \hat{x}=\hat{2}$ în ${\mathbb{Z}}_6$. Aici $(4,6)=2\ne 1$. Produsele sunt $\hat{0},\hat{4},\hat{2},\hat{0},\hat{4},\hat{2}$, deci soluțiile sunt $\hat{2}$ și $\hat{5}$: două soluții. În schimb ecuația $\hat{4}\cdot \hat{x}=\hat{3}$, în același ${\mathbb{Z}}_6$, nu are soluții, pentru că printre produse nu apare $\hat{3}$.

Criteriul de alegere, de reținut ca atare: calculezi $d=(a,n)$.

• Dacă $d=1$, folosești metoda 1; ecuația are exact o soluție. Verificarea celor $n$ clase ar da același rezultat, dar te-ar costa de zeci de ori mai mult timp.
• Dacă $d>1$, folosești metoda 2; ecuația are soluții numai dacă $d\mid b$, iar în acest caz are exact $d$ soluții.

Ecuațiile cu termen liber se aduc întâi la forma de mai sus, folosind opusele la adunare și distributivitatea demonstrată în lecția anterioară. De pildă, în ${\mathbb{Z}}_7$:

$$\hat{3}\cdot \hat{x}+\hat{5}=\hat{1}⟹\hat{3}\cdot \hat{x}=\hat{1}-\hat{5}=\widehat{-4}=\hat{3}⟹\hat{x}={\hat{3}}^{-1}\cdot \hat{3}=\hat{5}\cdot \hat{3}=\widehat{15}=\hat{1}.$$

Verificare: $\hat{3}\cdot \hat{1}+\hat{5}=\hat{3}+\hat{5}=\hat{8}=\hat{1}$ ✓. Iar dacă necunoscuta apare în mai mulți termeni, dai factor comun — tot prin distributivitate: $\hat{2}\hat{x}+\hat{3}\hat{x}=(\hat{2}+\hat{3})\hat{x}=\hat{5}\hat{x}$.

Deprinderea de a determina un element necunoscut punând o condiție și de a verifica apoi rezultatul revine, într-un alt decor, în ultima lecție a unității: Legi de compoziție cu parametri: determinarea parametrilor din proprietăți, unde necunoscuta nu mai e o clasă, ci un parametru din formula legii.

7. Ecuații de grad mai mare și probleme de divizibilitate

Când necunoscuta apare la putere, metoda inversului nu mai ajută: se verifică toate clasele. Rezultatele sunt uneori surprinzătoare.

În ${\mathbb{Z}}_8$, ecuația ${\hat{x}}^2=\hat{1}$ are patru soluții: $\hat{1},\hat{3},\hat{5},\hat{7}$, pentru că $9=8+1$, $25=3\cdot 8+1$ și $49=6\cdot 8+1$. O ecuație de gradul al doilea cu patru soluții este imposibilă peste $\mathbb{R}$, dar perfect normală aici.

În ${\mathbb{Z}}_6$, ecuația ${\hat{x}}^2+\hat{x}=\hat{0}$ se scrie, dând factor comun, $\hat{x}\cdot (\hat{x}+\hat{1})=\hat{0}$. Atenție: de aici nu rezultă „$\hat{x}=\hat{0}$ sau $\hat{x}+\hat{1}=\hat{0}$", pentru că în ${\mathbb{Z}}_6$ un produs nul poate avea ambii factori nenuli. Verificând cele șase clase, găsim soluțiile $\hat{0},\hat{2},\hat{3},\hat{5}$ — patru, nu două.

Aplicația la divizibilitate în $\mathbb{Z}$ este cerută explicit de programă și merge invers: o întrebare despre numere întregi se traduce într-un calcul finit cu clase. Arătăm, de exemplu, că niciun număr de forma $n^2+1$ nu se divide cu $3$. Lucrăm în ${\mathbb{Z}}_3$, unde există doar trei clase. Pătratele sunt ${\hat{0}}^2=\hat{0}$, ${\hat{1}}^2=\hat{1}$, ${\hat{2}}^2=\hat{4}=\hat{1}$, deci ${\hat{n}}^2\in \{\hat{0},\hat{1}\}$ și

$${\hat{n}}^2+\hat{1}\in \{\hat{1},\hat{2}\},$$

adică niciodată $\hat{0}$. Cum divizibilitatea cu $3$ înseamnă exact „clasa este $\hat{0}$", concluzia e demonstrată — pentru o infinitate de numere, prin trei verificări.

Exemple rezolvate

Exemplul 1 — Determinarea mulțimii elementelor inversabile

Determinați $U({\mathbb{Z}}_{15})$ și inversul clasei $\hat{4}$.

Rezolvare. Căutăm clasele $\hat{a}$ cu $(a,15)=1$. Cum $15=3\cdot 5$, eliminăm multiplii lui $3$ ($0,3,6,9,12$) și pe cei ai lui $5$ ($0,5,10$). Rămân

$$U({\mathbb{Z}}_{15})=\{\hat{1},\hat{2},\hat{4},\hat{7},\hat{8},\widehat{11},\widehat{13},\widehat{14}\},$$

opt clase. Pentru inversul lui $\hat{4}$ căutăm primul număr de forma $1+15k$ divizibil cu $4$: $16=4\cdot 4$. Deci ${\hat{4}}^{-1}=\hat{4}$, iar verificarea este $4\cdot 4=16=15+1$ ✓.

Exemplul 2 — O clasă neinversabilă

Arătați că $\hat{6}$ nu este inversabilă în ${\mathbb{Z}}_{15}$, în două moduri.

Rezolvare. Cu teorema: $(6,15)=3\ne 1$, deci $\hat{6}$ nu este inversabilă.

Direct: dacă ar exista $\hat{b}$ cu $\hat{6}\cdot \hat{b}=\hat{1}$, atunci $15\mid 6b-1$. Dar $6b-1$ este un număr impar care nu se divide cu $3$ (căci $3\mid 6b$, deci $6b-1$ dă restul $2$ la împărțirea cu $3$), în timp ce orice multiplu al lui $15$ se divide cu $3$. Contradicție.

A doua cale arată de unde vine, de fapt, condiția din teoremă: divizorul comun al lui $a$ și $n$ ar trebui să dividă și pe $1$.

Exemplul 3 — Ecuație rezolvată prin înmulțire cu inversul

Rezolvați în ${\mathbb{Z}}_{11}$ ecuația $\hat{5}\cdot \hat{x}+\hat{3}=\hat{1}$.

Rezolvare. Izolăm termenul cu necunoscuta: $\hat{5}\cdot \hat{x}=\hat{1}-\hat{3}=\widehat{-2}=\hat{9}$.

Cum $11$ este prim și $\hat{5}\ne \hat{0}$, clasa $\hat{5}$ este inversabilă. Căutăm inversul: $1+11k$ dă $12,23,34,45$, iar $45=5\cdot 9$, deci ${\hat{5}}^{-1}=\hat{9}$. Atunci

$$\hat{x}={\hat{5}}^{-1}\cdot \hat{9}=\hat{9}\cdot \hat{9}=\widehat{81}=\hat{4},$$

pentru că $81=7\cdot 11+4$. Verificare: $\hat{5}\cdot \hat{4}+\hat{3}=\widehat{20}+\hat{3}=\hat{9}+\hat{3}=\widehat{12}=\hat{1}$ ✓. Soluția este unică.

Exemplul 4 — Ecuație cu coeficient neinversabil

Rezolvați în ${\mathbb{Z}}_9$ ecuația $\hat{6}\cdot \hat{x}=\hat{3}$.

Rezolvare. Avem $d=(6,9)=3$, deci $\hat{6}$ nu este inversabilă și metoda inversului nu se aplică. Cum $3\mid 3$, criteriul anunță soluții: exact $d=3$. Le găsim verificând cele nouă clase; produsele $\hat{6}\cdot \hat{x}$ sunt, pentru $x=0,\dots ,8$:

$$\hat{0},\hat{6},\hat{3},\hat{0},\hat{6},\hat{3},\hat{0},\hat{6},\hat{3}.$$

Clasa $\hat{3}$ apare pentru $x\in \{2,5,8\}$, deci soluțiile sunt $\hat{2},\hat{5},\hat{8}$. Verificare pentru una dintre ele: $\hat{6}\cdot \hat{5}=\widehat{30}=\hat{3}$ ✓, pentru că $30=3\cdot 9+3$.

Exemplul 5 — Sistem de ecuații cu clase de resturi

Rezolvați în ${\mathbb{Z}}_5$ sistemul $\hat{2}\hat{x}+\hat{3}\hat{y}=\hat{1}$, $\hat{x}+\hat{y}=\hat{4}$.

Rezolvare. Din a doua ecuație, $\hat{y}=\hat{4}-\hat{x}$. Înlocuim în prima și folosim distributivitatea:

$$\hat{2}\hat{x}+\hat{3}(\hat{4}-\hat{x})=\hat{2}\hat{x}+\widehat{12}-\hat{3}\hat{x}=(\hat{2}-\hat{3})\hat{x}+\hat{2}=\widehat{-1}\cdot \hat{x}+\hat{2}=\hat{4}\hat{x}+\hat{2}.$$

Ecuația devine $\hat{4}\hat{x}=\hat{1}-\hat{2}=\widehat{-1}=\hat{4}$. Cum $5$ este prim, $\hat{4}$ este inversabilă, cu ${\hat{4}}^{-1}=\hat{4}$ (căci $16=3\cdot 5+1$), deci $\hat{x}=\hat{4}\cdot \hat{4}=\widehat{16}=\hat{1}$. Atunci $\hat{y}=\hat{4}-\hat{1}=\hat{3}$.

Verificare: $\hat{2}\cdot \hat{1}+\hat{3}\cdot \hat{3}=\hat{2}+\hat{9}=\hat{2}+\hat{4}=\hat{6}=\hat{1}$ ✓ și $\hat{1}+\hat{3}=\hat{4}$ ✓. Soluția este perechea $(\hat{1},\hat{3})$.

Exemplul 6 — Exemplu tip Bacalaureat M1

Se consideră mulțimea ${\mathbb{Z}}_{10}$ a claselor de resturi modulo $10$. a) Determinați $U({\mathbb{Z}}_{10})$ și inversele elementelor ei. b) Rezolvați ecuația $\hat{3}\cdot \hat{x}+\hat{7}=\hat{2}$. c) Arătați că ecuația $\hat{4}\cdot \hat{x}=\hat{3}$ nu are soluții în ${\mathbb{Z}}_{10}$.

Rezolvare. a) Cum $10=2\cdot 5$, sunt prime cu $10$ exact clasele $\hat{1},\hat{3},\hat{7},\hat{9}$, deci $U({\mathbb{Z}}_{10})=\{\hat{1},\hat{3},\hat{7},\hat{9}\}$. Inversele: ${\hat{1}}^{-1}=\hat{1}$; $\hat{3}\cdot \hat{7}=\widehat{21}=\hat{1}$, deci ${\hat{3}}^{-1}=\hat{7}$ și ${\hat{7}}^{-1}=\hat{3}$; $\hat{9}\cdot \hat{9}=\widehat{81}=\hat{1}$, deci ${\hat{9}}^{-1}=\hat{9}$.

b) Izolăm: $\hat{3}\cdot \hat{x}=\hat{2}-\hat{7}=\widehat{-5}=\hat{5}$. Înmulțim cu ${\hat{3}}^{-1}=\hat{7}$:

$$\hat{x}=\hat{7}\cdot \hat{5}=\widehat{35}=\hat{5}.$$

Verificare: $\hat{3}\cdot \hat{5}+\hat{7}=\widehat{15}+\hat{7}=\hat{5}+\hat{7}=\widehat{12}=\hat{2}$ ✓. Soluția este unică, pentru că $\hat{3}$ este inversabilă.

c) Aici $(4,10)=2$, deci $\hat{4}$ nu este inversabilă. Produsul $\hat{4}\cdot \hat{x}=\widehat{4x}$ are întotdeauna reprezentantul $4x$ par, iar restul unui număr par la împărțirea cu $10$ este tot par; clasa $\hat{3}$ are reprezentant impar, deci nu poate fi atinsă. Altfel spus, $2=(4,10)$ nu divide $3$, iar criteriul din lecție dă direct mulțimea vidă. Un asemenea subiect apare la Bacalaureat M1 în Subiectul al II-lea, unde punctul c) verifică tocmai dacă elevul a înțeles că nu orice ecuație liniară are soluție.

Să exersăm

La fiecare ecuație, primul gest este calculul lui $(a,n)$: el îți spune și ce metodă folosești, și câte soluții să aștepți. La final, verifică soluția în ecuația inițială.

1. Determină $U({\mathbb{Z}}_9)$.

2. Scrie inversul fiecărei clase din $U({\mathbb{Z}}_9)$.

3. Este $\hat{6}$ inversabilă în ${\mathbb{Z}}_{15}$? Dar în ${\mathbb{Z}}_{25}$?

4. Rezolvă în ${\mathbb{Z}}_9$ ecuația $\hat{4}\cdot \hat{x}=\hat{1}$.

5. Rezolvă în ${\mathbb{Z}}_9$ ecuația $\hat{6}\cdot \hat{x}=\hat{3}$ și numără soluțiile.

6. (Adevărat/Fals cu motivare.) „Dacă $n$ este prim, atunci orice clasă din ${\mathbb{Z}}_n$ este inversabilă."

7. Rezolvă în ${\mathbb{Z}}_{11}$ ecuația $\hat{5}\cdot \hat{x}+\hat{3}=\hat{1}$.

8. Câte elemente are $U({\mathbb{Z}}_{16})$? Dar $U({\mathbb{Z}}_{13})$?

9. Determină inversul clasei $\hat{9}$ în ${\mathbb{Z}}_{20}$.

10. (Adevărat/Fals cu motivare.) „O ecuație de forma $\hat{a}\cdot \hat{x}=\hat{b}$ are cel mult o soluție în ${\mathbb{Z}}_n$."

11. Rezolvă în ${\mathbb{Z}}_{12}$ ecuația ${\hat{x}}^2=\hat{4}$.

12. (Problemă aplicată.) Un mecanism cu $24$ de poziții avansează cu $7$ poziții la fiecare pas, pornind din poziția $0$. După câți pași ajunge, pentru prima oară, în poziția $1$?

13. Arată că niciun număr întreg de forma $n^2+2$ nu se divide cu $5$.

14. Determină clasa $\hat{a}\in {\mathbb{Z}}_{13}$ pentru care ${\hat{a}}^{-1}=\hat{3}$.

15. (Exercițiu tip Bacalaureat M1.) În ${\mathbb{Z}}_7$: a) arată că orice clasă nenulă este inversabilă și scrie inversele; b) rezolvă ecuația $\hat{3}\cdot \hat{x}+\hat{4}=\hat{2}$; c) rezolvă ecuația ${\hat{x}}^2=\hat{2}$.

16. Rezolvă în ${\mathbb{Z}}_5$ sistemul $\hat{2}\hat{x}+\hat{3}\hat{y}=\hat{1}$, $\hat{x}+\hat{y}=\hat{4}$, fără să te uiți la Exemplul 5.

17. Determină toate numerele $n$ cu $2\le n\le 12$ pentru care clasa $\hat{3}$ este inversabilă în ${\mathbb{Z}}_n$.

18. (Provocare.) Fie $d=(a,n)$. Arată că ecuația $\hat{a}\cdot \hat{x}=\hat{b}$ are soluții în ${\mathbb{Z}}_n$ dacă și numai dacă $d\mid b$, și că atunci are exact $d$ soluții.

Răspunsuri și explicații

1. Sunt prime cu $9$ clasele al căror reprezentant nu e multiplu de $3$: $U({\mathbb{Z}}_9)=\{\hat{1},\hat{2},\hat{4},\hat{5},\hat{7},\hat{8}\}$, șase clase.

2. ${\hat{1}}^{-1}=\hat{1}$; ${\hat{2}}^{-1}=\hat{5}$ ($10=9+1$); ${\hat{4}}^{-1}=\hat{7}$ ($28=3\cdot 9+1$); ${\hat{5}}^{-1}=\hat{2}$; ${\hat{7}}^{-1}=\hat{4}$; ${\hat{8}}^{-1}=\hat{8}$ ($64=7\cdot 9+1$).

3. În ${\mathbb{Z}}_{15}$: $(6,15)=3\ne 1$, deci nu. În ${\mathbb{Z}}_{25}$: $(6,25)=1$, deci da; inversul este $\widehat{21}$, pentru că $6\cdot 21=126=5\cdot 25+1$.

4. Cum $(4,9)=1$, ecuația cere chiar inversul lui $\hat{4}$: din $28=3\cdot 9+1$ obținem $\hat{x}=\hat{7}$. Verificare: $\hat{4}\cdot \hat{7}=\widehat{28}=\hat{1}$ ✓.

5. $(6,9)=3$ și $3\mid 3$, deci sunt exact trei soluții. Verificând clasele: $\hat{x}\in \{\hat{2},\hat{5},\hat{8}\}$.

6. Fals. Clasa $\hat{0}$ nu este niciodată inversabilă, pentru că $\hat{0}\cdot \hat{b}=\hat{0}\ne \hat{1}$. Enunțul corect este: dacă $p$ e prim, toate clasele nenule din ${\mathbb{Z}}_p$ sunt inversabile.

7. $\hat{5}\hat{x}=\hat{1}-\hat{3}=\hat{9}$; din $45=5\cdot 9$ rezultă ${\hat{5}}^{-1}=\hat{9}$, deci $\hat{x}=\hat{9}\cdot \hat{9}=\widehat{81}=\hat{4}$. Verificare: $\widehat{20}+\hat{3}=\hat{9}+\hat{3}=\hat{1}$ ✓.

8. În ${\mathbb{Z}}_{16}$ sunt inversabile clasele impare: $\hat{1},\hat{3},\hat{5},\hat{7},\hat{9},\widehat{11},\widehat{13},\widehat{15}$, deci opt. În ${\mathbb{Z}}_{13}$, cum $13$ e prim, sunt inversabile toate cele douăsprezece clase nenule.

9. $(9,20)=1$, iar $9\cdot 9=81=4\cdot 20+1$, deci ${\hat{9}}^{-1}=\hat{9}$.

10. Fals. Exercițiul $5$ dă un contraexemplu: $\hat{6}\hat{x}=\hat{3}$ are trei soluții în ${\mathbb{Z}}_9$. Afirmația e adevărată doar când $\hat{a}$ este inversabilă.

11. Verificăm pătratele claselor din ${\mathbb{Z}}_{12}$: ${\hat{2}}^2=\hat{4}$, ${\hat{4}}^2=\widehat{16}=\hat{4}$, ${\hat{8}}^2=\widehat{64}=\hat{4}$, ${\widehat{10}}^2=\widehat{100}=\hat{4}$, iar celelalte pătrate diferă de $\hat{4}$. Soluțiile sunt $\hat{2},\hat{4},\hat{8},\widehat{10}$.

12. Poziția după $x$ pași este clasa lui $7x$ în ${\mathbb{Z}}_{24}$, deci rezolvăm $\hat{7}\cdot \hat{x}=\hat{1}$. Cum $(7,24)=1$ și $7\cdot 7=49=2\cdot 24+1$, avem ${\hat{7}}^{-1}=\hat{7}$, deci $\hat{x}=\hat{7}$: după șapte pași.

13. În ${\mathbb{Z}}_5$ pătratele sunt $\hat{0},\hat{1},\hat{4},\hat{4},\hat{1}$, deci ${\hat{n}}^2\in \{\hat{0},\hat{1},\hat{4}\}$ și ${\hat{n}}^2+\hat{2}\in \{\hat{2},\hat{3},\hat{1}\}$. Clasa $\hat{0}$ nu apare niciodată, deci $5\nmid n^2+2$ pentru orice $n\in \mathbb{Z}$.

14. Relația ${\hat{a}}^{-1}=\hat{3}$ înseamnă $\hat{a}\cdot \hat{3}=\hat{1}$, deci $\hat{a}={\hat{3}}^{-1}$. Din $27=2\cdot 13+1$ rezultă ${\hat{3}}^{-1}=\hat{9}$, deci $\hat{a}=\hat{9}$.

15. a) $7$ este prim, deci toate cele șase clase nenule sunt inversabile: ${\hat{1}}^{-1}=\hat{1}$, ${\hat{2}}^{-1}=\hat{4}$, ${\hat{3}}^{-1}=\hat{5}$, ${\hat{4}}^{-1}=\hat{2}$, ${\hat{5}}^{-1}=\hat{3}$, ${\hat{6}}^{-1}=\hat{6}$. b) $\hat{3}\hat{x}=\hat{2}-\hat{4}=\widehat{-2}=\hat{5}$, deci $\hat{x}={\hat{3}}^{-1}\cdot \hat{5}=\hat{5}\cdot \hat{5}=\widehat{25}=\hat{4}$; verificare: $\widehat{12}+\hat{4}=\hat{5}+\hat{4}=\hat{9}=\hat{2}$ ✓. c) Pătratele claselor din ${\mathbb{Z}}_7$ sunt $\hat{0},\hat{1},\hat{4},\hat{2},\hat{2},\hat{4},\hat{1}$, deci ${\hat{x}}^2=\hat{2}$ pentru $\hat{x}\in \{\hat{3},\hat{4}\}$.

16. Soluția este $(\hat{1},\hat{3})$, ca în Exemplul 5. Dacă ai obținut altceva, verifică pasul $\hat{2}-\hat{3}=\widehat{-1}=\hat{4}$: opusul unei clase se calculează ca $\widehat{n-a}$.

17. Clasa $\hat{3}$ este inversabilă exact când $(3,n)=1$, adică atunci când $n$ nu este multiplu de $3$: $n\in \{2,4,5,7,8,10,11\}$.

18. Dacă $\hat{a}\hat{x}=\hat{b}$ are soluție, există $k$ cu $ax-b=kn$, deci $b=ax-kn$; cum $d\mid a$ și $d\mid n$, rezultă $d\mid b$. Reciproc, dacă $d\mid b$, scriem $a=d{a}_1$, $n=d{n}_1$, $b=d{b}_1$, unde $(a_1,n_1)=1$. Condiția $n\mid (ax-b)$ devine $d{n}_1\mid d(a_{1}x-b_1)$, adică $n_1\mid (a_{1}x-b_1)$: în ${\mathbb{Z}}_{n_1}$, ecuația $\widehat{a_1}\cdot \hat{x}=\widehat{b_1}$ are, prin metoda inversului, exact o soluție, adică un singur rest $x_0$ la împărțirea cu $n_1$. Numerele cuprinse între $0$ și $n-1$ care dau acest rest sunt $x_0,x_0+n_1,\dots ,x_0+(d-1)n_1$, adică exact $d$ clase din ${\mathbb{Z}}_n$.

De reținut

• O clasă $\hat{a}\in {\mathbb{Z}}_n$ este inversabilă dacă există $\hat{b}$ cu $\hat{a}\cdot \hat{b}=\hat{1}$, iar această clasă $\hat{b}$, numită inversul lui $\hat{a}$ și notată ${\hat{a}}^{-1}$, este unică atunci când există.
• Clasa $\hat{a}$ este inversabilă în ${\mathbb{Z}}_n$ dacă și numai dacă $(a,n)=1$, deci mulțimea $U({\mathbb{Z}}_n,\cdot )$ este formată exact din clasele ai căror reprezentanți sunt primi cu $n$.
• Dacă $p$ este un număr prim, toate cele $p-1$ clase nenule din ${\mathbb{Z}}_p$ sunt inversabile, în timp ce clasa $\hat{0}$ nu este inversabilă în niciun ${\mathbb{Z}}_n$.
• Ecuația $\hat{a}\cdot \hat{x}=\hat{b}$ se rezolvă prin înmulțire cu ${\hat{a}}^{-1}$ atunci când $(a,n)=1$, caz în care are exact o soluție, și prin verificarea celor $n$ clase atunci când $\hat{a}$ nu este inversabilă.
• Dacă $d=(a,n)>1$, ecuația $\hat{a}\cdot \hat{x}=\hat{b}$ are soluții numai când $d\mid b$, iar atunci numărul soluțiilor este exact $d$.

Greșeli frecvente

• „Împărțim ambii membri la $\hat{a}$." Împărțirea nu există în ${\mathbb{Z}}_n$. Scrie explicit „înmulțim ambii membri cu ${\hat{a}}^{-1}$" și, înainte, justifică existența inversului prin $(a,n)=1$; fără această justificare, pasul nu primește punctaj.
• Confuzia dintre „nenulă" și „inversabilă". În ${\mathbb{Z}}_{12}$, clasa $\hat{4}$ este nenulă, dar nu este inversabilă. Echivalența „nenul $\Rightarrow$ inversabil" este adevărată doar în ${\mathbb{Z}}_p$ cu $p$ prim.
• Anularea unui produs. Din $\hat{x}\cdot (\hat{x}+\hat{1})=\hat{0}$ în ${\mathbb{Z}}_6$ nu rezultă că unul dintre factori este $\hat{0}$; ecuația are patru soluții, nu două. Când $n$ este compus, singura metodă sigură este verificarea claselor.
• Uitarea cazului fără soluții. O ecuație liniară în ${\mathbb{Z}}_n$ poate să nu aibă nicio soluție, ca $\hat{4}\hat{x}=\hat{3}$ în ${\mathbb{Z}}_6$. Răspunsul „mulțimea soluțiilor este vidă" este un răspuns complet, dacă e însoțit de motivul: $(4,6)=2\nmid 3$.
• Numărul soluțiilor ghicit. După ce ai găsit o soluție cu $\hat{a}$ neinversabilă, nu te opri: mai există încă $d-1$. Verificarea tuturor claselor e singura care garantează că nu ai pierdut soluții.

Aplică acasă

1. Harta inversabilelor. Scrie pe o foaie, pentru $n$ de la $2$ la $12$, mulțimea $U({\mathbb{Z}}_n)$ și numărul elementelor ei. Marchează cu roșu valorile lui $n$ pentru care toate clasele nenule sunt inversabile și compară lista obținută cu lista numerelor prime.

2. Inversul, cronometrat. Alege cinci perechi $(a,n)$ cu $n$ între $20$ și $40$ și $(a,n)=1$. Calculează fiecare invers prin metoda numerelor $1+kn$ și notează câți pași ți-au trebuit. Vei observa că metoda e rapidă când $a$ e mic și lentă când $a$ e aproape de $n$ — în acest al doilea caz, lucrează cu reprezentantul negativ al clasei.

3. Un criteriu de divizibilitate propriu. Folosind clasele modulo $9$, explică de ce un număr se divide cu $9$ exact atunci când suma cifrelor lui se divide cu $9$. Pornește de la $\widehat{10}=\hat{1}$ în ${\mathbb{Z}}_9$ și scrie numărul în baza zece.

Pentru părinți și profesori

Lecția răspunde la întrebarea pe care programa de matematică-informatică o pune explicit: care sunt elementele inversabile ale monoidului $({\mathbb{Z}}_n,\cdot )$ și cum se compară situația când $n$ este prim cu cea când $n$ este compus. Teorema $(a,n)=1$ se demonstrează integral, în ambele sensuri, iar demonstrația implicației inverse folosește un raționament de numărare — o funcție injectivă de la o mulțime finită la ea însăși este bijectivă — care merită subliniat, pentru că se va repeta de multe ori în anul de BAC M1. Indicatorul lui Euler este doar menționat, nu predat.

De verificat în caiet: (1) înainte de orice înmulțire cu inversul apare justificarea $(a,n)=1$; (2) la ecuațiile cu coeficient neinversabil sunt scrise toate soluțiile, nu prima găsită; (3) rezultatul e verificat în ecuația inițială; (4) nu apare nicăieri simbolul de împărțire între clase. Întrebări de control: „Când este o clasă inversabilă?"; „De ce $\hat{0}$ nu are invers?"; „Câte soluții are $\hat{4}\hat{x}=\hat{2}$ în ${\mathbb{Z}}_6$ și de ce?"; „Cum arăți că $n^2+1$ nu se divide cu $3$?".

La BAC M1, subiectul apare în Subiectul al II-lea, de obicei în trei trepte: determinarea mulțimii elementelor inversabile, o ecuație liniară rezolvată cu inversul și o ecuație fără soluții sau cu mai multe soluții, care testează înțelegerea criteriului. Semn că elevul a înțeles: privește o ecuație în ${\mathbb{Z}}_n$ și spune numărul soluțiilor înainte de a le calcula, doar din $(a,n)$.

Întrebări frecvente

Ce înseamnă că o clasă de resturi este inversabilă?

O clasă $\hat{a}$ din ${\mathbb{Z}}_n$ este inversabilă dacă există o clasă $\hat{b}$ cu $\hat{a}\cdot \hat{b}=\hat{1}$, adică dacă produsul lor este elementul neutru al înmulțirii claselor. Clasa $\hat{b}$ se numește inversul lui $\hat{a}$, se notează ${\hat{a}}^{-1}$ și este unică. Mulțimea claselor inversabile se notează $U({\mathbb{Z}}_n)$.

Când este o clasă de resturi inversabilă în Z_n?

Exact atunci când reprezentantul ei este prim cu $n$, adică $(a,n)=1$. De exemplu, în ${\mathbb{Z}}_{12}$ sunt inversabile clasele $\hat{1},\hat{5},\hat{7},\widehat{11}$, iar $\hat{4}$ nu este, pentru că $(4,12)=4$. Criteriul se demonstrează în ambele sensuri și este cel mai folosit rezultat al lecției.

Cum se calculează inversul unei clase de resturi?

Se caută primul număr de forma $1+kn$ care se divide cu $a$, iar câtul obținut, redus modulo $n$, este inversul. De exemplu, pentru $\hat{7}$ în ${\mathbb{Z}}_{15}$: numerele $16,31,46,61,76,91$, iar $91=7\cdot 13$, deci ${\hat{7}}^{-1}=\widehat{13}$. Verificarea finală, $7\cdot 13=91=6\cdot 15+1$, este obligatorie.

Cum se rezolvă o ecuație cu clase de resturi la Bacalaureat M1?

Se calculează întâi $d=(a,n)$. Dacă $d=1$, se înmulțesc ambii membri cu ${\hat{a}}^{-1}$ și se obține soluția unică $\hat{x}={\hat{a}}^{-1}\cdot \hat{b}$. Dacă $d>1$, se verifică pe rând cele $n$ clase: ecuația are soluții doar când $d\mid b$, iar atunci are exact $d$ soluții.

De ce în Z_7 toate clasele nenule sunt inversabile?

Pentru că $7$ este număr prim, deci orice $a$ cu $1\le a\le 6$ este prim cu $7$, iar criteriul $(a,7)=1$ este îndeplinit automat. Același lucru se întâmplă în orice ${\mathbb{Z}}_p$ cu $p$ prim. Clasa $\hat{0}$ rămâne, și acolo, neinversabilă, pentru că orice produs cu ea este $\hat{0}$.

Care este mulțimea U(Z_n) și câte elemente are?

Este mulțimea claselor inversabile față de înmulțire, $U({\mathbb{Z}}_n,\cdot )=\{\hat{a}\mid (a,n)=1\}$. Numărul elementelor ei se notează $\phi (n)$, indicatorul lui Euler, dar la clasa a 12-a se numără direct: se listează clasele prime cu $n$. De exemplu, $U({\mathbb{Z}}_{10})=\{\hat{1},\hat{3},\hat{7},\hat{9}\}$ are patru elemente.

Poate o ecuație de gradul al doilea să aibă patru soluții?

În ${\mathbb{Z}}_n$, da. Ecuația ${\hat{x}}^2=\hat{1}$ are în ${\mathbb{Z}}_8$ soluțiile $\hat{1},\hat{3},\hat{5},\hat{7}$, deci patru la număr. Explicația este că, atunci când $n$ este compus, un produs de clase poate fi nul fără ca vreun factor să fie nul, deci descompunerea în factori nu mai limitează numărul de soluții.

Cum folosesc clasele de resturi la probleme de divizibilitate?

Traduci întrebarea despre numere întregi într-una despre clase: „numărul se divide cu $n$" înseamnă „clasa lui este $\hat{0}$". Apoi verifici toate cele $n$ clase, ceea ce e un calcul finit. Așa arăți, în trei rânduri, că niciun număr de forma $n^2+1$ nu se divide cu $3$.