Exerciții rezolvate cu aritmetică modulară (ℤₙ) — clasa a 12-a

$\mathbb{Z}_n = \{\hat{0}, \hat{1}, \ldots, \widehat{n-1}\}$ are $n$ elemente. Deci $\mathbb{Z}_5$ are $5$.

$4 + 5 = 9$, și $9 \bmod 6 = 3$. Deci răspunsul este $\hat{3}$.

$3 + 5 = 8 \equiv 0 \pmod{8}$, deci inversul este $\hat{5}$.

$2 \cdot 3 = 6 \equiv 1 \pmod{5}$, deci inversul este $\hat{3}$.

$\gcd(2, 6) = 2 \ne 1$, deci $\hat{2}$ nu are invers multiplicativ în $\mathbb{Z}_6$. ($\hat{1}$ și $\hat{5}$ sunt coprime cu $6$ și sunt inversabile.)

$\hat{2} \cdot \hat{3} = \hat{6} = \hat{0}$. ($\mathbb{Z}_6$ are divizori ai lui zero!)

Prin Fermat, $3^{6} \equiv 1 \pmod 7$, deci $\hat{3}^{\,6} = \hat{1}$.

$\mathbb{Z}_n$ este corp dacă și numai dacă orice element nenul este inversabil, dacă și numai dacă orice element de la $1$ la $n - 1$ este coprim cu $n$, dacă și numai dacă $n$ este prim.

Scriem $30=2\cdot3\cdot5$, produs de trei prime distincte. Pentru orice modul prim $p$, ecuația $x^2\equiv x\pmod p$ (adică $x(x-1)\equiv0$) are exact $2$ soluții: $x\equiv0$ și $x\equiv1$ (căci $\mathbb{Z}_p$ este corp, fără divizori ai lui zero). Prin Teorema Chineză a Resturilor, fiecare combinație de soluții modulo $2,3,5$ dă exact o soluție modulo $30$, deci numărul total este $2\cdot2\cdot2=8$. Verificare directă (câteva soluții): $\hat0,\hat1,\hat6$ ($36\equiv6$), $\hat{10}$ ($100\equiv10$), $\hat{15}$ ($225\equiv15$), $\hat{16}$ ($256\equiv16$), $\hat{21}$ ($441\equiv21$), $\hat{25}$ ($625\equiv25$) — exact $8$ clase idempotente ✓.

Scriem $40=8\cdot5$, cu $\gcd(8,5)=1$. Modulo $5$ (prim): $x^2\equiv1\pmod5$ are soluțiile $x\equiv1,4$ — exact $2$ soluții, ca de obicei pentru un modul prim. Modulo $8$ (nu prim, ci $2^3$): aici formula standard „$2$ soluții" nu se aplică — trebuie enumerat direct. Testăm toate resturile impare posibile: $1^2=1$, $3^2=9\equiv1$, $5^2=25\equiv1$, $7^2=49\equiv1\pmod8$. Toate cele $4$ clase impare satisfac $x^2\equiv1\pmod8$! Prin Teorema Chineză a Resturilor, numărul total de soluții modulo $40$ este $4\cdot2=8$ (nu $2^2=4$, cum ar sugera formula naivă valabilă doar pentru module impare/fără factori $2^k$ cu $k\ge3$). Verificare directă (soluțiile modulo $40$): $\{1,9,11,19,21,29,31,39\}$ — se poate verifica prin calcul direct că fiecare din aceste $8$ clase satisface $x^2\equiv1\pmod{40}$ ✓.

Pentru reprezentantul $x=0$: $2^0=1$, deci $1\bmod16=1$. Pentru reprezentantul $x=4$ (aceeași clasă $\hat0\in\mathbb{Z}_4$, căci $4-0=4$ e multiplu de $4$): $2^4=16$, deci $16\bmod16=0$. Diferența absolută: $|1-0|=1$. Cum cele două rezultate ($1$ și $0$) diferă, $f$ NU este bine definită — rezultatul depinde de reprezentantul ales, nu doar de clasă. Acest exemplu arată de ce, la construcția funcțiilor pe $\mathbb{Z}_n$, buna-definire trebuie verificată explicit, nu presupusă. ✓

Condiția de bună-definire este: pentru orice doi reprezentanți $x$ și $x+n$ ai aceleiași clase din $\mathbb{Z}_n$, trebuie ca $5^{x+n}\equiv5^x\pmod9$, adică (simplificând prin $5^x$, invers­abil modulo $9$) $5^n\equiv1\pmod9$. Calculăm puterile lui $5$ modulo $9$: $5^1=5$, $5^2=25\equiv7$, $5^3=35\equiv8$, $5^4=40\equiv4$, $5^5=20\equiv2$, $5^6=10\equiv1\pmod9$. Deci ordinul multiplicativ al lui $5$ modulo $9$ este exact $6$ — $f$ este bine definită dacă și numai dacă $n$ este multiplu de $6$. Cel mai mic $n\ge2$ multiplu de $6$ este $n=6$. Verificare: pentru $n=6$, $5^6\equiv1\pmod9$, deci $5^{x+6}=5^x\cdot5^6\equiv5^x\cdot1=5^x\pmod9$ pentru orice $x$ — bine definită. Pentru $n=3$ (candidat mai mic), $5^3\equiv8\ne1\pmod9$ — NU e bine definită (contraexemplu: $x=0\Rightarrow5^0=1$, dar $x=3\Rightarrow5^3\equiv8\ne1$, deși $\hat0=\hat3$ în $\mathbb{Z}_3$... de fapt reprezentanții claselor din $\mathbb{Z}_3$ diferă prin multipli de $3$, iar $5^3\not\equiv1$ arată direct eșecul). Pentru $n=4$: $5^4\equiv4\ne1$ — eșuează. Cel mai mic $n$ valid este $6$. ✓