Clasele de resturi în aritmetică: pe scurt

Reducerea modulo $n$ duce fiecare întreg $a$ în clasa lui $\hat{a}$ și păstrează ambele operații: $\widehat{a+b}=\hat{a}+\hat{b}$, $\widehat{ab}=\hat{a}\hat{b}$, iar $n\mid a$ exact când $\hat{a}=\hat{0}$. De aici regula practică: orice expresie polinomială cu coeficienți întregi se reduce termen cu termen, deci o afirmație despre toate numerele întregi se verifică pe cele $n$ clase — un număr finit de cazuri în locul unei infinități. Atenție la sensul invers: din $\hat{a}=\hat{b}$ rezultă doar $n\mid (a-b)$.

Rețetele lecției: pentru o divizibilitate, descompui modulul în factori primi între ei, verifici toate clasele pentru fiecare factor și reunești concluziile (pasul final cere ca factorii să fie primi între ei). Pentru ultima cifră a unei puteri lucrezi în ${\mathbb{Z}}_{10}$: afli ordinul clasei bazei, împarți exponentul la el și păstrezi restul; pentru ultimele două cifre, în ${\mathbb{Z}}_{100}$. Pentru restul unei puteri mari folosești Consecința 2 a teoremei lui Lagrange în grupul claselor inversabile: dacă $(a,n)=1$ și $m=\mathrm{card}U({\mathbb{Z}}_n,\cdot )$, atunci ${\hat{a}}^m=\hat{1}$. Pentru a arăta că o ecuație nu are soluții întregi, alegi un modul potrivit — $3$, $4$, $5$ sau $8$ la pătrate, $7$ sau $9$ la cuburi, un divizor al unui coeficient ca să elimini un termen — și arăți că cei doi membri nu iau niciodată aceeași clasă; metoda respinge, dar nu confirmă. Criteriile de divizibilitate cu $9$ și cu $11$ ies din $\widehat{10}=\hat{1}$, respectiv $\widehat{10}=\widehat{-1}$.

Exerciții din această mini-lecție

1. Ultima cifră a numărului $13^{2027}$ este:

   • a) $1$
   • b) $3$
   • c) $7$
   • d) $9$
   Vezi răspunsul

   Răspuns corect: c) $7$

   Lucrăm în ${\mathbb{Z}}_{10}$, unde $\widehat{13}=\hat{3}$. Puterile lui $\hat{3}$ sunt $\hat{3},\hat{9},\hat{7},\hat{1}$, deci ordinul este $4$. Cum $2027=4\cdot 506+3$, obținem ${\widehat{13}}^{2027}={\hat{3}}^3=\hat{7}$. Variantele $3$, $9$ și $1$ corespund resturilor $1$, $2$ și $0$ — greșeala tipică este împărțirea exponentului la altceva decât la ordin.

2. Restul împărțirii numărului $7^{2026}$ la $15$ este:

   • a) $1$
   • b) $4$
   • c) $7$
   • d) $13$
   Vezi răspunsul

   Răspuns corect: b) $4$

   Cum $(7,15)=1$, clasa $\hat{7}$ este inversabilă. Grupul $U({\mathbb{Z}}_{15},\cdot )=\left\{\hat{1},\hat{2},\hat{4},\hat{7},\hat{8},\widehat{11},\widehat{13},\widehat{14}\right\}$ are $8$ elemente, deci, din Consecința 2 a teoremei lui Lagrange, ${\hat{7}}^8=\hat{1}$. Din $2026=8\cdot 253+2$ rămâne ${\hat{7}}^2=\widehat{49}=\hat{4}$, deci restul este $4$.

3. Ecuația $x^2+y^2=2027$ nu are soluții în numere întregi. Ce modul o arată cel mai repede?

   • a) modulo $4$
   • b) modulo $3$
   • c) modulo $5$
   • d) modulo $10$
   Vezi răspunsul

   Răspuns corect: a) modulo $4$

   Modulo $4$, pătratele sunt doar $\hat{0}$ și $\hat{1}$, deci o sumă de două pătrate este $\hat{0}$, $\hat{1}$ sau $\hat{2}$ — niciodată $\hat{3}$. Dar $2027=4\cdot 506+3$, deci membrul drept este $\hat{3}$: contradicție. Modulo $3$ pătratele sunt tot $\{\hat{0},\hat{1}\}$, dar suma lor poate lua orice valoare, deci nu decide; modulele $5$ și $10$ au mulțimi de pătrate prea mari.