Clase de resturi modulo n (Zn)

Doi întregi $a$ și $b$ sunt congruenți modulo $n$, scris $a\equiv b(\mathrm{mod}n)$, dacă $n\mid a-b$, adică dau același rest la împărțirea prin $n$. Mulțimea întregilor congruenți cu $a$ modulo $n$ este clasa $\hat{a}=\{a+kn\mid k\in \mathbb{Z}\}$. Există exact $n$ clase distincte, iar mulțimea lor este ${\mathbb{Z}}_n=\{\hat{0};\hat{1};\dots ;\widehat{n-1}\}$, pentru $n\ge 2$.

Operațiile se fac cu reprezentanți: $\hat{a}+\hat{b}=\widehat{a+b}$ și $\hat{a}\cdot \hat{b}=\widehat{ab}$. În ${\mathbb{Z}}_5$, $\hat{3}+\hat{4}=\hat{7}=\hat{2}$ și $\hat{3}\cdot \hat{4}=\widehat{12}=\hat{2}$. Față de adunare, ${\mathbb{Z}}_n$ este grup abelian cu neutrul $\hat{0}$; cu ambele operații este inel comutativ cu unitatea $\hat{1}$. Inelul ${\mathbb{Z}}_n$ este corp dacă și numai dacă $n$ este prim.

Operațiile sunt bine definite. Rezultatul nu depinde de reprezentanții aleși: dacă $a^{\prime }=a+kn$ și $b^{\prime }=b+tn$, atunci $a^{\prime }+b^{\prime }=a+b+(k+t)n$ și $a^{\prime }{b}^{\prime }=ab+n(at+bk+ktn)$, deci $\widehat{a^{\prime }+b^{\prime }}=\widehat{a+b}$ și $\widehat{a^{\prime }{b}^{\prime }}=\widehat{ab}$. Egalitatea $\hat{a}=\hat{b}$ are loc dacă și numai dacă $n\mid a-b$.

Opus și invers. Opusul lui $\hat{a}$ este $\widehat{n-a}$ când $a\ne 0$. Clasa $\hat{a}$ este inversabilă în ${\mathbb{Z}}_n$ dacă și numai dacă $\mathrm{cmmdc}(a;n)=1$. Dacă $\mathrm{cmmdc}(a;n)=1$, există întregii $u,v$ cu $au+nv=1$, deci $\hat{a}\cdot \hat{u}=\hat{1}$. Dacă $d=\mathrm{cmmdc}(a;n)>1$ și $ab=1+kn$, atunci $d$ ar divide $1$, ceea ce este imposibil. De aici: ${\mathbb{Z}}_n$ este corp dacă și numai dacă $n$ este prim, fiindcă pentru $n$ prim toate numerele $1;2;\dots ;n-1$ sunt prime cu $n$. Pentru $n=pq$ cu $1<p,q<n$ avem $\hat{p}\cdot \hat{q}=\hat{0}$ cu ambii factori nenuli (divizori ai lui zero). Față de înmulțire, $({\mathbb{Z}}_n,\cdot )$ este monoid comutativ cu neutrul $\hat{1}$ și nu este niciodată grup, deoarece $\hat{0}$ nu are invers; mulțimea ${\mathbb{Z}}_p\setminus \{\hat{0}\}$ cu înmulțirea este grup, deoarece ${\mathbb{Z}}_p$ este corp.

Exemplu rezolvat 1: tabla înmulțirii în ${\mathbb{Z}}_4$. Tabla arată operația pentru fiecare pereche de clase:

Pe rândul lui $\hat{2}$ nu apare $\hat{1}$, deci $\hat{2}$ nu are invers; $\hat{2}\cdot \hat{2}=\hat{0}$ arată că $\hat{2}$ este divizor al lui zero. Inversabile sunt $\hat{1}$ și $\hat{3}$, adică exact clasele cu $\mathrm{cmmdc}(a;4)=1$.

Exemplu rezolvat 2: ecuații liniare. Ecuația $\hat{a}x=\hat{b}$ în ${\mathbb{Z}}_n$ are soluție unică dacă $\mathrm{cmmdc}(a;n)=1$. Dacă $d=\mathrm{cmmdc}(a;n)>1$, ecuația are soluții dacă și numai dacă $d\mid b$, și atunci are exact $d$ soluții.

1. În ${\mathbb{Z}}_5$, ecuația $\hat{3}x=\hat{2}$: $\hat{3}\cdot \hat{2}=\hat{6}=\hat{1}$, deci inversul lui $\hat{3}$ este $\hat{2}$. Înmulțim cu $\hat{2}$ și obținem $x=\hat{2}\cdot \hat{2}=\hat{4}$; verificare: $\hat{3}\cdot \hat{4}=\widehat{12}=\hat{2}$.
2. În ${\mathbb{Z}}_{10}$, ecuația $\hat{4}x=\hat{6}$: $d=\mathrm{cmmdc}(4;10)=2$ divide $6$, deci există $2$ soluții. Împărțim congruența $4x\equiv 6(\mathrm{mod}10)$ la $2$ și obținem $2x\equiv 3(\mathrm{mod}5)$, deci $x\equiv 4(\mathrm{mod}5)$. Soluțiile sunt $\hat{4}$ și $\hat{9}$; într-adevăr $4\cdot 4=16\equiv 6$ și $4\cdot 9=36\equiv 6$.
3. În ${\mathbb{Z}}_6$, ecuația $\hat{2}x=\hat{1}$ nu are soluții, deoarece $\mathrm{cmmdc}(2;6)=2$ nu divide $1$.

Exemplu rezolvat 3: puteri. Calculăm ${\hat{3}}^{100}$ în ${\mathbb{Z}}_7$ și ultima cifră a lui $7^{2023}$.

1. Puterile succesive ale lui $\hat{3}$ în ${\mathbb{Z}}_7$ sunt $\hat{3};\hat{2};\hat{6};\hat{4};\hat{5};\hat{1}$; după $6$ pași se revine la $\hat{1}$, deci ordinul lui $\hat{3}$ este $6$.
2. Cum $100=6\cdot 16+4$, avem ${\hat{3}}^{100}=({\hat{3}}^6{)}^{16}\cdot {\hat{3}}^4={\hat{3}}^4=\hat{4}$.
3. Ultima cifră a unui număr este clasa lui modulo $10$. În ${\mathbb{Z}}_{10}$, puterile lui $\hat{7}$ sunt $\hat{7};\hat{9};\hat{3};\hat{1}$, deci se repetă din $4$ în $4$.
4. Cum $2023=4\cdot 505+3$, avem ${\hat{7}}^{2023}={\hat{7}}^3=\hat{3}$: ultima cifră a lui $7^{2023}$ este $3$.

Ecuația $x^2=\hat{1}$. În ${\mathbb{Z}}_7$, care este corp, soluțiile sunt $\hat{1}$ și $\hat{6}$, doar două. În ${\mathbb{Z}}_8$, care nu este corp, soluțiile sunt $\hat{1}$, $\hat{3}$, $\hat{5}$ și $\hat{7}$, patru la număr, deși într-un corp o ecuație de gradul al doilea are cel mult două soluții. Cauza este existența divizorilor lui zero: din $(x-\hat{1})(x+\hat{1})=\hat{0}$ nu rezultă $x-\hat{1}=\hat{0}$ sau $x+\hat{1}=\hat{0}$.

Greșeli frecvente

• Greșit: $\hat{2}+\hat{4}$ este o clasă nouă $\hat{6}$ în ${\mathbb{Z}}_5$.
  Corect: $\hat{6}=\hat{1}$; reprezentanții se reduc modulo $5$.
• Greșit: ${\mathbb{Z}}_n$ este corp pentru orice $n\ge 2$.
  Corect: este corp dacă și numai dacă $n$ este prim.
• Greșit: $\hat{a}=\hat{b}$ în ${\mathbb{Z}}_n$ numai când $a=b$.
  Corect: $\hat{a}=\hat{b}$ dacă și numai dacă $n\mid a-b$; în ${\mathbb{Z}}_5$, $\widehat{12}=\hat{2}$.
• Greșit: ecuația $\hat{2}x=\hat{1}$ în ${\mathbb{Z}}_6$ are soluția $x=\frac{1}{2}$.
  Corect: $\frac{1}{2}$ nu este clasă de resturi, iar ecuația nu are soluții, fiindcă $\mathrm{cmmdc}(2;6)=2$ nu divide $1$.
• Greșit: din $\hat{2}x=\hat{2}y$ în ${\mathbb{Z}}_6$ rezultă $x=y$.
  Corect: $\hat{2}\cdot \hat{1}=\hat{2}\cdot \hat{4}=\hat{2}$, dar $\hat{1}\ne \hat{4}$; se simplifică numai cu o clasă inversabilă.

Înainte și după