Álgebra para alunos de Ciências de Computadores

´ Algebra Christian Lomp 2004 2 Sum´ario 1 Preliminares 5 1.1 L´ogica ............................... 5 1.2 Conjuntos ............................. 8 1.3 O princ´ıpio da Indu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Rela¸c˜oes.............................. 11 2 Aritm´etica 19 2.1 Divisores e m´ultiplos . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 M´aximo divisor comum . . . . . . . . . . . . . . . . . . . . . . 21 2.3 N´umeros primos e factoriza¸c˜ao . . . . . . . . . . . . . . . . . . 27 3 Aritm´etica modulo n33 3.1 Congruˆencias ........................... 33 3.2 Resolu¸c˜ao da congruˆencia linear ax ≡b(modn)......... 36 3.3 O pequeno Teorema de Fermat . . . . . . . . . . . . . . . . . 40 3.4 Sistema criptogr´afico RSA . . . . . . . . . . . . . . . . . . . . 42 3.5 Representa¸c˜ao na base n . . . . . . . . . . . . . . . . . . . . . 45 4 Permuta¸c˜oes 49 4.1 Ogruposim´etrico......................... 49 4.2 Ciclos e Transposi¸c˜oes . . . . . . . . . . . . . . . . . . . . . . 54 4.3 Permuta¸c˜oes pares e ´ımpares . . . . . . . . . . . . . . . . . . . 59 5 Mon´oides e Grupos 63 5.1 Opera¸c˜oes Bin´arias . . . . . . . . . . . . . . . . . . . . . . . . 63 5.2 Mon´oides ............................. 64 5.3 Invertibilidade em mon´oides . . . . . . . . . . . . . . . . . . . 66 5.4 Grupos............................... 67 5.5 Gruposc´ıclicos .......................... 72 5.6 Classes laterais e o Teorema de Lagrange . . . . . . . . . . . . 74 3 4SUM ´ ARIO 6 An´eis e corpos 81 6.1 An´eis................................ 81 6.2 Ideais e Teorema Fundamental do Homomorfismo . . . . . . . 84 6.3 Dom´ınios de Integridade e Corpos . . . . . . . . . . . . . . . . 87 Cap´ıtulo 1 Preliminares 1.1 L´ogica Neste curso s´o consideramos afirma¸c˜oes(proposi¸c˜oes) relativamente as quais podemos decidir se s˜ao verdadeiras ou falsos. Por exemplo a afirma¸c˜ao ”Este frase ´e falsa.” ´e uma afirma¸c˜ao inadmiss´ıvel. Sejam AeBafirma¸c˜oes. Temos as seguintes opera¸c˜oes: conjuga¸c˜ao A∧B´e verdadeira se e s´o se A´e Bs˜ao verdadeiras. disjun¸c˜ao A∨B´e verdadeira se e s´o se Aou B´e verdadeira. implica¸c˜ao A⇒B´e verdadeira se e s´o se B´e verdadeira ou A´e falsa. equivalˆencia A⇔B´e verdadeira se e s´o se AeBs˜ao ambos verdadeiras ou ambas falsas. nega¸c˜ao ¬A´e verdadeira se e s´o se A´e falsa. Podemos representar estes opera¸c˜oes por uma tabela de verdade (em rela¸c˜ao com os valores de AeB). A letra Frepresenta o valor ”falsa”e a letra Vrepresenta o valor ”verdadeira”. A B A ∧B A ∨B A ⇒B A ⇔B¬A F F F F V V V F V F V V F V V F F V F F F V V V V V V F Estes tabelas dizem-se tamb´em tabelas de verdade. Seja A(X1, . . . , Xn) uma afirma¸c˜ao que depende das vari´aveis X1, . . . , Xncujos valores ´e Fou V. A tabela de verdade de A´e uma tabela onda para toda a combina¸c˜ao de F eVpor X1, . . . , Xno valor de A(X1, . . . , Xn) ´e registado. 5 6CAP´ ITULO 1. PRELIMINARES Por exemplo: Seja A(X, Y ) a afirma¸c˜ao que ´e verdade se e s´o se X´e verdade e Y´e falso. Ent˜ao a tabela de verdade de A´e: X Y A(X, Y ) F F A(F, F) = F F V A(F, V ) = F V F A(V, F) = V V V A(V, V ) = F Duas afirma¸c˜oes A(X1, . . . , Xn) e B(X1, . . . , Xn) que dependem da algumas vari´aveis X1, . . . , Xns˜ao equivalentes se tˆem a mesma tabela de verdade. Seja A(X, Y ) a afirma¸c˜ao do exemplo anterior e seja B(X, Y ) := ¬(X⇒ Y). Ent˜ao vemos que as afirma¸c˜oes AeBs˜ao equivalentes. Escrevemos A≡B. Exerc´ıcio 1.1.1 Verifique que as duas afirma¸c˜oes (X∧(¬Y)) ∨((¬X)∧Y) e¬(X⇔Y)s˜ao equivalentes. Observa¸c˜ao 1.1.2 As seguintes afirma¸c˜oes s˜ao verdadeiras para afirma¸c˜oes A, B eC: (1) [A⇒B]≡[B∨(¬A)] (2) ¬(A∧B)≡(¬A)∨(¬B) (3) ¬(A∨B)≡(¬A)∧(¬B) (4) A∧(B∨C)≡(A∧B)∨(A∧C) (5) A∨(B∧C)≡(A∨B)∧(A∨C) (6) ¬(¬A)≡A (7) A∧B=B∧A (8) A∨B=B∨A. Demonstra¸c˜ao: Exerc´ıcio.  As equivalˆencias (2) e (3) dizem-se as leis de DeMorgan. Quantificadores Suponhamos que queremos fazer afirma¸c˜oes sobre alguns objectos/entidades. Por exemplo sobre ”os alunos da FCUP”. H´a duas maneiras de formular estas afirma¸c˜oes: 1.1. L ´ OGICA 7 •Afirma¸c˜oes que s˜ao validas para todos os objectos; por exemplo a afirma¸c˜ao ”Todos os alunos da FCUP tˆem um n´umero mecanogr´afico”. •Afirma¸c˜oes que s˜ao validas para (pelo menos) um objecto; por exemplo a afirma¸c˜ao ”Existe um aluno da FCUP que tem cabelo louro.” Na linguagem de matem´atica escrevemos ∀x:P(x) para dizer que todo o objecto xtem a propriedade P(x). E escrevemos ∃x:P(x) para dizer que existe (pelo menos) um objecto xque tem a propriedade P(x). Temos sempre de indicar a qual objectos nos referimos. Por exemplo; seja Ao conjunto das alunos da FCUP e seja P(x)= ” xtem um n´umero mecanogr´afico ”. Podemos construir a afirma¸c˜ao ∀x∈A:P(x). Observa¸c˜ao 1.1.3 A nega¸c˜ao das afirma¸c˜oes que contˆem quantificadores ´e importante. Seja P(x)uma propriedade. (1) A nega¸c˜ao da afirma¸c˜ao ”todos objectos x tˆem a propriedade P” ´e equivalente da afirma¸c˜ao ”existe (pelo menos um) objecto xque n˜ao tem a propriedade P”. Em linguagem simb´olica, escrevemos: ¬(∀x:P(x)) ≡ ∃x:¬P(x) (2) A nega¸c˜ao da afirma¸c˜ao ”existe um objecto x que tem a propriedade P” ´e equivalente da afirma¸c˜ao ”todos os objectos x n˜ao tˆem a propriedade P”. Em linguagem simb´olica, escrevemos: ¬(∃x:P(x)) ≡ ∀x:¬P(x) Em vez de ¬(∃x:P(x)) escrevemos tamb´em @x:P(x). Exemplo 1.1.4 Seja Ro conjunto dos n´umeros reais. Consideramos as seguintes afirma¸c˜oes: (1) ∀x∈R:x2>0. (2) ∃x∈R:x2>0. (3) @x∈R:x2>0. S´o a afirma¸c˜ao em (2) ´e verdadeira; as outras s˜ao falsas. 8CAP´ ITULO 1. PRELIMINARES Seja P(x, y) uma propriedade que depende de dois objectos. Por exemplo a propriedade ”x+y= 0” para x, y ∈R´e uma propriedade P(x, y) que depende de dois objectos xey. Temos: [∃x∃y:P(x, y)] ≡[∃y∃x:P(x, y)] [∀x∀y:P(x, y)] ≡[∀y∀x:P(x, y)]. Ent˜ao a ordem das quantificadores do mesmo tipo n˜ao interesse. Mas cuidado ! Geralmente a ordem das quantificadores de dois tipos diferentes ´e importante: [∀x∃y:P(x, y)] 6≡ [∃y∀x:P(x, y)] Por exemplo: seja P(x, y) = ”x+y= 0” para x, y ∈Rent˜ao a afirma¸c˜ao (∀x∈R)(∃y∈R) : x+y= 0 ´e verdadeira (para um x∈Rescolhemos y=−x). Mas a afirma¸c˜ao (∃y∈R)(∀x∈R) : x+y= 0 ´e falsa; se existe um y∈Rtal que para todo x∈R:x+y= 0 temos em particular 0+y= 0 que implica y= 0. Mas 1 = 1+0 = 1 +y= 0 ´e absurdo. O problema ´e que na frase ”para todos x existe um y tal que ...” o y pode depender de x. Ou seja para qualquer xexiste um ycom uma certa propriedade mas este ypode ser diferente para diferentes x. No entanto na frase ”existe um y tal que para todos o x ...” o y´e fixo para todos os x. 1.2 Conjuntos Um conjunto ´e uma colec¸c˜ao de alguns objectos. Os objectos de um conjunto chamam-se elementos. Escrevemos a∈Ase a´e um elemento do conjunto Aou a6∈ Ase an˜ao ´e um elemento de A. Dois conjuntos s˜ao iguais se tˆem os mesmos elementos. Por exemplo os conjuntos A={0,1,2} eB={0,0,0,1,1,2}s˜ao iguais; A=B. Escrevemos |A|para o n´umero de elementos do conjunto de A. Se A tem um n´umero infinito de elementos escrevemos |A|=∞. Nota-se | {0,0,0,1,1,2} |= 3. Exemplo 1.2.1 Temos as seguintes conjuntos conhecidos: 1.2. CONJUNTOS 9 N={0,1,2,3,···} os n´umeros naturais Z={0,±1,±2,±3,···} os inteiros Q={a b|a, b ∈Z∧b6= 0}os n´umeros racionais Ros n´umeros reais C={a+ıb |a, b ∈R}os n´umeros complexos Axioma do conjunto vazio: Existe um conjunto sem elementos. Este conjunto chama-se o conjunto vazio. Escrevemos ∅para o conjunto vazio. Sejam A e B conjuntos. Se todo o elemento de A ´e tamb´em um elemento de B digamos que A ´e um subconjunto de B e escrevemos A⊆B. Observa¸c˜ao 1.2.2 (i) Sejam AeBdois conjuntos. Temos A=Bse e s´o se A⊆BeB⊆A. (ii) O conjunto vazio ´e um subconjunto de todo o conjunto. Seja Bum conjunto e seja Puma propriedade que os elementos xde B tˆem ou n˜ao tˆem. Ent˜ao A:= {x∈B|xtem a propriedade P} ´e um subconjunto de B. Seja B=R+por exemplo igual ao conjunto dos n´umeros reais positivos e seja P(x) =00 1 x>100 a propriedade que um n´umero real xtem se 1 x>1 A:= {x∈R+|xtem a propriedade P(x)}=x∈R+|1 x>1=]0,1[. Note-se que: se B´e um conjunto e Puma propriedade tal que nenhum elemento de B tem esta propriedade, ent˜ao A:= {x∈B|xtem a propriedade P}=∅. Axioma dos conjunto das partes: Para todo o conjunto B existe um conjunto P(B) cujo elementos s˜ao os subconjuntos de B. Por exemplo para B:= {0,1,2}o conjunto das partes P(B) de B´e igual P(B) = {∅,{0},{1},{2},{0,1},{0,2},{1,2}, B}. Axioma da reuni˜ao: Para quaisquer dois conjuntos A e B existe um conjunto que consiste precisamente dos elementos de A e de B. Chama-se a reuni˜ao de A e B. Escrevemos A∪Bpara este conjunto. Dado dois conjuntos A e B definimos os seguintes conjuntos: 16 CAP´ ITULO 1. PRELIMINARES Observa¸c˜ao 1.4.23 Seja {Ai}i∈Iuma parti¸c˜ao de um conjunto n˜ao vazio Aindexada por I. Definimos a rela¸c˜ao R:= {(a, b)∈A×A| ∃i∈I:a∈Aieb∈Ai}. Ent˜ao R´e uma rela¸c˜ao da equivalˆencia. Exerc´ıcio 1.4.24 Sejam A, B eCafirma¸c˜oes. Mostre que: 1. [A⇒B]≡[(¬B)⇒(¬A)] 2. [A⇔B]≡[A⇒B∧B⇒A] 3. A∧(B∨C)≡(A∧B)∨(A∧C) 4. A∨(B∧C)≡(A∨B)∧(A∨C) 5. ¬(A∧B)≡(¬A)∨(¬B) 6. ¬(A∨B) = (¬A)∧(¬B) Sejam A, B eCconjuntos. Mostre que as seguintes igualdades s˜ao validas: (a) A∩(B∪C) = (A∩B)∪(A∩C) (b) A∪(B∩C) = (A∪B)∩(A∪C) (c) A\(B∩C) = (A\B)∪(A\C) (d) A\(B∪C) = (A\B)∩(A\C) Sejam XeYconjuntos e seja f:X→Yuma fun¸c˜ao. Sejam AeB subconjuntos de Xe sejam DeEsubconjuntos de Y. Mostre que se verifica: (a) f(A∪B) = f(A)∪f(B); (b) f(A∩B)⊆f(A)∩f(B); (c) f−1(D∩E) = f−1(D)∩f−1(E); (d) f−1(D∪E) = f−1(D)∪f−1(E); (e) A⊆f−1(f(A)) ef(f−1(f(A))) = f(A); (f) D⊇f(f−1(D)) ef−1(f(f−1(D))) = f−1(D). 1. Descreva os subconjuntos Sn∈N[1 n+1 ,1] eTn∈N[1 n+1 ,1] de R. 1.4. RELAC¸ ˜ OES 17 2. Seja A:= Ze seja An:= {3a+n|a∈Z}para qualquer n∈N. A fam´ılia {An}n∈N´e uma parti¸c˜ao de Z? Quantos subconjuntos An diferentes existem ? 3. Seja A:= R2e seja Ar:= {(x, 3x+r)∈R2|x∈R}para qualquer r∈ R. A fam´ılia {Ar}r∈R´e uma parti¸c˜ao de R2? Como pode descrever Ar geometricamente ? A fam´ılia {Ar}r∈N´e uma parti¸c˜ao de R2tamb´em? 18 CAP´ ITULO 1. PRELIMINARES Cap´ıtulo 2 Aritm´etica Neste cap´ıtulo estudamos as propriedade aritm´eticas dos inteiros Z. 2.1 Divisores e m´ultiplos Defini¸c˜ao 2.1.1 Um inteiro adivide um inteiro bse existe um inteiro qtal que b=qa. Escrevemos a|bse adivide b. O inteiro qdiz-se o quociente, o inteiro bdiz-se um m´ultiplo de aeadiz-se um divisor de b.bdiz-se divis´ıvel por a. Observa¸c˜ao 2.1.2 Sejam a,becinteiros. (1) Se a|beb|cent˜ao a|c. (2) Se a|bent˜ao −a|bea|bc para qualquer inteiro c. (3) Se a|bea|cent˜ao a|b+c. (4) Se 0|bent˜ao b= 0. (5) para qualquer inteiro atemos a|0 Demonstra¸c˜ao: Exerc´ıcio.  Relembre a ordem dos inteiros: a≤bse e s´o se b−a≥0. Observa¸c˜ao 2.1.3 Seja bum inteiro positivo. Ent˜ao todo o divisor positivo de best´a entre 1eb. Demonstra¸c˜ao: Se a > 0 e a|b. Logo existe um inteiro qtal que b=aq. Como aebs˜ao positivo, q´e positivo. Ent˜ao b−a=a(q−1) >0 ou equivalentemente b > a. 19 20 CAP´ ITULO 2. ARITM´ ETICA Corol´ario 2.1.4 Seja aum inteiro. Se a|1ent˜ao a= 1 ou a=−1. Demonstra¸c˜ao: Suponhamos que a´e positivo. Ent˜ao por 2.1.3 temos a= 1. Se a´e negativo ent˜ao −a´e positivo e pelo 2.1.3 −a= 1 ⇔a=−1.  Corol´ario 2.1.5 Sejam aebinteiros. Se a|beb|aent˜ao a=bou a=−b. Demonstra¸c˜ao: a|bimplica que existe um c∈Ztal que b=ac eb|a implica que existe um d∈Zcom a=bd. Logo temos b=ac =bdc ou seja b(1 −dc) = 0. Se b= 0 ent˜ao a= 0 por 2.1.2(4). Se b6= 0 temos 1 = dc ou seja d|1. Por Corol´ario 2.1.4 temos d=±1 e portanto a=±b.  Teorema 2.1.6 (Algoritmo da divis˜ao) Seja aum inteiro e bum n´umero positivo. Ent˜ao existe um inteiro qe um n´umero rtais que a=bq +re 0≤r < b. Em vez de uma demonstra¸c˜ao consideramos o seguinte algoritmo: Algor´ıtmo da divis˜ao INPUT:dois n´umeros positivos aeb OUTPUT:dois n´umeros positivos qertal que a=bq +re 0 ≤r < b (1) q:= 0; r:= 0; (2) while(a−qb > b)q:= q+ 1; (3) r:= a−qb; Para um inteiro anegativo podemos aplicar o algoritmo com −aebe obtemos q0er0tal que −a=bq0+r0. Se r0= 0 podemos escolher r= 0 e q=−q0. Se r06= 0 podemos escolher r:= b−r0eq=−(q0+ 1). Temos a=−(bq0+r0) = −bq0−b+b−r0=qb +r. O n´umero rdiz-se o resto eqdiz-se o quociente da divis˜ao de bpor a. Em qualquer linguagem de programa¸c˜ao existem fun¸c˜oes para calcular req. Por exemplo em C tem-se r:= b%aeq:= b/a. Exerc´ıcio 2.1.7 Calcule o resto e o quociente para os seguintes inteiros: (i) a= 2047, b = 128; (ii) a= 5251, b = 89; (iii) a=−34, b = 13 (iv) a= 4, b = 12; 2.2. M ´ AXIMO DIVISOR COMUM 21 2.2 M´aximo divisor comum Defini¸c˜ao 2.2.1 Sejam aebinteiros n˜ao simultaneamente nulos. Um inteiro cque divide aebdiz-se um divisor comum entre aeb. O maior divisor comum de aebdiz-se o m´aximo divisor comum entre aeb. Escrevemos mdc(a, b)para este inteiro positivo. Note que s´o existe um m´aximo divisor comum entre dois inteiros. Observa¸c˜ao 2.2.2 Sejam aebinteiros n˜ao simultaneamente nulos. (1) mdc(a, b) = mdc(b, a) (2) mdc(a, b) = mdc(−a, b) (3) mdc(a, 0) = |a| (4) mdc(a, b) = mdc(a, b +na)para qualquer n∈Z. Demonstra¸c˜ao: (1-3) Exerc´ıcios. (4) Todo o divisor comum entre aeb´e tamb´em um divisor comum entre ae b+na (para qualquer n∈Z) e todo o divisor comum entre aeb+na ´e um divisor comum entre e aeb. De facto, se d|aed|bent˜ao d|b+an (por 2.1.2(2+3) ) e se d|aed|b+na ent˜ao d|b+na −na, isto ´e d|b. Portanto mdc(a, b) = mdc(a, b +na).  Corol´ario 2.2.3 Sejam aebinteiros n˜ao simultaneamente nulos. Seja a= qb +rcom q, r ∈Ze0≤r < b. Ent˜ao mdc(a, b) = mdc(b, r). Demonstra¸c˜ao: Por 2.2.2(1) temos mdc(a, b) = mdc(b, a). Como r=a+ (−q)btemos por 2.2.2(4) mdc(b, a) = mdc(b, r). Logo mdc(a, b) = mdc(b, r).  O ´ultimo corol´ario ajuda calcular o m´aximo divisor comum. Por exemplo seja a= 45 e b= 18. O resto 45 por 18 ´e 9. Por o corol´ario temos mdc(45,18) = mdc(18,9). O resto de 18 por 9 ´e 0. Aplicamos o corol´ario de novo temos mdc(18,9) = mdc(9,0). Por 2.2.2(3) temos mdc(9,0) = 9. Portanto: mdc(45,18) = mdc(18,9) = mdc(9,0) = 9. O seguinte algoritmo de Euclides (325 - 265 A.D.) usa o ´ultimo corol´ario para determinar o mdc: 22 CAP´ ITULO 2. ARITM´ ETICA Algor´ıtmo de Euclides INPUT: a, b ∈N>0 OUTPUT: mdc(a, b) while (b6= 0) do {substitue ao mesmo tempo apor bebpelo resto da divis~ao de a por b.} return a Podemos implementar facilmente este algoritmo na linguagem C: int mdc(int a, int b) {int aux; while(b!=0) {aux=b; b=a%b; a=aux } return a } Exemplo 2.2.4 Sejam a= 144 eb= 81. O algoritmo trabalha da seguinte forma: a b a%b 144 81 63 144 = 1*81 + 63 (1) 81 63 18 81 = 1*63 + 18 (2) 63 18 9 63 = 3*18 + 9 (3) 18 9 0 18 = 2*9 + 0 (4) 9 0 algoritmo termina Logo mdc(144,81) = 9. Note que as equa¸c˜oes (3),(2) e (1) implicam: mdc(144,81) = 63 −3∗18 por (3) = 63 −3∗(81 −1∗63) por (2) = 4 ∗63 + (−3) ∗81 = 4 ∗(144 −1∗81) + (−3) ∗81 por (1) = 4 ∗144 + (−7) ∗81 Encontr´amos inteiros res(r= 4, s=−7) tal que mdc(144,81) = r∗144 + s∗81 Teorema 2.2.5 Sejam aebinteiros n˜ao simultaneamente nulos. Ent˜ao existem inteiros restais que mdc(a, b) = r∗a+s∗b. 2.2. M ´ AXIMO DIVISOR COMUM 23 Se aebs˜ao inteiros positivos e a=qb +rpara alguns inteiros q, r com 0≤r < b ent˜ao sabemos mdc(a, b) = mdc(b, r). Suponha que existem inteiros x, y ∈Ztal que mdc(b, r) = xb +yr ent˜ao temos: mdc(a, b) = mdc(b, r) = xb +yr =xb +y(a−qb) = ya + (x−qy)b. Isto surgiu o seguinte algoritmo recursivo: Algor´ıtmo mdc INPUT:a, b ∈Z+ex, y ∈Z OUTPUT:mdc(a, b) = xa +yb if (b! = 0){ determine qertal que a=qb +r; aux:=mdc(b,r,x,y); substitue x por y e y por x-qy; return aux; } else {x=1; y=0; return a; } Temos tamb´em a seguinte vers˜ao alargada do Algoritmo de Euclides que n˜ao usa recurs˜ao: Algor´ıtmo de Euclides(alargada) INPUT: a, b ∈N>0 OUTPUT: x, y ∈Ztal que mdc(a, b) = xa +yb Vari´aveis auxiliar: q, r, u, v, x, y ∈Z Inicializa¸c~ao: x= 1; v= 1; y= 0; u= 0; while (bn~ao nulo) do {encontre qertal que a=qb +re0≤r < b substitue simultaneamente: apor bebpor r xpor ueupor x−qu ypor vevpor y−qv } return xey 24 CAP´ ITULO 2. ARITM´ ETICA Por exemplo sejam a= 144 e b= 81. O algoritmo trabalha assim: a b x u y u 144 81 1 0 0 1 144 = 1*81 + 63 81 63 0 1 1 -1 81 = 1*63 + 18 63 18 -1 1 -1 2 63 = 3*18 + 9 18 9 -1 4 2 -7 18 = 2*9 + 0 9 0 4 -9 -7 16 algoritmo termina Podemos agora mostrar algumas propriedades importantes do m´aximo divisor comum. Teorema 2.2.6 Sejam a, b edinteiros positivos. As seguintes afirma¸c˜oes s˜ao equivalentes: (a) d= mdc(a, b). (b) d´e um divisor comum entre aebtal que todo o divisor comum positivo de aebtamb´em ´e um divisor de d. (c) d´e o menor inteiro positivo tal que existem inteiros xeytal que d=x∗a+y∗b. A caracteriza¸c˜ao (c) do mdc diz: mdc(a, b) = min{d∈Z>0| ∃x, y ∈Z:d=x∗a+y∗b} Demonstra¸c˜ao: (a)⇒(c) Seja e:= min{z∈Z>0| ∃x, y ∈Z:z= xa +yb}. Pelo Algoritmo de Euclides existem x, y ∈Ztais que d=xa +yb. Como e´e o menor inteiro com esta propriedade tem-se e≤d. Por outro lado d´e um divisor comum entre aeb. Logo temos d|ra +sb para quaisquer inteiros resed|eou seja d≤e. Portanto d=e. (c)⇒(b) Seja d:= min{z∈Z>0| ∃x, y ∈Z:z=xa +yb}e sejam xey inteiros tais que d=xa +yb. Seja cum divisor comum positivo de aeb. Logo existem restal que a=rc eb=sc. Portanto d=xa+(yb =xr+ys)c mostra que cdivide d. (b)⇒(a) Como mdc(a, b) ´e um divisor comum positivo de aebtemos por hip´otese mdc(a, b)|dou seja mdc(a, b)≤d(2.1.3). Mas mdc(a, b) ´e o m´aximo divisor comum entre aeb. Portanto tem-se mdc(a, b) = d. Em particular temos o seguinte corol´ario: Corol´ario 2.2.7 Sejam aebinteiros positivos e existem inteiros xeytais que 1 = x∗a+y∗bent˜ao mdc(a, b) = 1. 2.2. M ´ AXIMO DIVISOR COMUM 25 Dois inteiros aebcom mdc(a, b) = 1 dizem-se relativamente primos. Observa¸c˜ao 2.2.8 Para qualquer inteiros a, b ∈Z\ {0}temos a mdc(a,b)e b mdc(a,b)s˜ao relativamente primos. Demonstra¸c˜ao: De facto se um d≥1 ´e um divisor comum de a mdc(a,b)e b mdc(a,b)ent˜ao existem x, y ∈Ztal que a mdc(a,b)=xd eb mdc(a,b)=yd. Logo dmdc(a, b) ´e um divisor comum de aeb. Portanto dmdc(a, b)≤mdc(a, b) porque mdc(a, b) ´e o m´aximo divisor comum. Mas isto implica d≤1 ou seja d= 1. Ent˜ao mdc( a mdc(a,b),b mdc(a,b)) = 1.  Corol´ario 2.2.9 Sejam aebdois inteiros positivos e suponha que aebs˜ao relativamente primos. Para qualquer inteiro ctemos: se a|bc ent˜ao a|c. Demonstra¸c˜ao: Pelo algoritmo de Euclides existem inteiros xeytais que 1 = xa +yb. Logo c=xac +ybc. Se a|bc ent˜ao a|xac +ybc ⇒a|c. Dados inteiros a, b, c ∈Zqueremos encontrar todos os inteiros XeYtais que aX +bY =c. Uma equa¸c˜ao deste tipo diz-se uma equa¸c˜ao de Diofanto linear. ( Diofanto de Alexandria, matem´atico grego, vivia (cerca) entre 200-284 A.D.) Observa¸c˜ao 2.2.10 Sejam aebinteiros n˜ao simultaneamente nulos e relativamente primos (mdc(a, b) = 1). Suponha que existem inteiros XeYtais que aX +bY = 0 ent˜ao existe um inteiro ntal que X=−nb eY=na. Demonstra¸c˜ao: aX +bY = 0 ⇒aX =−bY . Se a= 0 temos b= 1 porque mdc(0, b) = 1 ⇒b= 1. Logo Y= 0 = n0 e X=−npara qualquer n∈Z. Suponha que a6= 0. Como a| −bY e mdc(a, b) = 1 temos por 2.2.9 a| −Y. Portanto existe n∈Ztal que Y=na eaX =−bY =−nab implica X=−nb. Teorema 2.2.11 Sejam aebinteiros n˜ao simultaneamente nulos. As solu¸c˜oes inteiros XeYda equa¸c˜ao aX +bY = 0 s˜ao da forma X=−nb mdc(a, b)eY=na mdc(a, b) para algum n∈Z. 32 CAP´ ITULO 2. ARITM´ ETICA Cap´ıtulo 3 Aritm´etica modulo n 3.1 Congruˆencias Defini¸c˜ao 3.1.1 Seja n∈N. Definimos a seguinte rela¸c˜ao de equivalˆencia em Z: Rn:= {(a, b)∈Z×Z|n|b−a} Se (a, b)∈Rnent˜ao dizemos que a´e congruente com bmodulo n. Escrevemos tamb´em a≡b(mod n). Dado um inteiro a∈Z. O subconjunto de Zque consiste de todos os inteiros b tais que a´e congruente com bm´odulo ndiz-se a classe de am´odulo n. [a]n:= {b∈Z|b≡a(mod n)} Exemplo 3.1.2 Seja n= 2 ea, b ∈Z. Suponha que a´e congruente com bm´odulo 2ou seja a≡b(mod 2). Por defini¸c˜ao 2|b−a. Se a´e um n´umero par ent˜ao existe um inteiro ktal que a= 2k. Tem-se 2|b−2k⇒2|b. Logo b´e um n´umero par. Se a´e ´ımpar ent˜ao existe um inteiro ktal que a= 2k+ 1. Logo 2|b−2k−1⇒2|b−1ou seja b= 2l+1 para um l∈Z. Logo b´e ´ımpar tamb´em. Portanto se a´e congruente com bm´odulo 2ent˜ao aebs˜ao ambos par ou ambos ´ımpar. No outro caso suponha que aebs˜ao dois n´umeros pares ent˜ao b−a´e par tamb´em e logo 2|b−a. Logo a´e congruente com bm´odulo 2. Se aebs˜ao ambos ´ımpar ent˜ao b−a´e par e tamb´em temos a´e congruente com bm´odulo 2. Vimos que dois inteiros a´e bs˜ao congruente m´odulo 2se e s´o se ambos s˜ao n´umeros pares ou n´umeros ´ımpares. A congruˆencia m´odulo 2divide os inteiros em duas partes : os n´umeros pares e os n´umeros ´ımpares. A classe [a]2m´odulo 2de um elemento aou ´e igual os n´umeros pares ou ´e igual os n´umeros ´ımpares. [a]2={os n´umeros pares }= [0]2[a]2={os n´umeros ´ımpares}= [1]2 33 34 CAP´ ITULO 3. ARITM´ ETICA MODULO N Observa¸c˜ao 3.1.3 Seja n∈N: 1. ∀a∈Z:a∈[a]nporque a≡a(mod n). 2. ∀a, b ∈Z:b≡a(mod n)⇔a≡b(mod n). 3. ∀a, b, c ∈Z:se a≡b(mod n)eb≡c(mod n)ent˜ao a≡c(mod n). Isto implica tamb´em: b≡c(mod n)⇔[b]n⊆[c]n. 4. Temos em particular: [a]n= [b]n⇔[a]n∩[b]n6=∅ ⇔ a≡b(mod n) (suponha que existe c∈[a]n∩[b]n. Ent˜ao [c]n⊆[a]n∩[b]n. Por (2) temos tamb´em a, b ∈[c]ne logo [a]n∪[b]n⊆[c]n⊆[a]n∩[b]n, que implica [a]n= [c]n= [b]n. Portanto [a]n∩[b]n6=∅ ⇒ [a]n= [b]n. A outra implica¸c˜ao ´e obvia.) 5. As classes {[a]n}a∈Zm´odulo nformam uma parti¸c˜ao de Z. (Pois, como todo o inteiro a∈Zpertence a [a]ntemos Sa∈Z[a]n=Z. Vimos na al´ınea anterior que [a]n= [b]nou [a]n∩[b]n=∅para qualquer a, b ∈Z.) 6. Seja a∈Z. Pelo Algoritmo da Divis˜ao existem q, r ∈Ztais que a=qn +re0≤r < n. Temos a−r=qn ou seja a≡r(mod n). Por (4) temos [a]n= [r]nou seja a classe de um inteiro am´odulo n´e igual a classe do resto da sua divis˜ao por n. 7. Para o conjunto das classes m´odulo nescrevemos: Zn:= {[a]n|a∈Z} Se n6= 0 este conjunto tem precisamente nelementos (distintos) ou seja |Zn|=n. Vimos na al´ınea anterior que, para qualquer a∈Z, existe um n´umero 0≤r < 0(o resto da divis˜ao de apor n) tal que [a]n= [r]n. Logo Zn:= {[0]n,[1]n,[2]n, . . . , [n−1]n} Exemplo 3.1.4 Seja n= 5. Qual ´e a classe de 73 m´odulo 5? Temos para um inteiro b b≡73(mod n)⇔ ∃n∈Z:b−73 = 5n ⇔ ∃n∈Z:b−14 ∗5−3 = 5n ⇔ ∃n∈Z:b−3 = 5(n+ 14) ⇔b≡3(mod5). 3.1. CONGRUˆ ENCIAS 35 Portanto as classes [73]5e[3]5s˜ao iguais e temos: [73]5= [3]5={b∈Z|o resto da divis˜ao de bpor 5´e 3}={5n+ 3 |n∈Z}. Observa¸c˜ao 3.1.5 Seja n∈Ne sejam a, a0, b, b0∈Ztais que a≡a0(mod n)e b≡b0(mod n). Temos (i) a±b≡a0±b0(mod n); (ii) a∗b≡a0∗b0(mod n); (iii) para qualquer k∈Ntem-se ak≡(a0)k(mod n). Em geral n˜ao temos a/b ≡a0/b0(mod n) se b|aeb0|a0. Por exemplo seja n= 4, a = 10, a0= 6, b = 10, b0= 2. Tem-se a= 10 ≡6 = a0(mod 4) e b= 10 ≡2 = b0(mod 4) mas n˜ao temos a/b = 1 ≡a0/b0= 3(mod 4). Defini¸c˜ao 3.1.6 Seja n∈N. Temos as seguintes opera¸c˜oes no conjunto Zn. Para qualquer [a]n,[b]n∈Zndefinimos: [a]n+ [b]n:= [a+b]ne[a]n∗[b]n= [a∗b]n Observa¸c˜ao 3.1.7 1. As opera¸c˜oes +e∗s˜ao independente das escolha do representante dos elementos [a]n. 2. As opera¸c˜oes +e∗s˜ao comutativas [a]n+ [b]n= [b]n+ [a]ne[a]n∗[b]n= [b]n∗[a]n e distributiva relativamente + [a]n∗([b]n+ [c]n) = ([a]n∗[b]n) + ([a]n∗[c]n). A aritm´etica modular tem alguns aplica¸c˜oes ´uteis: Observa¸c˜ao 3.1.8 A aritm´etica modular pode ser usado para verificar que um n´umero ´e divis´ıvel por 9. Seja a∈Z+. Podemos representar ana forma: a=an10n+an−110n−1+···+a2102+a110 + a0 para a0, a1, . . . , an∈ {0,1, . . . , 9}ean6= 0. Tem-se 10 ≡1(mod 9) e logo 10k≡(1)k(mod 9) = 1(mod 9). Portanto 9|a ⇔a≡0(mod 9) ⇔an10n+ +an−110n−1+···+a2102+a110 + a0≡0(mod 9) ⇔an+an−1+···+a2+a1+a0≡0(mod 9) 36 CAP´ ITULO 3. ARITM´ ETICA MODULO N Por exemplo os n´umeros a= 1233 ea= 123456789 s˜ao divis´ıveis por 9. Observa¸c˜ao 3.1.9 A aritm´etica modular ajuda tamb´em a reduzir potˆencias. Suponhamos que queremos decidir se o n´umero 109+ 1 ´e divis´ıvel por 19. Temos: 10 ≡(−9)(mod 19) e logo 102≡(−9)2(mod 19) = 81(mod 19) = 5(mod 19). Continuando assim obtemos: 104≡(102)2(mod 19) = 52(mod 19) = 6(mod 19) 108≡(104)2(mod 19) = 62(mod 19) = (−2)(mod 19) 109≡10 ∗(10)8(mod 19) = (−20)(mod 19) = (−1)(mod 19) 109+ 1 ≡(−1) + 1(mod 19) = 0(mod 19) Portanto 19 |109+ 1. 3.2 Resolu¸c˜ao da congruˆencia linear ax ≡b(modn) Em vez da equa¸c˜ao linear aX =bcom inteiros aebpodemos tamb´em estudar solu¸c˜oes da congruˆencia linear aX ≡b(mod n). Observa¸c˜ao 3.2.1 As opera¸c˜oes +e∗tˆem um elemento neutro. Temos [a]n+ [0]n= [a+ 0]n= [a]n= [0 + a]n= [0]n+ [a]n [a]n∗[1]n= [a∗1]n= [a]n= [1 ∗a]n= [1]n∗[a]n Defini¸c˜ao 3.2.2 Um elemento [a]n∈Zn\{[0]n}diz-se invert´ıvel se existe um elemento [b]n∈Zntal que [a]n∗[b]n= [1]n O elemento [b]ndiz-se o inverso multiplicativo de [a]n. Nota¸c˜ao [a]−1 n:= [b]n. Um inteiro a∈Zdiz-se invert´ıvel m´odulo nse [a]n´e invert´ıvel em Zn. Exemplo 3.2.3 Seja n= 10 temos [3]10 ∗[7]10 = [21]10 = [1]10. Portanto [3]10 ´e invert´ıvel e 3´e invert´ıvel m´odulo 10. Uma solu¸c˜ao da congruˆencia linear aX ≡b(mod n) ´e equivalente a equa¸c˜ao [a]n[X]n= [b]n. Se [a]n´e invert´ıvel podemos multiplicar com [a]−1 ne obtemos [X]n= [b]n[a]−1 n. Teorema 3.2.4 Seja n > 1ea∈Z. As seguintes afirma¸c˜oes s˜ao equivalentes: 3.2. RESOLUC¸ ˜ AO DA CONGRU ˆ ENCIA LINEAR AX ≡B(MODN) 37 (a) a classe [a]n´e invert´ıvel; (b) mdc(a, n) = 1 (ou seja aens˜ao relativamente primos); (c) a congruˆencia aX ≡1(mod n)tem uma solu¸c˜ao. Demonstra¸c˜ao: (a)⇒(b).Suponha que [a]n´e invert´ıvel. Ent˜ao existe um x∈Z tal que [1]n= [a]n∗[x]n= [ax]n. Ent˜ao existe um y∈Ztal que 1 −ax =yn ⇔ 1 = ax +ny. Por 2.2.7 mdc(a, n) = 1. (b)⇒(c) Suponha que mdc(a, n) = 1 ent˜ao por 2.2.9 existem inteiros X, Y tais que 1 = aX +nY ou seja n|1−aX. Ent˜ao aX ≡1(mod n) tem uma solu¸c˜ao. (c)⇒(a) Seja Xa solu¸c˜ao de aX ≡1(mod n) ent˜ao [a]n∗[X]n[aX]n= [1]n implica [a]ninvert´ıvel.  Corol´ario 3.2.5 Seja pum n´umero primo. Todo o elemento [a]p∈Zp\{[0]p}´e invert´ıvel. Teorema 3.2.6 Seja num inteiro positivo. A congruˆencia linear aX ≡b(mod n) tem uma solu¸c˜ao se e s´o se mdc(a, n)|b. Neste caso as solu¸c˜oes s˜ao da forma: X≡rb +nk mdc(a, n)(mod n)onde k∈ {0,1, . . . , mdc(a, n)−1} er∈Ztal que mdc(a, n) = ra +sn para algum s∈Z. Demonstra¸c˜ao: Sejam aeb∈Ze seja n≥1. Temos aX ≡b(mod n)⇔n|b−aX ⇔ ∃Y∈Z:aX +nY =b. A ultima equa¸c˜ao ´e uma equa¸c˜ao de Diofanto linear. Por 2.2.12 esta equa¸c˜ao tem uma solu¸c˜ao se e s´o se mdc(a, n)|b. Portanto aX ≡b(mod n) tem uma solu¸c˜ao se e s´o se mdc(a, n)|n. Teorema 2.2.12 diz tamb´em que neste caso as solu¸c˜oes s˜ao da forma: X=rb +nk mdc(a, n)para k∈Zer, s ∈Ztal que mdc(a, n) = ra +sn. Dois solu¸c˜oes rb+nk mdc(a,n)erb+nk0 mdc(a,n)s˜ao congruente m´odulo nse e s´o se n|rb +nk mdc(a, n)−rb +nk0 mdc(a, n)=n(k0−k) mdc(a, n)⇔mdc(a, n)|(k0−k). Portanto as solu¸c˜oes m´odulo ns˜ao da forma X≡rb +nk mdc(a, n)(mod n) onde k∈ {0,1, . . . , mdc(a, n)−1}.  38 CAP´ ITULO 3. ARITM´ ETICA MODULO N Exemplo 3.2.7 Queremos encontrar todos as solu¸c˜oes da congruˆencia linear 15X≡ 66(mod 9). O m´aximo divisor comum entre 15 e9´e 3 = mdc(15,9) = 2 ∗15 + (−3) ∗9. Logo r= 2 e as solu¸c˜oes s˜ao da forma: X≡2∗66 −9k 3(mod 9) = 44 −3k(mod 9) = 8 −3k(mod 9) para k∈ {0,1,2}. Portanto X≡8(mod 9) ou X≡5(mod 9) ou X≡2(mod 9) s˜ao todos as solu¸c˜oes. Observa¸c˜ao 3.2.8 (i) Se a congruˆencia aX ≡b(mod n)tem uma solu¸c˜ao ent˜ao qualquer inteiro X=rb mdc(a, n)+n mdc(a, n)kpara k∈Z ´e uma solu¸c˜ao. (ii) Se mdc(a, n) = 1 ent˜ao s´o h´a uma solu¸c˜ao X≡rb(mod n)m´odulo n. (iii) As solu¸c˜oes da congruˆencia aX ≡0(mod n)s˜ao da forma X≡n mdc(a, n)k(mod n)para k∈ {0,1, . . . , mdc(a, n)−1} (iv) Seja c∈Zec6= 0. Ent˜ao as congruˆencias acX ≡bc(mod nc)eaX ≡b(mod n) tˆem as mesmas solu¸c˜oes. Tem-se: acX ≡bc(mod nc)⇔nc |(b−aX)c⇔n|b−aX ⇔aX ≡b(mod n). Por exemplo: 15X≡12(mod 21) ⇔5X≡4(mod 7) ⇔X≡5(mod 7). (v) Suponha que mdc(a, n)|bent˜ao aX ≡b(mod n)⇔a mdc(a, n)X≡b mdc(a, n)mod n mdc(a, n). Como mdc a mdc(a,n),n mdc(a,n)= 1,a mdc(a,n)´e invert´ıvel m´odulo n mdc(a,n). Logo existe um r∈Ztal que ra mdc(a,n)≡1(mod n mdc(a,n)). Portanto aX ≡b(mod n)⇔X≡rb mdc(a, n)mod n mdc(a, n). 3.2. RESOLUC¸ ˜ AO DA CONGRU ˆ ENCIA LINEAR AX ≡B(MODN) 39 Teorema 3.2.9 (Teorema chinˆes do resto) Dados inteiros positivos n1, . . . , nk e inteiros a1, . . . , ak. Se mdc(ni, nj) = 1 para i6=jent˜ao o sistema das congruˆencias lineares X≡ai(mod ni)para i= 1, . . . , k tem uma ´unica solu¸c˜ao m´odulo n1n2···nk Demonstra¸c˜ao: Suponha que mdc(ni, nj) = 1 para i6=j. Para qualquer i∈ {1,2, . . . , k}seja ˆni:= Y j6=i nj:= n1···ni−1ni+1 ···nk. Temos mdc(ni,ˆni) = 1. Logo pelo Algoritmo de Euclides existem inteiros ri, si∈Z tal que 1 = rini+siˆni Tem-se ai=aisiˆni+airiniou seja aisiˆni≡ai(mod ni). Temos tamb´em aisiˆni≡0(mod nj) para qualquer j6=i Seja X:= Pk i=1 aisiˆni:= a1s1ˆn1+···akskˆnk.Ent˜ao X≡aisiˆni(mod ni)≡ai(mod ni) para qualquer i∈ {1, . . . , k}. Logo X´e uma solu¸c˜ao. Suponha que X´e Ys˜ao solu¸c˜oes. Ent˜ao X−Y≡0(mod ni) para qualquer iou seja ni|X−Y. Como mdc(ni, nj) = 1 temos n1···nk|X−YeX≡ Y(mod n1···nk).  Exemplo 3.2.10 Seja k= 3. Consideramos o sistema: (1) X≡3(mod 5) (2) X≡6(mod 7) (3) X≡4(mod 6) Pela equa¸c˜ao (1) uma solu¸c˜ao Xdeste sistema tem ser igual X= 3 + 5Ypara um inteiro Y. Substitu´ımos Xpor 3+5Yna equa¸c˜ao (2) obtemos: X≡6(mod 7) ⇔3+5Y≡6(mod 7) ⇔5Y≡3(mod 7). 40 CAP´ ITULO 3. ARITM´ ETICA MODULO N Como mdc(5,7) = 1 |3pelo Teorema 3.2.6 a solu¸c˜ao para Y´e Y≡3r(mod 7) onde r´e um inteiro tal que existe um s∈Ze1 = mdc(5,7) = 5r+ 7s. Neste caso podemos escolher r= (−4) (e s= 3). Portanto Y= (−4) ∗3+7Z=−12 + 7Z para um Z∈Ze X= 3 + 5Y= 3 + 5(−12 + 7Z) = −57 + 35Z. Substitu´ımos Xpor −57 + 35Zna equa¸c˜ao (3) temos X≡4(mod 6) ⇔ −57 + 35Z≡4(mod 6) ⇔35Z≡61(mod 6) ⇔5Z≡1(mod 6) Como mdc(5,6) = 1 |1pelo Teorema 3.2.6 a solu¸c˜ao para Z´e Z≡t(mod 6) onde t´e um inteiro tal que existe um u∈Ze1 = mdc(5,6) = 5t+ 6u. Neste caso podemos escolher t=−1(e u= 1). Portanto Z=−1+6W para um W∈Z. Logo X=−57 + 35Z=−57 + 35(−1+6W) = −92 + 210W. Como 118 ≡ −92(mod 210) X≡118(mod 210) ´e a (´unica) solu¸c˜ao do sistema. 3.3 O pequeno Teorema de Fermat O seguinte teorema ´e muito importante e a funda¸c˜ao do sistema criptogr´afico RSA. Teorema 3.3.1 (Pequeno Teorema de Fermat) Seja pum n´umero primo. Para qualquer inteiro a∈Zse mdc(a, p) = 1 ent˜ao ap−1≡1(mod p). Em particular tem-se ap≡a(mod p)para qualquer a∈Z. 3.3. O PEQUENO TEOREMA DE FERMAT 41 Demonstra¸c˜ao: Seja Zp:= {[0]p,[1]p, . . . , [p−1]p}o conjunto das classes m´odulo p. Se a∈Z´e um inteiro tal que mdc(a, p) = 1 temos em particular p-aou seja [a]p6= [0]p. Pelo Corol´ario 3.2.5 sabemos que [a]p´e invert´ıvel em Zp. Ent˜ao existe um b∈Ztal que [a]p∗[b]p= [1]P. Escrevemos [a]−1 p:= [b]p. Consideramos a fun¸c˜ao f:Zp−→ Zptal que [x]p7→ [x]p∗[a]p Como [a]p´e invert´ıvel a fun¸c˜ao ftem um inverso f−1:Zp−→ Zptal que [x]p7→ [x]p∗[a]−1 p Pois temos f−1(f([x]p)) = f−1([x]p∗[a]p) = [x]p∗[a]p∗[a]−1 p= [x]p∗[1]p= [x]p e temos tamb´em ff−1([x]p)= [x]p. Portanto a imagem de f´e igual Zp(para qualquer [x]ptemos f([x]p[a]−1 p) = [x]p). Im(f) = {[x]p∗[a]p|x∈ {0,1, . . . , p −1}} ={[0]p,[a]p,[2a]p, . . . , [(p−1)a]p} =Zp ={[0]p,[1]p,[2]p, . . . , [p−1]p} Portanto o produto de todos os elementos em Im(f)\{[0]p}´e igual ao produto de todos os elementos em Zp\{[0]p}. [a]p∗[2a]p∗···∗[(p−1) ∗a]p= [1]p∗[2]p∗···∗[p−1]p Note-se que o produto tem p−1 factores. Ent˜ao temos (?) [ap−1(p−1)!]p= [(p−1)!]p Note-se que p-(p−1)! (pois, se p|(p−1)! ent˜ao p|xcom 1 ≤x≤p−1 que ´e imposs´ıvel.) Ent˜ao pelo 3.2.5 [(p−1)!]p´e invert´ıvel e logo existe um elemento [(p−1)!]−1 p∈Zptal que [(p−1)!]p∗[(p−1)]−1 p= [1]p. Multiplicamos a equa¸c˜ao (?) com [(p−1)!]−1 pobtemos [ap−1]p= [1]p ou seja ap−1≡1(mod p). Se mdc(a, p) = 1 temos ap−1≡1(mod p). Multiplicamos com aobtemos ap≡a(mod p). Se mdc(a, p)6= 1 ent˜ao p|a⇒a≡0(mod p)⇒ap≡a(mod p).  Precisamos a seguinte observa¸c˜ao: Observa¸c˜ao 3.3.2 Sejam aebdois inteiros e seja cum m´ultiplo comum de a eb. Ent˜ao mmc(a, b)|c. Em particular se aebs˜ao relativamente primo, i.e. mdc(a, b) = 1 ent˜ao ab |c. 48 CAP´ ITULO 3. ARITM´ ETICA MODULO N Cap´ıtulo 4 Permuta¸c˜oes 4.1 O grupo sim´etrico Sejam XeYconjuntos n˜ao vazios. Defini¸c˜ao 4.1.1 Uma fun¸c˜ao f:X→Ydiz-se •injectiva se x16=x2implica f(x1)6=f(x2)para todo x1, x2∈X; •sobrejectiva se, para todo y∈Yexiste um x∈Xtal que f(x) = y; •bijectiva se f´e injectiva e sobrejectiva. A fun¸c˜ao idX:X→Xcom idX(x) = xpara todo x∈X´e uma fun¸c˜ao bijectiva e diz-se a identidade em X. Observa¸c˜ao 4.1.2 Uma fun¸c˜ao f:X→Y´e bijectiva se e s´o se existe uma fun¸c˜ao inversa g:Y→Xou seja uma fun¸c˜ao gtal que g(f(x)) = xef(g(y)) = y para todo x∈Xey∈Y. Nota¸c˜ao: f−1:= g. Se ftem um inverso ent˜ao para qualquer y∈Yexiste um x∈X(x:= g(y)) tal que f(x) = y. Logo f´e sobrejectiva. Se x1ex2s˜ao elementos de Xent˜ao f(x1) = f(x2)implica x1=g(f(x1)) = g(f(x2)) = x2. Portanto f´e injectiva e logo bijectiva. Reciprocamente, se f´e bijectiva ent˜ao a correspondˆencia g:Y→Xda forma g(y) := xse e s´o se f(x) = y´e uma fun¸c˜ao. Uma vez que para todo o yexiste um x∈Xtal que f(x) = y(pois f´e sobrejectiva) e existe um s´o x∈Xcom esta propriedade (pois f´e injectiva). Por defini¸c˜ao g´e o inverso de f. Seja f:X→Yuma fun¸c˜ao bijectiva. Tem-se f◦f−1=idYef−1◦f=idX. 49 50 CAP´ ITULO 4. PERMUTAC¸ ˜ OES Defini¸c˜ao 4.1.3 Uma fun¸c˜ao f:X→Ybijectiva diz-se tamb´em bijec¸c˜ao. Se existe uma bijec¸c˜ao entre dois conjuntos XeYescrevemos X≃Y. Se X=Y uma bijec¸c˜ao f:X→Xdiz-se permuta¸c˜ao. Denote-se por SXo conjunto de todas as permuta¸c˜oes de X, isto ´e SX:= {f:X→X|f´e bijectiva }. SXdiz-se o grupo sim´etrico de X. Observa¸c˜ao 4.1.4 A composi¸c˜ao de duas permuta¸c˜oes ´e uma permuta¸c˜ao. Pois, se f, g ∈SXent˜ao f◦g:X→Xcom f◦g(x) := f(g(x)) ´e uma fun¸c˜ao. f◦g´e bijectiva porque tem um inverso que ´e a fun¸c˜ao g−1◦f−1. Tem-se (f◦g)((g−1◦f−1)(x)) = f(g(g−1(f−1(x)))) = f(f−1(x)) = xe (g−1◦f−1)((f◦g)(x)) = g−1(f−1(f(g(x)))) = g(g−1(x)) = x∀x∈X. Suponha que existe uma bijec¸c˜ao ϕ:X→Yentre dois conjuntos XeY. Ent˜ao existe tamb´em uma bijec¸c˜ao entre os grupos sim´etricos SXeSY. Observa¸c˜ao 4.1.5 Sejam XeYdois conjuntos n˜ao vazios. Suponha que existe uma bijec¸c˜ao ϕ:X→Y. Ent˜ao a fun¸c˜ao ϕ:SX→SYf7→ ϕ◦f◦ϕ−1 ´e uma bijec¸c˜ao entre SXeSY. (Note-se ϕ(f)(y) := ϕ(f(ϕ−1(y)))) Demonstra¸c˜ao: A fun¸c˜ao ϕtem um inverso. Temos: Y−→ X−→ X−→ Y y7→ ϕ−1(y)7→ f(ϕ−1(y)) 7→ ϕ(f(ϕ−1(y))) = ϕ(f)(y) Seja ψ:SY→SXdefinido por ψ(g):=ϕ−1◦g◦ϕpara qualquer g∈SY. Logo: ψϕ(f) = ψϕ◦f◦ϕ−1=ϕ−1◦ϕ◦f◦ϕ−1◦ϕ=f e ϕψ(g) = ϕϕ−1◦g◦ϕ=ϕ◦ϕ−1◦g◦ϕ◦ϕ−1=g. Portanto ψ=: ϕ−1´e o inverso de ϕ. Queremos estudar o grupo sim´etrico de um conjunto finito X. 4.1. O GRUPO SIM´ ETRICO 51 Observa¸c˜ao 4.1.6 Seja Xum conjunto com nelementos (n≥1). Ent˜ao existe uma bijec¸c˜ao entre Xe o subconjunto {1,2, . . . , n}de N. Em particular SX≃ S{1,2,...,n}. Demonstra¸c˜ao: Exerc´ıcio.  Estamos particularmente interessados no caso de Xser um conjunto finito de ordem n(n≥1). Pela observa¸c˜ao anterior podemos supor que X:= {1,2, . . . , n}. Denotamos SXpor Sn. Sn:= {f:{1,2, . . . , n} −→ {1,2, . . . , n} | f´e bijectiva }. Sndiz-se o grupo sim´etrico de grau n. A composi¸c˜ao ◦´e uma opera¸c˜ao bin´aria em Sne a identidade id em {1,2, . . . , n}´e o elemento neutro, i.e. f◦id = f=id ◦fpara todo f∈Sn. Seja f∈SX, denota-se f0:= id fk:= f◦f◦···◦f | {z } kvezes para k≥1 Denota-se ainda f−k:= (f−1)kpara k≥1. Observa¸c˜ao 4.1.7 Seja f∈SX. Para todos m, n ∈Z: fm◦fn=fm+ne(fm)n=fm·n. Sendo f∈Sn´e usual representar fatrav´es de uma matriz 2 ×n, da seguinte maneira: f=1 2 ··· n f(1) f(2) ··· f(n) Tem-se na primeira linha os elementos de {1,2, . . . , n}e abaixo de cada 1 ≤ i≤ntem-se a sua imagem f(i). Exemplo 4.1.8 S´o existe uma fun¸c˜ao {1} → {1}, a identidade. Logo S1={id}. Podemos escrever em vez de id :1 1. Existem quatro fun¸c˜oes f:{1,2}→{1,2}mas s´o dois bijec¸c˜oes: a identidade e a fun¸c˜ao que troca 1e2, i.e. f(1) = 2 ef(2) = 1. Logo S2={id, f}. Podemos representar fna forma: f=1 2 2 1 . 52 CAP´ ITULO 4. PERMUTAC¸ ˜ OES Existem 27 fun¸c˜oes f:{1,2,3}→{1,2,3}mas existem s´o seis bijec¸c˜oes: id =123 123f1=1 2 3 1 3 2 f2=1 2 3 2 1 3  f3=123 321f4=1 2 3 3 1 2 f5=1 2 3 2 3 1  Logo S3={id, f1, f2, f3, f4, f5}. A composi¸c˜ao de dois permuta¸c˜oes em Sn´e tamb´em uma permuta¸c˜ao. Por exemplo a composi¸c˜ao de f3ef5: Tem-se f3◦f5(1) = f3(f5(1)) = f3(2) = 2 f3◦f5(2) = f3(f5(2)) = f3(3) = 1 f3◦f5(3) = f3(f5(3)) = f3(1) = 3 Logo f3◦f5=123 3211 2 3 2 3 1 =123 213=f2. Para a composi¸c˜ao f5◦f3tem-se: f5◦f3(1) = f5(f3(1)) = f3(3) = 1 f5◦f3(2) = f5(f3(2)) = f3(2) = 3 f5◦f3(3) = f5(f3(3)) = f3(1) = 2 Logo f5◦f3=123 231123 321=1 2 3 1 3 2 =f1. Note-se que f3◦f5=f26=f1=f5◦f3 Para calcular o inverso de uma permuta¸c˜ao temos trocar as linhas. Por exemplo f5=123 231e f−1 5=231 123=1 2 3 3 1 2 =f4. Teorema 4.1.9 Seja n≥1. O grupo sim´etrico Snde grau ntem n!elementos. Demonstra¸c˜ao: Seja f∈Sn. Temos npossibilidades para a imagem f(1), n−1 possibilidades para f(2), n−2 possibilidades para f(3), . . ., 2 possibilidades para f(n−1) e uma possibilidades para f(n). Logo f´e uma das n(n−1)(n−2)·····2·1 = n! bijec¸c˜oes poss´ıveis. Portanto |Sn|=n!.  Teorema 4.1.10 Seja n≥1. Para toda a permuta¸c˜ao f∈Snexiste um k∈N tal que fk=id. 4.1. O GRUPO SIM´ ETRICO 53 Demonstra¸c˜ao: Consideramos o subconjunto P:= {fk|k≥1} ⊆ Sn. Como Sn ´e um conjunto finito (s´o tem n! elementos) o subconjunto P´e um conjunto finito tamb´em. Portanto nem todas as potˆencias fks˜ao distintas. Portanto existem n´umeros n>mtal que fn=fme fn=fm⇔fn◦f−m=fm◦f−m⇔fn−m=id. Logo existe um k≥1 (aqui k=n−m) tal que fk=id. Defini¸c˜ao 4.1.11 A ordem de f∈Sn´e o menor inteiro positivo k≥1tal que fk=id. A ordem da identidade ´e igual 1. Exemplo 4.1.12 Seja n= 3 ef:= 1 2 3 1 3 2 ∈S3. f6=id f2=123 1321 2 3 1 3 2 =123 123=id. Logo ftem ordem 2. Seja f:= 123 312∈S3. f6=id f2=123 3121 2 3 3 1 2 =123 2316=id f3=123 3121 2 3 2 3 1 =123 123=id Logo ftem ordem 3. Observa¸c˜ao 4.1.13 Seja n≥1ef∈Sn. Seja ka ordem de f. 1. Tem-se f−1=fk−1, pois fk=id implica fk−1=fk◦f−1=f−1. 2. Suponha que fl=id para um inteiro l≥1. Ent˜ao k|l, pois fl=id implica l≥kcomo ke o menor inteiro positivo tal que fk=id. Pelo algoritmo da divis˜ao existem inteiros qertais que l=qk +re0≥r < k. Tem-se id =fl=fqk ◦fr=fkq◦fr= (id)q◦fr=fr. Como k´e o menor inteiro positivo com a propriedade fk=id e como r < k tem-se r= 0. Portanto l=qk ou seja k|l. 54 CAP´ ITULO 4. PERMUTAC¸ ˜ OES 4.2 Ciclos e Transposi¸c˜oes Defini¸c˜ao 4.2.1 Seja f∈Sn. Definimos os elementos fixos fix(f):={i∈ {1,2, . . . , n} | f(i) = i} eo suporte de f sup(f):={i∈ {1,2, . . . , n} | f(i)6=i} Obviamente temos fixf={1,2, . . . , n}\supf. Note-se que supf=∅se e s´o se f=id. Exemplo 4.2.2 Seja f=1 2 3 4 2 3 1 4 ent˜ao sup(f) = {1,2,3}efix(f) = {4}. Note-se que f−1=1 2 3 4 3 1 2 4 esup(f−1) = sup(f)efix(f−1) = fix(f). Observa¸c˜ao 4.2.3 Seja f∈Sn. Tem-se sup(f−1) = sup(f). Tamb´em tem-se i∈sup(f)se e s´o se f(i)∈sup(f)para todo 1≤i≤n. Demonstra¸c˜ao: Seja i∈fix(f). Ent˜ao f(i) = i⇒f(f(i)) = f(i). Logo f(i)∈ fix(f). Se f(i)∈fix(f) ent˜ao f(f(i)) = f(i)⇒f−1(f(f(i))) = f−1(f(i)) ⇔ f(i) = i. Portanto i∈sup(f)⇔i6∈ fix(f)⇔f(i)6∈ fix(f)⇔f(i)∈sup(f). Seja i∈fix(f), i.e i=f(i) ent˜ao f−1(i) = f−1(f(i)) = iimplica i∈fix(f−1). Seja i∈fix(f−1) , i.e. f−1(i) = i. Ent˜ao i=f(f−1(i)) = f(i) implica i∈fix(f). Logo sup(f) = sup(f−1).  Defini¸c˜ao 4.2.4 Seja m≥2. Uma permuta¸c˜ao f∈Sndiz-se m-ciclo se se puder ordenar o suporte de fsup(f) = {a1, a2, . . . , am}com ai6=aj∀i6=j, de forma que f(ai) = ai+1 (∀i∈ {1, . . . , m −1})ef(am) = a1 Escrevemos f= (a1a2···am)para um m-ciclo f. Um 2-ciclo diz-se uma transposi¸c˜ao. identidade um 1-ciclo. Note-se que a nota¸c˜ao f= (a1···am) ´e amb´ıgua. Para ser precisa, ´e necess´ario indicar o grupo Snao qual fpertence. Exemplo 4.2.5 Seja f=1 2 3 4 3 1 2 4 ∈S4ent˜ao sup(f) = {1,2,3}. Podemos ordenar o suporte da forma sup(f) = {1,3,2}ou seja sup(f) = {a1, a2, a3} com a1= 1,a2= 3 ea3= 2, pois temos f(a1) = a2, f(a2) = a3ef(a3) = a1. Logo f´e um 3-ciclo f= (132). 4.2. CICLOS E TRANSPOSIC¸ ˜ OES 55 Note-se que f−1=1 2 3 4 2 3 1 4 ´e tamb´em um 3-ciclo. O suporte sup(f−1) = sup(f) = {1,3,2}pode ser ordenado da forma sup(f−1) = {1,2,3}. Temos f−1(1) = 2, f−1(2) = 3, f−1(3) = 1. Logo f−1= (123). Seja g=1 2 3 4 2 1 4 3 . O suporte sup(g) = {1,2,3,4}n˜ao pode ser ordenado da forma sup(g) = {a1, a2, a3, a4}tal que g(ai) = ai+1 para i= 1,2,3e g(a4) = a1. Por exemplo come¸camos com a1= 1 tem-se g(1) = 2 eg(2) = 1. Portanto temos um 2-ciclo (12) ”dentro” g. N˜ao ´e dif´ıcil de ver que g= (12)(34). Como ciclos s˜ao permuta¸c˜oes, a composi¸c˜ao de ciclos ´e definido. Mas em geral o produto de dois ciclos n˜ao ´e um ciclo. Por exemplo (12)(34) = 1 2 3 4 2 1 3 4 1 2 3 4 1 2 4 3 =1 2 3 4 2 1 4 3 =g. O produto dos ciclos (23)(543) ´e igual (23)(543) = 12345 1324512345 12534=12345 13524= (2354). Observa¸c˜ao 4.2.6 Seja f= (a1···am)∈Snum m-ciclo. Ent˜ao f−1´e um mciclo tamb´em e tem-se f−1= (amam−1···a2a1) Demonstra¸c˜ao: Tem-se f(ai) = ai+1 para 1 ≤i < m ef(am) = a1. Logo f−1(ai+1) = f−1(f(ai)) = aipara 1 ≤i<mef−1(a)=f−1(f(am)) mostra que o suporte sup(f−1) = sup(f) = {am, am−1, . . . , a1}pode ser ordenado na forma querida. Logo f=(amam−1···a1) ´e um m-ciclo.  Note-se que os m-ciclos (a1a2···am) e (ama1···am−1) s˜ao iguais. Logo o inverso (231) do ciclo (132) ´e igual o ciclo (123). Teorema 4.2.7 A ordem de um m-ciclo ´e m. Demonstra¸c˜ao: Seja f= (a1···am) um m-ciclo. Seja 1 ≤k < m. Tem-se fk(a1) = fk−1(a2) = fk−2(a3) = ··· =f2(ak−1) = f(ak) = ak+1. Ent˜ao fk(a1) = ak+1 6=a1mostra que a ordem de f´e ≥m. Temos fm(a1) = f(fm−1(a1)) = f(am−1+1) = f(am) = a1. Para qualquer 1 < i ≤mtem-se fm(ai) = fm(fi−1(a1)) = fi−1(fm(a1)) = fi−1(a1) = ai. Portanto m´e a ordem de f. 56 CAP´ ITULO 4. PERMUTAC¸ ˜ OES Exemplo 4.2.8 Seja f=123456 352641∈S6. Podemos ordenar o suporte sup(f) = {1,2,3,4,5,6}={1,3,2,5,4,6}tal que f(1) = 3, f(3) = 2, f(2) = 5, f(5) = 4, f(4) = 6 ef(6) = 1. Logo f= (132546) ´e um 6-ciclo. Portanto a ordem de f´e 6. Defini¸c˜ao 4.2.9 Dois permuta¸c˜oes fegde Sndizem-se disjuntas se sup(f)∩ sup(g) = ∅. Observa¸c˜ao 4.2.10 Sejam f, g ∈Snpermuta¸c˜oes disjuntas ent˜ao f◦g=g◦f. Demonstra¸c˜ao: Tem-se {1,2, . . . , n}= sup(f)∪sup(g)∪(fix(f)∩fix(g)) como conjuntos disjuntos. Para todo i∈fix(f)∩fix(g) temos f(g(i)) = f(i) = i=g(i) = g(f(i)). Para todo i∈sup(f) temos i∈fix(g) e logo f(g(i)) = f(i) = g(f(i)) (ver 4.2.3). Analogamente temos para todo i∈sup(g) tamb´em f(g(i)) = g(i) = g(f(i)). Portanto f◦g=g◦f. Digamos tamb´em que as permuta¸c˜oes fegcomutam se f◦g=g◦f. Teorema 4.2.11 Seja fegdois permuta¸c˜oes disjuntas de Sn. A ordem da composi¸c˜ao f◦g´e o m´ınimo m´ultiplo comum das ordens de fe de g: ord(f◦g) = mmc(ord(f),ord(g)). Demonstra¸c˜ao: Seja k= mmc(ord(f),ord(g)). Como fegs˜ao disjuntas temos f◦g=g◦fe (f◦g)k= (f◦g)◦···◦(f◦g) | {z } k−vezes =fk◦gk=ford(f)q◦gord(g)p=id onde q=k/ord(f) e p=k/ord(g). Logo m:= ord(f◦g)≤k. Tem-se id = (f◦g)m=fm◦gmimplica fm=g−me sup(fm) = sup(g−m) = sup(gm). Como fix(g)⊆fix(gm) temos sup(g)⊇sup(gm). Logo sup(fm) = sup(gm)⊆sup(f)∩sup(g) = ∅ implica sup(fm) = ∅= sup(gm) ou seja fm=id =gm. Portanto ord(f)|me ord(g)|mimplica k= mmc(ord(f),ord(g)) ≤m. Logo m=k. Teorema 4.2.12 Toda a permuta¸c˜ao de Sn´e um produto de ciclos disjuntos. Al´em disso, o produto ´e ´unico a menos da permuta¸c˜ao identidade e da ordem dos factores. 4.2. CICLOS E TRANSPOSIC¸ ˜ OES 57 Demonstra¸c˜ao: Seja f∈Sn. Definimos uma rela¸c˜ao de equivalˆencia no conjunto {1,2, . . . , n}por i∼jse e s´o se j=fk(i) para algum k≥0. Seja [i]∼:= {j∈ {1,2, . . . , n} | i∼j}a classe de i. Tem-se [i]∼={i} ⇔ i∈fix(f). Como o conjunto {1,2, . . . , n}´e finito temos s´o um n´umero finito de classes distintas. Sejam [a1]∼,[a2]∼, . . . , [ak]∼as classes com mais do que 1 elemento. Ent˜ao {1,2, . . . , n}= fix(f)∪[a1]∼∪[a2]∼∪···∪[ak]∼. Para cada 1 ≤i≤kseja mi≥1 o menor inteiro positivo tal que fmi+1(ai) = ai. Tem-se [ai]∼={ai, f(ai), f2(ai), . . . , fmi(ai)} Seja gi:= (aif(ai)f2(ai)···fmi(ai)) o mi-ciclo. Ent˜ao temos f=g1◦g2◦···◦gk. Para todo x∈fix(f) tem-se gi(x) = x, ∀1≤i≤k. Portanto g1◦g2◦···◦gk(x) = x=f(x). Seja x∈[ai]∼ent˜ao x=fr(ai) para 0 ≤r≤mi. Portanto gi(x) = gi(fr(ai)) = fr+1(ai) = f(fr(ai)) = f(x). Como x, f(x)6∈ [aj]∼para j6=i. Tem-se gj(x) = xegj(f(x)) = f(x) para j6=i. Logo g1◦g2◦···◦gk(x) = ··· =g1◦g2◦···◦gi−1◦gi(x) = g1◦g2◦···◦gi−1(f(x)) = ··· =f(x). Portanto para todo x∈ {1,2, . . . n},f(x) = g1◦···◦gk(x). Suponhamos f=g1···gk=h1···hl´e produto de ciclos disjuntos giehj. Seja x∈sup(f) ent˜ao existem i, j tais que x∈sup(gi) e x∈sup(hj). Sem perda da generalidade podemos supor i=j= 1. Tem-se gr 1(x) = fr(x) = hr 1(x) para todo r∈N. Portanto existe um r≥1 tal que gr 1(x) = x=hr 1(x). Tem-se g1= (xg1(x)g2 1(x)···gr 1(x)) = h1. Logo g1=h1ou seja g−1 1f=h−1 1f=: ˜ f. Repetindo o processo conclui-se que k=le, a menos da ordem dos factores fi=gi. Exemplo 4.2.13 Seja f=123456 312465. Ent˜ao sup(f) = {1,2,3,5,6}. Escolhemos um n´umero i∈sup(f); por exemplo i= 1. Tem-se 1, f(1) = 3, f2(1) = f(3) = 2, f3(1) = f2(3) = f(2) = 1. Logo temos um 3-ciclo g1:= (132) 64 CAP´ ITULO 5. MON ´ OIDES E GRUPOS 3. (Zn,+,[0]n)e(Zn\{[0]n},·,[1]n)s˜ao mon´oides para n≥1. 4. (M2(A),+,0 0 0 0 )´e um mon´oide onde M2(A) = {a b c d |a, b, c, d ∈ A}para A=N,Z,Q,R,C. 5. O conjunto dos polin´omios (A[X],+,0) com coeficientes em A=N,Z,Q,R,C ´e um mon´oide. 5.2 Mon´oides Observa¸c˜ao 5.2.1 Sejam (M, , e)e(N, ~, f)mon´oides. No produto cartesiano M×Npodemos definir uma opera¸c˜ao bin´aria : (M×N)×(M×N)→(M×N) por (m, n)(m0, n0) := (mm0, n ~n0) para todos os elementos (m, n),(m0, n0)∈M×N. Ent˜ao (M×N, ,(e, f)) ´e um mon´oide e diz-se o produto directo de MeN. Demonstra¸c˜ao: Por defini¸c˜ao ´e uma fun¸c˜ao. Ent˜ao (M×N, ) ´e um grup´oide. O elemento (e, f) ´e o elemento neutro de (M×N, ), pois para todo (m, n)∈M×N tem-se (m, n)(e, f) = (me, n ~f) = (m, n) = (em, f ~n) = (e, f)(m, n). A opera¸c˜ao ´e associativa, porque para (m, n),(m0, n0),(m00, n00)∈M×Ntem-se (m, n)((m0, n0)(m00, n00)) = (m(m0m00), n ~(n0~n00)) = ((mm0)m00),(n~n0)~n00) = ((m, n)(m0, n0)) (m00, n00) Portanto (M×N, ,(e, f)) ´e um mon´oide.  Defini¸c˜ao 5.2.2 Seja (M, , e)um mon´oide. Um subconjunto N⊆Mdiz-se submon´oide de Mse (i) e∈N (ii) N´e fechado para , i.e. ∀x, y ∈N⇒xy∈N. Observa¸c˜ao 5.2.3 Sejam (M, , e)um mon´oide e Cum conjunto de submon´oides de M. Ent˜ao \ N∈C N ´e um submon´oide de M. 5.2. MON ´ OIDES 65 Demonstra¸c˜ao: Como e∈Npara todo N∈ C,e∈TN∈C N. Sejam x, y ∈ TN∈C Nent˜ao x, y ∈Npara todo N∈ C. Logo xy∈N∀N∈ C ⇒ xy∈\ N∈C N.  Seja Aum conjunto n˜ao vazio que designamos por alfabeto (os elementos de A s˜ao as letras). Seja A+o conjunto das palavras no alfabeto A, i.e. as sequˆencias a1a2···ancom ai∈A. Seja A∗=A+∪{∅}, onde ∅´e a palavra vazia. Define-se a opera¸c˜ao ·de concatena¸c˜ao da seguinte maneira: (a1···an)·(b1···bm) = a1···anb1···bm ∅·∅=∅ (a1···an)·∅ =a1···an=∅·(a1···an) para ai, bj∈A. Ent˜ao (A+,·) ´e um semigrupo e (A∗,·,∅) ´e um mon´oide, que se diz o mon´oide livre em A. Suponha A={x}ent˜ao h:N→A∗com h(0) := ∅eh(k) := xx ···x | {z } k−vezes ´e uma fun¸c˜ao bijectiva. Temos tamb´em h(k+l) = h(k)·h(l). Defini¸c˜ao 5.2.4 Sejam (M, , e)e(N, ~, f)dois mon´oides. Uma fun¸c˜ao h: M→Ndiz-se homomorfismo de mon´oides se (i) h(e) = f (ii) h(mm0) = h(m)~h(m0)para todo m, n ∈M. Se h´e uma fun¸c˜ao bijectiva hdiz-se um isomorfismo de mon´oides. Se existe um isomorfismo entre dois mon´oides MeNdizemos que MeNs˜ao isomorfos e escrevemos M≃N. Vimos que os mon´oides (N,+,0) e ({x}∗,·,∅) s˜ao isomorfos. Observa¸c˜ao 5.2.5 Seja f:M→Num isomorfismo entre mon´oides. Ent˜ao |M|=|N|ef−1:N→M´e tamb´em um isomorfismo de mon´oides. Defini¸c˜ao 5.2.6 Sejam (M, , e)um mon´oide e Dum subconjunto de M. O submon´oide gerado por D´e hDi:= {x1x2···xn|n≥1, xi∈D}∪{e}. Observa¸c˜ao 5.2.7 Sejam (M, , e)um mon´oide e Dum subconjunto de M. 1. hDi´e o menor submon´oide de Mque cont´em D. 2. hDi=TN∈C Nonde C´e o conjunto dos submon´oides Nde Mque contˆem D. 66 CAP´ ITULO 5. MON ´ OIDES E GRUPOS 5.3 Invertibilidade em mon´oides Defini¸c˜ao 5.3.1 Sejam (M, , e)ex, y ∈M. Diz-se que y´e o inverso de xse xy=e=yx. Se xtem um inverso dizemos que x´e invert´ıvel. Neste caso denota-se o inverso de xpor x−1. Observa¸c˜ao 5.3.2 Um elemento de um mon´oide tem apenas um inverso. Demonstra¸c˜ao: Seja xum elemento de um mon´oide (M, , e) e suponhamos que yezs˜ao inversos de x. Ent˜ao y=ye=y(xz) = (yx)z=ez=z.  Seja U(M):={x∈M|x´e invert´ıvel }. Observa¸c˜ao 5.3.3 Sejam (M, , e)ex, y ∈M. 1. e´e invert´ıvel, i.e. e∈U(M). 2. se xeys˜ao invert´ıveis ent˜ao xy´e invert´ıvel, i.e xy∈U(M). O inverso de xy´e (xy)−1=y−1x−1. 3. U(M)´e um submon´oide de M. Demonstra¸c˜ao: 1) Como ee=e,e´e invert´ıvel. 2) Como (xy)(y−1x−1) = x(yy−1)x−1=xex−1=xx−1=e e (y−1x−1)(xy) = y−1(x−1x)y=y−1ey=y−1y=e Tem-se (xy)−1=y−1x−1. Teorema 5.3.4 Sejam (M, , e)um mon´oide e x∈Mum elemento invert´ıvel. Ent˜ao para qualquer a, b ∈M, se ax=bxou xa=xbent˜ao a=b. Demonstra¸c˜ao: Seja x−1o inverso de xent˜ao ax=bx⇒(ax)x−1= (bx)x−1 ⇒a(xx−1) = b(xx−1) ⇒ae=be ⇒a=b. Analogamente mostra-se que xa=xb⇒a=b. 5.4. GRUPOS 67 5.4 Grupos Defini¸c˜ao 5.4.1 Um grupo ´e um mon´oide (G, ·, e)tal que todo o elemento de G ´e invert´ıvel. Ent˜ao (G, ·, e) ´e um grupo se •G´e um conjunto • · :G×G−→ G´e uma opera¸c˜ao bin´aria •e∈G´e o elemento neutro, i.e. a·e=a=e·a∀a∈G •todo o elemento de Gtem um inverso (em G), i.e. ∀g∈G:∃h∈G:h·g= e=g·h. Exemplo 5.4.2 1. (Z,+,0) ´e um grupo. 2. (Z,·,1) n˜ao ´e um grupo, mas ({1,−1},·,1) ´e um grupo. 3. (Q,+,0) e(Q\{0},·,1) s˜ao grupos. 4. (Sn,◦, id)e(An,◦, id)s˜ao grupos. 5. (M2(Q),+,0 0 0 0 )e(GL2(Q),·,1 0 0 1 )s˜ao grupos onde GL2(Q):={A∈M2(Q)|det A6= 0}. Um grupo cuja opera¸c˜ao bin´aria ´e comutativa diz-se tamb´em grupo abeliano. Observa¸c˜ao 5.4.3 Sejam G1eG2grupos. O produto directo G1×G2´e um grupo. Demonstra¸c˜ao: Sejam (G1,, e1) e (G2,~, e2) grupos. Sabemos que G1×G2´e um mon´oide com a opera¸c˜ao bin´aria: (a1, a2)(b1, b2) := (a1b1, a2~b2) e com o elemento neutro (e1, e2). Como G1eG2s˜ao grupos todo o elemento a1∈G1ea2∈G2tem um inverso. Logo o inverso do elemento (a1, a2)∈G1×G2 ´e o elemento (a−1 1, a−1 2), pois (a1, a2)(a−1 1, a−1 2) = (a1a−1 1, a2~a−1 2) = (e1, e2).  Defini¸c˜ao 5.4.4 Seja Hum subconjunto de um grupo G.Hdiz-se um subgrupo de Gse H´e um submon´oide de Gtal para todo h∈Htamb´em o inverso h−1 pertence H. 68 CAP´ ITULO 5. MON ´ OIDES E GRUPOS Ent˜ao um subconjunto Hde um grupo G´e um subgrupo de Gse •e∈H • ∀h∈H:h−1∈H • ∀h, g ∈H:hg ∈H. Exemplo 5.4.5 1. An´e um subgrupo de Sn 2. (Z,+,0) ´e um subgrupo de (Q,+,0). 3. (Z\{0},·,1) n˜ao ´e um subgrupo de (Q\{0},·,1). 4. SL2(Q)´e um subgrupo de GL2(Q). 5. (2Z4,+,[0]4´e um subgrupo de (Z4,+,[0]4)onde 2Z4:= {[2a]4|a∈Z}={[0]4,[2]4}. Observa¸c˜ao 5.4.6 Seja Cum conjunto de subgrupos de um grupo G. Ent˜ao TH∈C H´e um subgrupo de G. Demonstra¸c˜ao: Seja K:= TH∈C H. J´a sabemos que K´e um submon´oide de G. Seja k∈Kent˜ao k∈Hpara todo H∈ C. Como H´e um subgrupo temos k−1∈Hpara todo H∈ C. Logo k−1∈K. Defini¸c˜ao 5.4.7 Seja (G, , e)um grupo e D⊆Gum subconjunto. O subgrupo gerado por Dem G´e hDi:= {x1x2···xn|n≥0exi∈Dou x−1 i∈D}. Por conven¸c˜ao o produto com 0 factores ´e igual a e(= o elemento neutro de G). Note-se que hDi´e igual ao submon´oide gerado por D∪D−1onde D−1:= {d−1| d∈D}. Observa¸c˜ao 5.4.8 Seja Gum grupo e D⊆G. 1. hDi´e o menor subgrupo de Gque cont´em D. 2. hDi=TH∈C Honde C´e o conjunto dos subgrupos Hde Gque contˆem D. Defini¸c˜ao 5.4.9 Suponha G=hDipara um subconjunto D⊆G. Ent˜ao dizemos que G´e gerado por DeD´e um conjunto dos geradores de G. Se existe um conjunto finito D={d1, d2, . . . , dm}tal que G=hDient˜ao Gdiz-se finitamente gerado. Se existe um elemento d∈Gtal que G=h{d}i ent˜ao Gdiz-se c´ıclico. 5.4. GRUPOS 69 Usamos a seguinte nota¸c˜ao. Seja xum elemento de um grupo (G, , e) e seja k∈Z: xk:= x···x | {z } k−vezes para k > 0, xk:= epara k= 0, xk:= x−1···x−1 | {z } |k|−vezes para k < 0. Note-se que se G=Ze 0 6=x∈Zent˜ao no grupo (Z,+,0) temos xk=x+···+x | {z } k−vezes =kx para k > 0 e xk= (−x) + ···+ (−x) | {z } |k|−vezes = (−k)x para k < 0. No grupo (Q\{0},·,1) temos xk=x·····x | {z } k−vezes =xk para k > 0 e xk=1 x····· 1 x | {z } |k|−vezes =1 xk para k < 0. Observa¸c˜ao 5.4.10 1. Todo o grupo G´e gerado pelos seus elementos, i.e. G=hGi. Logo se o conjunto G´e finito, G´e finitamente gerado. 2. O grupo (Z,+,0) ´e c´ıclico, pois Z=h{1}i. 3. Seja (G, , e)um grupo abeliano e D⊆G. Ent˜ao hDi={xk1 1xk2 2···xkn n|n≥0, ki∈Z, xi∈Dexi6=xj∀i6=j}. 4. O grupo (Q,+,0) n˜ao ´e finitamente gerado. Demonstra¸c˜ao: (1),(2) exerc´ıcio; (3) Por defini¸c˜ao qualquer elemento x∈ hDi ´e igual x=x1x2··· xmpara xi∈Dou x−1 i∈D. Como a opera¸c˜ao ´e comutativo podemos reordenar os factores e obtemos x=yk1 1···ykn npara yi∈ {x1, . . . , xm}eyi6=yjeki∈Z. Portanto todo o elemento de hDipode ser descrito desta forma. (4) Seja D:= {a1 b1, . . . , am bm} ⊂ Q. Por (3) todo o elemento x∈ hDipode ser escrito como x=k1 a1 b1 +···km am bm 70 CAP´ ITULO 5. MON ´ OIDES E GRUPOS onde ki∈Z. Calculando esta soma obtemos um elemento de Qda forma x=c b1b2···bm para algum c∈Z( talvez seja poss´ıvel simplificar este termo, mas isso ser´a ignorado aqui). Seja pum primo tal que p-bipara todo 1 ≤i≤m. Ent˜ao 1 p6∈ hDi, caso contr´ario suponhamos que 1 p∈ hDi. Ent˜ao existira um c∈Ztal que 1 p=c b1b2···bmou seja b1b2···bm=cp. Logo p|b1b2···bm. Assim, como p´e primo, p|bipara algum 1 ≤i≤mabsurdo. Portanto 1 p6∈ hDieQ6=hDipara qualquer subconjunto finito Dde Q. Logo Q n˜ao ´e finitamente gerado.  Defini¸c˜ao 5.4.11 Sejam (G1,, e1)e(G2,~, e2)grupos. Uma fun¸c˜ao f:G1−→ G2diz-se um homomorfismo de grupos se f´e um homomorfismo de mon´oides tal que f(x−1) = f(x)−1para todo x∈G1. Ent˜ao f:G1−→ G2´e um homomorfismo de grupos se •f(e1) = e2; • ∀x∈G1:f(x−1) = f(x)−1; • ∀x, y ∈G1:f(xy) = f(x)~f(y). Observa¸c˜ao 5.4.12 Seja f:G1→G2uma fun¸c˜ao. Ent˜ao f´e um homomorfismo de grupos se e s´o se f(xy) = f(x)~f(y). Demonstra¸c˜ao: ⇒por defini¸c˜ao. ⇐Temos f(e1) = f(e1)~e2 =f(e1)~(f(e1)~f(e1)−1) =f(e1e1)~f(e1)−1 =f(e1)~f(e1)−1 =e2 Para todo x∈G1temos f(x)−1=f(x)−1~e2 =f(x)−1~f(e1) =f(x)−1~f(xx−1) =f(x)−1~f(x)~f(x−1) = f(x−1). 5.4. GRUPOS 71  Seja f:G1−→ G2um homomorfismo de grupos. O subconjunto de G1 Ker(f):={x∈G1|f(x) = e2} diz-se o n´ucleo de f. Para a imagem de fescrevemos f(G1). Teorema 5.4.13 Seja f:G1−→ G2um homomorfismos de grupos. 1. A imagem f(G1)´e um subgrupo de G2. 2. O n´ucleo Ker(f)´e um subgrupo de G1. 3. O homomorfismo f´e injectivo se e s´o se Ker(f) = {e1}. 4. se f´e um isomorfismo ent˜ao f−1:G2→G1´e um isomorfismo tamb´em. Demonstra¸c˜ao: (3) Suponhamos que Ker(f) = {e1}. Sejam x, y ∈G1tais que f(x) = f(y). Ent˜ao e2=f(y)~f(x)−1=f(yx−1). Logo yx−1∈Ker(f) = {e1}. Consequentemente yx−1=e1ou seja y=x. Portanto f´e injectivo. Se f´e injectivo e f(x) = e2logo x=e1. Teorema 5.4.14 (Teorema de Cayley) Qualquer grupo (G, , e)´e isomorfo a um subgrupo de um grupo sim´etrico SX. Demonstra¸c˜ao: Seja X=GeSXo grupo sim´etrico do conjunto X. Para qualquer g∈Gseja Lg:X→Xa fun¸c˜ao: Lg(x) = gx. Tem-se Lg◦Lg−1(x) = gg−1x=x=id(x) para qualquer x∈X, portanto Lg´e bijectiva e Lg∈SX. Nota que Lgh(x) = ghx=Lg(Lh(x)) = (Lg◦Lh)(x) para qualquer x∈X. A aplica¸c˜ao L:G→SXcom f(g) = Lg´e um homomorfismo de grupos, porque f(gh) = Lgh=Lg◦Lh=f(g)◦f(h). Se f(g) = Lg=id, ent˜ao e=gg−1=Lg(g−1) = id(g−1) = g−1. . Portanto Ker(f) = {e}ef´e injectivo e G´e isomorfo ao imagem de f, que ´e um subgrupo de SX. 72 CAP´ ITULO 5. MON ´ OIDES E GRUPOS 5.5 Grupos c´ıclicos Teorema 5.5.1 Seja (G, , e)um grupo c´ıclico, i.e. G=hxipara algum x∈G. Ent˜ao ou G´e isomorfo ao grupo (Z,+,0) ou G´e isomorfo ao grupo (Zn,+,[0]n) para algum n≥1. Demonstra¸c˜ao: Suponhamos que n˜ao existe nenhum inteiro k6= 0 tal que xk=e onde e´e o elemento neutro de G. Ent˜ao a fun¸c˜ao f:Z→Gtal que f(k) := xk´e bijectiva, porque se f(k) = f(l) para k≥lent˜ao xk=xl⇒xk−l=xl−l=e⇒k−l= 0 ⇒k=l. A fun¸c˜ao f´e um homomorfismo de grupos, pois f(k+l) = xk+l=xkxl= f(k)f(l) para k, l ∈Z. Ent˜ao f´e um isomorfismo de grupos. Suponhamos que existe um inteiro k6= 0 tal que xk=e. Sem perda de generalidade podemos supor que existe um inteiro positivo, porque se k < 0 e xk=eent˜ao x−k=e−1=ee−k > 0. Seja no menor inteiro positivo tal que xn=e. Temos que f:Zn→Gcom f([k]n) := xk∀[k]n∈Zn ´e uma fun¸c˜ao. Temos de verificar se fest´a bem-definida. Ent˜ao sejam k≤ldois inteiros tais que [k]n= [l]n. Logo n|l−k⇒ ∃q∈Z:l=k+qn. Portanto f([l]n) = xl=xk(xn)q=xke=f([k]n) mostre que fest´a bem-definida. Temos que f´e um homomorfismo de grupos, pois f([k]n+ [l]n) = f([k+l]n) = xk+l=xkxl=f([k]n)f([l]n) para todo [k]n,[l]n∈Zn. Suponha que existe um k∈Ztal que f([k]n) = xk=e. Pelo Algoritmo da divis˜ao existem q∈Zer∈ {0,1, . . . , n−1}tais que k=nq +r. Portanto e=xk= (xn)qxr=exr=xr. Como n´e o menor inteiro positivo tal que xn=ee 0 ≤r < n temos r= 0. Logo n|k⇒[k]n= [0]n. Portanto f´e injectivo. Como f´e tamb´em sobrejectivo, f´e bijectiva e um isomorfismo de grupos.  Defini¸c˜ao 5.5.2 Seja Gum grupo. Define-se ordem de g∈Ge denota-se por ord(g), como sendo a ordem do subgrupo hgigerado por g;ord(g) :=| hgi |. Observa¸c˜ao 5.5.3 Seja g∈G. Se ord(g)´e finito ent˜ao ord(g)´e o menor inteiro positivo ntal que gn=e. Al´em disso gk=e⇔ord(g)|kpara k∈Z. 5.5. GRUPOS C´ ICLICOS 73 Demonstra¸c˜ao: Suponhamos que ord(g) =| hgi |=n < ∞. Ent˜ao f:Zn→ hgi com f([k]n) = gk´e um isomorfismo de grupos. Suponhamos que gk=epara algum k∈Z. Ent˜ao f([k]n) = gk=e=g0=f([0]n) o que implica que [k]n= [0]n, pois f´e injectivo. Logo n|k. Se k > 0 ent˜ao k≥n. Portanto n= ord(g) ´e o menor inteiro positivo tal que gn=e. Tamb´em temos que se gk=eent˜ao n= ord(g)|k. A afirma¸c˜ao contr´aria ´e obvia.  Lema 5.5.4 Todo o subgrupo de um grupo c´ıclico ´e c´ıclico. Demonstra¸c˜ao: Seja (G, , e) um grupo c´ıclico. Ent˜ao existe um g∈Gtal que G=hgi. Seja Hum subgrupo de G. Se H={e}ent˜ao H´e c´ıclico, pois H=hei. Suponha que H6={e}e seja h∈Htal que h6=e. Como todo o elemento de G´e da forma gkpara k∈Zexiste k∈Ztal que h=gk. Sem perda de generalidade podemos supor que existe um inteiro positivo k > 0 tal que gk∈H, pois se k < 0 ent˜ao g−k=h−1∈He−k > 0. Sejam ko menor inteiro positivo tal que gk∈He gl∈Hcom l∈Zum elemento de Hqualquer. Pelo algoritmo da divis˜ao existem inteiros q∈Zer∈ {0,1, . . . , k −1}tais que l=qk +r. Portanto gl=gkq qr⇒gr=gl−qk ∈H. Como k´e o menor inteiro positivo tal que gk∈He como 0 ≤r < k temos r= 0 ek|l. Logo todo o elemento de H´e da forma (gk)qpara um q∈Z. Ent˜ao H⊆ hgki ⊆ Himplica que H=hgki´e c´ıclico.  Corol´ario 5.5.5 Os subgrupos de (Z,+,0) s˜ao da forma nZpara n≥0. Demonstra¸c˜ao: O subgrupo gerado por um inteiro n∈Z´e igual hni={n+. . . +n | {z } k−vezes |k > 0}∪{0}∪{(−n) + . . . + (−n) |{z } |k|−vezes |k < 0} ={kn |k∈Z} =nZ. Obviamente nZ= (−n)Z, ent˜ao todo o subgrupo tem a forma nZpara algum n≥0.  Observa¸c˜ao 5.5.6 Seja G=hgium grupo c´ıclico tal que ord(g) = n. As seguintes propriedades s˜ao satisfeitas para todo o elemento gk∈Gcom k∈Z: (i) ord(gk) = n mdc(n,k). (ii) hgki=hgmdc(n,k)i. 80 CAP´ ITULO 5. MON ´ OIDES E GRUPOS Cap´ıtulo 6 An´eis e corpos 6.1 An´eis Defini¸c˜ao 6.1.1 Um conjunto Acom duas opera¸c˜oes bin´arias +e·´e um anel se (i) (A, +,0) ´e um grupo abeliano. (ii) (A, ·,1) ´e um mon´oide. (iii) ∀a, b, c ∈A: a·(b+c) = a·b+a·c (b+c)·a=b·a+c·a A opera¸c˜ao + diz-se a adi¸c˜ao do anel, a opera¸c˜ao ·diz-se a multiplica¸c˜ao do anel; o elemento neutro 0 da adi¸c˜ao diz-se o zero do anel; o elemento neutro 1 da multiplica¸c˜ao diz-se o elemento um do anel. Dado a∈Ao inverso de aem (A, +,0) diz-se o sim´etrico de ae representa-se por −a. Se a multiplica¸c˜ao do anel for comutativa, o anel diz-se anel comutativo. Em geral representamos apenas por Ao anel (A, +,·,0,1). Um elemento ado anel Adiz-se invert´ıvel se afor invert´ıvel no mon´oide (A, ·,1), i.e. se existir b∈Atal que ab = 1 = ba. Se afor invert´ıvel o inverso de aem (A, ·,1) ´e ´unico e denota-se por a−1. Um anel Atal que todo o elemento an˜ao nulo, i.e. a6= 0, ´e invert´ıvel diz-se um corpo. O anel A={0}diz-se anel trivial. N˜ao ´e dif´ıcil mostrar que A´e o anel trivial se e s´o se |A|= 1. Exemplo 6.1.2 •Z,Q,R,Cs˜ao an´eis. Nn˜ao ´e um anel porque (N,+,0) n˜ao ´e um grupo. 81 82 CAP´ ITULO 6. AN´ EIS E CORPOS •(Zn,+,·,[0]n,[1]n)´e um anel para n≥0. •(M2(R),+,·,0 0 0 0 ,1 0 0 1 )munido da soma e produto de matrizes ´e um anel. •(R[X],+,·,0,1) munido da soma e produto de polin´omios ´e um anel. Observa¸c˜ao 6.1.3 Seja Aum anel e a, b ∈A. Tem-se que (i) a·0=0=0·a. (ii) (−a)·b=−(a·b) = a·(−b) (iii) (−a)·(−b) = a·b (iv) A´e o anel trivial se e s´o se 0 = 1. Demonstra¸c˜ao: (i) Seja a∈Aent˜ao a·0 = a·(0 + 0) = a·0 + a·0⇒0 = a·0. (ii) (−a)·b+a·b= (−a+a)·b= 0 ·b= 0. Logo (−a)·b=−(a·b). (iii) 0 = (−a)·(−b)+(−(a·b) = (−a)·(−b)+(−a)·b= (−a)·(−b+b) = (−a)·0 = 0. Logo (−a)·(−b) = −(−(a·b)) = a·b. (iv) Obviamente se A´e trivial ent˜ao 0 = 1. Seja 0 = 1. Para todo a∈Atemos a=a·1 = a·0 = 0. Logo A={0}. Teorema 6.1.4 Sejam (A, +,·,0,1) e(A0,+0,·0,00,10)an´eis. O produto cartesiano A×A0´e um anel com as opera¸c˜oes (a, a0)+(b, b0) := (a+b, a0+0b0)e (a, a0)·(b, b0) := (a·b, a0·0b0), zero (0,00)e elemento um (1,10). O anel (A× A0,+,·,(0,00),(1,10)) diz-se o produto directo de AeA0. Demonstra¸c˜ao: J´a sabemos que (A×A0,+,(0,00) ´e um grupo e (A×A0,·,(1,10)) ´e um mon´oide. Como (a, a0)+(b, b0) = (a+b, a0+0b0) = (b+a, b0+0a0) = (b, b0)+(a, a0) para qualquer (a, a0),(b, b0)∈A×A0o grupo (A×A0,+,(0,00)) ´e abeliano. Sejam (a, a0),(b, b0),(c, c0)∈A×A0ent˜ao (a, a0)·[(b, b0)+(c, c0)] = (a, a0)·(b+c, b0+0c0) = (a·(b+c), a0·0(b0+0c0)) = (a·b+a·c), a0·0b0+0a0·0c0) = (a·b, a0·b0)+(a·c, a0·0c0) = (a, a0)·(b, b0)+(a, a0)·(c, c0). Analogamente tem-se [(b, b0)+(c, c0)]·(a, a0) = (b, b0)·(a, a0)+(c, c0)·(a, a0). Portanto A×A0´e um anel.  6.1. AN´ EIS 83 Defini¸c˜ao 6.1.5 Seja (A, +,·,0,1) um anel e B⊆A. Diz-se que B´e um subanel de A se B´e um subgrupo de (A, +,0) eB´e um submon´oide de (A, ·,1). Assim B´e um subanel de Ase e s´o se (i) 0 ∈B; (ii) ∀b∈B:−b∈B; (iii) ∀a, b ∈B:a+b∈B; (iv) 1 ∈B; (v) ∀a, b ∈B:a·b∈B. Defini¸c˜ao 6.1.6 Seja Aum corpo e B⊆A. Diz-se que B´e um subcorpo de A se B´e um subanel de Ae∀b∈B\{0}:b−1∈B. Exemplo 6.1.7 •Z´e um subanel de Qmas n˜ao ´e um subcorpo de Q. •Q´e um subcorpo de ReC. Teorema 6.1.8 Seja Aum anel e seja Cum conjunto de suban´eis de A. Ent˜ao a intersec¸c˜ao \ B∈C B ´e um subanel de A. Seja Dum subconjunto n˜ao vazio de um anel A. Seja C:= {B⊆A|B´e um subanel de Ae cont´em todos os elementos de D}. Ent˜ao o subanel gerado por D´e hDi:= \ B∈C B. Um anel Adiz-se finitamente gerado se existe um subconjunto n˜ao vazio finito {d1, . . . , dn} ⊆ Atal que A=h{d1, . . . , dn}i. Por exemplo Z=h{1}i e Z×Z=h{(1,0),(0,1)}i.Os n´umeros racionais Qn˜ao s˜ao finitamente gerado como anel. 84 CAP´ ITULO 6. AN´ EIS E CORPOS 6.2 Ideais e Teorema Fundamental do Homomorfismo Defini¸c˜ao 6.2.1 Sejam (A, +,·,0,1) e(A0,+0,·0,00,10)dois an´eis. Uma fun¸c˜ao f:A→A0diz-se homomorfismo de an´eis se f´e um homomorfismo entre os grupos (A, +,0) e(A0,+0,00)e ´e um homomorfismo entre os mon´oides (A, ·,1) e (A0,·0,10). Ent˜ao uma fun¸c˜ao f´e um homomorfismo de an´eis se (i) f(a+b) = f(a) +0f(b) para a, b ∈A (ii) f(a·b) = f(a)·0f(b) para a, b ∈A (iii) f(1) = 10. Um homomorfismo bijectivo diz-se um isomorfismo. Observa¸c˜ao 6.2.2 Seja f:A→A0um homomorfismo de an´eis. (i) f(0) = 00; (ii) f(−a) = −f(a)para todo a∈A; (iii) se a∈A´e invert´ıvel ent˜ao f(a)´e invert´ıvel e f(a)−1=f(a−1); (iv) f´e injectivo se e s´o se Ker(f) = {0}; (v) se f´e um isomorfismo, ent˜ao f−1:A0→A´e tamb´em um isomorfismo de an´eis. (vi) Im(f)´e um subanel de A0. Demonstra¸c˜ao: Como f´e um homomorfismo de grupos (A, +,0) e (A0,+0,00) tem-se (i),(ii) e (iv). (iii) Seja a∈Ainvert´ıvel. Ent˜ao f(a)·0f(a−1) = f(a·a−1) = f(1) = 10=f(1) = f(a−1·a) = f(a−1)·0f(a). Logo f(a−1) = f(a)−1.  Defini¸c˜ao 6.2.3 Um subconjunto Ide um anel (A, +,·,0,1) diz-se ideal se I´e um subgrupo de (A, +,0) tal que ax ∈Iexa ∈Ipara todo a∈Aex∈I. 6.2. IDEAIS E TEOREMA FUNDAMENTAL DO HOMOMORFISMO 85 Exemplo 6.2.4 (1){0}eAs˜ao ideais de um anel A. (2) Os ideais de Zs˜ao da forma nZpara n∈N. Todo o ideal Ide Z´e tamb´em um subgrupo do grupo (Z,+,0). Logo I=nZpor 5.5.5. Por outro lado todo o subconjunto nZ´e um subgrupo de (Z,+,0). Como para todo a∈Zenx ∈nZ: a(nx) = (nx)a=n(xa)∈nZ nZ´e um ideal. Lema 6.2.5 Seja f:A→A0um homomorfismo de an´eis ent˜ao Ker(f)´e um ideal de A. Demonstra¸c˜ao: J´a sabemos que Ker(f) ´e um subgrupo de (A, +,0). Sejam a∈A ek∈Ker(f) ent˜ao f(a·k) = f(a)·0f(k) = f(a)·000= 00= 00·0f(a) = f(k)·0f(a) = f(k·a). Logo a·k, k ·a∈Ker(f).  Teorema 6.2.6 Seja Ium ideal de um anel (A, +,·,0,1) ent˜ao o grupo quociente (A/I, +, I)´e um anel com a multiplica¸c˜ao (a+I)·(b+I) := (a·b) + I∀a, b ∈A e o elemento um 1 + I. O anel (A/I, +,·, I, 1 + I)diz-se o anel quociente de A por I. Demonstra¸c˜ao: O grupo quociente (A/I, +, I) de Apor I´e um grupo. Como (A, +,0) ´e um grupo abeliano: (a+I)+(b+I) = (a+b) + I= (b+a) + I= (b+I)+(a+I)∀a, b ∈A, i.e. (A/I, +, I) ´e um grupo abeliano. Vamos ver que a multiplica¸c˜ao esteja bem-definida: Seja a+I=a0+Ieb+I=b0+I ou seja a−a0∈Ieb−b∈I. Ent˜ao existem x, y ∈Itais que a=a0+xeb=b0+y. Portanto (a+I)·(b+I)=(a·b) + I = ((a0+x)·(b0+y))+I = (a0·b0+a0·y+x·(b0+y))+I = (a0·b0) + I = (a0+I)·(b0+I) 86 CAP´ ITULO 6. AN´ EIS E CORPOS porque a0·y∈Iex·(b0+y)∈Icomo I´e um ideal e x, y ∈I. (Note-se que (a+z) + I=a+Ise z∈I). Portanto ·est´a bem-definida. (A/I, ·,1+I) ´e um mon´oide, pois para todos os elementos a+I, b+I, c+I∈A/I tem-se [(a+I)·(b+I)]·(c+I) = [(a·b) + I]·(c+I) = ((a·b)·c) + I = (a·(b·c))+I = (a+I)·[(b·c) + I] = (a+I)·[(b+I)·(c+I)], i.e. ·´e associativa. (a+I)·(1 + I) = (a·1) + I=a+I= (1 ·a) + I= (1 + I)·(a+I), i.e. 1 + I´e o elemento neutro de (A/I, ·). Tamb´em tem-se (a+I)·[(b+I)+(c+I)] = (a+I)·((b+c) + I) = (a·(b+c))+I = (a·b+a·c)) + I = [(a·b) + I]+[(a·c) + I] = [(a+I)·(b+I)]+[(a+I)·(c+I)] e analogamente [(b+I)+(c+I)]·(a+I) = [(b+I)·(a+I)]+[(c+I)·(a+I)]. Logo (A/I, +,·, I, 1 + I) ´e um anel.  Teorema 6.2.7 (Teorema fundamental de homomorfismos) Sejam AeA0 an´eis, f:A→A0um homomorfismo de an´eis e I:= Ker(f). A fun¸c˜ao f:A/I →A0com f(a+I):=f(a) para todo a+I∈A/I ´e um homomorfismo de an´eis injectivo. Demonstra¸c˜ao: J´a sabemos pelo 5.6.9 que f:A/I →A0´e um homomorfismo de grupos (A/I, +, I) e (A0,+0,00) onde I= Ker(f) e f(a+I) = f(a). Tamb´em sabemos que f´e injectivo. Basta mostrar que f´e um homomorfismo de an´eis ou seja que f´e um homomorfismo de mon´oides (A/I, ·,1 + I) e (A0,·0,10). Tem-se para todo a+I, b +I∈A/I : f((a+I)·(b+I)) = f((a·b) + I) =f(a·b) =f(a)·0f(b) =f(a+I)·0f(b+I). 6.3. DOM´ INIOS DE INTEGRIDADE E CORPOS 87 Verifique-se tamb´em f(1 + I) = f(1) = 10. Portanto f´e um homomorfismo de mon´oides (A/I, ·,1 + I)e(A0,·0,10) e como j´a sabemos que f´e um homomorfismo de grupos (A/I, +, I)e(A0,+0,00) tem-se que f´e um homomorfismo de an´eis.  Corol´ario 6.2.8 Seja f:A→A0um homomorfismo de an´eis. Ent˜ao os an´eis A/Ker(f)eIm(f)s˜ao isomorfos: A/Ker(f)≃Im(f). 6.3 Dom´ınios de Integridade e Corpos Defini¸c˜ao 6.3.1 Seja Aum anel comutativo. Um elemento a∈A\{0}diz-se um divisor de zero se existir b∈A\{0}tal que ab = 0. Exemplo 6.3.2 Seja A=Z6. O elemento a= [2]6∈A´e um divisor de zero, porque para b= [3]6tem-se ab = [2]6[3]6= [6]6= [0]6. Por defini¸c˜ao: Um elemento a∈A´e um divisor de zero se a afirma¸c˜ao ∃b∈A: b6= 0 ∧ab = 0 for verdade. Negamos esta afirma¸c˜ao obtemos que um elemento a n˜ao ´e um divisor de zero se 6 ∃b∈A:b6= 0∧ab = 0 ou seja se ∀b∈A:b= 0∨ab 6= 0. Observa¸c˜ao 6.3.3 Seja Aum anel comutativo e a∈A. Suponha que a´e invert´ıvel ent˜ao an˜ao ´e um divisor de zero. Demonstra¸c˜ao: Suponha que a∈A´e invert´ıvel. Seja a−1o inverso de a. Se ab = 0 para algum b∈Aent˜ao b=a−1ab =a−10 = 0. Portanto an˜ao pode ser um divisor de zero.  Defini¸c˜ao 6.3.4 Um anel comutativo Adiz-se dom´ınio de integridade se A n˜ao tem divisores de zero. Observa¸c˜ao 6.3.5 Seja Aum anel comutativo. A´e um dom´ınio de integridade se e s´o se xa =xb ⇒x= 0 ∨a=bpara todo a, b, x ∈A. Demonstra¸c˜ao: Seja Aum dom´ınio de integridade. Suponha que xa =xb para x, a, b ∈A. Logo x(a−b) = 0. Como A´e um dom´ınio de integridade, An˜ao tem divisores de zero. Logo ou xou a−b´e igual 0. Portanto x= 0 ∨a=b. Suponha que xa =xb ⇒x= 0 ∨a=bpara todo a, b, x ∈A. Se ab = 0 para alguns elementos a, b ∈Aent˜ao ab =0=a0⇒a= 0 ∨b= 0. Portanto An˜ao tem divisores de zero.  88 CAP´ ITULO 6. AN´ EIS E CORPOS Exemplo 6.3.6 Z,Q,R,Cs˜ao dom´ınios de integridades. Teorema 6.3.7 Todo o corpo ´e um dom´ınio de integridade. Demonstra¸c˜ao: Como todo o elemento de um corpo ou ´e igual 0 ou ´e um elemento invert´ıvel a observa¸c˜ao 6.3.3 mostre que um corpo n˜ao tem divisores de zero.  O anel Z´e um dom´ınio de integridade mas n˜ao ´e um corpo. Digamos que um anel A´e finito se |A|´e um n´umero finito. Teorema 6.3.8 Todo o dom´ınio de integridade finito ´e um corpo. Demonstra¸c˜ao: Seja Aum dom´ınio de integridade finito com nelementos. Para qualquer x∈A\ {0}consideramos a fun¸c˜ao Ex:A→Acom Ex(a) = xa. Se Ex(a) = Ex(b) ent˜ao xa =xb ⇒a=bpor 6.3.5. Logo Ex´e injectivo. Como A tem nelementos e Ex´e injectivo, a imagem da fun¸c˜ao Ex: Im(Ex) = {xa |a∈A} ⊆ A tem tamb´em nelementos. Logo Ex´e sobrejectivo, i.e. Im(()Ex) = A. Portanto existe um a∈Atal que xa =Ex(a) = 1, i.e x´e invert´ıvel. Mostr´amos que todo o elemento x6= 0 ´e invert´ıvel; logo A´e um corpo.  Defini¸c˜ao 6.3.9 Seja Aum anel comutativo. Um ideal Ide Adiz-se primo se ∀a, b ∈A:ab ∈I⇒a∈I∨b∈I. Um ideal Ide Adiz-se maximal se para todo ideal Jde A: I⊆J⊆A⇒I=J∨J=A. Exemplo 6.3.10 Os ideais maximais de Zs˜ao da forma pZonde p´e um n´umero primo. Para ver isto seja Ium ideal maximal de Z. Como todo o subgrupo de Z´e da forma nZcom n≥0existe um n∈Ntal que I=nZ. Seja dum divisor positivo de n, i.e. 1≤d≤ned|n. Ent˜ao I=nZ⊆dZ⊆Z porque todo o elemento na ∈nZ´e tamb´em um m´ultiplo de d, portanto na ∈dZ. Como I´e maximal, I=dZou dZ=Z. No primeiro caso tem-se d∈I=nZou seja d=nx mas como n=dy para algum y∈Ztem-se d=dyx ⇒1 = yx ⇒y=x= 1 ⇒d=n. No segundo caso tem-se 1∈dZou seja 1 = dx para algum x∈Z. Logo d= 1. Portanto os ´unicos divisores positivos de ns˜ao 1en, i.e. n´e um n´umero primo. Suponha que I=pZcom pum n´umero primo. Seja Jum ideal de Ztal que pZ⊆J⊆Z. Se pZ6=Jent˜ao existe um n∈J\pZ. Logo p-nou seja mdc(p, n) = 1. Pelo Algoritmo de Euclides existem x, y ∈Ztais que 1 = px +ny. Como px ∈pZ⊆Jeny ∈Jtem-se 1∈J. Portanto J=Z. 6.3. DOM´ INIOS DE INTEGRIDADE E CORPOS 89 Exemplo 6.3.11 Os ideais primos de Zs˜ao os ideais maximais de Ze o ideal {0}. Seja Ium ideal primo de Z. Existe um n∈Ntal que I=nZ. Se n= 0 ent˜ao I={0}. Suponha que n6= 0. Seja dum divisor positivo de ntal que n=dx para algum x∈Z. Como dx =n∈nZ=IeI´e primo, d∈Iou x∈I. Se d∈Ient˜ao d=ny para algum y∈Z. Logo n=dx =nyx ⇒1 = yx ⇒x= 1 ⇒n=d. Se x∈Ient˜ao x=ny para algum y∈Z. Logo n=dx =dny ⇒1 = dy ⇒d= 1. Portanto os ´unicos divisores positivos de ns˜ao 1en, i.e. n´e um n´umero primo. O ideal {0}´e um ideal primo, pois se a, b ∈Z: ab ∈ {0} ⇒ ab = 0 ⇒a= 0 ∨b= 0 ⇒a∈ {0}∨b∈ {0}. Seja pum n´umero primo e a, b ∈Z ab ∈pZ⇒p|ab ⇒p|a∨p|b⇒a∈pZ∨b∈pZ. Portanto pZ´e um ideal primo de Z. Lema 6.3.12 Sejam IeJideais de um anel A, ent˜ao I+J:= {x+y|x∈I, y ∈ J}´e um ideal de A. Demonstra¸c˜ao: Verificamos que I+J´e um subgrupo de A: (i) 0 ∈I⊆I+J; (ii) ∀x, x0∈Iey, y0∈J: (x+y)+(x0+y0) = (x+x0)+(y+y0)∈I+J; ent˜ao I+Jest´a fechado para +. (iii) ∀x+y∈I+J: (−x)+(−y)∈I+J. Sejam a∈Aex+y∈I+Jcom x∈Iey∈J. Ent˜ao a·(x+y) = a·x+a·y∈I+Je (x+y)·a=x·a+y·a∈I+J  Lema 6.3.13 Sejam Aum anel e I⊆Jideais de A. O subconjunto J/I := {a+I|a∈J}´e um ideal do anel quociente A/I. Demonstra¸c˜ao: Exerc´ıcio.  Teorema 6.3.14 Seja Aum anel comutativo e Ium ideal de A. Tem-se (1) I´e um ideal primo se e s´o se o anel quociente A/I ´e um dom´ınio de integridade.