GRUPURI, INELE, CORPURI

download GRUPURI, INELE, CORPURI

of 21

  • date post

    28-Oct-2015
  • Category

    Documents

  • view

    97
  • download

    2

Embed Size (px)

description

Fundamentele Algebrice Ale Informaticii

Transcript of GRUPURI, INELE, CORPURI

  • MODULUL 6GRUPURI, INELE, CORPURI

    Tema are ca scop prezentarea detaliat a noiunilor de aritmetica numerelor ntrgi, carestau la baza multor aplicaii din criptografie precum i din alte domenii ale informaticii.Aceste operaii sunt abordate folosind suportul structurilor algebrice. Algoritmeleprezentate constituie un punct de plecare n abordarea problemelor privind baze de date demare volum. Mediul familiar al obiectelor cu care se lucreaz precum i abordareariguroas a problemelor face ca aceast lecie s constituie un model pe care viitoriiabsolveni s-l poat folosi pentru a aborda singuri tematici similare.

    Studenii vor ntocmi o tem de cas care const n rezolvarea problemelor iexerciiilor propuse. Cuvinte cheie: numere prime, numere prime ntre ele, clase de resturi, uniti ale unui inel,generatori.Indicaii de studiere a temei: Timpul minim pe care trebuie s-l acordai studierii acestuimodul este de 4 ore.Se citete cu atenie i se noteaz ideile principale, ecuaiile matematice, se aprofundeaznoiunile subliniate. Se apeleaz la literatura suplimentar indicat. Se parcurg ntrebrilede control i testele de verificare. Se studiaz problemele i exerciiile rezolvate. Se rezolvexerciiile propuse. Dac nu se neleg rezolvrile sau nu pot da soluii unor problemepropuse se restudiaz subiectul n cauz.

    Cuprins6.1.Teorema mpririi cu rest; relaia de divizibilitate; numere prime.6.2. Cel mai mare divizor comun a dou numere.6.3. Algoritmul lui Euclid.6.4. Grupuri, subgrupuri, grupuri ciclice, teorema lui Lagrange.6.5. Inelul claselor de resturi modulo n.6.6. Produse directe de grupuri i inele.6.7. Teorema chinez.6.8. Caracteristica lui Euler.6.9. Teoremele Fermat, Euler, Wilson.6.10. Probleme rezolvate.6.11. Teme pentru cas.

    Dup parcurgerea i nsuirea acestei teme, studentul va cunoate: Noiuni de baz ale aritmeticii numerelor ntregi; Algoritme de calcularea ctului, restului, a celui mai mare divizor comun; Structura de inel a mulimii claselor de resturi modulo n; Generatori ai grupului unitilor;

  • 6.1 TEOREMA MPRIRII CU REST; RELAIA DEDIVIZIBILITATE; NUMERE PRIME

    Punctul de plecare n structurarea aritmetic a numerelor ntregi l constituiealgoritmul cunoscut sub numele de Teorema mpririi cu rest, avnd urmtorul enun:

    Date fiind numerele ntregi m i n n care n este nenul, exist i sunt unicenumerele ntregi q i r care ndeplinesc condiiile:

    ; 0 1 m nq r r n .Subliniem faptul c teorema afirm pe de o parte existena numerelor q i r, iar pe de

    alt parte unicitatea lor. Existena are la baz algoritmul de mprire bine cunoscut. n ceprivete unicitatea, dac numerele 1 1

    iq r ndeplinesc aceleai condiii ca numerele q i r,atunci: 1 10 ( )m m n q q r r 1 1r r n q q . n aceast egalitatemembrul stng este strict mai mic dect n , deoarece este modului diferenei a dou numerepozitive strict mai mici dect n . Pe de alt parte, membrul drept nu poate fi strict mai micdect n dect dac 1q q , adic dac membrul drept este nul. Dar n acest caz i membrulstng este nul, adic 1r r .

    Cazul 0r conduce la noiunea de divizibilitate:DEFINIIESpunem c n divide m (notm acest lucru n|m) dac exist un numr ntreg q astfel

    nct m = qn. Se mai spune c n este divizor al lui m sau c m este multiplu al lui n, sau c meste divizibil prin n.

    Din definiia relaiei de divizibilitate rezult urmtoarele proprieti ale acesteia:I) reflexivitatea: n|n;II) tranzitivitatea: dac n|m i m|k, atunci n|k;III) dac n|m i m|n, atunci m = n;IV) dac n|m, atunci n m .

    Remarcm c dac 0m , atunci lund 0q , se ndeplinete relaia m qn oricarear fi n. Deci, orice numr este divizor al lui zero, adic orice numr divide pe zero sau zeroeste multiplu al oricrui numr.

    Pe de alt parte, dac 0n , atunci singurul numr m pentru care relaia n|m poate fisatisfcut este 0m . Singurul numr care-l are pe zero ca divizor, deci care este divizibilprin zero, este numai zero.

    Numerele 1 i 1 au fiecare numai doi divizori: 1.Oricare alt numr n n afar de 0, 1, 1 are cel puin patru divizori: 1 i

    n numii i divizori improprii. Ceilali divizori pe care i-ar mai putea avea numrul n senumesc divizori proprii. Evident c orice divizor propriu al lui m are valoarea absolut strictmai mic dect valoarea absolut a lui m.

    Numerele m i n au aceiai divizori dac i numai dac m = n. n acest caz spunemc ele sunt asociate.

  • DEFINIIEUn numr ntreg p se zice c este numr prim dac este diferit de 0, 1, 1 i nu are ali

    divizori n afar de divizorii improprii. Altfel spus, nu are divizori proprii.Un numr care nu este prim se numete numr compus. Evident c dac n este un

    numr compus, atunci el se poate scrie ca produsul a doi divizori proprii, fiecare avndvaloarea absolut strict cuprins ntre unu i valoarea absolut a lui n.

    Numrul 2 este cel mai mic numr prim i este singurul numr prim care este numrpar. Toate celelalte numere prime sunt, firete, impare. De aceea preferm ca n loc s spunemc un numr prim este diferit de 2 i menionm calitatea sa de a fi impar.

    Urmtoarea teorem pune n eviden o proprietate esenial a numerelor prime.TEOREMDac numrul prim p divide produsul a dou numere nenule a i b, atunci p divide cel

    puin unul din cele dou numere.DEMONSTRAIEDeoarece relaia de divizibilitate m|n rmne valabil cnd se schimb semnul lui m

    sau al lui n, este suficient s se demonstreze teorema pentru numerele ntregi pozitive.Prin reducere la absurd presupunem c ar exista numere prime pentru care teorema nu

    este adevrat i c numrul prim p este cel mai mic dintre acestea. n plus, numrul prim pfiind fixat, dintre toate perechile de numere a, b pentru care teorema nu este valabilpresupunem c am ales acea pereche pentru care produsul ab este minim.

    Putem considera c numerele a i b sunt strict mai mici dect p.ntr-adevr, dac a p , aplicnd teorema mpririi cu rest obinem dou numere naturale qi r care ndeplinesc condiiile:

    ; 0a pq r r p ,unde am inut seam c a nu este divizibil cu p. Rezult c numrul:

    ( )rb a pq b ab pbq este divizibil prin p, deoarece produsele ab i pbq suntdivizibile prin p. Aadar numrul a poate fi nlocuit cu numrul r care este strict mai micdect p. La fel se poate proceda i cu numrul b. n concluzie, putem admite c 2ab p .

    Relaia p ab nseamn c exist un numr natural c astfel nct ab = pc i deoarece2ab p rezult c < p. Dac numrul c nu este prim, atunci exist un numr prim q care

    divide pe c, adic exist un numr h astfel nct c = hq. Evident, q < c < p i dinminimalitatea lui p rezult c pentru numrul prim q este adevrat teorema. Deci, din faptulc q|ab rezult q|a sau q|b. n cazul cnd q|a, avem: ab = qsb = pc = phq de unde rezult ph= sb, adic p|sb, n care, evident, sb < ab. Din minimalitatea produsului ab rezult c p|s saup|b, adic p|a sau p|b, ceea ce contrazice presupunerea fcut.

    QEDOBSERVAIEProprietatea enunat n teorema precedent este valabil numai pentru numerele

    prime. Numerele compuse nu au aceast proprietate. ntr-adevr, dac n este un numr naturalcompus, atunci n = ab, n care a i b sunt divizori proprii, deci a < n i b < n. Dac n|a saun|b, atunci ar rezulta n a , respectiv n b .

    TEOREMOrice numr ntreg diferit de 0, 1, 1 se poate descompune n produs de numere prime,

    iar aceast descompunere este unic, n afara semnului acestora.

  • DEMONSTRAIETeorema afirm dou lucruri: pe de o parte existena, iar pe de alt parte unicitatea

    descompunerii.Demonstrm mai nti existena descompunerii.Prin reducere la absurd presupunem c ar exista numere care nu se pot descompune n

    produs de numere prime i fie n numrul cu cea mai mic valoare absolut dintre acestea.Evident c numrul n nu poate fi prim. Dar numrul n nu poate fi nici compus,

    deoarece n acest caz el s-ar scrie ca produs de dou numere, n = ab, numerele a i b avndfiecare valoarea absolut strict mai mic dect valoarea absolut a lui n. Din minimalitatea luin rezult c numerele a i b se pot descompune n produs de numere prime i se obine astfeldescompunerea lui n.

    n ce privete unicitatea presupunem c pe de o parte 1 2... rn p p p , iar pe de altparte 1 2... sn q q q , unde

    ii jp q sunt numere prime nu neaprat distincte.

    Vom arta c r s i c = ; 1,2,...,i iq p i r . Presupunem r s . n egalitatea1 2 1 2... ...r sp p p q q q

    pe baza teoremei precedente, fiecare factor din membrul stng (fiind numr prim) se poatesimplifica cu un numr din membrul drept, cu care este asociat. Schimbnd numerotareafactorilor din membrul drept i nlocuind unii dintre aceti factori cu asociaii lor, putemconsidera ; 1,2,...,i iq p i r . Dup simplificare, relaia anterioar devine:

    1 21 ...r r sq q q .Deoarece nici un numr prim nu poate fi divizor al lui unu rezult c n membrul drept

    nu poate s apar nici un factor prim. Deci:ir s 1 1 2 2, ,..., r rq p q p q p .

    QEDOBSERVAIEUneori este util s punem n eviden factorii primi distinci din descompunerea lui n,

    astfel c aceast descompunere se scrie n felul urmtor:1 2 1 21 2 ... ; , ,...,k kkn p p p N ,

    n care 1 2, ,..., kp p p sunt numere prime distincte. Descompunerea lui n este unic n afaranlocuirii unora din factorii primi cu opuii lor.

    n plus, putem considera c numerele prime 1 2, ,..., kp p p sunt strict pozitive dacscriem pe n sub forma:

    1 2 1 21 2 ... ; , ,...,k kkn p p p N ,unde se pune semnul plus sau minus dup cum n este pozitiv sau negativ.

  • 6.2 CEL MAI MARE DIVIZOR COMUN A DOU NUMERE

    DEFINIIESe numete cel mai mare divizor comun al numerelor a i b numrul pozitiv d, notat

    (a,b), care are urmtoarele proprieti: iid a d bc a c b c d

    Numerele a i b se spune c sunt prime ntre ele dac (a,b) = 1.EXEMPLE1. Deoarece orice numr se afl printre divizorii lui zero, rezult c

    (a,0) = |a| oricare ar fi numrul ntreg a. Deci, numrul zero este prim numai cu numerele 1 i1.

    2. Pentru orice numr ntreg a, avem: (a,1) = 1. Deci, o