Informaţii, definiţii, teoreme, formule, exerciţii şi probleme rezolvate din matematica de liceu. RSS/XML

»CLASE DE RESTURI modulo n

Data publicarii: 19 Iunie, 2010

TEORIE

Teorema impartirii cu rest in multimea numerelor intregi:

Fiind dat un numar natural n, nenul, pentru orice numar intreg k exista numerele unice

q (intreg) si r (natural, mai mic decat n), astfel incat a = nq + r.

Observatii:

1) Numarul q este catul, iar r este restul impartirii numarului a la n.

2) Notatie: r = a(mod n); se citeste "a modulo n" si r se numeste

redusul modulo n al numarului a.

3) Imaginandu-ne ca impartim toate numerele intregi la n, este evident ca resturile

obtinute sunt mai mari sau egale cu 0 (in cazul multiplilor lui n), dar mai mici, cel mult

egale cu n - 1; deci exista exact n tipuri de numere intregi, care se constituie in n

submultimi, disjuncte 2 cate 2, a caror reuniune formeaza multimea Z (se spune ca

se defineste astfel o partitie a multimii numerelor intregi).

In cazul particular n = 5, se noteaza astfel:

$\hat{0}=\{...-10,-5,0,5,10...\}=\{5k|k\in{\mathbb{Z}}\},$ \hat{0}=\{...-10,-5,0,5,10...\}=\{5k|k\in{\mathbb{Z}}\},

$\hat{1}=\{...-9,-4,1,6,11...\}=\{5k+1|k\in{\mathbb{Z}}\},$ \hat{1}=\{...-9,-4,1,6,11...\}=\{5k+1|k\in{\mathbb{Z}}\},

$\hat{2}=\{...-8,-3,2,7,12...\}=\{5k+2|k\in{\mathbb{Z}}\},$ \hat{2}=\{...-8,-3,2,7,12...\}=\{5k+2|k\in{\mathbb{Z}}\},

$\hat{3}=\{...-7,-2,3,8,13...\}=\{5k+3|k\in{\mathbb{Z}}\},$ \hat{3}=\{...-7,-2,3,8,13...\}=\{5k+3|k\in{\mathbb{Z}}\},

$\hat{4}=\{...-6,-1,4,9,14...\}=\{5k+4|k\in{\mathbb{Z}}\}.$ \hat{4}=\{...-6,-1,4,9,14...\}=\{5k+4|k\in{\mathbb{Z}}\}.

4) In general, pentru un n oarecare, submultimile respective sunt:

$\hat{0},\;\hat{1},\;\hat{2},\;\cdots,\widehat{n - 1},$ \hat{0},\;\hat{1},\;\hat{2},\;\cdots,\widehat{n - 1},

ele continand toate numerele intregi de forma nk, nk + 1, nk + 2, ... , respectiv nk + (n - 1),

unde k parcurge multimea Z.

5) Multimile

$\hat{0},\;\hat{1},\;\hat{2},\;\cdots,\widehat{n-1},$ \hat{0},\;\hat{1},\;\hat{2},\;\cdots,\widehat{n-1},

se numesc clase de resturi modulo n, numerele 0, 1, 2, 3, ... , n - 1 fiind numite

reprezentantii canonici ai multimilor respective (sunt cele mai mici numere naturale,

cel mult egale cu n - 1, din multimile respective).

Pentru multimea claselor de resturi modulo n se foloseste notatia:

$\mathbb{Z}_n=\{\hat{0},\;\hat{1},\;\hat{2},\;\cdots,\widehat{n-1}\}.$ \mathbb{Z}_n=\{\hat{0},\;\hat{1},\;\hat{2},\;\cdots,\widehat{n-1}\}.

${\mathbb{Z}}/{n{\mathbb{Z}}}=\{\hat{0},\;\hat{1},\;\hat{2},\;\cdots,\widehat{n-1}\}$ {\mathbb{Z}}/{n{\mathbb{Z}}}=\{\hat{0},\;\hat{1},\;\hat{2},\;\cdots,\widehat{n-1}\} (multimea cat Z/nZ).

6) In locul unui reprezentant canonic se poate folosi orice alt numar intreg din clasa

respectiva; de pilda, in multimea

$\mathbb{Z}_7,\;putem\; scrie\;\hat{5}=\hat{12},$ \mathbb{Z}_7,\;putem\; scrie\;\hat{5}=\hat{12},

pentru ca este vorba despre reprezentarea aceleasi multimi (a numerelor intregi care

dau acelasi rest 5 prin impartire la 7).

7) De retinut:

${\hat{a}=\hat{b}}\Leftrightarrow{a}\equiv{b}(mod\; n)\Leftrightarrow{\exists{k}\in{\mathbb{Z}},\;astfel\;incat\;a-b=nk.}$ {\hat{a}=\hat{b}}\Leftrightarrow{a}\equiv{b}(mod\; n)\Leftrightarrow{\exists{k}\in{\mathbb{Z}},\;astfel\;incat\;a-b=nk.}