GRUPURI, INELE, CORPURI

download GRUPURI, INELE, CORPURI

of 21

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, orice numr este prim cunumerele 1 i 1.

    3. Dac a|b, atunci (a,b) = |a|.4. Dac p i q sunt dou numere prime distincte, atunci (p,q) = 1, adic sunt prime

    ntre ele.OBSERVAIEDeoarece din m|n rezult |m| |n|, condiiile din definiia lui (a,b) arat c acesta este,

    aa cum indic numele, cel mai mare dintre divizorii comuni ai numerelor a i b.6.2.1 O metod de calculare a celui mai mare divizor comun

    a dou numereUnicitatea descompunerii unui numr n (diferit de 0, 1, 1) ca produs de puteri de

    numere prime pozitive permite identificarea tuturor divizorilor lui n. Anume, dac1 2 1 21 2 ... ; , ,...,k kkn p p p N i d|n, atunci d poate avea ca factori primi numai

    numerele 1 2, ,..., kp p p sau opusele lor. Deci:1 21 2 ... ; 0 ; 1,2,...,k i ikd p p p i n .

    Dac 1 2, ,..., kp p p sunt factorii primi pozitivi comuni numerelor m i n, atunci:1 2 1 21 1 1 11 2 1 2... ; ... ; , ; ( , ) 1k k i ik km p p p m n p p p n N m n .

    Rezult c orice divizor propriu comun numerelor m i n este de forma:1 21 2 ... ; 0 min( , ); 1,2,...,k i i ikd p p p i n .

    Firete, cel mai mare dintre divizorii comuni se obine cnd exponenii iau toivaloarea maxim, adic min( , )i i i .

    S-a obinut astfel regula de calculare a celui mai mare divizor comun a dou numere,bazat pe descompunerea acestora n factori primi: este produsul factorilor primi (pozitivi)la puterea cea mai mic.

    DEFINIIESe numete cel mai mic multiplu comun al numerelor a i b numrul:

  • [ , ] ( , )aba b a b .

    Aa cum indic denumirea, numrul [a,b] este cel mai mic dintre multiplii comuni aicelor dou numere.

    ntr-adevr, notnd: d = (a,b), 1 1,a ba bd d , avem:21 1 1 1 1 1

    ab a b d a b d ab a bd d .Deci, [a,b] este multiplu i al lui a i al lui b.Fie acum m un multiplu comun al numerelor a i b. Din a|m rezult un numr ntreg h

    care ndeplinete condiia: m=ah. Din b|m rezult 1b |m=ah i cum 1, 1b a rezult 1b |h,adic h este de forma 1h b h .

    Deci, 1 [ , ]abm ah ab h h a b hd , adic m este multiplu al lui [a,b].PROPRIETI ALE RELAIEI DE DIVIZIBILITATEI. Dac m|ab i (m,a) = 1, atunci m|b.ntr-adevr din (m,a) = 1 rezult c m nu are factori comuni cu a. Pe de alt parte, din

    m|ab rezult c toi factorii lui m se afl n descompunerea lui ab, deci m|b.III. Dac a|m, b|m i (a,b) = 1, atunci ab|m.ntr-adevr, [a,b]|m i din (a,b) = 1 rezult [a,b] = ab.

    6.3 ALGORITMUL LUI EUCLIDOricare ar fi numerele ntregi a i b exist i este unic cel mai mare divizor comun al

    lor. n plus, se pot gsi dou numere ntregi u i v astfel nct:(a,b) = ua + vb. (Expresia ua + vb, adic suma numerelor a i b nmulite cu nite numerentregi se numete combinaie liniar a numerelor a i b).

    DEMONSTRAIEUnicitatea se deduce din faptul c dac dou numere d i d ndeplinesc amndou

    cele dou condiii din definiia celui mai mare divizor comun al numerelor a i b, atuncirezult att d|d , ct i d |d, adic d = d . Dar cum numerele d i d sunt pozitivenseamn c d = d .

    Unicitatea justific folosirea articolului hotrt n denumirea cel mai mare divizorcomun. El este n fapt cel mai mare dintre divizorii comuni pozitivi ai celor dou numere.

    n ce privete existena, deoarece exemplul 1 de mai sus justific teorema pentru cazulcnd a sau b este nul, putem considera c numerele a i b sunt amndou nenule.

    n plus, deoarece orice numr are aceiai divizori ca i opusul su, putem considera cnumerele a i b sunt strict pozitive i c a > b.

    Din teorema mpririi cu rest rezult c exist numerele 1 1,q r astfel nct:

  • 1 1 1; 0a bq r r b .Dac 1 0r , atunci rezult b|a i deci (a,b) = b. Dac 1 0r , atunci mprim pe b la

    1r i obinem:1 2 2 2 1; 0b r q r r r .

    Continund s mprim mpritorul la rest, acesta scade cu cel puin o unitate cnd setrece de la o operaie la cea urmtoare, astfel c dup un numr de n mpriri se ajunge c

    0nr . Ultimele trei mpriri arat astfel:4 3 2 23 2 1 12 1 .

    n n n nn n n nn n n

    r r q rr r q rr r q

    Se observ din acest algoritm c ultimul rest nenul, adic 1nr divide succesivresturile anterioare: 2 3 4 2 1, , ,..., , , ,n n nr r r r r b a , deci este divizor comun al numerelor a ib.

    Pe de alt parte, dac c|a i c|b, atunci parcurgnd pas cu pas, de sus n jos etapelealgoritmului, obinem succesiv c numrul c divide: 1 2 1, ,..., nr r r .

    Deci 1nr ndeplinete cele dou condiii din definiia celui mai mare divizor comun.Din penultima relaie a algoritmului se poate exprima 1nr , care este (a,b), ca o

    combinaie liniar de resturile anterioare, adic 2nr i 3nr . Folosind relaia antepenultima,2nr se poate exprima n funcie de resturile anterioare, astfel c 1nr se exprim ca o

    combinaie liniar de resturile 2nr i 3nr . Continund acest proces, se ajunge la exprimarealui 1nr ca o combinaie liniar de a i b.

    QED

    6.4. Grupuri, subgrupuri, grupuri ciclice, teorema lui Lagrange

    6.4.1. Definiii, notaiiDEFINIIESe numete grup o mulime G n care este definit o operaie intern:

    ,x y G x y G avnd urmtoarele proprieti:

    1) asociativitatea: ( ) ( );2) element neutru: ; ;3) element simetric: , ; .

    x y z x y ze G x G e x x e xx G x' G x x x x e

    Dac, n plus, operaia are proprietatea de comutativitate, adic:

  • ,x y G x y y x ,atunci grupul se numete grup comutativ.

    OBSERVAIII. Spre deosebire de modul standard n care este prezentat definiia de mai sus

    (considerat bine cunoscut), n general, pentru simplitate, se renun la precizareaapartenenei elementelor, de exemplu: ,x y G , atunci cnd aceasta este de la sine neleasdin context. n plus, se folosete, de regul, numai cuantificatorul existenial ( ) , iar cnd nuapare nici un cuantificator se subnelege cuantificatorul universal ( ) .

    II. Cnd este vorba de un grup abstract (adic n care nu se precizeaz naturaelementelor) operaia se noteaz cu diferite simboluri, cum ar fi: , , etc. n grupuriconcrete se folosesc de regul dou notaii:

    - notaia aditiv, cu semnul +. n acest caz, grupul se mai numete grup aditiv.Elementul neutru se noteaz atunci cu 0 sau , numindu-se elementul nul, iar simetriculunui lui x se numete opusul lui x i se noteaz x. Ca exemple menionm: (Z,+); (Q,+);(R,+); (C,+);

    - notaia multiplicativ n care se folosete punctul ca semn al operrii sau lipsaoricrui semn. n acest caz grupul se mai numete grup multiplicativ. Elementul neutru senoteaz de regul cu 1 i se numete elementul unitate al grupului, iar simetricul lui x se mainumete inversul lui x i se noteaz 1x . Exemple de astfel de grupuri sunt: (Q*,); (R*,);(C*,) n care semnul stea nseamn c din mulimea respectiv s-a exclus elementul nul.

    De regul, n ambele cazuri grupul este comutativ, cum este n toate exemplelemenionate.

    III. Dac grupul G este finit, adic are un numr finit de elemente, atunci numrulelementelor sale se noteaz G sau ord(G) i se numete ordinul grupului G.

    DEFINIIESe numete inel o mulime A cu dou operaii interne, una notat aditiv, iar cealalt

    notat multiplicativ, astfel nct:- (A,+) este grup abelian;- operaia de nmulire este asociativ;- operaia de nmulire are element neutru, notat 1;- nmulirea este distributiv fa de adunare, adic:

    ( ) ; ( ) ; , ,x y z xy xz x y z xz yz x y z A .OBSERVAIII. Dac nmulirea structurii de inel este comutativ, atunci inelul A se numete inel

    comutativ. De exemplu, ( , , ); ( , , ); ( , , ); ( , , )Z Q R C sunt toate inele comutative.Mulimea matricelor ptratice de ordinul n, formate cu numere reale, notat ( )nM R , cuoperaiile cunoscute, de adunare i de nmulire a matricelor, formeaz un inel care nu estecomutativ.

    II. Din definiia inelului rezult c fa de adunare fiecare element x al inelului are unsimetric numit, aa cum am menionat, opusul lui x, care se noteaz x. Fa de operaia denmulire nu toate elementele inelului au simetric (numit invers). Se poate deduce cu uurinc elementul nul al inelului nu are invers. De aici rezult c ntr-un inel unele elemente suntinversabile, iar altele nu. Elementele inversabile ale unui inel se numesc unitile inelului.

  • Este uor de demonstrat c mulimea unitilor unui inel A, mulime notat A* este grup fade operaia de nmulire a inelului, numit grupul unitilor inelului.

    De exemplu, n inelul numerelor ntregi, grupul unitilor este format numai din douelemente: 1. n inelele ( , , ); ( , , ); ( , , )Q R C grupul unitilor se obine eliminndelementul nul. n inelul necomutativ ( ( ) , )nM R grupul ( )*nM R al unitilor esteconstituit din mulimea matricelor care au determinantul nenul.

    III. n cazul cnd grupul unitilor inelului A este format din toate elementele nenuleale inelului, atunci inelul se numete corp. De exemplu, inelele ( , , ); ( , , ); ( , , )Q R C sunt corpuri, iar inelele Z i ( )nM R nu sunt corpuri.

    6.4.2. Subgrupuri, grupuri ciclice, teorema lui LagrangeDefiniiin definiiile i faptele elementare de teoria grupurilor pe care le vom prezenta n cele

    ce urmeaz vom folosi notaia multiplicativ n grupul G.DEFINIIESe numete subgrup al grupului G o submulime nevid H G avnd urmtoarele

    proprieti:

    1,

    .h k H hk Hh H h H

    Prima condiie din definiia subgrupului exprim faptul c submulimea H este o partestabil a lui G, fa de operaia intern a grupului G. Pe baza acesteia putem considera coperaia grupului G este o operaie intern pe submulimea H, numit i operaia indus pe Hde operaia lui G. Evident c operaia indus pe H este i ea asociativ, ca i operaiaconsiderat pe ntreaga mulime G. n plus, dac grupul G este comutativ, atunci i operaiaindus pe H este comutativ.

    Pentru ca submulimea H, cu operaia indus s fie grup trebuie s fie ndeplinitecelelalte dou condiii: s aib element neutru i fiecare element din H s aib inversul tot nH. Aceste condiii nu sunt obligatoriu ndeplinite numai pe baza ipotezei c H este partestabil. De exemplu, mulimea *N a numerelor naturale nenule este o parte stabil a grupuluiaditiv (Z,+) al numerelor ntregi, dar nu ndeplinete cele dou condiii menionate alestructurii de grup. Dei mulimea (Z,+) are element neutru, acesta neaflndu-se nsubmulimea *N , proprietatea elementului neutru nu este ndeplinit pentru operaia induspe *N .

    Mulimea N a tuturor numerelor naturale (inclusiv zero) este iari parte stabil i dedata asta are element neutru, deoarece numrul zero se afl n aceast mulime. Darproprietatea elementului simetric nu este ndeplinit deoarece, dei fiecare element din N areun opus n (Z,+), n general acesta nu se afl n N . Singurul element din N care are opusultot n N este zero.

    Condiia a doua din definiia subgrupului exprim faptul c pentru orice element dinH, inversul su se afl tot n H, adic se ndeplinete proprietatea elementului simetric. nplus, aceast condiie asigur i existena elementului neutru: lund n prima condiie

    11 2i

    h h h h , obinem 1hh e H .

  • Aadar, un subgrup este o submulime nevid a grupului G, care fa de operaiaindus este grup.

    Teorema lui LagrangeDac H este subgrup al grupului G, m=|H|, n=|G|, atunci m|n.DEMONSTRAIEPentru orice element x al grupului G considerm mulimea { ; }xH xh x H .

    Deoarece elementul neutru e al grupului se afl n H, rezult c x nsui se afl n aceastmulime, deoarece x xe , deci reuniunea mulimilor xH d ntreaga mulime G.

    Submulimile xH au urmtoarele dou proprieti:I) pentru orice element x din G mulimea xH are m elemente.

    ntr-adevr, n mulimea H se afl m elemente i dac 1 2xh xh atunci, compunnd la stngaambii membri ai acestei egaliti cu inversul lui G, se obine 1 2h h ;

    II) dac submulimile xH i yH au un element n comun, atunci acestesubmulimi coincid. ntr-adevr, 1 2, ;z xH yH h h H 1,z xh

    2 1 2z xh xh yh . Dac u este un element oarecare al mulimii xH, atunci:12 1u xh yh h h yH , deci xH yH . La fel se demonstreaz i incluziunea invers.

    Aadar, submulimile xH sau sunt disjuncte sau coincid.Prin urmare, mulimea G, avnd n elemente, este mprit n clase disjuncte, toate

    avnd acelai numr de elemente, i anume: m elemente, ca i H. Dac i este numrul acestorclase, atunci n = mi, de unde rezult m|n.

    QEDOrdinul unui elementPentru un element oarecare a al grupului finit G notm:

    2 3[ ] , , ,...a a a a .Deoarece grupul G este finit, elementele acestei mulimi nu pot fi toate distincte, deci

    exist i > j, astfel nct i ja a , de unde rezult i ja e .Fie *min{ ; }km k N a e . Acest numr natural se numete ordinul elementului

    a i-l notm ord(a). Folosind acest numr putem descrie mai precis submulimea [a], ianume: 2 3 1[ ] , , ,..., ,m ma a a a a a e . Se poate deduce cu uurin faptul c cele melemente menionate ale acestei submulimi sunt distincte, din cauza minimalitii lui m i cputerile lui a, mai mari dect m, se regsesc printre acestea. Deci, submulimea [a] are melemente.

    n plus, aceast submulime satisface condiiile din definiia subgrupului. ntr-adevr,compunerea elementelor din [a] se efectueaz prin adunareamodulo m a exponenilor, deci submulimea [a] este o parte stabil a lui G fa de operaiagrupului. Pe de alt parte, observm c pentru un element

    1;1 [ ]i i m ia i m a a a , deci este ndeplinit i a doua condiie din definiiasubgrupului.

    Subgrupul [a] se numete subgrupul generat de elementul a. Ordinul acestui subgrupeste tocmai ordinul elementului a.

  • Din teorema lui Lagrange rezult: Ordinul oricrui element al grupului divideordinul grupului.

    Grupuri cicliceDEFINIIESe numete grup ciclic un grup G n care exist un element g astfel nct [g] = G.

    Elementul g se numete generator al grupului G.EXEMPLE

    I. Pentru orice numr natural n grupul (Zn,+) este ciclic. ntr-adevr, putemconsidera ca generator clasa reprezentat de numrul ntreg 1, deoarece orice clas modulo nse obine prin compunerea (n sensul operaiei de adunare) clasei lui 1 cu ea nsi de unnumr de ori. Evident, compunnd de n ori aceast clas cu ea nsi, se obine elementul nulal grupului. Deci [1] = Zn.

    II. Tot pentru orice numr natural n mulimea Un a rdcinilor complexe aleecuaiei zn = 1 formeaz un grup ciclic fa de operaia de nmulire a numerelor complexe.ntr-adevr, notnd 2 2cos isinn n

    , acest numr complex este rdcin a ecuaiei zn=1 i toate cele n rdcini ale acestei ecuaii sunt numerele:

    2 2cos isin ; 1,2,..., ; 1k nk k k nn n , prin urmare [ ] G .

    OBSERVAIESe observ c aceste dou grupuri, avnd acelai numr de elemente, difer numai prin

    modul cum sunt notate elementele lor (la primul elementele sunt: 1,2,..., 0n , iar la aldoilea elementele sunt: 1 2 3, , ,..., 1n ) i prin modul cum este notat operaia (primuleste grup aditiv, iar al doilea este multiplicativ). Modul cum se compun elementele esteacelai n cele dou grupuri. ntr-adevr, n grupul nU elementele k se compun prinadunarea modulo n a exponenilor, iar n grupul (Z , )n elementele k se compun tot prinadunarea modulo n a numerelor k.

    Acest lucru se confirm n cazul general.TEOREMDou grupuri ciclice de acelai ordin sunt izomorfe.DEMONSTRAIEFie G i H dou grupuri ciclice de acelai ordin n. Pentru simplitatea demonstraiei

    vom folosi notaia multiplicativ n cele dou grupuri. Dac g este generatorul grupului ciclicG i h al lui H, atunci:

    1 2 1 2, ,..., ; , ,...,n nG g g g g e H h h h h e ,unde am notat e, e elementul neutru din G, respectiv H. Evident, compunerea n ambelegrupuri se face prin adunarea modulo n a exponenilor.

    Fie funcia : ; ( ) ; 1,2,...,i if G H f g h i n . Evident, funcia f este bijectiv.Ea este i morfism: i j k k i j i jf g g f g h h h f g f g unde k = (i+j)(mod.n).

  • QEDCONSECINDac ordinul unui grup G este un numr prim p, atunci G este izomorf cu grupul ciclic

    Zp. ntr-adevr, dac a este un element al lui G diferit de elementul neutru, atunci ordinul lui afiind diferit de unu i fiind divizor al numrului prim p trebuie s fie egal cu p, adic G estegrup ciclic avnd ca generator pe a. Din teorema precedent grupul G fiind ciclic de ordinul p,este izomorf cu Zp.

    Generatorii unui grup ciclic de ordinul nTEOREMFie G un grup ciclic de ordinul n notat multiplicativ i g un generator al su. Atunci

    ordinul elementului ;1 este ( , )k ng k n k n . n particular, condiia necesar i suficient

    ca elementul kg s fie generator al grupului G, adic kg G , este ca numrul k s fieprim cu n.

    DEMONSTRAIEDemonstrm mai nti teorema pentru cazul cnd (k,n) = k, adic numrul k este un

    divizor al lui n. Notm cu m ctul mpririi lui n la k, adic n = mk. Din definiia ordinuluiunui element rezult c ordinul lui kg este chiar m, deoarece elementele:

    1 2 32 3, , ,..., mk k k k k k k mk ng g g g g g g g g e sunt distincte, elementul g fiind un generator al grupului G.

    n cazul general, notnd ( , )d k n i ,n k astfel nct n dn i k dk rezult: kk dk d k d k dg g g g g g g .

    Pe de alt parte, o proprietate a celui mai mare divizor comun asigur c existnumerele ntregi u i v astfel nct d uk vn , de unde, innd seam c ng e , rezult:

    u v ud uk vn uk vn k n k k d ug g g g g g g g g g .Aadar elementele kg i dg genereaz acelai subgrup, deci au acelai ordin. Dar,

    deoarece d este un divizor al lui n, ordinul lui dg este ctul mpririi lui n la ( , )d k n .ntr-adevr, notnd d acest ct, avem: n dd i cea mai mic valoare a numrului naturalh pentru care hdg e este h d .QED.

  • 6.5. INELUL CLASELOR DE RESTURI MODULO n

    6.4.1 Congruena modulo nPentru fiecare numr ntreg x notm x mulimea tuturor numerelor ntregi care dau

    acelai rest la mprirea cu numrul natural nenul n. Aceast mulime se numete clasa decongruen modulo n a lui x.

    Evident c oricare dou astfel de clase sunt disjuncte, adic n-au nici un element ncomun. Pe de alt parte, reuniunea tuturor claselor de congruen modulo n este egal cuntreaga mulime Z a numerelor ntregi. Cu alte cuvinte, mulimea Z este mprit n nclase de congruen, corespunztoare celor n resturi care se pot obine la mprirea cunumrul natural n.

    Notm nZ mulimea care are ca elemente aceste clase. Mulimea nZ are deci nelemente.

    EXEMPLEI. Pentru 2n , mulimea Z se mparte n dou clase: clasa numerelor pare (care dau

    restul zero la mprirea cu 2) i clasa numerelor impare (care dau restul unu la mprirea cu2).

    II. Pentru 1n toate numerele ntregi sunt congruente, deci ele se constituie ntr-osingur clas.

    Dou numere ntregi, x i y, care se afl n aceeai clas de congruen modulo n sespune c sunt congruente modulo n. Aceast relaie se exprim n felul urmtor:

    (mod. )x y n . Se poate deduce cu uurin c:(mod. ) ( )x y n n x y . (2.1)

    OBSERVAIERelaia de congruen exprimat sub forma (2.1) are sens i pentru 0n . De remarcat

    c relaia de congruen modulo zero este relaia de egalitate, deoarece numrul zero l dividenumai pe zero. Dou numere ntregi sunt congruente modulo zero dac i numai dac ele suntegale.

    n cazul 1n toate numerele ntregi sunt congruente, deoarece numrul unu divideorice numr ntreg. La antipod se afl cazul 0n n care nu exist dou numere congruentedistincte, deoarece singurul numr care este divizibil cu zero este zero nsui.

    Orice element al unei clase este numit reprezentant al clasei respective sau creprezint acea clas. De exemplu, pentru 2n , orice numr par reprezint clasa numerelorpare, n timp ce orice numr impar reprezint clasa numerelor impare.

    n general se prefer s facem o alegere a cte unui reprezentant din fiecare clas. Oastfel de alegere definete ceea ce numim un sistem complet de resturi modulo n. Cea mai desfolosit modalitate de alegere este s se ia ca reprezentant al unei clase, restul pe care-l dautoate numerele acelei clase la mprirea cu numrul natural n. Deoarece acest rest poate fiorice numr cuprins ntre zero i n 1, nseamn c un sistem complet de resturi estemulimea constituit de numerele: 0, 1, 2,, n 1.

    Cu aceast alegere mulimea nZ se poate reprezenta astfel:

  • 0,1,..., 1nZ n .Elementele lui nZ se pot identifica astfel:

    ;k x qn k q Z .Uneori se prefer ca s se ia n ca reprezentant al clasei multiplilor lui n, adic al clasei

    numerelor care dau restul zero la mprirea cu n, caz n care mulimea nZ se poatereprezenta astfel:

    1,2,...,nZ n .Sistemul complet de resturi este atunci mulimea format din numerele:

    1, 2,, n.6.4.2 Adunarea i nmulirea claselor de congruen modulo nClasele se pot aduna dup urmtoarea regul:

    x y x y .S observm c adunarea claselor, dei se efectueaz cu ajutorul unor reprezentani ai

    celor dou clase, clasa care se obine ca rezultat nu depinde de reprezentanii alei n celedou clase. ntr-adevr,

    (mod. )i (mod. ) ( ) i ( ) ( )

    [( ) ( )] (mod. ) .x x n y y n n x x n y y n x x y y

    n x y x y x y x y n x y x y

    La fel se efectueaz operaia de nmulire a claselor:

    xy xy .Este uor de verificat c aceste dou operaii definite pe mulimea nZ ndeplinesc

    condiiile prevzute n definiia inelului comutativ.TEOREMGrupul *nZ al unitilor inelului nZ este constituit din clasele reprezentate de numere

    prime cu n.DEMONSTRAIEObservm mai nti c dac un reprezentant x al unei clase modulo n este prim cu n,

    adic (x,n) = 1, atunci toate numerele din acea clas sunt prime cu n. ntr-adevr, dac y seafl n aceeai clas cu x, atunci diferena y x este divizibil cu n. Dac y nu ar fi prim cun, atunci ar avea un factor comun propriu, s zicem d, cu n. Numrul d va divide atunci i pex, adic x i n ar avea un factor comun propriu i deci x nu ar mai fi prim cu n.

    Dac x este prim cu n, adic (x,n) = 1, atunci o proprietate a celui mai mare divizorcomun ne asigur c exist dou numere ntregi u i v astfel c:1 = (x,n) = ux + vn, deci:

    1 ux vn ux vn ux ,adic x reprezint o clas inversabil.

  • Reciproc, dac x reprezint o clas inversabil, atunci exist un numr ntreg u astfelnct produsul ux este congruent cu 1, adic n divide diferenaux 1. Dac x ar avea un divizor propriu d comun cu n, atunci acesta ar divide att pe x, ct idiferena ux 1 (care este multiplu al lui n) i deci divide i pe 1, ceea ce contrazice definiiadivizorului propriu

    6.6 PRODUSUL DIRECT DE GRUPURI I PRODUSUL DIRECTDE INELE

    Fiind date dou grupuri G i H, amndou notate moltiplicativ, cu elementul neutru e,respectiv e , pe mulimea {( , ); , }G H x h x G h H numit produsul cartezian almulimilor G i H se consider operaia pe componente, i anume:( , )( , ) ( , )x h x h xx hh .

    Este uor de verificat c aceast operaie definit pe produsul cartezian ndeplineteproprietile structurii de grup. Acest grup se numete produsul direct al celor dou grupuri.Elementul neutru al produsului direct este perechea ( , )e e i inversa perechii (x,h) esteperechea 1 1( , )x h . Dac grupurile G i H sunt comutative, respectiv finite, atunci produsullor direct este comutativ, respectiv finit.

    Acelai lucru este valabil n cazul a dou inele A i B. Notnd aditiv i multiplicativoperaiile n cele dou inele, pe produsul cartezian A B se consider operaiile de adunarei de nmulire pe componente, adic: ( , ) ( , ) ( , )a b a b a a b b i( , )( , ) ( , )a b a b aa bb . Aceste operaii definite pe A B ndeplinesc proprietilestructurii de inel. Elementul neutru al nmulirii din A B este perechea (1,1) unde am notatcu 1 att elementul neutru al lui A, ct i cel al lui B.

    TEOREMGrupul unitilor lui A B este produsul direct dintre grupul unitilor lui A i grupul

    unitilor lui B, adic: * * *( )A B A B DEMONSTRAIEDac * *( , )a b A B , atunci * *,a A b B , deci exist ,a A b B astfel

    nct 1aa i 1bb . Rezult c ( , )( , ) ( , ) (1,1)a b a b aa bb , adic1( , ) ( , )a b a b i deci perechea (a,b) este inversabil, ( , ) ( )a b A B . Ca urmare,

    * * *( )A B A B .Reciproc, dac *( , ) ( )a b A B , atunci exist perechea ( , )a b astfel nct

    ( , )( , ) (1,1)a b a b . Dar ( , )( , ) ( , )a b a b aa bb i deci 1aa , 1bb , adic* *,a A b B . Prin urmare, * * *( )A B A B .

    QED

  • 6.7. TEOREMA CHINEZDac (m,n) = 1, atunci funcia:

    : ; ( ) ( , )mn m n mn m nf Z Z Z f x x x n care x este un numr ntreg oarecare, iar , ,mn m nx x x reprezint clasa lui x modulo mn, m,n, respectiv, este un izomorfism de inele.

    DEMONSTRAIES observm mai nti c funcia f este corect definit, n sensul c dei ea opereaz

    cu un reprezentant modulo mn al unei clase, anume numrul ntreg x, perechea ( , )m nx x nuse schimb dac se nlocuiete x cu un alt numr y aflat n aceeai clas modulo mn ca i x.ntr-adevr,

    ( ) ( ), ( ), ( , ) ( , )

    mn mnm m n n m n m n

    y x mn x y m x y n x yx y x y x x y y

    Funcia f astfel definit este un morfism de inele. ntr-adevr,( ) (( ) ) (( ) ,( ) ) ( , )( , ) ( , ) ( ) ( )( ) (( ) ) (( ) ,( ) ) ( , )( , )( , ) ( ) ( )

    mn mn mn m n m m n nm n m n mn mnmn mn mn m n m m n nm n m n mn mn

    f x y f x y x y x y x y x yx x y y f x f y

    f x y f xy xy xy x y x yx x y y f x f y

    De remarcat c pn n acest stadiu al demonstraiei nu s-a folosit faptul c numerele

    m i n sunt prime ntre ele. Este nevoie de aceast ipotez pentru a arta c funcia f estebijectiv.

    De fapt, domeniul i codomeniul funciei f fiind mulimi finite cu acelai numr deelemente, i anume mn, este suficient s se demonstreze numai injectivitatea.

    Dar funcia f este injectiv:( ) ( ) ( , ) ( , ) ,

    ( ), ( ),( , ) 1 ( ) ( )mn mn m n m n m m n n

    mn mn

    f x f y x x y y x y x ym x y n x y m n mn x y x y

    QEDOBSERVAIEInversarea funciei f nseamn rezolvarea sistemului de ecuaii n x

    (numr ntreg) cu parametrii ntregi a i b:m mn n

    x ax b

    Acest sistem de congruene are soluii oricare ar fi numerele ntregi a i b dac i

    numai dac numerele m i n sunt prime ntre ele. ntr-adevr, numai n acest caz funcia f fiindsurjectiv, dat fiind un element oarecare ( , ) dinm n m na b Z Z exist (i este unic) o clas

  • modulo mn, reprezentat de un numr ntreg x, astfel nct: ( ) ( , )mn m nf x a b , adicm mx a i n nx b .

    Soluia sistemului se obine folosind nite numere u i v care ndeplinesc condiia: um+ vn = (m,n) = 1, din care rezult: 1m = (um + vn)m = (vn)m i1n = (um + vn)n= (um)n. Pentru x = avn + bum avem:

    xm= (avn + bum)m= (avn)m= am(vn)m= am1m= ami

    xn= (avn + bum)n= (bum)n= bn(um)n= bn1n= bn .

    6.8. CARACTERISTICA LUI EULERDEFINIIESe numete caracteristica lui Euler numrul, notat (n), al claselor modulo n

    reprezentate de numere prime cu n. Am demonstrat c dac un reprezentant al unei clasemodulo n este un numr prim cu n, atunci toi reprezentanii acelei clase sunt numere prime cun. De aceea putem vorbi de clase prime cu n.

    EXEMPLEI. Dac n = p este un numr prim, atunci dintre numerele 1, 2,, p singurul care nu

    este prim cu p este nsui p. Deci, (p) = p 1.II. Dac kn p n care p este numr prim, atunci numerele cuprinse ntre unu i n

    care nu sunt prime cu n sunt multiplii lui p, i anume: p, 2p, 3p,, 1k kp p p . Numrulacestora este 1kp . Deci numrul claselor prime cu n este diferena 1k kp p . Aadar, 1 11k k k kp p p p p .

    III. Dac 1 21 2 ... kkn p p p este descompunerea lui n n produs de puteri de factoriprimi distinci, atunci:

    1 21 1 1( ) 1 1 ... 1

    kn n p p p

    ntr-adevr, din teorema chinez rezult c 1 21 2

    * * * *... kkn p p pZ Z Z Z . Pe dealt parte, am remarcat mai sus c ( )n este ordinul grupului *nZ . Prin urmare,

    1 2 1 21 2 1 21 2

    1 2

    1 1 1( ) ... 1 1 ... 11 1 1 1 1 ... 1 .

    k kk kk

    k

    n p p p p p pp p pn p p p

    Proprieti ale caracteristicei lui EulerI. Ordinul grupului unitilor inelului nZ este egal cu ( )n .

  • ntr-adevr, elementele inversabile ale inelului nZ sunt clase reprezentate de numereprime cu n, iar numrul acestor clase este, prin definiie, ( )n .

    II. ( )n este numrul generatorilor unui grup ciclic de ordinul n.ntr-adevr, dac G este un grup ciclic de ordinul n avnd ca generator elementul g,

    atunci elementele care genereaz grupul sunt cele de forma mg n care 1 m n i (m,n) = 1.Numrul acestora este ( )n .

    III. Dac G este un grup ciclic de ordinul n, atunci acest grup are elemente de ordinuld numai dac d este un divizor al lui n. n acest caz elementele de ordinul d sunt elementele de

    forma mndg , n care 1 m d i (m,d) = 1. Numrul acestora este ( )d .ntr-adevr, din teorema lui Lagrange, ordinul unui element al unui grup finit divide

    ordinul grupului. Deci, grupul G nu poate avea elemente de ordinul d dect dac d este divizoral lui n.

    Pe de alt parte, dac d este un divizor al lui n, atunci rezult c hg ;1 h n are ordinul d dac i numai dac ( , )

    n dh n . Notnd ( , )h n d , aceasta nseamn

    c h md i n dd , n care (m,d) = 1, adic mnh d m dg g g cu1 m d i (m,d) = 1.

    IV. Pentru orice numr natural n este adevrat egalitatea:( )

    d nn d .

    ntr-adevr, dac n este ordinul unui grup ciclic, atunci elementele sale se grupeazdup ordinele lor, care sunt divizori ai lui n. Pentru fiecare divizor d al lui n, numrulelementelor de ordinul d este ( )d .

    Reciproca teoremei chinezeTeorema chinez afirm c dac numerele naturale m i n sunt prime ntre ele, atunci

    grupul m nZ Z este izomorf cu mnZ i deci este ciclic.Vom arta c este valabil i reciproca acestei teoreme, n sensul c m nZ Z este

    izomorf cu mnZ numai n cazul cnd m i n sunt prime ntre ele.Ca urmare, grupul m nZ Z este ciclic dac i numai dac m i n sunt primentre ele.

    TEOREMDac numerele naturale m i n nu sunt prime ntre ele, atunci grupul m nZ Z nu este

    ciclic i deci nu este izomorf cu mnZ .

  • DEMONSTRAIEFie p un numr prim care divide att pe m, ct i pe n i fie ,m n cturile respective,

    adic: m pm , n pn . Pentru orice k = 1, 2,, p 1 numrul km reprezint unelement de ordinul p din grupul aditiv mZ . ntr-adevr, ordinul clasei lui km este

    ( , ) ( , ) ( , ) ( , ) 1m m pm p p pkm m km pm k p m k p

    .Analog, numerele hn ; h = 1, 2,, p 1 reprezint clase de ordinul p din grupul

    aditiv nZ . Rezult c perechile de numere ( , )km hn , n numr de 2( 1)p reprezintelemente de ordinul p n grupul m nZ Z .

    Dar dac m nZ Z ar fi un grup ciclic, atunci pentru divizorul p al ordinului acestuigrup am avea numai ( ) 1p p elemente de ordinul p.

    QED

    6.9. TEOREMELE FERMAT, EULER, WILSONTEOREMA FERMATDac p este numr prim, atunci pentru orice numr ntreg x avem:

    (mod. )px x pDEMONSTRAIEGrupul *pZ are ordinul ( ) 1p p i deci ordinul oricrui element al grupului

    divide 1p . Ca urmare, orice clas nenul, ridicat la puterea 1p d ca rezultat clasaunitate, aceasta fiind clasa lui unu. Rezult c pentru orice numr ntreg nedivizibil cu p esteadevrat congruena: 1 1(mod. )px p .

    nmulind aceast congruen cu numrul oarecare x (care poate fi i multiplu de p) seobine relaia din enun.

    QEDTEOREMA EULERDac (m,n) = 1, atunci ( ) 1(mod. )nm n .DEMONSTRAIEOrdinul grupului *nZ este ( )n , ca urmare, orice element al grupului, ridicat la

    puterea ( )n d elementul neutru al grupului. Elementele grupului sunt reprezentate denumerele m care sunt prime cu n.

    QEDTEOREMA WILSONDac p este un numr prim, atunci ( 1)! 1(mod. )p p .

  • DEMONSTRAIETeorema se verific lesne pentru p = 2. Putem deci considera c p este un numr prim

    impar.Elementele grupului *pZ sunt reprezentate de numerele: 1, 2, 3,, p 1 dintre care

    numai primul i ultimul element este propriul su invers, deoarece n corpul pZ ecuaia2 1x nu poate avea mai mult de dou rdcini. Prin urmare, celelalte clase, n numr de p

    3 (care este par), sunt grupate dou cte dou, inverse una alteia, deci produsul acestora delementul unitate al grupului *pZ , reprezentat de numrul unu. Deci produsul ( 1)!p modulop se reduce la produsul dintre primul i ultimul factor, care produs este congruent cu1 modulo p.

    6.10. PROBLEME REZOLVATE6.10.1. S se verifice c numrul n = 1009 este prim.Rezolvare

    Este suficient s se verifice c nu are divizori primi. Se vede c nu se mparte exact la2, 3, 5,.. Nu parcurgem ns toate numerele prime mai mici det 1009. Este uor de observatc dac n nu are divizori primi mai mici dect rdcina ptrat a lui n (mai precis mai micidect partea ntreag a acestei rdcini) atunci nu poate avea divizori primi mai mari. Cum322 = 1024 rezult c trebuie testate toate numerele prime pn la 31(inclusiv).6.10.2. S se arate c dac n este un numr natural impar atunci exist o corespondenbiunivoc ntre divizorii lui n care sunt mai mari ca i modurile de scriere a lui n subforma: n = u2 v2.Rezolvare. Fie n = a.b n care a . Evident, numerele a i b sunt impare i a b. Sistemul:

    are ca unic soluie:

    Deoarece numerele a i b sunt impare rezult c numerele u i v sunt ntregi.De exemplu, divizorii lui n = 35 care sunt mai mari dect sunt 7 i 35 i aceti

    divizori corespund la scrierile: 35 = 62 12 = 182 172.6.10.3. S se afle cel mai mare divizor comun d al numerelor a = 189 i b = 154 i s se scrienumrul d sub forma d = u.a + v.b n care u i v sunt numere ntregi.Rezolvare

    Se aplic algoritmul lui Euclid:189 = 154 + 35;154 = 4.35 + 14;35 = 2.14 + 7;14 = 2.7 + 0.

  • de unde rezult d = 7.Din penultima relaie a algoritmului se onine:

    7 = -2.14 + 35Din a doua relaie a algoritmului se obine 14 = 154 4.35 i deci: 7 = -2.14 + 35 == -2(154 4.35) + 35 = -2.154 +35[(-2).(-4) + 1] = -2.154 + 9.35Din prima relaie a algoritmului se scoate: 35 = 189 154 i se obine:

    7 = -2.154 + 9.35 = -2.154 + 9(189 -154) = 9.189 11.154.adic 7 = u.189 + v.154 cu u = 9 i v = -11.6.10.4. S se afle inversele claselor nenule din corpul Z43.Rezolvare

    Este suficient s se afle inversele claselor reprezentate de numerele prime.Pentru a afla inversa clasei lui 2 se observ c (2,43) = 1, deoarece numrul 43 este

    prim i se scrie numrul 1 ca o combinaie de 2 43, folosind, n general, algoritmul luiEuclid: 1 = 22.2 43. Reducnd modulo 43 se obine 2.22 = 1, adic 22 este inversa clasei lui2. Rezult 11.4 = 1, deci 11-1 = 4.

    Din 1 = 43 3.14 rezult 3-1 = -14 = 29. Din 1 = 2.43 17.5 rezult 5-1 = -17 = 26.Din aceast ultim relaie rezult 2.13 = 5-1 adic 13-1 = (5-1.2-1)-1 = 5.2 = 10.

    Pe de alt parte, deoarece (-1)-1 = -1 = 42 rezult: 17-1 = (-5-1) = -5 = 38 = 2.19. Maideparte, 19-1 = (17-1.2-1)-1 = 17.2 = 34. n plus, din 1 = 43 -6.7 rezult -6.7 = 1 i deci 7-1 = (-6-1)-1 = -6 = 37.

    Pentru numerele prime mai mari dect 43/2 se trece la opusul lor. De exemplu,23-1 = (-20)-1 = -2-1.2-15-1 = - 22.22.26 = 15

    6.11. TEME PENTRU CAS6.11.1. S se verifice c numerele: 1013, 1019, 1021, 1031, 1033 sunt prime.6.11.2. Numerele prime de forma 2n 1 se numesc numere prime Mersenne. Evident, pentruca numrul 2n 1 s fie prim este necesar ca numrul n s fie prim (dar nu i suficient). S sedetermine primele 8 numere prime Mersenne.6.11.3. S se afle toate modurile de scriere a numrului n = 1575 sub forma u2 v2

    6.11.4. S se afle inversele claselor nenule din inelele: Z17, Z53, Z101.

    Bibliografie[1] C. DOCHIOIU, Instrumente algebrice ale criptografiei, Editura ATM, Bucureti, 2009.[2] N. KOBLITZ, A Course in Number Theory and Cryptography, Editura Springer, Berlin,1988[3], by A. MENEZES, P. van OORSCHOT, and S. VANSTONE, Handbook of AppliedCryptography, CRC Press, 1996.