Fai Id m1 V25iun [PDF]

Zitiervorschau

Fundamentele Algebrice ale Informaticii -învăţământ la distanţăMODULUL I Adelina-Loredana Manea

Cuprins 1 M1.U1. Mulţimi. Funcţii 6 1.1 Mulţimi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Funcţii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Temă de control la finalul unităţii de învăţare M1.U1. 17 2 M1.U2. Relaţii 2.1 Relaţii binare . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Relaţii de echivalenţă. Relaţii de ordine . . . . . . . . . . . . 2.3 Temă de control la finalul unităţii de învăţare M1.U2.

19 19 23 28

3 M1.U3. Monoid. Monoidul liber generat de o mulţime 3.1 Monoid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Monoidul liber generat de o mulţime nevidă . . . . . . . . . . 3.3 Temă de control la finalul unităţii de învăţare M1.U3.

30 31 35 40

4 M1.U4. Grupuri 4.1 Grupuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Morfisme de grupuri . . . . . . . . . . . . . . . . . . . . . . . 4.3 Subgrup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Teorema lui Lagrange . . . . . . . . . . . . . . . . . . . . . . 4.5 Temă de control la finalul unităţii de învăţare M1.U4.

41 42 43 52 60 65

5 M1.U5. Grupuri de permutări 67 5.1 Grupuri de permutări . . . . . . . . . . . . . . . . . . . . . . . 67 5.2 Temă de control la finalul unităţii de învăţare M1.U5. 77 6 M1.U6. Ordinul unui element. Grupuri ciclice 6.1 Ordinul unui element . . . . . . . . . . . . . . . 6.2 Grupuri ciclice . . . . . . . . . . . . . . . . . . 6.3 Teorema lui Euler. Mica Teoremă a lui Fermat . 6.4 Extindere-Logaritmul discret . . . . . . . . . . . 4

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

78 79 84 87 92

5 6.5

Temă de control la finalul unităţii de învăţare M1.U6.

96

Unitatea de învăţare 1 M1.U1. Mulţimi. Funcţii U1.0 Obiectivele unităţii de învăţare Această unitate de învăţare are rolul de a actualiza şi de a completa noţiuni cu care studenţii sunt familiarizaţi din ciclul de învăţamânt preuniversitar: mulţimi şi funcţii. Sunt noţiuni fundamentale, cu care se lucrează pe tot parcursulul facultăţii şi a căror bună înţelegere şi cunoaştere sunt esenţiale.

La sfârşitul acestei unităţi de învăţare cursanţii trebuie să fie capabili să opereze cu mulţimi, să cunoască imaginea şi preimaginea unei mulţimi printr-o funcţie, să stăpânească tehnici de numărare.

Nefiind cunoştinţe noi în totalitate, estimăm parcurgerea acestei unităţi de învăţare în 2 ore.

1.1 Mulţimi Teoria mulţimilor, aşa cum o utilizăm noi astăzi, a fost iniţiată de matematicianul Greg Cantor în ultimul sfert al secolului al XIX-lea. Abordarea lui a condus însă la paradoxuri, ceea ce a dus la abordarea axiomatică a acestei teorii. Conform lui Cantor, prin mulţime înţelegem orice colecţie de obiecte distincte şi bine definite ale intuiţiei şi ale gândirii noastre, considerată ca un întreg. Noţiunea de mulţime trebuie gândită ca una primitivă, suficient de bine înţeleasă intuitiv, care nu este precis definită, dar care poate fi utilizată în 6

7 definirea altor noţiuni. Aşadar von considera mulţimile ca fiind colecţii de obiecte numite elementele mulţimii. O mulţime poate fi descrisă prin enumerarea elementelor sale sau prin precizarea unei proprietăţi pe care o au toate elementele sale şi doar ele. Exemplul 1.1.1 Mulţimea numerelor naturale pare mai mici decât 10 poate fi dată prin enumerare {0, 2, 4, 6, 8} sau prin precizarea proprietăţii descrise, {x ∈ N|x < 10, 2|x}. Notăm mulţimile cu litere mari ale alfabetului latin (A, B, C, ..., X, Y, Z), iar elementele le notăm cu litere mici ale alfabetului latin (a, b, c, ..., x, y, z). Dacă elementul a este obiect al mulţimii A vom spune că el aparţine mulţimii A şi vom nota acest fapt prin x ∈ A. În caz contrar, vom spune că a nu aparţine mulţimii A şi vomm scrie x ∈ / A. Dacă toate elementele mulţimii A sunt şi elemente ale mulţimii B, atunci vom spune că mulţimea A este inclusă în mulţimea B şi vom nota acest fapt prin A ⊆ B. Dacă B are şi alte elemente în afară de cele ale mulţimii A, spunem că A este inclusă strict în mulţimea B şi notăm A ⊂ B. Spunem că două mulţimi sunt egale dacă fiecare este inclusă în cealaltă. Deci două mulţimi sunt egale dacă au aceleaşi elemente. Numărul de elemente al unei mulţimi A îl numim cardinalul mulţimii A şi îl notăm |A|. Mulţimile de cardinal finit se numesc mulţimi finite, iar cele de cardinal infinit se numesc mulţimi infinite. Mulţimea cu 0 elemente se numeşte mulţimea vidă şi se notează Φ. De remarcat faptul că două mulţimi de cardinale diferite nu pot fi egale. Observatia 1.1.1 Mulţimea vidă este considerată submulţime a oricărei mulţimi. Date fiind două elemente a, b, numim pereche ordonată notată (a, b) mulţimea {a, {a, b}}. Evident, egaliatatea (a, b) = (c, d) este posibilă dacă şi numai dacă a = c şi b = d. Date fiind două mulţimi A, B, din ele putem obţine noi mulţimi prin aşa numitele operaţii cu mulţimi: 1. Intersectia(∩): A ∩ B = {x|x ∈ A şi x ∈ B}, numită intersecţia mulţimilor A şi B. În cazul în care A ∩ B = Φ spunem că mulţimile A şi B sunt disjuncte. 2. Reuniunea (∪): A ∪ B = {x|x ∈ A sau x ∈ B}, numită reuniunea mulţimilor A şi B. 3. Diferenţa (− ):A − B = {x|x ∈ A şi x ∈ / B}, numită diferenţa mulţimilor A şi B.

8 4. Diferenţa simetrică (∆): A∆B = (A − B) ∪ (B − A), numită diferenţa simetrică a mulţimilor A şi B. 5. Produs cartezian (×): A × B = {(a, b)|a ∈ A şi b ∈ B}, numită produsul cartezian al mulţimilor A şi B. Pentru o mulţime A notăm cu P (A) mulţimea tuturor submulţimilor sale, numită mulţimea părţilor lui A. Exemplul 1.1.2 Dacă A = {a, b, c}, atunci P (A) = {Φ, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. Pentru a nu uita submulţimi, putem stabili o regulă în scrierea părţilor unuie mulţimi, scriind mai întâi submulţimea cu 0 elemente, apoi submulţimile cu 1 element, apoi cu 2 elemente, etc.

Ne reamintim Inducţia matematică este un procedeu prin care se demonstrează afirmaţii matematice referitoare la orice număr natural n ≥ n0 . Fie P (n) o afirmaţie matematică şi n0 ∈ N un număr natural fixat. Se cere să se arate că P (n) este adevărată pentru orice n ≥ n0 . Inducţia matematică constă în doi paşi: verificarea şi etapa de demonstraţie, numită şi etapa inductivă. Inducţia simplă: • Verificăm P (n0 ) adevărat. • Presupunem P (k) adevărat şi demonstrăm P (k + 1) adevărat. Inducţia completă: • Verificăm P (n0 ) adevărat. • Presupunem P (k) adevărat pentru orice n0 ≤ k ≤ n şi demonstrăm P (n + 1) adevărat.

Exemplificăm aplicarea metodei inducţiei matematice în rezolvarea următoarei probleme de numărare: Exemplul 1.1.3 Fie A o mulţime finită cu n elemente. Atunci mulţimea părţilor lui A, P (A), are 2n elemente. Scriem |P (A)| = 2 n. Verificarea afirmaţiei de mai sus se poate face prin inducţie matematică astfel: Fie P (n) : |A| = n → |P (A)| = 2 n .

9 Pasul 1: Verificăm pentru n = 0, adică A este mulţimea vidă. Atunci P (A) = {Φ}, deci are 20 elemente, adică P (0) este adevărat. Pasul 2: Presupunem P (k) adevărată, deci că orice mulţime cu k elemente are 2k submulţimi şi fie A o mulţime cu k + 1 elemente. Trebuie să demonstrăm că are 2k+1 submulţimi. Fie x ∈ A arbitrar ales şi A′ = A − {x} evident, mulţimea A′ are nk elemente, deci 2k submulţimi, conform ipotezei de inducţie. Să analizăm submulţimile mulţimii A. Acestea pot să conţină sau să nu conţină elementul x. Submulţimile lui A care nu conţin x sunt submulţimile lui A′ , deci există 2k astfel de submulţimi. Submulţimile lui A care conţin x sunt de forma B = B ′ ∪{x}, unde B ′ ⊆ A′ , deci tot 2k . În total am obţinut că A are 2k + 2k = 2k+1 submulţimi. Rezultă P (k + 1) adevărată. Conform inducţiei matematice, P (n) este adevărată, ∀n ∈ N. Afirmaţia demonstrată mai sus se poate justifica şi utilizând identitatea 0 1 m Cm + Cm + ... + Cm = 2m . Exerciţiu: Scrieţi mulţimea părţilor mulţimii A = {1, 2, 3, 4} Operaţiile cu mulţimi au următoarele proprietăţi a căror verificare o lăsă în seama cititorului ca exerciţiu. Amintim doar faptul că egalitatea a două mulţimi se demonstrează prin dublă incluziune. Propozitia 1.1.1 Fie A, B, C mulţimi. Atunci: (1) A ∩ (B ∩ C) = (A ∩ B) ∩ C (asociativitate); (2) A ∩ B = B ∩ A (comutativitate); (3) A ∩ A = A (idempotenţă); (4) A ∩ Φ = Φ; (5) P (A) ∩ P (B ) = P (A ∩ B ); (6) A∪(B∪C) = (A∪B)∪C A∩(B∩C) = (A∩B)∩C (asociativitate); (7) A ∪ B = B ∪ A A ∩ B = B ∩ A (comutativitate); (8) A ∪ A = A A ∩ A = A (idempotenţă); (9) A ∪ Φ = A A ∩ Φ = Φ; (10) P (A) ∪ P (B ) ⊆ P (A ∪ B ); (11) A − A = Φ, A − Φ = A, Φ − A = Φ; (12) A − (B − C) = (A − B) ∪ (A ∩ C); Exemplul 1.1.4 Egalitatea (12) se demonstrează astfel: Incluziunea directă: Fie x ∈ A − (B − C), arbitrar ales, deci x ∈ A şi x ∈ / B − C. Rezultă că x ∈ A şi fie x ∈ / B, fie, dacă x ∈ B, atunci x ∈ C ∩ B. Adică x ∈ A − B sau x ∈ A ∩ B ∩ C,

10 deci x ∈ (A − B) ∪ (A ∩ B ∩ C), mulţime care este inclusă în (A − B) ∪ (A ∩ C). Deoarece x a fost ales arbitrar, rezultă că orice element din prima mulţime (cea din membrul drept) este şi în a doua (membrul stâng), deci A − (B − C) ⊆ (A − B) ∪ (A ∩ C). (1) Incluziunea inversă Fie acum x ∈ (A − B) ∪ (A ∩ C), arbitrar ales. Rezultă x ∈ (A − B) sau x ∈ A ∩ C. Din acestea rezultă că x se alflă în A, dar nu oriunde, ci fie nu este deloc în B, fie, dacă ar aparţine lui B, ar aparţine şi lui C. Deci ar aparţine mulţimii B ∩ C. Deci x este element al lui A dar nu al lui B − C, de unde scriem x ∈ A − (B − C). Am obţinut (A − B) ∪ (A ∩ C) ⊆ A − (B − C). (2) Din relaţiile (1) şi (2) rezultă egalitatea celor două mulţimi. La acest tip de raţinament de un real folos este vizualizarea mulţimilor prin diagrame Venn. Exerciţiu: Demonstraţi incluziunea (10) din Propoziţia anterioară Fie M o mulţime şi A o submulţime a sa. Diferenţa M −A se mai numeşte complementara mulţimii A şi se notează CM A sau simplu A¯ dacă mulţimea M se subîţelege din context. Propozitia 1.1.2 Fie M o mulţime nevidă şi A, B două submulţimi ale sale. Au loc următoarele egalităţi: (1) CM (CM A) = A; CM Φ = M ; CM M = Φ; (2) CM (A ∩ B) = CM A ∪ CM B; CM (A ∪ B) = CM A ∩ CM B, (legile lui De Morgan); (3) A ∩ CM A = Φ; A ∪ CM A = M ; A − B = A ∩ CM B. Referindu-ne la cardinalul mulţimilor, este util următorul rezultat, cunoscut sub numele de Principiul includerii şi excluderii: Propozitia 1.1.3 Fie A, B două mulţimi finite. Au loc următoarele: a) Dacă A ∩ B = Φ, atunci |A ∪ B| = |A| + |B|. b) |A ∪ B| = |A| + |B| − |A ∩ B| c) Generalizare: Cardinalul reuniunii a m mulţimi este dat de formula de mai jos |A1 ∪ A2 ∪ ... ∪ Am | =

m ∑ i=1

+(−1)k

∑ 1≤i1 , se numeşte ciclic. Propozitia 4.3.4 Fie (G, ·) un grup şi S ⊂ G. Are loc egalitatea < S >= {x1 · x2 · ... · xm /

m ∈ N, xi ∈ S

sau(xi )−1 ∈ S}.

Demonstraţie: Trebuie să demonstrăm că intersecţia tuturor subgrupurilor lui G care includ S este egală cu mulţimea tuturor compunerilor de elemente din S şi din S −1 . Notăm această mulţime cu A, deci A = {x1 · x2 · ... · xm /

m ∈ N, xi ∈ S

sau(xi )−1 ∈ S}.

În A avem şi elementul x · x−1 pentru un x oarecare din S, deci 1 ∈ A. Pentru orice două elemente din A, rezultatul operaţiei din G dintre ele va avea aceeaşi formă, deci (A, ·) e parte stabilă. Mai mult, pentru orice x1 · x2 · ... · xm ∈ A, (x1 · x2 · ... · xm )−1 =

57

(xm )−1 · (xm−1 )−1 · ... · (x1 )−1 este tot o compunere de elemente din S şi din S −1 . Rezultă că A este subgrup în G. Acest subgrup conţine şi compuneri de câte un element din S, deci include S. Prin urmare A este unul din subgrupurile a căror intersecţie este < S >, de unde < S >⊆ A. Pentru orice subgrup H al lui G, care include S, din proprietatea de parte stabilă, H va conţine şi toate compunerile de elemente din S şi din S −1 , adică A ⊆ H. Cum H era oarecare, A ⊆ |{z} ∩ H, deci A ⊆< S >. Aveam şi incluziunea inversă, H≤G,S⊂H

aşadar < S >= A. Observatia 4.3.2 a) Dacă elementele x1 , x2 , ..., xk din grupul aditiv (G, +) comută două câte douâ, atunci < x1 , x2 , ..., xk >= {n1 x1 + n2 x2 + ... + nk xk /

ni ∈ Z, i = 1, n}.

În particular, subgrupul ciclic generat de un element x ∈ G este < x >= {nx/n ∈ Z}. b) În notaţie multiplicativă, subgrupul generat de elementele x1 , x2 , ..., xk din (G, ·) care comută două câte douâ, este < x1 , x2 , ..., xk >= {xn1 1 · xn2 2 · ... · xnk k / ni ∈ Z, i = 1, n}. iar subgrupul ciclic generat de un element x din grupul (G, ·) este de forma < x >= {xn | n ∈ Z}. În Exemplul 4.3.1 am văzut că toate subgrupurile grupului (Z, +) sunt de forma nZ, cu n ∈ N. Putem spune că: Propozitia 4.3.5 Toate subgrupurile grupului aditiv al numerelor întregi sunt grupuri ciclice.

58

Exemplul 4.3.2 a) Grupul aditiv al numerelor întregi este ciclic, Z =< 1 >=< −1 > . b) Grupul aditiv al claselor de resturi modulo n este ciclic, Zn =< b 1 >. Ne amintim! Funcţia f : (G, ·) → (G′ , +)cu proprietatea că f (x · y) = f (x) + f (y) pentru orice x, y ∈ G, este un morfism de grupuri. Notând cu 1, respectiv cu 0 elementele neutre în grupurile (G, ·), respectiv (G′ , +, au loc f (1) = 0 şi f (x−1 ) = −x. Următoarea afirmaţie este cunoscută sub numele de Teorema de corespondenţă şi precizează modul de comportare a subgrupurilor la morfisme. Propozitia 4.3.6 Fie f : (G, ·) → (G′ , +) un morfism de grupuri. a) Dacă H ≤ G, atunci f (H) ≤ G′ . b) Dacă K ≤ G′ , atunci f −1 (K) ≤ G şi Ker(f ) ⊂ f −1 (K). c) Dacă f : (G, ·) → (G′ , +) este morfism surjectiv de grupuri, atunci există o corespondenţă bijectivă între subgrupurile lui G care includ Kerf şi subgrupurile lui G′ . Demonstraţie: a) Fie H un subgrup al grupului (G, ·). Imaginea sa prin morfismul f este mulţimea f (H) = {y ∈ G′ | ∃x ∈ H,

f (x) = y} = {f (x)|

x ∈ H}.

Vom nota cu 1 şi 0 elementele neutre în grupurile (G, ·), respectiv (G′ , +). Deoarece 1 ∈ H şi, conform Propoziţiei 4.2.1, f (1) = 0, avem 0 ∈ f (H) . Fie acum două elemente y1 , y2 ∈ f (H). Există x1 , x2 ∈ H astfel încât f (x1 ) = y1 şi f (x2 ) = y2 . Calculăm y1 + y2 = f (x1 ) + f (x2 ) = f (x1 · x2 ) ∈ f (H), −y1 = (−f (x1 )) = f (x−1 1 ) ∈ f (H),

59

unde am folosit proprietăţile morfismului f şi faptul că H este subgrup. Am obţinut că submulţimea f (H) a lui G′ satsiface condiţiile b) din Propoziţia 4.3.1, deci este subgrup. b) Fie K ∈ S(G′ ). Preimaginea sa prin morfismul f este mulţimea f −1 (K) = {x ∈ G| f (x) ∈ K}. Din f (1) = 0 ∈ K rezultă 0 ∈ f −1 (K). Fie x1 , x2 ∈ f −1 (K), arbitrar alese. Avem f (x1 ), f (x2 ) ∈ K şi K subgrup, deci f (x1 )+ f (x2 ) ∈ K, de unde, folosind faptul că f este morfism, f (x1 + x2 ) ∈ K. Am obţinut x1 + x2 ∈ f −1 (K). Analog, f (x−1 1 ) = −1 −1 −1 −1 (f (x1 )) ∈ K, deci x1 ∈ f (K). Rezultă că f (K) ≤ G. c) Vom demonstra că dacă f este morfism surjectiv, atunci următoarele aplicaţii sunt inverse una celeilalte şi deci bijective: φ : [Ker(f ), G] → S(G′ ), η : S(G′ ) → [Ker(f ), G],

φ(H) = f (H),

∀H ∈ [Ker(f ), G],

η(K) = f −1 (K),

∀K ∈ S(G′ ),

unde [Ker(f ), G] = {H ∈ S(G)| Ker(f ) ⊆ H}. Remarcăm faptul că η e corect definită. Într-adevăr, pentru orice subgrup K din G′ , f −1 (K) include Ker(f ) deoarece 0 ∈ K implică f −1 (0) ⊆ f −1 (K). Din surjectivitatea morfismului f şi rezultă f (f −1 (K)) = K pentru orice K ∈ S(G′ ), deci φ ◦ η = 1S(G′ ) . Avem şi H ⊆ f −1 (f (H)), ∀H ∈ S(G). Pentru un subgrup H care include nucleul morfismului f , fie x ∈ f −1 (f (H)). Obţinem f (x) ∈ f (H), deci ∃h ∈ H astfel încât f (x) = f (h). f (x)−f (h) = 0 ⇒ f (x·h−1 ) = 0 ⇒ x·h−1 ∈ Ker(f ) ⊆ H ⇒ x ∈ H. Din cele de mai sus rezultă η ◦ φ = 1[Ker(f ),G] . Test de autoevaluare

60

1. Scrieţi toate subgrupurile grupului (Z12 , +). Determinaţi intersecţia, respectiv suma a două dintre ele. 2. Demonstraţi că nucleul unui morfism de grupuri f : (G, ·) → (G′ , ∗) este subgrup al domeniului G, iar imaginea sa este subgrup al grupului G′ . Indicaţii de rezolvare: 1) Similar cu Exemplul 4.3.1 c). 2) A se studia demonstraţia Propoziţiei 4.3.6.

4.4 Teorema lui Lagrange În continuare preferăm notaţia aditivă pentru legea de compoziţie a grupurilor considerate, deoarece ideile se reiau în studiul inelelor, relativ la grupul aditiv al unui inel. Fie (G, +) un grup şi H un subgrup al său. Definim relaţiile de congruenţă modulo H la stânga, ≡s , respectiv la dreapta ≡d , prin: x, y ∈ G, x ≡s y(modH) ⇔ −x + y ∈ H, x, y ∈ G,

x ≡d y(modH) ⇔ x − y ∈ H.

Ne amintim! O relaţie binară pe o mulţime se numeşte relaţie de echivalenţă dacă este reflexivă, simetrică şi tranzitiviă. Propozitia 4.4.1 Cele două relaţii definite mai sus sunt relaţii de echivalenţă. Demonstraţie: Vom arăta că relaţia de congruenţă modulo H la stânga este o relaţie de echivalenţă, demonstraţia fiind analoagă şi pentru relaţia de congruenţă modulo H la dreapta. 1. reflexivitatea: −x + x = 0 ∈ H, ∀x ∈ G ⇒ x ≡s x(modH), ∀x ∈ G.

61

2. simetria: x ≡s y(modH) ⇔ −x + y ∈ H ⇒ −(−x + y) ∈ H ⇒ ⇒ −y + x ∈ H ⇒ y ≡s x(modH). 3. tranzitivitatea: x ≡s y(modH), y ≡s z(modH) ⇒ −x + y, −y + z ∈ H ⇒ ⇒ (−x + y) + (−y + z) = −x + z ∈ H ⇒ x ≡s z(modH). Am folosit în raţionamentul de mai sus faptul că H este subgrup, deci parte stabilă în raport cu legea de compoziţie din G. Clasa de echivalenţă a elementului x ∈ G în raport cu ≡s , numită şi clasa laterală a elementului x, este mulţimea xˆ = {y ∈ G|x ≡s y(modH)} = {y ∈ G| − x + y ∈ H} = = {y ∈ G|y ∈ x + H} = x + H, iar în raport cu ≡d este mulţimea H +x. Mulţimile cât (mulţimile claselor de echivalenţă) relativ la cele două relaţii de echivalenţă sunt: (G/H)s = {x + H| x ∈ G},

(G/H)d = {H + x|

x ∈ G}.

În general, pentru orice subgrup H avem: Propozitia 4.4.2 Mulţimile cât (numite şi factor) (G/H)s şi (G/H)d sunt echipotente. Demonstraţie: Fie funcţia f : (G/H)s → (G/H)d definită prin f (x + H) = H + (−x),

∀x + H ∈ (G/H)s .

Fiind o funcţie ale cărei argumente sunt clase de echivalenţă trebuie să ne asigurăm că este corect definită, adică legea ei nu

62

depinde de reprezentanţi. Fie x′ ∈ x + H, deci există h ∈ H, x′ = x + h şi x + H = x′ + H. Avem f (x′ + H) = H + (−x′ ) = H − h − x = H + (−x) = f (x + H), de unde rezultă că f este corect definită. Fie două clase la stânga x+H, y +H cu f (x+H) = f (y +H). f (x+H) = f (y+H) ⇒ H+(−x) = H+(−y) ⇒ −x ≡d −y(modH) ⇒ ⇒ −y + x ∈ H ⇒ y ≡s x(modH) ⇒ x + H = y + H, deci f este injectivă. Pentru orice clasă de echivalenţă la dreapta modulo H, H +x, există clasa (−x) + H ∈ (G/H)s care are proprietatea f ((−x) + H) = H + x, deci f este surjectivă. Am obţinut prin urmare o bijecţie între cele două mulţimi cât, deci ele au acelaşi cardinal, |(G/H)s | = |(G/H)d | .

Definitia 4.4.1 Cardinalul mulţimii cât (G/H)s se numeşte indicele subgrupului H în G şi se notează |G : H|. Exemplul 4.4.1 Indicele subgrupului H = {ˆ0, ˆ3, ˆ6, ˆ9} ⊆ Z12 este 3 deoarece mulţimea cât (Z12 /H)s are trei elemente: ˆ0 + H = H = ˆ3 + H = ˆ6 + H = ˆ9 + H, ˆ1 + H = {ˆ1, ˆ4, ˆ7, 10} ˆ = ˆ4 + H = ˆ7 + H = 10 ˆ + H, ˆ2 + H = {ˆ2, ˆ5, ˆ8, 11} ˆ = ˆ5 + H = ˆ8 + H = 11 ˆ + H. Exerciţiu: Determinaţi indicele subgrupului H = {ˆ0, ˆ2, ˆ4, ˆ6} în grupul (Z8 , +).

63

Teorema 4.4.1 [Lagrange] Dacă H este un subgrup al grupului G, atunci |G| = |H| · |G : H| . Demonstraţie: Fie H ∈ S(G). Folosim faptul că o relaţie de echivalenţă determină o partiţie a mulţimii pe care este definită. Aici, ≡s determină partiţie a lui G în clasele din (G/H)s , mai exact G este reunuiunea disjunctă a elementelor mulţimii factor (G/H)s . Cum această mulţime are |G : H| elemente, iar fiecare element este o mulţime de forma x + H, deci echipotentă cu H, obţinem rezultatul dorit. O consecinţă imediată a teoremei lui Lagrange este: Propozitia 4.4.3 Dacă G este un grup finit, atunci ordinul oricărui subgrup al său este divizor al ordinului grupului. Încheiem acest paragraf cu un rezultat foarte important: Teorema 4.4.2 [Teorema fundamentală de izomorfism] Fie f : (G, +) → (G′ , +) un morfism de grupuri. Atunci grupul factor G/Ker(f ) este izomorf cu subgrupul Im(f ) al lui G′ . Demonstraţie: Aplicând Propoziţia 4.3.6 subgrupului {eG′ } din codomeniu, rezultă că nucleul unui morfism este subgrup al domeniului de definiţie. Fie mulţimea factor G/Ker(f ), pe care definim legea de compoziţie (x + Ker(f )) + (y + Ker(f )) = (x + y) + Ker(f ). Mai simplu, definim compunerea a două clase laterale ca fiind clasa compunerii (ˆ x + yˆ = x[ + y). Se verifică cu uşurinţă faptul că aceasta este o lege de compoziţie pe G/Ker(f ) şi că G/Ker(f ) este grup în raport cu această lege. Considerăm funcţia φ : G/Ker(f ) → G′ ,

φ(x + Ker(f )) = f (x),

64

(∀)x+Ker(f ) ∈ G/Ker(f ). Aceasta este corect definită deoarece pentru orice x′ + Ker(f ) = x + Ker(f ), deci x − x′ ∈ Ker(f ), avem f (x − x′ ) = 0, adică f (x) = f (x′ ). Funcţia φ este morfism de grupuri:

φ((x+Ker(f ))+(y+Ker(f ))) = φ((x+y)+Ker(f )) = f (x+y) = f (x)+f (y) = = φ(x + Ker(f )) + φ(y + Ker(f )). Nucleul acestui morfism este Ker(φ) = {x + Ker(f )|

f (x) = 0} =

= {x + Ker(f )| x ∈ Ker(f )} = {Ker(f )}, care este elementul neutru în grupul factor G/Ker(f ), deci φ este morfism injectiv. Imaginea morfismului φ este Im(φ) = {f (x)| x + Ker(f ) ∈ G/Ker(f )} = Im(f ). Restrângând codomeniul morfismului injectiv φ la imaginea sa, obţinem φ izomorfism de grupuri. Test de autoevaluare 1. Determinaţi subgrupurile unui grup de ordin 2017. 2. Fie H subgrupul generat de elementul ˆ4 în grupul (Z10 , +). Scrieţi clasele laterale (la stânga) modulo subgrupul H şi verificaţi Teorema lui Lagrange. 3. Fie (G, ·) un grup abelian şi H un subgrup al său, iar xH o clasă laterală a sa. Demonstraţi că mulţimile H şi xH sunt cardinal echivalente. Indicaţii de rezolvare: 1) Folsim faptul că 2017 este număr prim şi Teorema lui Lagrange. 2) A se revedea Exemplul 4.4.1. 3) Se defineşte ψx : H → xH, prin ψx (h) = x · h pentru orice h ∈ H. Se arată că este bijecţie.

65

REZUMAT Grupul este un monoid în care orice element este simetrizabil. Subgrupul este o submulţime a unui grup care are proprietatea că devine grup dacă restrângem legea de compozitie de pe grup la această submulţime. Nucleul şi imaginea unui morfism de grupuri sunt subgrupuri ale domeniului, respectiv codomeniului. Orice subgrup determină o partiţie pe grupul în care se află. Numărul claselor de echivalenţă din partiţie se numeşte indicele subgrupului. Are loc Teorema lui Lagrange, care, în cazul grupurilor finite, conduce la faptul că ordinul oricărui subgrup divide ordinul grupului.

4.5 Temă de control la finalul unităţii de învăţare M1.U4. 1. Se consideră mulţimea de funcţii K = {f0 , f1 , f2 , f3 }, cu fi : R × R → R × R, (∀)i ∈ {0, 1, 2, 3}, unde f0 (x, y) = (x, y), f1 (x, y) = (x, −y), f2 (x, y) = (−x, y), f3 (x, y) = (−x, −y), (∀)(x, y) ∈ R × R. Întocmiţi tabla operaţiei de compunere pe K şi demonstraţi că mulţimea K este grup în raport cu compunerea funcţiilor. Acest grup se numeşte grupul lui Klein. Elementele sale reprezintă simetriile în plan faţă de axele de coordonate şi origine, respectiv. Demonstraţi că grupurile (K, ◦) şi (Z2 × Z2 , +) sunt izomorfe. ˆ = [4·k], pentru 2. Fie f : Z15 → Z20 definită prin f (k) orice kˆ ∈ Z15 , unde am notat cu [x] clasa de resturi modulo 20 a întregului x.

66

a) Arătaţi că f este corect definită, adică nu depinde de reprezentanţi. b) Demonstraţi că f este morfism între grupurile (Z15 , +) şi (Z20 , +). c) Determinaţi Ker(f ) şi Im(f ). d) Câte soluţii are ecuaţia f (x) = [7]? Dar ecuaţia f (x) = [12]? De ce? 3. Demonstraţi că funcţia f : Z → Zn definită prin ˆ (∀)k ∈ Z este un morfism surjectiv de f (k) = k, grupuri de la (Z, +) la (Zn , +). Determinaţi nucleul acestui morfism. Indicaţii de rezolvarea a temei de control: 1) Se întocmesc tablele celor două grupuri şi se stabileşte izomorfismul φ : K → Z2 × Z2 , φ(f0 ) = (ˆ 0, ˆ 0), φ(f1 ) = (ˆ0, ˆ1), φ(f2 ) = (ˆ1, ˆ0), φ(f3 ) = (ˆ1, ˆ1). 2) A se revedea Exemplul 4.2.3. 3) Se verifică f (x + y) = f (x) + f (y) pentru orice x, y ∈ Z. Nucleul este nZ.

Unitatea de învăţare 5 M1.U5. Grupuri de permutări . U5.0 Obiectivele unităţii de învăţare Această unitate de învăţare este foarte scurtă şi introduce un caz particular dar foarte important de grup, Grupul de permutări al unei mulţimi finie. La sfârşitul acestei unităţi de învăţare studenţii vor fi capabili să descompună o permutare în produs de cicluri disjuncte, să calculeze produs de permutări, descompunere în transpoziţii şi să determine semnul unei permutări lucrând cu cicluri. Estimăm parcurgerea acestei unităţi de învăţare în 2 ore.

5.1 Grupuri de permutări Fie A o mulţime nevidă şi AA mulţimea funcţiilor f : A → A. În raport cu compunerea funcţiilor, AA este monoid. Mulţimea elementelor inversabile în acest grup formează grup, numit grupul permutărilor mulţimii A. Prin urmare permutările unei mulţimi 67

68

A sunt funcţii bijective f : A → A. Ne amintim! O funcţie f : a → B se numeşte bijectivă dacă este injectvă şi surjectivă, adică dacă pentru orice element y ∈ B există în mod unic un element x ∈ A astfel încât y = f (x). Exemplul 5.1.1 Dacă A = {a, b, c}, atunci AA are 33 elemente, dintre care 6 sunt bijecţii, deci formează S(A): ( ) ( ) ( ) a b c a b c a b c f1 = , f2 = , f3 = , a b c b c a c a b ( ) ( ) ( ) a b c a b c a b c f4 = , f5 = , f6 = , a c b c b a b a c Fie M şi N două mulţimi şi (S(M ), ◦), (S(N ), ◦) grupurile lor de permutări introduse în Exemplul 4.1.1. Propozitia 5.1.1 Dacă M şi N sunt echipotente, atunci grupurile (S(M ), ◦) şi (S(N ), ◦) sunt izomorfe. Demonstraţie: Avem S(M ) = {f : M → M | f bijectivă}, S(N ) = {h : N → N | h bijectivă}. Din ipoteză există o bijecţie φ : M → N . Definim funcţia γ : S(M ) → S(N ),

γ(f ) = φ ◦ f ◦ φ−1 ,

∀f ∈ S(M ),

unde φ−1 este inversa bijecţiei φ. Deoarece compunerea funcţiilor bijective este tot o funcţie bijectivă, γ este corect definită. Vom demonstra că γ este morfism bijectiv de grupuri: γ(f1 ◦ f2 ) = φ ◦ (f1 ◦ f2 ) ◦ φ−1 = φ ◦ f1 ◦ (φ−1 ◦ φ) ◦ f2 ◦ φ−1 = = (φ ◦ f1 ◦ φ−1 ) ◦ (φ ◦ f2 ◦ φ−1 ) = γ(f1 ) ◦ γ(f2 ), ∀f1 , f2 ∈ S(M ), deci γ este morfism de la grupul (S(M ), ◦) la grupul (S(N ), ◦).

69

Fie acum f ∈ Ker(γ). Avem f : M → M bijectivă astfel încât γ(f ) este elementul neutru în S(N ), ◦), deci γ(f ) = 1N . Din definiţia funcţiei γ rezultă φ ◦ f ◦ φ−1 = 1N , de unde f = φ−1 ◦ φ = 1M . Prin urmare nucleul morfismului γ conţine doar elementul neutru din domeniul de definiţie şi, conform Propoziţiei 4.2.5, γ este injectiv. Pentru h ∈ S(N ) arbitrar ales, există f = φ−1 ◦ h ◦ φ ∈ S(M ) care are proprietatea că γ(f ) = h. Rezultă că morfismul γ este şi surjectiv, deci este un izomorfism.

Observatia 5.1.1 O consecinţă imediată a Propoziţiei 5.1.1 este faptul că grupurile de permutări ale tuturor mulţimilor cu n elemente sunt izomorfe, fiind izomorfe cu Sn , grupul de permutări al mulţimii In = {1, 2, ..., n}. Grupul (Sn , ◦) se numeşte grupul simetric Sn . Fie (Sn , ◦) grupul introdus mai sus. Un element σ ∈ Sn este o funcţie bijectivă, σ : In → In . Această funcţie o numim permutare şi o putem reprezenta printr-un tablou ( ) 1 2 ... n , σ(i) ̸= σ(j), ∀i ̸= j. σ(1) σ(2) ... σ(n) Permutarea identică corespunde funcţiei identice(şi o notăm ) de 1 2 obicei cu e. De exemplu, S2 are elementele e = ,σ= 1 2 ( ) 1 2 . 2 1 Deoarece grupul (Sn , ◦) are ca elemente toate bijecţiile de la o mulţime cu n elemente la ea însăşi, rezultă: Propozitia 5.1.2 Ordinul grupului simetric Sn este n!, pentru orice număr natural n ≥ 2.

70

Fie σ ∈ Sn . Numim ciclu o permutare σ ∈ Sn cu proprietatea că există o secvenţă (i1 , i2 , ..., im ) de elemente din In , astfel încât σ(i1 ) = i2 , σ(i2 ) = i3 ,..., σ(im ) = i1 şi σ(i) = i, ∀i ∈ / {i1 , ..., im }. Numărul m se numeşte lungimea ciclului. Scriem σ = (i1 , i2 , ..., im ). Exemplul 5.1.2 Ciclul (1, 3, 2) ∈ S7 este permutarea ( ) 1 2 3 4 5 6 7 , σ1 = 3 1 2 4 5 6 7 iar (4, 5, 7, 6) ∈ S7 este permutarea ( ) 1 2 3 4 5 6 7 σ2 = . 1 2 3 5 7 4 6 Exerciţiu: Ce permutare este ciclul (2, 1, 4, 8) în grupul (S9 , ◦)? O permutare poate conţine mai multe cicluri. Exemplul 5.1.3 a) Permutarea identică din Sn conţine n cicluri de lungime 1. ( ) 1 2 3 4 5 6 7 b) Permutarea σ = conţine 3 1 2 5 7 4 6 două cicluri: (1, 3, 2) şi (4, 5, 7, 6). Observatia 5.1.2 Dacă σ = (i1 , i2 , ..., ik ) este un ciclu din Sn , atunci inversul acestuia în Sn este tot un ciclu şi anume σ −1 = (ik , ik−1 , ..., i2 , i1 ). Într-adevăr, compunând cele două permutări găsim permutarea identică. Fie σ = (i1 , i2 , ..., im ). Mulţimea {i1 , i2 , ..., im } reprezintă mulţimea de definiţie a ciclului σ. Două cicluri se numesc disjuncte dacă mulţimile lor de definiţie sunt disjuncte.

71

Propozitia 5.1.3 Dacă σ1 , σ2 ∈ Sn sunt două cicluri disjuncte , atunci σ1 ◦ σ2 = σ2 ◦ σ1 . Mai spunem că oricare două cicluri disjuncte comută. Demonstraţie: Fie σ1 = (i1 , i2 , ..., in ) şi σ2 = (j1 , j2 , ..., jm ) cele două cicluri. Ciclurile fiind disjuncte rezultă că σ1 (i) = i, ∀i ∈ {j1 , ..., jm } şi σ2 (i) = i, ∀i ∈ {i1 , ..., in }. Calculăm  ∀i ∈ / {j1 , ..., jm }  σ1 (i), σ1 ◦ σ2 (i) = σ (j ), i = jk , ∀k ∈ {1, ..., m − 1}  1 k+1 σ1 (j1 ), i = jm  i, ∀i ∈ / {i1 , ..., in , j1 , ..., jm }      il+1 , i = il , ∀l ∈ {1, ..., n − 1} i1 , i = in , =   j , i = jk , ∀k ∈ {1, ..., m − 1}    k+1 j1 , i = jm apoi  ∀i ∈ / {i1 , ..., in }  σ2 (i), σ (i ), i = il , ∀l ∈ {1, ..., n − 1} σ2 ◦ σ1 (i) =  2 l+1 σ2 (i1 ), i = in  i, ∀i ∈ / {i1 , ..., in , j1 , ..., jm }      il+1 , i = il , ∀l ∈ {1, ..., n − 1} i1 , i = in , =    j , i = jk , ∀k ∈ {1, ..., m − 1}   k+1 j1 , i = jm Am obţinut aceeaşi lege de definiţie pentru permutările σ1 ◦ σ2 şi σ2 ◦ σ1 , deci sunt egale.

72

Propozitia 5.1.4 Pentru orice permutare σ ∈ Sn , există un număr natural k şi ciclurile σ1 , σ2 , ..., σk ∈ Sn , disjuncte două câte două astfel încât σ = σ1 ◦ σ2 ◦ ... ◦ σk . În plus, descompunerea este unică, abstracţie făcând de ordinea factorilor. Demonstraţie: Pornind căutarea de la 1, identificăm primul ciclu din σ şi îl notăm σ1 = (i1 , ..., ik ). Calculăm σ1−1 ◦ σ şi în noua permutare obţinută astfel elementul il este dus în el însuşi deoarece prin σ era dus în il+1 , iar prin σ1−1 , il+1 este dus în il , ∀l ∈ {1, ..., k − 1}. Analog pentru ik . Deci în această nouă permutare elementele ciclului σ1 nu mai sunt implicate în niciun alt ciclu. Identificând aici următorul ciclu σ2 , acesta va fi deci disjunct de σ1 . Cum mulţimea de definiţie a permutării σ este finită, după un număr finit de paşi obţinem descompunerea lui σ în produs de cicluri disjuncte. Datorită Propoziţiei 5.1.3, nu are importanţă ordinea în care se compun ciclurile. ( ) 1 2 3 4 5 6 7 Exemplul 5.1.4 Permutarea σ = 3 1 2 5 7 4 6 se descompune σ = (132) ◦ (4576). De obicei se omite scrierea operaţiei(de compunere, deci σ =)(132)(4576). 1 2 3 4 5 6 7 8 Permutarea τ = se descom3 2 1 5 6 4 8 7 pune τ = (13)(2)(456)(78). Compunerea permutărilor se poate face mai uşor folosind descompunerea lor în produs de cicluri disjuncte σ ◦ τ = (132)(4576) ◦ (13)(2)(456)(78), astfel: prin τ elementul 1 este dus în 3, iar prin σ elementul 3 este dus în 2. Scriem deci la rezultat începutul

73

unui ciclu 1, 2. Am rămas la 2, care prin τ este dus în el însuşi fiind element al unui ciclu de lungime 1. De remarcat faptul că ciclurile de lungime 1 reprezintă permutarea identică şi se pot omite la descompunere. Prin urmare absenţa unui element din scrierea unei permutări ca produs de cicluri disjuncte arată că acel element e dus în el însuşi. Continuăm calculul, 2 e dus prin σ în 1, deci închidem ciclul (12). Continuăm cu primul element în ordine crescătoare care nu a apărut la rezultat, în cazul nostru cu 3. Prin τ 3 e dus în 1, care e dus în 3 prin σ . Permutarea rezultat invariază elementul 3, deci scriu (3) sau îl omit. Continuăm cu 4. Prin τ este dus în 5, iar acesta e dus în 7 prin σ. Scriem deci 4, 7. Elementul 7 merge prin τ în 8 care prin σ merge în 8. Scriem după 7 elementul 8 la rezultat. Prin τ , 8 este dus în 7, care prin σ este dus în 6. Scriem 6 şi continuăm cu el. 6 e dus prin τ în 4, iar prin σ 4 este dus în 5. Scriem 5 după 6 la rezultat. Elementul 5 e dus prin τ în 6 care prin σ e dus în 4, deci ciclul se încheie. Obţinem σ ◦ τ = (12)(47865). Analog putem calcula τ ◦ σ = (13)(2)(456)(78) ◦ (132)(4576) = (23)(46587). Exerciţiu: Scrieţi următoarele permutări ca produse de cicluri disjuncte, apoi calculaţi σ ◦ τ , τ ◦ σ: ) ( 1 2 3 4 5 6 7 8 9 , σ= 9 2 1 8 6 5 3 4 7 ) ( 1 2 3 4 5 6 7 8 9 . τ= 7 3 9 6 8 5 2 4 7

74

Definitia 5.1.1 Un ciclu de lungime 2 se numeşte transpoziţie. Observatia 5.1.3 Orice ciclu (i1 i2 ...im ) se poate scrie ca produs (compunere) de transpoziţii: (i1 i2 )(i2 i3 )...(im−1 im ), ceea ce se verifică prin calcul direct. Ţinând cont de Observaţia anterioară şi de Propoziţia 5.1.4, rezultă că: Propozitia 5.1.5 Orice permutare se descompune în produs de transpoziţii. Exemplul 5.1.5 Permutarea σ = (132)(4576) se scrie ca produs de transpoziţii astfel: σ = (13)(32)(45)(57)(76). Fie σ ∈ Sn . O pereche ordonată (i, j), cu 1 ≤ i < j ≤ n, se numeşte inversiune a permutării σ dacă σ(i) > σ(j). Numărul inversiunilor permutării σ se notează inv(σ). O permutare se numeşte pară, respectiv impară dacă are număr par, respectiv impar de inversiuni. Numărul sgn(σ) = (−1)inv(σ) , notat şi ϵ(σ), se numeşte semnul sau signatura permutării σ. Evident, sgn(σ) = 1, dacă σ este permutare pară şi sgn(σ) = −1, dacă σ este permutare impară. Propozitia 5.1.6 Avem sgn(σ) =

∏

σ(j) − σ(i) . j − i 1≤i≤j≤n

Demonstraţie: Din faptul că orice permutare σ este o bijecţie rezultă că membrul drept al egalităţii din enunţ este raportul

75

dintre produsul diferenţelor de tipul (k−l), cu k ̸= l, 1 ≤ k, l ≤ n şi acelaşi produs, eventual cu semne schimbate acolo unde σ are o inversiune. Deci ∏ σ(j) − σ(i) = (−1)inv(σ) = sgn(σ). j−i 1≤i≤j≤n

Propozitia 5.1.7 Orice transpoziţie este o permutare impară. Demonstraţie: Fie transpoziţia (ij) ∈ Sn , adică permutarea ( ) 1 2 ... i − 1 i i + 1 ... j − 1 j j + 1 ... n (ij) = 1 2 ... i − 1 j i + 1 ... j − 1 i j + 1 ... n Observăm că are următoarele inversiuni: (i, j), (i, k), (k, j), ∀k ∈ {i+1, ..., j −1}, adică număr impar de inversiuni. Conform definiţiei semnului unei permutări, rezultă că orice transpoziţie este impară. Propozitia 5.1.8 Funcţia sgn : Sn → {−1, 1} definită mai sus este un morfism de la grupul (Sn , ◦) la grupul ({−1, 1}, ·), unde · este înmulţirea uzuală a numerelor întregi. Demonstraţie: Pentru orice σ, τ ∈ Sn , avem: ∏ (σ ◦ τ )(j) − (σ ◦ τ )(i) ∏ σ(τ (j)) − σ(τ (i)) sgn(σ◦τ ) = = = j − i j − i 1≤i≤j≤n 1≤i≤j≤n = =

∏

∏

σ(τ (j)) − σ(τ (i)) τ (j) − τ (i) · = τ (j) − τ (i) j − i 1≤i≤j≤n

σ(τ (j)) − σ(τ (i)) ∏ τ (j) − τ (i) · = sgn(σ)·sgn(τ ). τ (j) − τ (i) j − i 1≤i≤j≤n 1≤i≤j≤n

76

Observatia 5.1.4 Din Propoziţiile 5.1.7, 5.1.8 şi Observaţia 5.1.3, rezultă că un ciclu este permtare pară sau impară, după cum lungimea lui este număr impar, respectiv par.

Exemplul 5.1.6 Semnul permutării σ = (1354)(267) se stabileşte astfel: descompunem σ în produs de transpoziţii (13)(35)(54)(26)(67) şi semnul produsului de transpoziţii este produsul semnelor conform Propoziţiei 5.1.8, adică (−1)5 = −1, de unde rezultă σ impară. O altă metodă este să utilizăm Observaţia 5.1.4, conform căreia sgn((1354)) = −1, sgn((267)) = 1, deci sgn(σ) = −1. Încheiem secţiunea cu o problemă de numărare: Câte cicluri de lungime k există în Sn ? Fie (i1 i2 ...ik ) un ciclu de lungime k ≤ n din Sn . Alegerea ordonată a elementelor i1 , i2 , ..., in din cele n ale mulţimii In se face n! în Akn = (n−k)! moduri. Dar ciclurile (i1 i2 ...ik ), (i2 i3 ...ik i1 ), ..., (ik i1 ...ik−1 ) coincid, deci numărul ciclurilor distincte de lungime k k este Akn = Cnk (k − 1)!. În particular, există n(n−1) transpoziţii 2 şi (n − 1)! cicluri de lungime n în Sn .

REZUMAT Grupurile de permutări sunt un caz particular de grupuri finite foarte importante. Permutările sunt funcţii bijective definite pe o mulţime finită cu valori în ea însăşi. Se pot compune, se pot descompune în produs de cicluri disjuncte şi în produs de transpoziţii.

77

5.2 Temă de control la finalul unităţii de învăţare M1.U5. 1. Scrieţi subgrupul generat de elementul σ = (1, 2, 3) în (S4 , ◦). 2. Fie permutările ( 1 σ= 4 ( 1 π= 5 ( 1 τ= 7

2 3 4 5 6 7 8 5 1 2 6 3 8 7 2 3 4 5 6 7 8 2 7 1 3 4 8 6 2 3 4 5 6 7 8 8 1 5 6 4 3 2

) ) , ) .

Descompuneţi permutările în produs de cicluri disjuncte, apoi în produs de transpoziţii şi precizaţi semnul fiecăreia. Determinaţi permutările σ 2 , σ 3 , σ −1 , σ ◦ π, π ◦ σ, σ ◦ τ , τ ◦ σ, τ ◦ π, π ◦ τ , efectuând calcul cu cicluri. 3. Arătaţi că în grupul permutărilor (S3 , ◦), submulţimea H = {e, (12)} este subgrup. Indicaţii de rezolvare a temei de control: 1) Subgrupul generat este {e, σ, σ 2 , σ 3 }. 2) Folosim Exemplul 5.1.4. 3) Verificăm condiţiile de subgrup, din Propoziţia 4.3.1 b).

Unitatea de învăţare 6 M1.U6. Ordinul unui element. Grupuri ciclice U6.0. Obiectivele unităţii de învăţare Ultima unitate de învăţare a modulului unu are ca temă ordinul unui element într-un grup şi grupuri ciclice. Noţiunea de grup ciclic a apărut încă din M1.U4. şi invităm cititorul să o actualizeze parcurgând din nou paragraful trei al celei de-a patra unităţi de învăţare a modulului unu. Rezultatele privind ordinul elementelor în grupuri finite se aplică în cazul particular al grupului multiplicativ al claselor de resturi (U (Zn ), ·) şi se obţin două teoreme celebre care îşi găsesc aplicaţii în criptografie. Unitatea de învăţare se încheie cu prezentarea unui algoritm de criptare care utilizează cele două teoreme. Acest paragraf reprezintă o extindere a materiei şi nu este cerut la examen. La sfârşitul acestei unităţi de învăţare studenţii vor fi capabili să determine ordinul unui element într-un grup finit şi să decidă dacă un grup finit este sau nu ciclic. Vor putea să utilizeze Teorema lui Euler şi Mica Teoremă a lui Fermat. 78

79

Estimăm parcurgerea acestei unităţi de învăţare în 2 ore.

6.1 Ordinul unui element Fie (G, ·) un grup cu elementul neutru e şi x ∈ G. În Observaţia 4.3.2 am precizat că subgrupul ciclic generat de elementul x în G este < x >= {xk | k ∈ Z}. Definitia 6.1.1 Ordinul subgrupului generat de elementul x ∈ G în grupul (G, ·) se numeşte ordinul elementului x şi se notează o(x). Amintim că ordinul unui grup este cardinalul său, notat |G| sau o(G). Din definiţia ordinului unui element şi din Propoziţia 4.4.3 rezultă: Propozitia 6.1.1 Într-un grup finit ordinul fiecărui element este divizor al ordinului grupului. Observatia 6.1.1 a) Afirmaţia anterioară spune, de exemplu, că un grup de ordin 10 nu poate avea elemente de ordin 3. b) Într-un grup oarecare (G, ·), singurul element de ordin 1 este elementul neutru e, deoarece subgrupul generat de el este {e}. Exemplul 6.1.1 a) În (Z6 , +), o(b 2) = 3, o(b 3) = 2, b b b o(4) = 3, o(1 = o(5) = 6. b) În grupul simetric (S3 , ◦) elementul σ = (123) este de ordin 3, iar τ = (23) este de ordin 2. c) În grupul lui Klein toate elementele cu exceptia celui neutru sunt de ordin 2.

80

d) Ordinul oricărui element nenul n din grupul (Z, +) este infinit, subgrupul generat de acesta fiind nZ. Propozitia 6.1.2 Fie (G, ·) un grup şi x ∈ G un element de ordin finit. Sunt adevărate următoarele afirmaţii: a) Ordinul elementului x este cel mai mic întreg pozitiv n0 cu proprietatea xn0 = e, adică: o(x) = min{n ∈ Z∗+ | xn = e}. b) Pentru orice m ∈ Z, xm = e ⇔ o(x) divide m. c) (∀)p, q ∈ Z, xp = xq ⇔ p ≡ q(mod o(x)). d) Dacă o(x) = n, atunci pentru orice întreg m, o(xm ) =

n , (m, n)

unde am notat cu (a, b) cel mai mare divizor comun al întregilor a şi b. Demonstraţie: a)Dacă < x >= {e}, ceea ce este echivalent cu x = e, atunci o(x) = 1 şi afirmaţia este adevărată. Dacă x ̸= e, deoarece din în ipoteză avem o(x) = |{xk | k ∈ Z}| < ∞, rezultă că nu toate elementele din < x > sunt distincte. Există întregii k > l astfel încât xk = xl . Compunând la dreapta cu (xl )−1 rezultă că există întregul pozitiv n = k − l cu proprietatea xn = e. Aşadar submulţimea numerelor naturale {n ∈ Z∗+ | xn = e} este nevidă. Din proprietatea de bună ordonare a mulţimii N, există un cel mai mic element n0 al acestei submulţimi.

81

Vom demonstra că < x >= {e, x, x2 , ..., xn0 −1 }. Notăm cu A mulţimea din membrul drept al egalităţii de mai sus. Incluziunea ’⊇’este evidentă din forma elementelor din < x >. Pentru a demonstra incluziunea inversă, fie y ∈< x > arbitrar ales. Există m ∈ Z astfel încât y = xm . Aplicăm Teorema împărţirii cu rest numerelor întregi m şi n0 , deci există c, r ∈ Z cu proprietatea m = c · n0 + r, 0 ≤ r < n0 . Ţinând cont că xn0 = e, obţinem xm = xc·n0 +r = (xn0 )c · xr = xr ,

0 ≤ r < n0 ⇒ xm ∈ A,

deci avem şi incluziunea inversă. Rezultă cardinalul mulţimii < x > egal cu n0 , de unde o(x) = n0 . b) Fie m ∈ Z pentru care xm = e. Rezultă că m este un element al mulţimii M = {n ∈ Z∗+ | xn = e} al cărei minim este n0 = o(x). Aplicăm din nou Teorema împărţirii cu rest numerelor întregi m şi n0 , deci există c, r ∈ Z cu proprietatea m = c · n0 + r, 0 ≤ r < n0 . Calculând xm obţinem xr = e, cu r nul sau mai mic strict decât n0 . Dacă presupunem r ̸= 0, contrazicem faptul că n0 este minimul mulţimii M . Deci r = 0, aşadar o(x)|m. Implicaţia inversă este evidentă. c) Fie p, q ∈ Z, cu proprietatea că xp = xq . Compunând la dreapta cu (xq )−1 , egalitatea este echivalentă cu xp−q = e, ceea ce este echivalent cu o(x)|(p − q), conform b). d) Fie o(x) = n, şi un întreg arbitrar m. Considerăm cel mai mare divizor comun al lor d = (m, n). Există numerele întregi m1 , n1 , prime între ele, cu m = m1 · d şi n = n1 · d. Numărul a = o(xm ) este, conform a), cel mai mic întreg pozitiv cu proprietatea (xm )a = e. Deoarece avem xn1 ·d = e, avem şi (xm )n1 = e, deci o(xm ) divide n1 , din b).

82

Avem (xm )a = e şi o(x) = n, deci n|m · a. Există k ∈ Z astfel încât m · a = n · k ⇔ m1 · d · a = n1 · d · k ⇔ m1 · a = n1 · k ⇒ n1 |m1 · a. Aveam şi (m1 , n1 ) = 1, deci n1 |a. Numerele întregi pozitive a şi n1 se divid unul pe celălalt, prin urmare am obţinut egalitatea dorită, o(xm ) = a = n1 = nd . Observatia 6.1.2 Afirmaţia a) din Propoziţia 6.1.2 este adesea considerată definiţia ordinului unui element. Ea oferă o metodă mai simplă de a determina ordinul unui element, decât determinarea subgrupului generat de acel element şi a ordinului acestuia. Observatia 6.1.3 În grupul simetric (Sn , ◦) orice transpoziţie este element de ordin 2, iar un ciclu de lungime k este element de ordin k. Într-adevăr, pentru σ = (i1 , i2 , ..., ik ) putem calcula: σ 2 = (i1 i3 ....ik−1 )(i2 i4 ...ik ), ∀k = par, σ 2 = (i1 i3 ...ik i2 i4 ...ik−1 ),

∀k = impar.

Observăm că regula este ”salt peste 2”. Pentru σ l , regula va fi ”salt peste l”, deci σ k = e. O consecinţă este următorul mod de a determina ordinul unei permutări. Se descompune permutarea în produs de cicluri. Ordinul permutării este cel mai mic multiplu comun al lungimilor ciclurilor din care e alcătuită. De exemplu, o((32)(56)(7891)) = 2, o((123)(4789)(56)) = 12. Exerciţiu: Detreminaţi ordinul permutării ( ) 1 2 3 4 5 6 7 8 9 σ= . 5 4 1 3 6 2 9 8 7

83

Exemplul 6.1.2 Pentru a determina ordinul elementului ˆ3 în grupul (Z15 , +), observăm 2 · ˆ3 ̸= ˆ0,

3 · ˆ3 ̸= ˆ0,

4 · ˆ3 ̸= ˆ0,

5 · ˆ3 = ˆ0 → o(ˆ3) = 5.

Faptul că ordinul unui element este divizor al ordinului grupului uşurează calculul. Ordinul lui ˆ3 ar putea fi doar 1, 3, 5 sau 15. Dar singurul element de ordin 1 este cel neutru, deci îl compunem pe ˆ3 cu el însuşi de 3, apoi de 5 ori şi observăm că o(ˆ3) = 5. Ştiind ordinul elementului ˆ3, ordinul elementului ˆ = 4· ˆ3 se determină folosind punctul d) al Propoziţiei 12 6.1.2: o(ˆ3) 5 o(4 · ˆ3) = = = 5. ˆ 4) (5, 4) (o(3), Exerciţiu: Determinaţi ordinul elementului ˆ5 în grupul (Z20 , +). Propozitia 6.1.3 Fie (G, ·) un grup finit. Pentru orice element x ∈ G are loc xo(G) = e. Demnostraţie: Conform Propoziţiei 6.1.1, o(x)|o(G). Există deci k ∈ Z astfel încât o(G) = k · o(x). Din Propoziţia 6.1.2 a) avem xo(x) = e, deci putem calcula xo(G) = xk·o(x) = (xo(x) )k = ek = e.

Test de autoevaluare 1. Definiţi ordinul unui element într-un grup. Demonstrăţi că, dacă grupul este finit, atunci ordinul oricărui element din grup divide ordinul grupului.

84

2. Determinaţi ordinul fiecărui element din grupurile: (S3 , ◦), (Z, +), (Z6 , +), (U (Z8 ), ·). Indicaţii de rezolvare: 1) Se foloseşte definiţia ordinului uni element şi Teorema lui Lagrange, pentru grupuri finite. 2) Folosim Exemplul 6.1.2.

6.2 Grupuri ciclice Fie (G, ·) un grup cu elementul neutru e şi grupul aditiv al numerelor întregi, (Z, +). Fie x ∈ G, arbitrar fixat. Funcţia fx : Z → G,

fx (k) = xk ,

(∀)k ∈ Z,

este un morfism de grupuri. Imaginea morfismului fx este subgrupul generat de x în G. Nucleul său este un subgrup în grupul (Z, +), iar toate subgrupurile acestui grup sunt ciclice. Deci Ker(fx ) este ciclic şi este fie 0, fie generat de cel mai mic întreg pozitiv n0 pe care îl conţine, Ker(fx ) = n0 Z. Pentru morfismul fx avem două situaţii: (I) Ker(fx ) = {0}, ceea ce este echivalent fx injectivă. În acest caz funcţia fx : Z →< x > este bijecţie, deci subgrupul generat de x este izomorf cu (Z, +). O consecinţă imediată de aici este că G este grup infinit, din moment ce conţine un subgrup infinit. (II) Ker(fx ) ̸= {0}, deci Ker(fx ) = n0 Z, n0 > 0, adică n0 este cel mai mic element al mulţimii {k ∈ Z|xk = e}. Conform Propoziţiei 6.1.2 a), generatorul nucleului este chiar ordinul elementului x. Aceasta conduce la (< x >, ·) izomorf cu (Zn0 , +) prin φ : Zn0 →< x >, φ(b k) = xk , conform Teoremei fundamentale de izomorfism. Din cele discutate mai sus reiese că:

85

Teorema 6.2.1 Într-un grup (G, ·), subgrupul ciclic (< x >, ·) generat de x ∈ G este izomorf cu (Z, +) dacă o(x) este infinit, respectiv cu (Zo(x) , +), pentru o(x), finit. Fie (G, ·) un grup ciclic, deci există x ∈ G astfel încât G =< x >. Un astfel de element x se numeşte generator al grupului. Exemplul 6.2.1 a) Elementele 1, −1 sunt generatori ai grupului ciclic (Z, +). b) În grupul (Zn , +) elementul ˆ1 este generator. Observatia 6.2.1 Un grup finit este ciclic dacă şi numai dacă conţine un element de ordin egal cu ordinul grupului. O consecinţă a Teoremei 6.2.1 este: Teorema 6.2.2 Orice grup ciclic infinit este izomorf cu grupul aditiv al numerelor întregi. şi orice grup ciclic finit de ordin n este izomorf cu grupul aditiv al claselor de resturi modulo n. O consecinţă imediată a Teoremei 6.2.2 este: Propozitia 6.2.1 Oricare două grupuri ciclice de acelaşi ordin sunt izomorfe. Propozitia 6.2.2 Orice grup de ordin p prim este ciclic, deci izomorf cu (Zp , +). Demonstraţie: Fie (G, ·) grup, |G| = p, cu p număr prim, şi x un element din G, diferit de elementul neutru. Fie n ordinul subgrupului < x > generat de x în G. Conform Propoziţiei 6.1.1, n divide p, deci n ∈ {1, p}. Dar singurul element de ordin 1 este cel neutru şi x ̸= e, de unde rezultă o(x) = p, deci G este ciclic. A doua afirmaţie rezultă aplicând Teorema 6.2.2. Suntem acum în măsură să dă o clasificare a grupurilor de ordin 4:

86

Aplicaţie: Grupuri de ordin 4 Fie (G, ·) un grup de ordin 4, arbitrar ales. Exemple de astfel de grupuri sunt: (Z4 , +), (U (Z8 ), ·), (Z2 × Z2 , +) (vezi Exemplul 4.1.2 pentru produs direct de grupuri), grupul lui Klein (K, ◦). Dacă grupul G ales este ciclic, atunci, conform Teoremei 6.2.2, este izomorf cu (Z4 , +). Dacă G nu este ciclic, conform Observaţiei 6.2.1, nu conţine niciun element de ordin 4. Rezultă că toate elementele diferite de cel neutru sunt de ordin 2, acesta fiind singurul divizor propriu al numărului 4. Fie a ∈ G − {e}, unde am notat cu e elementul neutru din G. Subgrupul generat de a realizează o partiţie a lui G în < a > ∪ < a > ·b, pentru un b ∈ G− < a > fixat arbitrar. Avem deci G = {e, a, b, a · b}. Din faptul că toate elementele diferite de e sunt de ordin 2 rezultă (ab)2 = e = a2 b2 , care compusă la stânga cu a şi la dreapta cu b conduce la ba = ab. Ţinând cont de egalitatea anterioară şi de a2 = e, b2 = e, tabla operaţiei · este: · e a b ab e e a b ab a a e ab b . b ab e a b ab ab b a e Tabla operaţiei de adunare în grupul produs direct (Z2 × Z2 , +) este: + (ˆ0, ˆ0) (ˆ0, ˆ1) (ˆ1, ˆ0) (ˆ1, ˆ1) (ˆ0, ˆ0) (ˆ0, ˆ0) (ˆ0, ˆ1) (ˆ1, ˆ0) (ˆ1, ˆ1) (ˆ0, ˆ1) (ˆ0, ˆ1) (ˆ0, ˆ0) (ˆ1, ˆ1) (ˆ1, ˆ0) . (ˆ1, ˆ0) (ˆ1, ˆ0) (ˆ1, ˆ1) (ˆ0, ˆ0) (ˆ0, ˆ1) (ˆ1, ˆ1) (ˆ1, ˆ1) (ˆ1, ˆ0) (ˆ0, ˆ1) (ˆ0, ˆ0) Observăm că cele două table sunt identice, deci grupurile sunt izomorfe prin morfismul f : (G, ·) → (Z2 × Z2 , +), f (e) = (ˆ0, ˆ0), f (a) = (ˆ0, ˆ1), f (b) = (ˆ1, ˆ0), f (ab) = (ˆ1, ˆ1).

87

Am obţinut astfel că există doar două tipuri de grupuri de ordin 4: Propozitia 6.2.3 Orice grup de ordin 4 este izomorf sau cu (Z4 , +) (dacă e ciclic) sau cu (Z2 ×Z2 , +), (dacă toate elementele diferite de cel neutru au ordinul 2). Precizaţi de ce tip sunt grupurile: (U (Z8 ), ·), grupul lui Klein. Test de autoevaluare 1. Fie (G, ·) un grup cu 17 elemente. Demonstraţi că este ciclic. Câţi generatori are? 2. Stabiliţi care dintre grupurile: (Z, +), (Z6 , +), (U (Z8 ), ·), (U (Z1 2), ·) este grup ciclic. Determinaţi toţi generatorii. Indicaţii de rezolvare: 1) Se foloseşte faptul că 17 este număr prim. 2) Se determină ordinul fiecărui element. Dacă există un element de ordin egal cu ordinul grupului, atunci grupul este ciclic.

6.3 Teorema lui Euler. Mica Teoremă a lui Fermat Încheiem paragraful cu două teoreme celebre de aritmetică, a căror demonstraţie utilizează teoria grupurilor, şi care îşi găsesc aplicaţii în criptografie. Pentru aceasta avem nevoie de următoarea funcţie, numită Indicatorul lui Euler: φ : N∗ → N,

φ(n) = |{k ∈ N| k < n,

(k, n) = 1}|,

definită prin: φ(1) = 1 şi pentru orice număr natural n ≥ 1, φ(n) este egal cu numărul numerelor mai mici decât n, prime cu n.

88

Exemplul 6.3.1 φ(6) = 2 pentru că singurele numere prime cu 6, mai mci decât el, sunt 1 şi 5. Următoarea Propoziţie oferă o metodă de determinare a valorilor indicatorului lui Euler: Propozitia 6.3.1 a) Dacă p este prim, atunci φ(p) = p − 1. b) Dacă p este prim, atunci φ(pl ) = pl − pl−1 . c) Dacă (m, n) = 1, atunci φ(m · n) = φ(m) · φ(n). d) Pentru n = pa11 pa22 ...pakk este descompunerea în factori primi a numărului natural n, atiunci φ(n) = n(1 −

1 1 1 )(1 − )...(1 − ). p1 p2 pk

Demonstraţie: a) Pentru p prim, toate numerele nenule mai mici decât p: 1,2,..,p − 1, sunt prime cu el. b) Fie p număr prim. Există pl numere naturale mai mici decât pl . Dintre acestea nu sunt prime cu pl următoarele: 0, p, 2p, 3p, ..., p2 , p(p + 1), ..., p(pl−1 − 1), adică pl−1 numere. Deci rămân pl − pl−1 numere prime cu p. c) În primul rând remarcăm faptul că definiţia indicatorului lui Euler conduce la φ(n) = |{kˆ ∈ Zn |(k, n) = 1}| = |U (Zn )|. Fie numerele naturale nenule m, n, prime între ele şi funcţia f : Zm × Zn → Zmn ,

f (ˆ x, y˘) = [nx + my],

ˆ k, ˘ [k], clasele de resturi modulo m, n, unde am notat cu k, respectiv mn, ale numărului k. Funcţia f este corect definită deoarece xˆ = xˆ′ , y˘ = y˘′ implică m|(x−x′ ) şi n|(y −y ′ ), de unde nx+my −nx′ −my ′ este divizibil prin mn, deci [nx + my] = [nx′ + my ′ ].

89

Funcţia f este injectivă deoarece [nx + my] = [nx′ + my ′ ] duce la mn|(nx + my − nx′ − my ′ ) ⇒ m|n(x − x′ ),

n|m(y − y ′ ).

Dar m şi n sunt prime între ele, deci xˆ = xˆ′ şi y˘ = y˘′ . Domeniul şi codomeniul acestei funcţii sunt de acelaşi cardinal finit (=mn). Deoarece f este injectivă rezultă că şi este surjectivă. Fie acum (x, m) = 1, (y, n) = 1. Fie d = (nx + my, mn), de unde d|mn. Dar (m, n) = 1 implică d divide exact unul din ele şi este prim cu celălalt. Fie d|m ,(d, n) = 1. Aplicând proprietăţile cunoscute ale relaţiei de divizibilitate obţinem d|(x, m), deci d = 1. Reciproc, pentru întregii x, y, m, n, cu (nx + my, mn) = 1, fie d = (x, m) Rezultă d|1, deci (x, m) = 1. Analog (y, n) = 1. Am obţinut (x, m) = 1, (y, n) = 1 ⇔ (nx + my, mn) = 1, deci restricţia funcţiei f la {ˆ x ∈ Zm | (x, m) = 1} × {˘ y ∈ Zn | (y, n) = 1} are codomeniul {[z] ∈ Zmn | (z, mn) = 1}. Prin urmare cele două mulţimi de mai sus sunt cardinal echivalente, aşadar φ(mn) = φ(m) · φ(n). d) Rezultatul se obţine aplicând formulele de la b) şi c) descompunerii în factori primi a lui n. Exemplul 6.3.2 φ(125) = φ(53 ) = 53 − 52 = 120, φ(36) = φ(22 · 32 ) = 36(1 − 12 )(1 − 31 ) = 12. Exerciţiu: Calculaţi φ(50), φ(720). Ştim că grupul (Zn , +) este ciclic (un generator este b 1), (∀)n ≥ 2. Care ar fi alţi generatori? Propozitia 6.3.2 Fie x ∈ Zn . Următoarele afirmaţii sunt echivalente: a) x b generator în grupul (Zn , +); b) x b inversabil în monoidul (Zn , ·); c) Numerele x şi n sunt prime între ele: (x, n) = 1.

90

Demonstraţie: ”a)⇒ b)” Avem Zn =< xˆ >, deci orice element din Zn se scrie ca un multiplu de xˆ. Prin urmare există k ∈ Z, kˆ x = ˆ1. Egalitatea anterioară conduce la k ˆ· x = ˆ1, deci ˆ xˆ ∈ U (Zn ), cu xˆ−1 = k. ”b)⇒ a)” Fie xˆ ∈ U (Zn ), deci există kˆ ∈ Zn , kˆ · xˆ = ˆ1. Egalitatea anterioară se mai poate scrie kˆ x = ˆ1. Orice element din Zn este de forma a ˆ = aˆ1 = a · kˆ x, deci xˆ este generator al grupului ciclic (Zn , +). ”b)⇒ c)” Fie xˆ ∈ U (Zn ), deci există kˆ ∈ Zn , kˆ · xˆ = ˆ1 ⇒ (∃)m ∈ Z,

k · x + n · m = 1.

Fie d = (x, n). Din d|n, d|x şi egalitatea k · x + n · m = 1 rezultă d|1, deci d = 1. ”c)⇒ a)” Ştim că (x, n) = 1. Este cunoscută existenţa a doi întregi k, l ∈ Z cu proprietatea k · x + l · n = 1. Trecând egalitatea anterioară în Zn avem xˆ · kˆ = ˆ1, adică xˆ ∈ U (Zn ). Observatia 6.3.1 a) O consecinţă a Propoziţiei anterioare este că în monoidul (Zn , ·) avem U (Zn ) = {ˆ x ∈ Zn | (x, n) = 1}, deci indicatorul lui Euler, φ(n), este ordinul grupului (U (Zn ), ·), fiind egal cu numărul numerelor prime cu n, mai mici decât n. b) Pentru p prim, în monoidul (Zp , ·), oricare x ∈ Z∗p este inversabil, deci (Z∗p , ·) este grup. Exerciţiu: Ce ordin are grupul (U (Z36 ), ·)? Ne amintim! într-un grup (G, ·), xo(G) = e, pentru orice x ∈ G, unde e este elementul neutru al grupului. Aplicând rezultatul amintit mai sus grupului (U (Zn ), ·), obţinem un rezultat foarte important:

91

Teorema 6.3.1 [Teorema lui Euler] cu n are loc relaţia xφ(n) ≡ 1(mod

Pentru orice întreg x prim n).

Cazul n = p prim conduce la : Teorema 6.3.2 [Mica teoremă a lui Fermat] Pentru orice întreg x, prim cu numărul prim p, are loc xp−1 ≡ 1(mod p). Exemplul 6.3.3 Teoremele 6.3.1, 6.3.2 permit calculul restului care se obţine la împărţirea unei puteri mari printr-un număr: Dacă dorim determinarea restului modulo 24 a lui 2012 7 , calculăm φ(24) = 24(1 − 21 )(1 − 13 ) = 8 folosind Propoziţia 6.3.1 şi aplicăm Teorema lui Euler deoarece (7, 24) = 1, 78 ≡ 1(mod24) ⇒ 72012 = (78 )251 · 74 ≡ 74 (mod24). Prin calcul direct stabilim 72 = 49 ≡ 1(mod24), deci restul cerut este 1. Revenind acum la grupul U (Zn ), ·), remarcăm faptul că acesta nu este întotdeauna ciclic. ˆ ˆ5, ˆ6} este grup Exemplul 6.3.4 a) U (Z7 ) = {ˆ1, ˆ2, ˆ3, 4, de ordin 6 în raport cu · în care elementul ˆ1 este de ordin 1, elementele ˆ2, ˆ4 sunt de ordin 3, iar elementele ˆ3, ˆ5, ˆ6 sunt de ordin 6, deci generatori pentru U (Z7 ). Remarcăm că numărul generatorilor este φ(6). b) U (Z8 ) = {ˆ1, ˆ3, ˆ5, ˆ7} este grup de ordin 4 în raport cu · în care elementul ˆ1 este de ordin 1, iar celelalte

92

elemente sunt de ordin 2. Prin urmare niciun element nu are ordinul egal cu al grupului, deci nu este grup ciclic. Exerciţiu: Stabiliţi dacă grupul (U (Z20 ), ·) este ciclic. Definitia 6.3.1 Dacă (U (Zn ), ·) este grup ciclic, atunci un generator al său se numeşte rădăcină primitivă modulo n. Observatia 6.3.2 Este clar că un element a ˆ ∈ U (Zn ) este rădăcină primitivă modulo n dacă şi numai dacă o(ˆ a) = φ(n) în (U (Zn ), ·). Exemplul 6.3.5 Elementele ˆ3, ˆ5, ˆ6 sunt rădăcini primitive modulo 6.

6.4 Extindere-Logaritmul discret Teoremele lui Euler şi Fermat prezentate în paragraful anterior permit calcularea resturilor modulo n pentru puteri mari ale unui număr, ceea ce îşi găseşte aplicaţii în criptografie. Criptografia este o ştiinţă matematică care se ocupă cu transformarea datelor în forme neinteligibile pentru prevenirea accesului neautorizat. Un element algebric important este logaritmul discret. Fie (G, ·) un grup finit ciclic, de ordin n, şi a ∈ G un generator al său. Definitia 6.4.1 Logaritmul discret al unui element x ∈ G este un întreg k ∈ {0, 1, ..., n − 1}, notat loga x, cu proprietatea că x = ak . Trebuie remarcat faptul că logaritmul discret loga x există pentru orice x ∈ G doar dacă a este generator al grupului G.

93

Exemplul 6.4.1 Grupul (Z∗11 , ·) este ciclic, generat de exemplu de ˆ6, deoarece ˆ610 = ˆ1, conform Micii Teoreme ˆ deci nicun divizor a lui Fermat şi ˆ62 = ˆ3, ˆ65 = 10, al ordinului grupului (10) nu e ordinul elementului ˆ6. Rămâne o(ˆ6) = 10, adică este generator. Avem ˆ x | ˆ1 ˆ2 ˆ3 ˆ4 ˆ5 ˆ6 ˆ7 ˆ8 ˆ9 10 , logˆ6 x | 0 9 2 8 6 1 3 7 4 5 pe când logˆ3 x nu există pentru orice element din Z∗11 : ˆ x | ˆ1 2ˆ ˆ3 4ˆ ˆ5 6ˆ ˆ7 8ˆ ˆ9 10 , log3 x | 0 − 1 4 3 − − − 3 − deoarece o(ˆ3) = 5, deci 3ˆ nu este generator al grupului. Problema logaritmului discret constă în determinarea întregului k = loga x când se dau grupul ciclic G, generatorul a şi elementul x ∈ G. Un algoritm de criptare bazat pe dificultatea calculării logaritmului discret este algoritmul El Gamal cu cheie privată: 1. Codificarea: -Alegem un număr prim p mare şi g un generator al lui Z∗p , adică o rădăcină primitivă modulo p. -Alegem un exponent privat x ∈ {0, 1, ..., p − 2} şi calculăm un exponent public y = g x . Remarcăm faptul că x poate fi ales orice întreg, dar, datorită Micii Teoreme a lui Fermat, g p−1 = 1 = g 0 , deci are sens alegerea lui x din mulţimea menţionată. Cheia publică este (p, g, y). Securitatea criptării este asigurată de dificultatea calculării lui x = logg y. -Alegem un element arbitrar k ∈ {0, 1, ..., p − 2} şi calculăm K = yk . -Pentru a transmite mesajul m ∈ Zp , calculez c1 = g k , c2 = K · m. Mesajul cifrat este c1 c2 . 2. Decodificarea:

94

-Recepţionăm c1 c2 . Folosim cheia privată x şi calculăm K = m = c2 K −1 . Justificarea calculului pentru K din decodificare constă în următorul şir de egalităţi evidente: ck1 ,

cx1 = (g k )x = (g x )k = y k . Exemplul 6.4.2 Pentru p = 11, fie generatorul g = 6, în (Z∗11 , ·). Pentru simplificarea scrierii omitem simbolul de clasa modulo 11, înţelegând prin 6 de fapt ˆ6 ∈ Z11 . Alegem cheia privată x = 4 şi elementul arbitrar k = 3. Calculăm în Z11 : y = g x = 64 = 9,

K = y k = 93 = 3.

Anunţăm cheia publică (11, 6, 9). Codificarea: În vederea transmiterii de mesaje, calculăm c1 = g k = 63 = 7. Dacă dorim transmiterea mesajului m = 10, calculăm: c2 = K · m = 3 · 10 = 8. Transmit succesiunea de elemente din Z11 : 78. Decodificarea: Se recepţionează 78. Şiind cheia privată x = 4 (ea se furnizează celor cărora li s-a autorizat accesul), calculăm: K = cx1 = 74 = 3,

m = c2 · K −1 = 8 · 4 = 10,

deci citesc mesajul 10. Dacă dorim transmiterea unei secvenţe de elemente din Z11 , de exemplu 7925, vom codifica fiecare simbol în parte: m = 7 ⇒ c2 = K · m = 3 · 7 = 10,

95

m = 9 ⇒ c2 = 3 · 9 = 5, m = 2 ⇒ c2 = 3 · 2 = 6, m = 5 ⇒ c2 = 3 · 5 = 4. Calculez şi c1 = 7, ca mai înainte. Transmitem 710564. Cel care recepţionează ştie că primul simbol este c1 = 7, apoi restul semnifică simboluri codificate. Calculăm K = 3 şi K −1 = 4 ca mai înainte şi decodific. Din păcate pot să apară erori detectabile doar dacă mesajul decriptat va fi incoerent, după cum consider simbolurile primite ca elemente din Z11 : 10, 5, 6, 4 ⇒ 7, 9, 2, 5, caz în care am decriptat corect, fie 1, 0, 5, 6, 4 ⇒ 4, 0, 9, 2, 5, deci citesc un alt mesaj decât cel transmis. REZUMAT Ordinul unui element într-un grup este ordinul subgrupului generat de acel element. Pentru elemente de ordin finit, ordinul este egal cu cel mai mic număr natural nenul care are proprietatea că elementul, compus cu sine de acel număr de ori, are ca rezultat elementul neutru al grupului. În cazul grupurilor finite, ordinul fiecărui element este divizor al ordinului grupului. Singurul element de ordin 1 este elementul neutru. Aceste proprietăţi conduc la două rezultate celebre, Teorema lui Euler şi Mica Teoremă a lui Fermat, care au aplicaţii i�n criptografie.

96

6.5 Temă de control la finalul unităţii de învăţare M1.U6. 1. Găsiţi ordinul fiecărui element din următoarele grupuri şi precizaţi care dintre ele este grup ciclic: a) (U (Z9 ), ·); b) (U (Z15 ), ·). 2. Demonstraţi că oricum am alege două grupuri de ordin 2011 ele sunt izomorfe. 3. Demonstraţi că oricum am alege trei grupuri de ordin 4, cel puţin două dintre ele sunt izomorfe. 4. Determinaţi σ 2017 (5) pentru: ( 1 2 3 4 5 6 7 a) σ = 4 6 7 1 2 5 9 ( 1 2 3 4 5 6 7 b) σ = 3 9 5 8 7 2 1 calculând ordinul permutării σ.

8 9 3 8 8 9 6 4

) ; ) ,

Indicaţii de rezolvare a temei de control: 1) Folosim Propoziţia 6.3.2 pentru identificarea elementelor din U (Zn ), apoi Propoziţia 6.1.2 a) pentru determinarea ordinului fiecărui element. A se studia Exemplul 6.3.4. 2) Folosim faptul că 2011 este număr prim şi Propoziţiile 6.2.1, 6.2.2. 3) Descompunem permutarea în cicluri disjuncte şi folosim Observaţia 6.1.3.