Baixe Introdução a Algebra Abstrata e outras Notas de estudo em PDF para Matemática, somente na Docsity! Jaime Evaristo Eduardo Perdigão “INTRODUÇÃO Ã ALGEBRA ABSTRATA (Com aplicações à Ciência da Computação e o estudo do Sistema de Criptografia RSA) EuelidesDio fan te Fermat EratóstenesculerMersanne PitágorasWilsonBernoulliNewtonCauchy (é. gXx) = f(g(x)):se pl(a.b), então pla ou pib: Z - A a=b.q+r;6.4=0Oa+(b+c)=(a+b)+c; a=cbl+e b'+.+eb'+e, D+6; a =b mod n “Segunda Edição/Formato Digital/Versão 02.2012 Instituto de Computação - Universidade Federal de Alagoas to Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Jaime Evaristo Mestre em Matemática Professor Adjunto Instituto de Computação Universidade Federal de Alagoas Eduardo Perdigão Doutor em Matemática Professor Aposentado Instituto de Matemática Universidade Federal de Alagoas Introdução à Álgebra Abstrata Segunda Edição Formato Digital/Versão 02.2012 Maceió, fevereiro de 2012 2 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Prefácio (da primeira edição) Quem atua em processos de ensino/aprendizagem de matemática, fatalmente, já teve de ouvir a pergunta: por que se estuda Matemática? Além do fato dela permitir o exercício de algumas ações práticas do cidadão (como o gerenciamento de suas finanças, por exemplo) e a compreensão de alguns fenômenos relativos à sociedade (como a evolução de uma população, por exemplo), a Matemática fornece uma poderosa ferramenta simbólica que serve de suporte ao pensamento humano, explicitando intensidades, relações entre grandezas e relações lógicas, sendo, por este motivo e por excelência, a linguagem da Ciência. Além disto, o ato de estudar Matemática desenvolve o raciocínio do estudante e isto permite que ele seja capaz de compreender com mais facilidade os conceitos de outros ramos do conhecimento humano e as inter-relações entre estes conceitos. A Álgebra Abstrata, estabelecendo os seus fundamentos, é onde a linguagem matemática é definida e onde a compreensão dos conceitos, pelos seus níveis de abstração, requer o desenvolvimento de raciocínios que ajudarão na aprendizagem de outras ciências. O escopo deste livro é servir de livro-texto para uma disciplina inicial de Álgebra Abstrata e foi concebido de tal forma que não exige nenhum conhecimento anterior, podendo também ser lido por estudantes ou profissionais de outras áreas que pretendam ter uma ideia do que é Matemática. Para que o seu conteúdo seja autossuficiente, o livro contém a construção de todos os conjuntos numéricos, com exceção do Conjunto dos Números Complexos. Além disto, e considerando a sua importância nas aplicações, o livro apresenta um estudo detalhado dos números inteiros, discutindo suas propriedades, números primos, fatoração, etc. O livro também apresenta uma aplicação muito importante da álgebra abstrata à informática e uma amostra (naturalmente, num exemplo bem simples) de como se pode fazer pesquisa em Matemática, apresentando definições de conjuntos e de funções que não constam da literatura. Uma parte importante do livro são seus 121 exercícios propostos. Alguns têm o objetivo de fixar a aprendizagem; outros são acréscimos à teoria exposta. O estudante deve tentar exaustivamente solucionar todos eles, não procurando ver a solução que se apresenta ao menor sinal de dificuldade (as soluções de todas as questões estão disponíveis em www.ccen.ufal.br/jaime). O esforço que se realiza ao se tentar resolver um problema de matemática, bem sucedido ou não, é muito importante para o processo da aprendizagem. Os autores agradecem a Elizamar Batista dos Santos e a Alcineu Bazilio Rodrigues Júnior pela colaboração na digitação do livro e, antecipadamente, a todo leitor, estudante ou professor, que enviar qualquer crítica ou sugestão para jaime@ccen.ufal.br ou para perdigao@mat.ufal.br. Os autores também agradecem ao Professor Antônio Carlos Marques da Silva que emitiu parecer sobre o material do livro para apreciação do Conselho Editorial da EDUFAL e ao Professor Eraldo Ferraz, Diretor da citada editora pelo empenho em publicar esta obra. Maceió, julho de 2002 Jaime Evaristo Eduardo Perdigão 5 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Prefácio (da atual edição) Esta segunda edição é uma revisão bastante acurada do texto original, incluindo correções de erros de digitação e erros de conceitos, destaques de alguns conteúdos como novas seções, apresentação de novas demonstrações de proposições matemáticas e introdução, exclusão e reordenação de exercícios propostos, dentre outras modificações. Além de contar com as percepções de erros e sugestões dos meus alunos que utilizaram a primeira edição no período compreendido entre de 2002 e 2008, esta edição teve importante participação dos alunos do curso de Ciência da Computação e de Engenharia de Computação da Universidade Federal de Alagoas Ailton Felix de Lima Filho, Bruno Normande Lins, Emanuella Toledo Lopes, Erique Cavalcante Medeiros da Hora, Fernando Henrique Tavares Lima da Silva, Jônathas Magalhães Nunes, Kaio Cezar da Silva Oliveira, Michael Denison Lemos Martins, Michel Alves dos Santos, Wylken dos Santos Machado, Yuri Soares Brandão Vanderlei, Clenisson Calaça Cavalcante Gomes, Dielson Sales de Carvalho, Erick Diego Odilon de Lima, Everton Hercilio do Nascimento Santos, Fernanda Silva Bezerra de Albuquerque, Rafael Fernandes Pugliese de Moraes, Rafael Henrique Santos Rocha, Daniel Duarte Baracho, Diogo Felipe da Costa Carvalho, Gilton José Ferreira da Silva, Joao Pedro Brazil Silva, Kalline Nascimento da Nóbrega, Revanes Rocha Lins, Rodrigo Rozendo Bastos, Samuel das Chagas Macena, Sergio Rafael Tenório da Silva, Thiago Luiz Cavalcante Peixoto, Rafaele Sthefane Barbosa Oliveira, Lucas Lins de Lima, Fernando dos Santos Costa, Francisco Victor dos Santos Correia, Luciano de Melo Silva, Gustavo de Oliveira Gama, Ivo Gabriel Guedes Alves, Yuri Santos Nunes, Iago Barboza de Souza, Ísis de Sá Araújo Costa, Michael Gusmão Buarque Aliendro, Nicole Goulart Fonseca Acioli, Layane Nascimento de Araújo, Laysa Silva de Paula, Paulo Henrique Félix Barbosa, Evérton Borges da Silva, Gustavo de Oliveira Gama, Luciano Menezes da Costa, Tamirys Coelho de Oliveira Pino e Daniel San Ferreira da Rocha. Sem demérito para os demais, gostaria de ressaltar a participação bastante efetiva dos alunos Gerlivaldo Felinto da Silva e Leonildo de Mello Nascimento. Também gostaríamos de agradecer as participação do Professor Alcino Dall'Igna, que propiciou a inclusão da seção “Divisão por 2 em computadores”, e de Pedro Roberto de Lima, que nos indicou um erro (grave) na bibliografia. Sendo uma edição digital, correções e inclusões no texto podem ser feitas a qualquer momento. Assim, os autores agradecem a participação dos leitores no sentido da melhoria do livro (inclusive, com a inclusão de novos exercícios) e prometem registrar no livro estas participações. Toda e qualquer observação deve ser encaminhada para jaime@ccen.ufal.br, com o assunto LIVRO INTRODUÇÃO À ÁLGEBRA ABSTRATA. Maceió, fevereiro de 2012 Jaime Evaristo Eduardo Perdigão 6 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão 1. Conjuntos e Funções 1.1 Entes primitivos Segundo o Dicionário Aurélio, definir é enunciar os atributos essenciais e específicos de (uma coisa), de modo que a torne inconfundível com outra. Para que o objetivo de uma definição seja atingido, devem ser observados dois aspectos: uma definição só pode conter termos que foram definidos previamente e uma definição de um objeto não pode conter um termo cuja definição contenha referência ao próprio objeto. Exemplos claros de “definições” que pecam em relação ao segundo aspecto levantado são: um ponto é a interseção de duas retas e uma reta é um conjunto de pontos alinhados. Com estas “definições”, para se entender o que é um ponto seria necessário saber o que é uma reta e para compreender o que é uma reta é indispensável se saber o que é um ponto e o que são pontos alinhados. Em alguns livros de Matemática do ensino médio encontra-se a seguinte "definição" de conjunto: conjunto é uma coleção de objetos. O problema agora é que esta "definição" dá margem à seguinte pergunta: e o que é uma coleção de objetos? A resposta não poderia ser conjunto pois cairíamos no outro problema. Algumas ciências, como a Matemática e a Física, necessitam considerar entes, relações ou grandezas que não são definidos, ditas então entes primitivos, grandezas primitivas ou relações estabelecidas primitivamente. Por exemplo, ponto, reta e plano são entes primitivos da Geometria Euclidiana enquanto que o tempo, a distância e a massa são grandezas primitivas da Mecânica Newtoniana. Estabelecidos os entes primitivos de uma ciência, pode-se então se definir novos objetos, e a partir destes, definir-se novos outros objetos, e assim por diante. Por exemplo, a partir das grandezas físicas da Mecânica pode-se definir velocidade como o quociente entre a distância percorrida e o tempo gasto para percorrê-la implicando no fato de que velocidade não é uma grandeza primitiva. A partir da grandeza física não primitiva velocidade e da grandeza primitiva tempo pode-se definir aceleração como sendo a variação da velocidade na unidade de tempo. 1.2 Conjuntos Em Matemática, conjunto é um ente primitivo e portanto não é definido. Entendemos conjunto como uma coleção de objetos, no sentido coloquial do termo. Os objetos que compõem a coleção que está sendo considerada um conjunto são chamados elementos do referido conjunto. De um modo geral, conjuntos são representados por letras maiúsculas e seus elementos por letras minúsculas. Se A designa um conjunto e a é um dos elementos, dizemos que a pertence a A, isto sendo simbolizado por a ∈ A. Estabelecemos então, também de forma primitiva, a relação de pertinência entre um conjunto e seus elementos. Naturalmente, se um objeto não está na coleção que se está considerando como um conjunto dizemos que tal objeto não pertence ao tal conjunto, sendo utilizado o símbolo ∉ para negar a relação de pertinência. Introduzido o conceito primitivo de conjunto podemos apresentar um exemplo de um objeto da Matemática que é definido a partir dos entes primitivos ponto, reta, plano e conjunto e da grandeza primitiva distância: dados um plano α, um ponto p pertencente a α e um número real r, a circunferência de centro p, de raio r e contida no plano α é o conjunto dos pontos do plano α situados a uma distância r do ponto p. 1.3 Igualdade Na linguagem coloquial, dois objetos são ditos iguais quando são do mesmo tipo e têm a 7 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão serem iguais) é suficiente que A seja subconjunto de B e que B seja subconjunto de A. Assim podemos definir igualdade de conjuntos A e B por: A = B se e somente se A ⊂ B e B ⊂ A. Esta definição mostra que na representação de um conjunto pela exibição dos seus elementos a ordem (no sentido usual do termo) com que os elementos são exibidos não é utilizada para discriminar um conjunto. Assim os conjuntos A = {a, b, c} e B = {b, c, a} são iguais. A repetição da exibição de um elemento também não implica a diferenciação de um conjunto: os conjuntos A = {a, b, c} e B = {a, b, a, c, b} também são iguais. 1.8 Par ordenado e produto cartesiano Teremos necessidade de trabalhar com pares de elementos de dois conjuntos dados, considerados numa ordem preestabelecida. Daí necessitarmos da seguinte definição. Sejam A e B dois conjuntos e a e b elementos de A e de B, respectivamente. O par ordenado a b, indicado por (a, b), é o conjunto {{a}, {a, b}}. Naturalmente, os conjuntos A e B podem ser iguais, definindo-se então par ordenado de dois elementos de um mesmo conjunto. Nesse caso, podemos ter par do tipo (a, a). Evidentemente, (a, a) = {{a}}. Sobre pares ordenados é verdadeira a seguinte afirmação. Sejam A e B dois conjuntos e a, a’ ∈ A e b, b’ ∈ B. Temos que (a, b) = (a’, b’) se e somente se a = a’ e b = b’. De fato, se a = a’ e b = b’ temos {a} = {a’} e {a, b} = {a’, b’} o que implica {{a}, {a, b}} = {{a’}, {a’, b’}}. Suponhamos agora que (a, b) = (a’, b’). Se a = b, temos que os conjuntos A = {{a}}e A’ = {{a’}, {a’, b’}} são iguais o que só acontece se a' = b' = a. Se a ≠ b, temos {a’} ≠ {a, b} e a igualdade dos conjuntos A = {{a}, {a, b}} e A’ = {{a’}, {a’, b’}} implica {a} = {a’} e {a, b} = {a’, b’} o que acarreta a = a’ e b = b’. A veracidade desta afirmação, além de justificar a denominação par ordenado, permite que se distinga os elementos que compõem o par (a, b): a é a primeira componente e b é a segunda componente. Uma afirmação verdadeira sobre um ente matemático é chamada de propriedade daquele ente. Assim, a afirmação “(a, b) = (a’, b’) se e somente se a = a’ e b = b’“ é uma propriedade dos pares ordenados. De um modo geral, fatos matemáticos verdadeiros são chamados propriedades. O produto cartesiano de dois conjuntos A e B, indicado por AxB, é o conjunto dos pares ordenados com primeiras componentes no conjunto A e segundas componentes no conjunto B. Por exemplo, se A = {a, c, d} e B = {e, f}, o produto cartesiano de A por B é o conjunto AxB = {(a, e), (a, f), (c, e), (c, f), (d, e), (d, f)} e o produto cartesiano de B por A é o conjunto BxA = {(e, a), (e, c), (e, d), (f, a), (f, c), (f, d)}, exemplo que já mostra que, de um modo geral, AxB ≠ BxA. É comum se utilizar a notação A2 para representar o produto cartesiano AxA. Assim, no exemplo acima temos B2 = {(e, e), (e, f), (f, f), (f, e)} e A2 = {(a, a), (a, c), (a, d), (c, a), (c, c), (c, d), (d, a), (d, c), (d, d)}. 1.9 Relações binárias Em muitas situações, é necessário e útil relacionar (no sentido usual do termo) elementos de um ou de dois conjuntos. Esta relação pode ser estabelecida através dos pares ordenados que se pretende relacionar. Se A e B são dois conjuntos, qualquer subconjunto do produto cartesiano AxB é chamado de uma relação binária entre A e B. Ou seja, uma relação binária entre dois conjuntos A e B é um conjunto de pares ordenados com primeiras componentes em A e segundas componentes em 10 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão B. Quando os conjuntos A e B são iguais uma relação entre A e B é dita simplesmente uma relação em A. Por exemplo, se A é o conjunto das vogais e B é o conjunto das consoantes os conjuntos R = {(a, b), (e, f), (i, j), (o, p), (u, v)}, S = {(a, x), (e, g), (i, b)} e T = {(e, m), (i, z)} são relações binárias entre A e B (ou de A em B). Normalmente, há interesse apenas em relações binárias em que as componentes dos pares guardem entre si alguma relação, no sentido usual do termo. Em outros termos, estamos interessados em relações em que haja uma regra para obtenção dos pares da relação, regra esta que permita que se defina se um dado par está ou não na relação. Nos exemplos acima, a relação R satisfaz a esta condição pois cada segunda componente é a consoante que sucede a vogal primeira componente. As componentes dos pares das outras relações dos exemplos não guardam nenhuma relação entre si e, portanto, não são relevantes. Utilizando uma barra vertical significando tal que, pode-se representar uma relação entre dois conjuntos por R = {(x, y) ∈ AxB| ...}, onde em … é colocada a regra que estabelece a relação entre x e y. Muitas vezes, associa-se um símbolo a uma relação definida num conjunto A. Neste caso, se o símbolo da relação é #, a indicação de que um par (a, b) pertence à relação é feita por a # b. Observe que em R = {(x, y) ∈ AxB| …} o símbolo x está sendo usado para representar todos os elementos do conjunto A e que y está sendo utilizado para representar todos os elementos do conjunto B. Neste caso dizemos que os símbolos x e y são indeterminadas ou variáveis dos conjuntos referidos. Uma relação definida num conjunto A pode ser adjetivada de acordo com algumas propriedades que ela satisfizer. Dizemos que uma relação R num conjunto A é: •reflexiva se (x, x) ∈ R qualquer que seja x ∈ A. •simétrica se (x, y) ∈ R implicar (y, x) ∈ R, quaisquer que sejam x, y ∈ A. •antissimétrica se não acontece (x, y) ∈ R e (y, x) ∈ R com x ≠ y, quaisquer que sejam x, y ∈ A. •transitiva se (x, y) ∈ R e (y, z) ∈ R acarretar (x, z) ∈ R, quaisquer que sejam x, y, z ∈ A. •total se quaisquer que sejam x, y ∈ A, (x, y) ∈ R e/ou (y, x) ∈ R, onde o "e/ou" indica que podem ocorrer as duas pertinências ou apenas uma delas. As definições anteriores estabelecem quando o adjetivo respectivo pode ser aplicado a uma relação binária. Como fizemos com a definição de subconjunto, é interessante observar as condições mínimas que negam as definições anteriores e, portanto, tal adjetivo não pode ser associado à relação. Com o desenvolvimento de um raciocínio simples, temos que uma relação R num conjunto A •não é reflexiva se existe x ∈ A tal que (x, x) ∉ R. •não é simétrica se existem x, y ∈ A tais que (x, y) ∈ R e (y, x) ∉ R. •não é antissimétrica se existem x, y ∈ A, com x ≠ y, tais que (x, y) ∈ R e (y, x) ∈ R. •não é transitiva se existem x, y, z ∈ A tais que (x, y) ∈ R e (y, z) ∈ R e (x, z) ∉ R. •não é total se existem x, y ∈ A tais que (x, y) ∉ R e (y, x) ∉ R. Por exemplo, se A é o conjunto das vogais, a relação R = {(a, a), (e, e), (i, i), (o, o), (u, u), (a, e), (a, i), (a, u), (e, a), (e, i), (e, u), (u, i)} é reflexiva, não é simétrica ((a, u) ∈ R e (u, a) ∉ R), não é antissimétrica ((a, e) ∈ R, (e, a) ∈ R e a ≠ e), é transitiva e não é total ((a, o) ∉ R e (o, a) ∉ R). Outro exemplo: seja A é o conjunto das vogais e consideremos a relação {(x, y) ∈ AxA|y = x}. Como cada vogal só é igual a ela mesma, os pares desta relação são (a, a), (e, e), (i, i), (o, o) e (u, 11 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão u). Observe que as afirmações estabelecidas na seção 1.3 implicam que a igualdade de objetos matemáticos é reflexiva, simétrica e transitiva. Para um outro exemplo, considere o conjunto das partes de um conjunto A definido como o conjunto de todos os subconjuntos de A e indicado por ℘(A). Como os elementos de ℘(A) são conjuntos cujos elementos são elementos do conjunto A, podemos definir a relação (chamada inclusão) I = {(X, Y) ∈ ℘(A)x℘(A) | X ⊂ Y}. As propriedades apresentadas na seção 1.4 mostram que esta relação é reflexiva e transitiva. A definição de igualdade de conjuntos garante que a inclusão é antissimétrica. Uma relação que é reflexiva, simétrica e transitiva é dita uma relação de equivalência enquanto que uma relação que é reflexiva, antissimétrica, transitiva é dita uma relação de ordem parcial. Uma relação de ordem parcial que é total é dita uma relação de ordem. A igualdade de objetos matemáticos é uma relação de equivalência. A inclusão de conjuntos não é uma relação de equivalência (pois não é simétrica), mas é uma relação de ordem parcial. Se uma relação R, com símbolo #, é transitiva, x # y e y # z implicam x # z. Isto permite que se escreva, neste caso, x # y # z. Por exemplo, se A é o conjunto das vogais, X = {a, e}, Y = {a, e, i} e Z = {a, e, i, o}, temos X ⊂ Y ⊂ Z. 1.10 Funções Estamos agora interessados em relações entre dois conjuntos A e B em que cada elemento de A esteja relacionado com um único elemento de B. Uma relação que satisfaz a esta propriedade é chamada função, definida formalmente como segue. Sejam A e B dois conjuntos. Uma função de A em B é uma relação binária f entre A e B tal que para cada x ∈ A existe um único y ∈ B tal que (x, y) ∈ f. Assim, para que uma relação binária f entre dois conjuntos A e B seja uma função de A em B é necessário e suficiente que para todo x ∈ A exista y ∈ B tal que (x, y) ∈ f e que se (x, y1) ∈ f e (x, y2) ∈ f então y1 = y2. Por exemplo, se A é o conjunto das vogais e B é o conjunto das consoantes, a relação entre A e B dada por f = {(a, b), (e, f), (i, j), (o, p), (u, v)} é uma função de A em B. Por outro lado, se A = {a, b, c}, a relação I = {(X, Y) ∈ ℘(A)x℘(A)| X ⊂ Y} não é uma função de ℘(A) em ℘(A) pois ({a}, {a, b}) ∈ I e ({a}, {a, c}) ∈ I e como {a, b} ≠ {a, c}, o elemento X = {a} estaria relacionado com Y1 = {a, b} e Y2 = {a, c}. Como já vimos fazendo, utilizaremos letras minúsculas f, g, h, etc., para representar funções e escreveremos y = f(x), para indicar que (x, y) ∈ f. Neste caso diremos que y é a imagem do objeto x pela função f. No futuro, usaremos também cadeia de caracteres para indicar funções. Se f é uma função de um conjunto A em um conjunto B, o conjunto A é chamado domínio e o conjunto B é chamado contradomínio de f. O subconjunto do contradomínio cujos elementos são imagens de objetos é chamado imagem da função, indicada por f(A). Uma função de A em B dada por y = f(x) pode ser indicada por f : A → B x → f(x). Nesse caso, y = f(x) fixa a regra que será utilizada para se associar um único y ∈ B a cada x ∈ A. Nada impede que a regra que associa uma única imagem a cada objeto seja constituída de várias sub-regras, de acordo com os diversos valores dos objetos. Por exemplo, se A é o alfabeto podemos definir a função g de A em A por g(x) = a, se x = z e g(x) é a letra sucessora de x se x ≠ z. Num caso como este, pode-se utilizar expressões como caso contrário, senão, em outra hipótese para indicar as situações em que a última sub-regra será aplicada. Isto será utilizado na seção 1.13. É importante verificar se uma pretensa definição define realmente uma função, caso em que se diz que a função está bem definida. Naturalmente, para que uma função f esteja bem definida é 12 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão A referência a cada uma destas propriedades é feita, de maneira óbvia, como comutatividade, associatividade, existência de elemento neutro. Observe que se uma operação o possuir, o elemento neutro é único. De fato, se e' e e” são elementos neutros de uma operação #, temos e' # e” = e” # e' = e', pois e” é elemento neutro e e” # e' = e' # e” = e”, pois e' é elemento neutro, implicando então, pela transitividade da igualdade, e' = e”. Portanto se encontrarmos um elemento neutro de uma operação ele é o elemento neutro desta operação. A operação no conjunto das vogais definida acima é comutativa e possui elemento neutro, u. Embora seja bastante enfadonho (teria que se verificar que x + (y + z) = (x + y) + z para todos os casos) é fácil mostrar que a operação também é associativa. Por exemplo, a + (e + o) = a + a = e que, como já foi visto, é igual a (a + e) + o. Numa operação associativa, não há a necessidade da colocação de parênteses. Se # é o operador de uma operação associativa, como a # (b # c) = (a # b) # c, podemos indicar a # (b # c) por a # b # c, como se estivesse operando três operandos. Esta flexibilização da notação se estende também quando há “mais de três operandos”. Quando há mais de dois operandos (e a operação é associativa, lembremo-nos), o mais prático é determinar o resultado da operação dos dois primeiros, operar este resultado com o próximo operando e, assim, sucessivamente. No exemplo acima temos, por exemplo, e + o + a + i = a + a + i = e + i = u. Além da comutatividade, associatividade e existência de elemento neutro, uma operação pode ser adjetivada em relação à outra operação. Se # e * são operações definidas num conjunto A, dizemos que # é distributiva em relação à * se a # (b * c) = (a # b) * (a # c), quaisquer que sejam a, b, c ∈ A. Esta propriedade é referida como distributividade de # em relação à *. Na notação prefixa a distributividade seria assim fixada: sejam f e g duas operações num conjunto A. A operação f é distributiva em relação à operação g se f(a, g(b, c)) = g(f(a, b), f(a, c)), quaisquer que sejam a, b, c ∈ A. À medida que formos apresentando as operações, discutiremos quais propriedades elas possuem e apresentaremos exemplos destas propriedades. 1.13 Operações com predicados (operações lógicas) As primeiras operações que discutiremos são as operações onde os operandos são predicados. Como veremos, as operações com predicados (também chamadas operações lógicas) permitem o estabelecimento de uma linguagem que facilita sobremaneira o discurso matemático. Dado um conjunto não vazio A, representemos por Pred(A) o conjunto dos predicados em A. Ou seja, Pred(A) é o conjunto de todas as funções de A no conjunto de Boole {V, F}. Pelo conceito de operação, para se definir uma operação em Pred(A) devemos associar a cada par de predicados de Pred(A) um outro predicado de Pred(A). Como já foi dito, para se definir um elemento de Pred(A) basta se estabelecer as imagens dos elementos de A em {V, F}. Temos as seguintes operações, considerando p, q ∈ Pred(A). •Conjunção (operador: ∧, denominação: e ) (p ∧ q)(x) = V se p(x) = q(x) = V. Isto é, a conjunção de dois predicados p e q será verdadeira quando e somente quando os dois predicados o forem. Daí a denominação e para o operador ∧,, indo ao encontro da linguagem coloquial: se o/a chefe da família anuncia “nas férias viajaremos para Maceió e Natal”, ele está afirmando que a família viajará para as duas cidades. Como a igualdade é uma relação simétrica (por exemplo, se p(x) = q(x) = V então q(x) = p(x) = V), a conjunção é comutativa. Ela também é associativa: se p, q e r são predicados em 15 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão A, por um lado ((p ∧ q) ∧ r)(x) = V se (p ∧ q)(x) = r(x) = V o que só acontece se p(x) = q(x) = r(x) = V e por outro lado (p ∧ (q ∧ r))(x) = V se p(x) = (q ∧ r)(x) = V o que só acontece também se p(x) = q(x) = r(x) = V. Claramente, uma tautologia τ é o elemento neutro da conjunção. •Disjunção (operador: ∨, denominação: ou) (p ∨ q)(x) = F se p(x) = q(x) = F. Isto é, a disjunção de dois predicados p e q é verdadeira se e somente se um dos predicados for verdadeiro ou se ambos forem verdadeiros. Observe agora que a denominação ou para o operador ∨ não corresponde exatamente ao uso da conjunção ou na linguagem comum: se o/a chefe da família anuncia “nas férias viajaremos para Maceió ou Natal”, ele está afirmando que a família viajará para apenas uma das duas cidades. Dizemos que o ou da Matemática é inclusivo, enquanto que o ou da linguagem coloquial é exclusivo. Embora os dicionários não apresentem esta possibilidade, é relativamente comum se usar e/ou na linguagem coloquial quando se pretende se expressar um “ou inclusivo”. Às vezes, a Matemática ao utilizar um vocábulo modifica (quase sempre, ligeiramente) o seu significado. Surge então a linguagem matemática, muito útil para o mundo científico. Daqui para frente, a conjunção ou utilizada em afirmações matemáticas terá sempre o sentido inclusivo. Dessa forma, o conceito de totalidade de uma relação, discutido na seção 1.9, pode ser escrito: uma relação binária num conjunto A é total se quaisquer que sejam x, y ∈ A, com x ≠ y, (x, y) ∈ R ou (y, x) ∈ R. Como a conjunção, a disjunção é claramente comutativa e associativa e seu elemento neutro é uma contradição γ. O exercício 1.5 pedirá para ser demonstrado que a conjunção é distributiva em relação à disjunção e que esta é distributiva em relação àquela. •Implicação (operador ⇒ , denominação: implica) (p ⇒ q)(x) = F se p(x) = V e q(x) = F. O predicado p ⇒ q também pode ser lido se p, então q e quando p e q são verdadeiros tem a conotação dada na seção 1.6. Observe que p ⇒ q só é falso se p é verdadeiro e q é falso. Assim, ao contrário da linguagem comum, na qual implicar é utilizado numa relação de causa e efeito, em Matemática uma mentira implica uma verdade e implica também outra mentira. O exemplo a seguir mostra que o significado matemático do se então, embora inusitado, tem sentido também no nosso dia a dia. Imagine a seguinte situação: (1) uma jovem adolescente está se preparando, com afinco, para fazer o vestibular para um curso superior; (2) para incentivá-la na reta final, o pai da adolescente, a dois meses do certame, adquire um automóvel e anuncia para ela: se você for aprovada, então este automóvel será seu. Após a divulgação do resultado do vestibular, se a filha foi aprovada (p verdade) e recebeu o carro (q verdade), a afirmação do pai se tornou verdadeira (p ⇒ q verdade); se a filha foi aprovada (p verdade) e não recebeu o carro (q falso), a afirmação do pai se tornou falsa (p ⇒ q falso); se a filha não foi aprovada (p falso) e não recebeu o carro (q falso), o pai não descumpriu a promessa (p ⇒ q verdade); finalmente, se a filha não foi aprovada (p falso) e recebeu o carro (q verdade), a afirmação do pai também não se tornou falsa e, portanto p ⇒ q é verdadeiro (nesse caso, o pai pode ter entendido que a filha, mesmo não tendo sido aprovada, merecia o prêmio – foi a primeira dos não aprovados, por exemplo). Como p ⇒ q só é falso se p é verdadeiro e q é falso, a demonstração de uma assertiva do tipo “se p, então q” pode ser feita supondo-se que p é verdade e provando que, a partir daí, q também o é. Normalmente, o predicado p é chamado hipótese (que é o que se supõe ser verdadeiro) e o predicado q é chamado tese (que é o que se quer provar que é verdadeiro). 16 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão •Equivalência (operador ⇔ , denominação: equivale) (p ⇔ q)(x) = V se p(x) = q(x). O predicado p ⇔ q também é referenciado como p se e somente se q e tem a mesma conotação dada à expressão se e somente se discutida na seção 1.6. É fácil ver que uma equivalência pode ser obtida a partir de uma conjunção de implicações, reiterando o que foi dito na referida seção. Na verdade temos a seguinte igualdade: p ⇔ q = ( p ⇒ q) ∧ ( q ⇒ p). A demonstração de uma igualdade de predicados é bastante simples (embora, às vezes, tediosa). Como são funções, para que dois predicados r e s sejam iguais basta que eles tenham o mesmo domínio (no nosso caso, conjunto A), o mesmo contradomínio (sempre {V, F}) e para cada x de A se tenha r(x) = s(x). Basta então mostrar a igualdade r(x) = s(x), para todo x ∈ A, o que pode ser feito através de uma tabela (chamada tabela verdade) na qual se determina todos os possíveis valores de r(x) e s(x). Para mostrar que r = p ⇔ q e s = ( p ⇒ q) ∧ ( q ⇒ p) são iguais, temos p q p ⇒ q q ⇒ p p ⇔ q ( p ⇒ q) ∧ ( q ⇒ p) V V V V V V V F F V F F F V V F F F F F V V V V Da igualdade p ⇔ q = ( p ⇒ q) ∧ ( q ⇒ p), segue que uma afirmação do tipo q se e somente se p pode ser demonstrada supondo que p é verdade e provando que, a partir daí, q também é e, reciprocamente, supondo que q é verdade e provando que, a partir daí, p também é. 1.14 Demonstração por redução ao absurdo (prova por contradição) Como foi dito na seção anterior, a demonstração de uma assertiva matemática do tipo “se p, então q” pode ser feita supondo-se que p é verdade e provando que, a partir daí, q também o é. Nesta seção, apresentaremos duas outras maneiras de se demonstrar afirmações da forma “se p, então q”, ambas chamadas demonstração por redução ao absurdo ou prova por contradição. Para isto, consideremos a seguinte definição. A negação de um predicado p é o predicado indicado por ~p tal que (~p)(x) = F se p(x) = V. Como é fácil provar que (ver exercício 1.9) se p e q são predicados num conjunto A, tem-se (p ⇒ q) = ((~q) ⇒ (~p)), uma outra forma de se provar uma afirmação matemática do tipo “se p, então q” é supor que q é falso e concluir, a partir daí, que p também o é. Ou seja, para provar que “uma hipótese implica uma tese” pode-se demonstrar que a negação da tese implica a negação da hipótese. Por exemplo, para demonstrar que o conjunto vazio é subconjunto de qualquer conjunto (ver seção 1.11), suponhamos que exista um conjunto A tal que ∅ ⊄ A (negação da tese). Daí teríamos que existe um elemento do conjunto ∅ que não pertence ao conjunto A. Porém, a existência de um elemento de ∅ negaria a hipótese (∅ é vazio). Também é fácil provar (ver exercício 1.10) que (p ⇒ q) = ((p ∧ (~q)) ⇒ γ), onde p e q são predicados num conjunto A e γ é uma contradição. Assim, também se pode provar uma afirmação da forma “se p, então q”, provando-se que a veracidade da hipótese e a negação da tese implicam uma contradição. Isto demonstra que a veracidade da hipótese implica a veracidade da tese. 1.15 Operações com conjuntos 17 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Por exemplo, se A é o conjunto das vogais, a função f ∈ ℑ(A), f = {(a, e), (e, i), (i, o), (o, u), (u, a)} é inversível e f -1 = {(e, a), (i, e), (o, i), (u, o), (a, u)}. De fato, (f ° f -1)(a) = f (f -1(a))= f(u) = a, (f ° f -1)(e) = f (f -1(e)) = f(a) = e, (f ° f -1)(i) = f (f -1(i)) = f(e) = i, (f ° f -1)(o) = f (f -1(o)) = f(i) = o, (f ° f -1)(u) = f (f -1(u)) = f(o) = u, o que mostra que f ° f -1 = IA. Como também (o que é muito fácil verificar) f -1 ° f = IA, temos que f é inversível. Por seu turno, a função g de ℑ(A), g = {(a, u), (e, u), (i, u), (o, u), (u, u)} não é inversível pois para que (g-1 ° g)(a) = a e (g-1 ° g)(e) = e dever-se-ia ter g-1(u) = a e g-1(u) = e e g-1 não seria uma função. O conceito de inversibilidade de função pode ser facilmente generalizado para as funções do conjunto ℑ(A, B), dados dois conjuntos A e B. Dizemos que uma função f ∈ ℑ(A, B) é inversível se existe uma função g ∈ ℑ(B, A) tal que f ° g = IB e g ° f = IA. Neste caso, e como acima, diz-se que g é a função inversa de A e indica-se g por f -1. Por exemplo, se A é o conjunto das vogais e B = {b, c, d, f, g}, a função f = {(a, b), (e, c), (i, d), (o, f), (u, g)} é claramente inversível e f -1 = {(b, a), (c, e), (d, i), (f, o), (g, u)}. Observe que f ∈ ℑ(A, B) é inversível, então f -1 é única. De fato, se g1 e g2 são inversas de f temos g1 = IA ° g1 = (g2 ° f) ° g1 = g2 ° (f ° g1) = g2 ° IB = g2, onde utilizamos a observação do final da seção anterior e as igualdades f ° g1 = IB e g2 ° f = IA decorrentes da hipótese de que g1 e g2 eram inversas de f. Além de f –1 ser única ela também é inversível pois, sendo f ° f -1 = IB e f -1 ° f = IA, temos que (f -1)-1 = f. Nos exemplos apresentados, concluímos a inversibilidade ou não de uma função procurando a sua função inversa. Vamos mostrar uma forma de analisar a inversibilidade de uma função sem nos preocuparmos com a inversa (na maioria das vezes, além de precisarmos apenas saber se a função é inversível, a determinação da inversa de uma função não é tarefa simples). Para isso, necessitamos de algumas definições. Uma função f ∈ ℑ(A, B) é dita injetiva (ou injetora ou uma injeção) se x1 ≠ x2 implicar f(x1) ≠ f(x2). Em outros termos, numa função injetiva objetos diferentes têm sempre imagens diferentes. Ou ainda, numa função injetiva de ℑ(A, B) não existe elemento de B que seja imagem de dois objetos distintos. Portanto, se f é injetiva e f(x1) = f(x2), então x1 = x2, o que é uma outra forma de se caracterizar a injetividade. Por exemplo, se A é o conjunto das vogais e B = {b, c, d, f, g}, a função f = {(a, b), (e, c), (i, d), (o, f), (u, g)} é claramente injetiva enquanto que a função g = {(a, b), (e, b) , (i, d), (o, d), (u, g)} não o é, pois g(a) = g(e). Obviamente, se g é uma restrição de f ∈ ℑ(A, B) a um subconjunto de A e f é injetora, então g também é injetora. Uma função f ∈ ℑ(A, B) é dita sobrejetiva (ou sobrejetora ou sobre ou, ainda, uma sobrejeção) se f(A) = B. Em outros termos, uma função é sobrejetiva se todo elemento do contradomínio é imagem de algum objeto. A função f do exemplo anterior é sobrejetiva enquanto que a função g não o é, pois c ∉ g(A). Uma função f ∈ ℑ(A, B) é dita bijetiva (ou bijetora ou uma bijeção) se ela é simultaneamente injetora e sobrejetora. Uma propriedade das funções bijetivas que será útil posteriormente é a seguinte: Sejam X e Y dois conjuntos, a um elemento de X e b um elemento de Y. Se existir uma função bijetiva f de X em Y, com b ≠ f(a), então existe uma função bijetiva g de X em Y tal que g(a) = b. 20 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão De fato, como f é sobrejetiva e b é um elemento de Y, existe a' ∈ X tal que b = f(a'). Se definirmos g de X em Y por g(a) = b, g(a') = b', com b' = f(a), e g(x) = f(x) se x ≠ a e x ≠ a', temos que g é bijetiva, pois a única diferença entre f e g está no fato de que (a', b), (a, b') ∈ f enquanto (a', b'), (a, b) ∈ g. A inversibilidade de uma função pode ser verificada sem que se determine a sua inversa, como mostra a seguinte propriedade. Uma função f ∈ ℑ(A, B) é inversível se e somente se f é bijetiva. Para provar, suponhamos inicialmente que f é bijetora e provemos que f é inversível. Seja g a função de B em A definida por g(y) = x, onde x é tal que f(x) = y. Como f é sobrejetora, para todo y ∈ B existe x ∈ A tal que y = f(x). Além disso, este x é único pois f é injetiva. Assim g está bem definida (ou seja, é realmente uma função) e (f ° g)(y) = f(g(y)) = f(x) = y, o que mostra que f ° g = IB, e (g ° f)(x) = g(f(x)) = g(y) = x, o que mostra que g ° f = IA. Assim f é inversível. Reciprocamente, suponhamos que f é inversível e provemos que f é bijetiva. Para mostrar que f é injetiva, suponhamos x1, x2 ∈ A com f(x1) = f(x2). Temos f -1(f(x1)) = f -1(f(x2)) e portanto x1 = x2, provando o que queríamos. Para provar que f é sobrejetiva, seja y ∈ B e provemos que existe x ∈ A tal que y = f(x). Como existe a função f -1, temos que existe x ∈ A tal que x = f -1(y) e então f(x) = f(f -1(y)) = IB(y) = y, concluindo o que queríamos provar. Observe que uma função bijetiva de um conjunto A num conjunto B e sua inversa (de B em A) estabelecem uma correspondência entre os elemento dos dois conjuntos: cada elemento a de A é relacionado com um único elemento b de B (através da função f) que, por sua vez, é associado, de maneira única, ao elemento a de A (através da inversa de f). Dizemos então que uma função bijetiva de um conjunto em outro conjunto estabelece uma correspondência biunívoca ou uma correspondência um a um entre os dois conjuntos. 1.18 Exercícios 1.1. Verifique se cada uma das relações abaixo, definidas no conjunto de habitantes da terra (com os significados usuais da linguagem coloquial), é reflexiva, simétrica, transitiva ou total. a) “x é primo de y”. b) “x é filho de y” c) “x ama y”. 1.2. Verifique se a relação “x é chefe de y”, definida no conjunto dos funcionários da Universidade Federal de Alagoas (com o significado usual da linguagem coloquial), é reflexiva, simétrica, transitiva ou total. 1.3. Dê um exemplo de uma relação binária definida no conjunto A = {a, b, c} que não seja reflexiva, seja simétrica e transitiva e não seja total. 1.4. Apresente um contraexemplo que mostre que a afirmação “se R é uma relação simétrica e transitiva, então R é reflexiva” é falsa. 1.5. Mostre que se p, q e r são predicados num conjunto A, então a) p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r) (isto é, a conjunção é distributiva em relação à disjunção) b) p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r) (isto é, a disjunção é distributiva em relação à conjunção) 1.6. Mostre que se p é um predicado num conjunto A, então a) p ∧ (~p) = γ. b) p ∨ (~p) = τ. 1.7. Prove as leis de Morgan: se p e q são predicados num conjunto A então a) ~(p ∧ q) = (~p) ∨ (~q). 21 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão b) ~(p ∨ q) = (~p) ∧ (~q) 1.8. Sejam p e q predicados num conjunto A. Mostre que (p ⇒ q) = (~p) ∨ q. 1.9. Sejam p e q predicados num conjunto A. Mostre que (p ⇒ q) = ((~q) ⇒ (~p)). 1.10. Sejam p e q predicados num conjunto A e γ uma contradição. Mostre que (p ⇒ q) = ((p ∧ (~q)) ⇒ γ). 1.11. Sejam um universo U e A, B, C subconjuntos quaisquer de U. Mostre que a) (A ∪ B) ∪ C = A ∪ (B ∪ C) (isto é, a união de conjuntos é associativa) b) A ∩ B ⊂ A c) (A ∩ B) ∩ C = A ∩ (B ∩ C) (isto é, a interseção de conjuntos é associativa) d) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (isto é, a interseção de conjuntos é distributiva em relação à união) e) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (isto é, a união de conjuntos é distributiva em relação à interseção) 1.12. Encontre contraexemplos que neguem as seguintes afirmações. a) Se A ∪ B = A ∪ C então B = C b) Se A ∩ B = A ∩ C então B = C 1.13. Mostre que se A ∪ B = A ∪ C e A ∩ B = A ∩ C então B = C. 1.14. Quando A ⊂ B a diferença B - A é chamada complementar de A em relação a B, indicada por CB(A). Mostre que, se A, A’ ⊂ B a) CB(CB(A)) = A b) Se CB(A’) ⊂ CB(A) então A ⊂ A’ c) CB(A ∩ A’) = CB(A) ∪ CB(A’) 1.15. Sejam A e B dois conjuntos e f uma função de A em B. Se X é um subconjunto de A a imagem direta de X pela função f é o conjunto f(X) = {y ∈ B| y = f(x) para algum x ∈ A}. Seja Y outro subconjunto de A. Mostre que a) Se X ⊂ Y então f(X) ⊂ f(Y) b) f(X ∪ Y) = f(X) ∪ f(Y) c) f(X ∩ Y) ⊂ f(X) ∩ f(Y) d) Encontre um contraexemplo que mostre que f(X ∩ Y) ≠ f(X) ∩ f(Y) e) f(X - Y) ⊃ f(X) - f(Y) f) Encontre um contraexemplo que mostre que f(X - Y) ≠ f(X) - f(Y) 1.16. Sejam A e B dois conjuntos e f uma função de A em B. Se Y é um subconjunto de B a imagem inversa de Y pela função f é o conjunto f -1(Y) = {x ∈ A| f(x) ∈ Y}. Seja Z outro subconjunto de A. Mostre que a) Se Y ⊂ Z então f -1(Y) ⊂ f -1(Z) b) f -1(Z ∪ Y) = f -1(Z) ∪ f -1(Y) c) f -1(Z ∩ Y) = f -1(Z) ∩ f -1(Y) d) f -1(X - Y) = f -1(X) - f -1(Y) 1.17. Sejam A, B e C três conjuntos, f uma função de A em B e g uma função de B em C. Mostre que a) Se f e g são injetoras, então g ° f é injetora b) Se f e g são sobrejetoras, então g ° f é sobrejetora c) Se f e g são bijetoras, então g ° f é bijetora d) Se g ° f é injetora, então f é injetora e) Se g ° f é injetora e f é sobrejetora, então g é injetora f) Se g ° f é sobrejetora, então g é sobrejetora g) Se g ° f é sobrejetora e g é injetora então f é sobrejetora h) Se f é bijetora, então f -1 é bijetora 22 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão então p é uma tautologia em ℕ. Observe que o segundo axioma implica que ℕ ≠ ∅ e que s(1) ≠ 1. Assim, ℕ possui elementos diferentes de 1. Representando por 2 (chamado dois) o natural s(1) e por 3 (chamado três) o natural s(2), temos que 3 ≠ 2, pois se s(2) = 2, s não seria injetiva já que s(1) = 2. Na verdade, provaremos adiante que temos s(n) ≠ n, qualquer que seja n ∈ ℕ. Utilizando as representações estabelecidas acima, representaremos o conjunto dos números naturais por ℕ = {1, 2, 3,...}, onde as reticências "substituem" s(3) = 4 (quatro), s(4) = 5 (cinco), s(5) = 6 (seis), s(6) = 7 (sete), s(7) = 8 (oito), s(8) = 9 (nove), s(9) = 10 (dez), s(10) = 11 (onze), s(11) = 12 (doze) e, assim, sucessivamente. O fato de utilizarmos o símbolo 1 repetido para representar o natural onze será explicado no capítulo 5. Observe ainda que este axioma implica que todo elemento n ∈ ℕ, n ≠ 1, é sucessor de um natural m. Este natural m é chamado antecessor de n e é indicado por n – 1 (como veremos adiante, o sucessor de n é indicado n + 1). Observe também que s(n – 1) = n. O terceiro axioma é chamado princípio da indução e pode ser utilizado para demonstrar afirmações sobre números naturais: para se demonstrar uma afirmação sobre os números naturais, basta se provar que a afirmação é verdadeira para 1 e que se for verdadeira para um natural k, sê-lo- á para o natural s(k). A condição (i) é chamada base da indução e a assunção p(n) = V é chamada hipótese de indução. Como mostra a proposição a seguir, o princípio da indução pode ser enunciado de uma outra forma. Proposição 1.2 O princípio da indução é equivalente à seguinte propriedade: Se A é um subconjunto de ℕ tal que 1 ∈ A e n ∈ A implica s(n) ∈ A, então A = ℕ. Demonstração Provemos inicialmente que o princípio da indução implica a propriedade acima. Para isto, seja A um subconjunto de ℕ tal que 1 ∈ A e n ∈ A implica s(n) ∈ A. Considere o predicado p em ℕ definido por p(x) = V se e somente se x ∈ A. De 1 ∈ A temos que p(1) = V e de n ∈ A implica s(n) ∈ A temos que p(n) = V implica p(s(n)) = V. Assim, pelo princípio da indução, p é uma tautologia em ℕ e, portanto, n ∈ A para todo n ∈ ℕ. Logo A = ℕ. Provemos agora que a propriedade acima implica o princípio da indução. Seja então um predicado p em ℕ tal que p(1) = V e se p(k) = V, então p(s(k)) = V. Considere o conjunto A = {x ∈ ℕ| p}. De p(1) = V segue que 1 ∈ A e de p(k) = V implica p(s(k)) = V segue que n ∈ A implica s(n) ∈ A. Assim, pela propriedade, A = ℕ e p é uma tautologia em ℕ. 2.3 Operações no conjunto dos números naturais Em ℕ definimos as seguintes operações, considerando n e m números naturais: Adição (operador: +, denominação: mais) a) n + 1 = s(n); b) n + (m + 1) = s(n + m). Multiplicação (operador: . ou ×, denominação: vez(es)) a) n . 1 = n; b) n . (m + 1) = n . m + n. Observe que, de acordo com o item a da definição da adição, os itens b podem ser escritos: 25 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão n + s(m) = s(n + m) e n . s(m) = n . m + n. É necessário se provar que estas operações são, de fato, operações em ℕ. Isto é, é necessário provar que se m, n ∈ ℕ, então n + m ∈ ℕ e n . m ∈ ℕ. Para demonstrar a primeira afirmação, seja n ∈ ℕ e consideremos o predicado em ℕ definido por p(m) = V se n + m ∈ ℕ. Temos que p(1) = V, pois n + 1 = s(n) e s é uma função de ℕ em ℕ. Além disso, se p(m) = V, temos n + m ∈ ℕ e então, como n + s(m) = n + (m + 1) = s(n + m), temos p(s(m)) = V, pois, novamente, s é uma função de ℕ em ℕ. Evidentemente, este raciocínio pode se aplicar à multiplicação. Exemplos a) 1 + 1 = s(1) = 2. b) 2 + 1 = s(2) = 3. c) 1 + 2 = 1 + (1 + 1) = s(1 + 1) = s(2) = 3. d) 2 + 2 = 2 + (1 + 1) = s(2 + 1) = s(3) = 4. e) 1 × 2 = 1 × (1 + 1) = 1 × 1 + 1 = 1 + 1 = 2. f) 2 × 2 = 2 × (1 + 1) = 2 × 1 + 2 = 2 + 2 = 4. Observe que, do mesmo modo que 2 = 1 + 1 = 2 e 3 = 2 + 1, temos 4 = 3 + 1, 5 = 4 + 1, 6 = 5 + 1, …, 12 = 11 + 1. Observe ainda que 3 = 2 + 1 = 1 + 1 + 1, 4 = 3 + 1 = 1 + 1 + 1 + 1 e, assim, para um natural n qualquer, n = 1 + 1 + … + 1, com o segundo membro contendo n parcelas, ou seja “n vezes 1”. Isto justifica a denominação vezes para o operador da multiplicação. Vale observar também que estas são as operações com números naturais que aprendemos nos primeiros anos do ensino fundamental. A imagem n + m é chamada soma de n e m. Neste caso, n e m são chamados parcelas. A imagem n . m é chamada produto de n por m. Neste caso, n e m são chamados fatores. Um produto do tipo n . n pode ser representada por n2 (lido n ao quadrado). Observe que o conceito de antecessor introduzido na seção anterior e a definição de adição implicam que se n ≠ 1, então (n – 1) + 1 = n. Para analisar a comutatividade, a associatividade e a existência de elemento neutro da multiplicação, necessitamos do seguinte lema. Lema 1.2 Para todo n ∈ ℕ, temos i) n + 1 = 1 + n; ii) n . 1 = 1 . n. Demonstração i) Consideremos o predicado em ℕ p(n) = V se n + 1 = 1 + n. Temos que p(1) = V pois, evidentemente, 1 + 1 = 1 + 1. Suponhamos agora que p(n) = V e provemos, a partir daí, que p(s(n)) = V. De p(n) = V, temos n + 1 = 1 + n e então 1 + s(n) = s(1 + n) = s(n + 1) = (n + 1) + 1 = s(n) + 1 e, portanto, p(s(n)) = V. Assim, pelo Princípio da Indução, p(n) = V para todo n ∈ ℕ. ii) Consideremos o predicado em ℕ, p(n) = V se n . 1 = 1 . n. Temos que p(1) = V pois, evidentemente, 1 . 1 = 1 . 1. Suponhamos agora que p(n) = V e provemos, a partir daí, que p(s(n)) = V. De p(n) = V, temos n . 1 = 1 . n e então s(n) . 1 = s(n) = n + 1 = n . 1 + 1 = 1 . n + 1 = 1 . s(n), onde, na última igualdade, utilizamos o item 26 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão (b) da definição da multiplicação. Logo p(s(n)) = V. Uma implicação imediata da igualdade n + 1 = 1 + n é a inexistência de elemento neutro da adição. De fato, se existisse um natural e tal que n + e = e + n = n, para todo natural n, teríamos 1 + e = e + 1 = 1, contrariando o segundo postulado de Peano. Por seu turno, as igualdades n = n . 1 = 1 . n implicam que o natural 1 é o elemento neutro da multiplicação. Sobre as demais propriedades das operações temos a seguinte proposição. Proposição 2.2 As operações adição e multiplicação são associativas e comutativas e a multiplicação é distributiva em relação à adição. Isto é, para todos n, m, p ∈ ℕ, temos i) n + (m + p) = (n + m) + p (associatividade da adição); ii) n . (m + p) = n . m + n . p (distributividade da multiplicação em relação à adição); iii) n . (m . p) = (n . m) . p (associatividade da multiplicação); iv) n + m = m + n (comutatividade da adição); v) n . m = m . n (comutatividade da multiplicação); Demonstração. i) Sejam n, m ∈ ℕ e consideremos o predicado em ℕ p(k) = V se (n + m) + k = n + (m + k). Temos p(1) = V, pois (n + m ) + 1 = s(n + m) = n + (m + 1), onde na última igualdade foi utilizada o item b da definição da adição. Suponhamos que p(k) = V, ou seja, suponhamos que (n + m) + k = n + (m + k), e provemos que p(s(k)) = V. Temos (n + m) + s(k) = s((n + m) + k) = s(n + (m + k)) = n + s(m + k) = n + (m + s(k)). ii) Sejam n, m ∈ ℕ e consideremos o predicado em ℕ p(k) = V se n . (m + k) = n . m + n . k. Temos p(1) = V, pois n . (m + 1) = n . m + n = n . m + n . 1. Suponhamos que p(k) = V, ou seja, suponhamos que n . (m + k) = n . m + n. k, e provemos que p(s(k)) = V. Temos n . (m + s(k)) = n . s(m + k) = n . ((m + k) + 1) = n . (m + k) + n = (n . m + n . k) + n = = n . m + (n . k + n) = n . m + n . s(k). iii) Sejam n, m ∈ ℕ e consideremos o predicado em ℕ p(k) = V se (n . m) . k = n . (m . k). Temos p(1) = V, pois (n . m) . 1 = n . m = n . (m . 1). Suponhamos que p(k) = V, ou seja, suponhamos que (n . m) . k = n . (m . k), e provemos que p(s(k)) = V. Temos (n . m) . s(k) = (n . m) . k + (n . m) (definição da multiplicação) (n . m) . s(k) = n . (m .k) + n . m (hipótese indutiva) (n . m) . s(k) = n . (m . k + m) (distributividade "ao contrário") (n . m) . s(k) = n . (m . s(k)) (definição de multiplicação) iv) Seja n ∈ ℕ e consideremos o predicado em ℕ p(m) = V se n + m = m + n. Pelo lema 1.2, temos p(1) = V. Suponhamos que p(m) = V, ou seja, suponhamos que n + m = m + n, e provemos que p(s(m)) = V. Temos n + s(m) = n + (m + 1) (definição de sucessor) 27 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão n + x = s(m) não seja solúvel. Daí, pelo item iv, a equação n + x = m não é solúvel o que implica pela hipótese de indução n = m ou n + x = m é solúvel. Porém, n ≠ m, pois, do contrário, n + 1 = s(m), o que contraria a hipótese levantada acima de que a equação n + x = s(m) não é solúvel. Logo, m + x = n é solúvel e então, pelo item iii, s(m) = n ou s(m) + x = n é solúvel, mostrando que p(s(m)) = V. Observe que o item (i) da proposição acima implica que dado um natural n não existe um natural k tal que n + k = n. Desta observação segue que s(n) ≠ n, para todo natural n. Agora temos condições de provar a lei do corte para a multiplicação. Proposição 5.2 Se n, m, p ∈ ℕ e n . p = m . p, então n = m. Demonstração Pela proposição anterior, se n ≠ m, uma das equações n + x = m ou m + x = n seria solúvel. Se existisse um natural r tal n + r = m, teríamos (n + r) . p = m . p o que implicaria n . p + r. p = m . p e a equação n . p + x = m . p seria solúvel, contrariando o item i da proposição anterior, pois, por hipótese, n . p = m . p. Como é evidente que este raciocínio se aplica à possibilidade de que a equação m + x = n seja solúvel, temos que n = m. 2.5 Uma relação de ordem no conjunto dos números naturais No conjunto dos números naturais definimos uma relação, chamada menor do que ou igual a e indicada pelo símbolo ≤, por n ≤ m se n = m ou a equação n + x = m é solúvel. Observe que, como a solubilidade da equação n + x = m implica a existência de um natural r tal que n + r = m, a relação ≤ poderia ser definida da seguinte forma n ≤ m se n = m ou existe um natural r tal que n + r = m. Proposição 6.2 A relação ≤ é uma relação de ordem. Isto é, ≤ é reflexiva, antissimétrica, transitiva e total. Demonstração Sejam a, b e c números naturais quaisquer. Pela própria definição da relação, se a = b, temos a ≤ b. Assim, a ≤ a e a relação é reflexiva. Suponhamos agora que a ≤ b e b ≤ a. Se a e b fossem diferentes, as equações a + x = b e b + x = a seriam solúveis o que contrariaria a proposição 4.2. Logo a = b e a relação é antissimétrica. Se a ≤ b e b ≤ c, temos a = b ou existe um natural p tal que a + p = b e b = c ou existe um natural r tal que b + r = c. Daí, a = c ou a + (r + p) = c, o que mostra que a ≤ c. Assim, ≤ é transitiva. Finalmente, a proposição 4.2 garante que a = b ou a + x = b é solúvel ou b + x = a é solúvel. Ou seja, a ≤ b ou b ≤ a e ≤ é total. Além de ser uma relação de ordem, a relação ≤ satisfaz às seguintes propriedades. Proposição 7.2 Sejam n, m ∈ ℕ tais que n ≤ m. Então, para todo natural p, n + p ≤ m + p e n . p ≤ m . p. 30 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Demonstração De n ≤ m segue que n = m ou existe um natural r tal que n + r = m. De n = m segue que n + p = m + p e n . p = m . p. De n + r = m segue que n + (r + p) = m + p e n . p + r . p = m . p, que implicam (n + p) + r = m + p e n . p + r . p = m . p. Logo, n + p ≤ m + p e n . p ≤ m . p. Quando dois naturais n e m são tais que n ≤ m e n ≠ m dizemos que n é menor do que m e indicamos por n < m. Observe que, como as condições “n = m” e “a equação n + x = m é solúvel” são incompatíveis, dizer que n < m implica que a equação n + x = m é solúvel. Ou seja, n < m se e somente se existe um natural r tal que n + r = m. Observe que < pode ser vista como uma relação binária em ℕ que, como é fácil provar, é transitiva (ver exercício 2.9). Também usamos m ≥ n (lido m maior do que ou igual a n) para indicar que n ≤ m e m > n (lido m maior que n) como sinônimo de n < m. Como as relações ≤ e < são transitivas, quando tivermos n ≤ m e m ≤ p, podemos escrever n ≤ m ≤ p e quando tivermos n < m e m < p, podemos escrever n < m < p, caso em que dizemos que m está entre n e p. Qualquer uma das relações <, ≤, >, ≥ e ≠ é chamada desigualdade. É interessante observar, como mostra a proposição a seguir, que não existe número natural entre um natural e o seu sucessor. Proposição 8.2 Sejam n e m números naturais. Se m > n, então m ≥ n + 1. Demonstração Se existisse um natural m tal que m > n e m < n + 1 existiriam naturais r e p tais que n + r = m e m + p = n + 1 de onde seguiria que n + (r + p) = n + 1. Daí, pela lei do corte, teríamos r + p =1. Porém a existência de naturais r e p tais que r + p =1 é uma contradição, pois, se p = 1, r + 1 =1 e se p ≠ 1, (r + (p – 1)) + 1 = 1, que contrariam o segundo axioma de Peano. O conjunto dos números naturais satisfaz a uma outra propriedade que será importante no sentido de relacionar o conjunto dos números naturais com contagens. Para sua demonstração necessitamos da seguinte proposição. Proposição 9.2 Sejam n, m ∈ ℕ. Então i) 1 ≤ n; ii) n < s(n); iii) Se n < s(m), então n ≤ m. Demonstração i) Se n ≠ 1, como 1 + (n – 1) = n, temos 1 < n. Logo, 1 ≤ n. ii) Decorre imediato da igualdade n + 1 = s(n). iii) Por contradição, suponhamos que m < n. Daí a equação m + x = n é solúvel e então, pela proposição 4.2, s(m) = n ou a equação s(m) + x = n é solúvel. Assim s(m) ≤ n, contrariando a hipótese de que n < s(m). Observe que o item ii desta proposição e a transitividade da relação < implicam que 1 < 2 < 3 < … < 9 < … . Daí ser natural (no sentido usual do termo) a representação do conjunto dos números naturais por ℕ = {1, 2, 3,...}. Observe também que o mesmo item ii mostra que n < n + 1 e, dessa forma, o início da demonstração da proposição poderia ser escrito: “Se existisse um natural m tal que n < m < n + 1 existiram naturais...” 31 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Proposição 10.2 (Princípio da Boa Ordenação (PBO)) Seja M um subconjunto dos números naturais. Se M ≠ ∅, então existe p ∈ M tal que p ≤ m qualquer que seja m ∈ M. Demonstração Consideremos o conjunto L = {x ∈ ℕ| m ∈ M ⇒ x ≤ m}. Observe que o item (i) do lema anterior implica que 1 ∈ L. Além disso, como pelo item (ii) do lema anterior s(k) > k, para todo natural k, temos que se m ∈ L, então s(m) ∉ L. Isto mostra que L ≠ ℕ e, então, a proposição 1.2 garante que existe p ∈ L tal que s(p) ∉ L. Logo, existe t ∈ M tal que t < s(p). Como o último item do lema anterior garante que t ≤ p e as pertinências p ∈ L e t ∈ M implicam p ≤ t, temos p = t. Assim, p ∈ M e p ≤ m, qualquer que seja m ∈ M, já que p ∈ L. O elemento p da proposição anterior é chamado menor elemento ou elemento mínimo de M. 2.6 Conjuntos finitos Como dissemos no início da seção 2.2, aprendemos a manipular números naturais associando- os a quantidades e realizando contagens. Nesta seção vamos formalizar estas ideias. Dado n ∈ ℕ, seja In = {x ∈ ℕ| x ≤ n}. Dizemos que um conjunto A é finito se A = ∅ ou existem um natural n e uma bijeção de In em A (ou, por inversibilidade, uma bijeção de A em In) . Por exemplo, o conjunto A = {a, b, c} é um conjunto finito pois, trivialmente, existe uma função bijetiva do conjunto I3 = {1, 2, 3} em A: f = {(1, a), (2, b), (3, c)}. Evidentemente, para cada n ∈ ℕ, o conjunto In é finito, pois a identidade é uma bijeção de In em In. Se um conjunto A não é finito dizemos que ele é infinito. Vamos mostrar que se A é finito, então o natural n é determinado pelo conjunto A e pela existência da bijeção de A em In. Esse fato decorre da seguinte propriedade dos conjuntos In. Proposição 11.2 Seja n ∈ ℕ. Se A é um subconjunto próprio de In e f é uma função de A em In, então f não é bijetiva. Demonstração Seja Y = {x ∈ ℕ|existem A ⊂ Ix, A ≠ Ix, e uma bijeção f de A em Ix}. Devemos provar que Y = ∅. Por contradição, suponhamos que Y ≠ ∅. Assim, pelo Princípio da Boa Ordenação, Y tem um menor elemento m e, portanto, há um subconjunto próprio A de Im tal que existe uma bijeção f de A em Im. Se m ∈ A, por uma propriedade apresentada na seção 1.16, existe uma função bijetiva g de A em Im, com g(m) = m e a restrição g ao conjunto A – {m} é uma bijeção de A – {m} em Im-1, o que contraria o fato de que m é o elemento mínimo de Y. Se m ∉ A, seja a ∈ A tal que m = f(a). Assim, a restrição de f ao conjunto A – {a} é uma bijeção de A – {a} em Im-1, o que contraria também fato de que m é o elemento mínimo de Y. Corolário 3.2 Seja A um conjunto finito não vazio. Se existem naturais n e m e bijeções f de A em In e g de Im em A, então n = m. Demonstração Como g de Im em A e f de A em In são bijetivas, as funções f o g, de Im em In, e (f o g)-1, de In em Im, são bijetivas. Se m < n, Im é subconjunto próprio de In e a função f o g contrariaria a proposição anterior. Do mesmo modo a função (f o g)-1 contrariaria a citada proposição se n < m. Logo n = m. Se A é um conjunto finito não vazio, o único natural n definido pela existência do subconjunto 32 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão 3. Os números inteiros 3.1 Introdução No capítulo anterior introduzimos a noção de equação no conjunto dos números naturais e vimos que uma equação n + x = m tem solução se e somente se n < m. Há situações na prática em que necessitamos investigar uma equação do tipo n + x = m, com n > m. Um exemplo bem simples é o seguinte. Uma criança, cuja mesada é administrada pela mãe, tem um saldo de R$ 3,00. Se ela convence a mãe a comprar um sorvete que custa R$ 5,00, ela fica devendo (para ser descontado da mesada do próximo mês) R$ 2,00. A questão é: como expressar numericamente este débito em relação ao saldo da sua mesada? Para que possamos fazer isto é necessário "ampliarmos" o conjunto dos números naturais, obtendo então o nosso velho conhecido conjunto dos números inteiros. A partir dos números naturais, o conjunto dos inteiros pode ser construído através de definições. Vamos optar, por enquanto, em construir os inteiros também de forma axiomática, deixando o estabelecimento dos inteiros por definição para o capítulo 8. Esta opção se deve ao fato de que as definições necessárias, embora fáceis, requerem uma maior maturidade matemática. Uma outra razão para construirmos os inteiros axiomaticamente é que, nesta construção, o Princípio da Indução Matemática agora será um teorema enquanto que o Princípio da Boa Ordenação será um axioma, ao contrário da construção axiomática dos números naturais. Esta mudança permitirá uma nova maneira de ver as coisas. Além disso, a construção axiomática dos inteiros requer o estudo de algumas estruturas algébricas, que são também utilizadas em outros ramos da Matemática. Uma estrutura algébrica consiste de um conjunto munido de uma ou mais operações que gozem de propriedades preestabelecidas. Estudaremos os anéis e outras “estruturas derivadas". 3.2 Anéis Um anel é a estrutura algébrica que consiste de um conjunto A munido de duas operações, chamadas adição (operador: +, denominação: mais) e multiplicação (operador: . ou ×, denominação: vez(es)), que satisfazem às seguintes propriedades. (A1) A adição é associativa: a + (b + c) = (a + b) + c, quaisquer que sejam a, b, c ∈ A. (A2) A adição é comutativa: a + b = b + a, quaisquer que sejam a, b ∈ A. (A3) A adição possui elemento neutro: existe e ∈ A tal que a + e = a, qualquer que seja a ∈ A. (A4) Todo elemento possui simétrico em relação à adição: para todo a ∈ A existe a’ ∈ A tal que a + a’ = e. (M1) A multiplicação é associativa: a . (b . c) = (a . b) . c, quaisquer que sejam a, b, c ∈ A. (M2) A multiplicação é comutativa: a . b = b . a, quaisquer que sejam a, b ∈ A. (M3) A multiplicação possui elemento neutro: existe f ∈ A, f ≠ e, tal que a . f = a, qualquer que seja a ∈ A. (AM) A multiplicação é distributiva em relação à adição: a . (b + c) = a . b + a . c, quaisquer que sejam a, b, c ∈ A. Normalmente, a referência a um anel genérico é feita apenas pela indicação do conjunto, ficando subentendidas as duas operações adição e multiplicação. Quando necessário, indicaremos um anel por (A, #, *), onde A é o conjunto, # e * são, respectivamente, as operações de adição e de multiplicação definidas no conjunto. Como nos naturais, uma imagem de uma adição a + b é chamada soma e uma imagem de uma multiplicação a . b é chamada produto. Na soma a + b, a e b são chamados parcelas e no produto a . b, a e b são chamados fatores. O produto a . a pode ser indicado por a2 (lido a ao quadrado). 35 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Consideremos, para exemplificar, um mostrador de um relógio. Imagine que num determinado instante o ponteiro das horas esteja sobre a marca das 11 horas. Três horas após este instante o ponteiro estará sobre a marca das 2 horas; seis horas após aquele instante o ponteiro estará sobre 5 horas e 11 horas após, ele estará sobre as 10 horas. 36 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Naturalmente, podemos expressar estes fatos através de uma operação definida no conjunto I12 = {1, 2, 3, ..., 12} pondo 11 + 3 = 2 11 + 6 = 5 11 + 11 = 10 Imagine agora que o ponteiro das horas esteja sobre a marcação das doze horas. Decorrido três vezes o intervalo de tempo de sete horas, o ponteiro ocupará a marca das nove horas o que justifica a igualdade 3 . 7 = 9. Isto mostra que, de forma natural, pode-se definir uma adição e uma multiplicação em I12 de acordo com as seguintes tabelas, onde o elemento da linha i e da coluna j, representa i + j na primeira e i . j na segunda. Adição em I12 + 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 Multiplicação em I12 . 1 2 3 4 5 6 7 8 9 10 11 12 1 1 2 3 4 5 6 7 8 9 10 11 12 2 2 4 6 8 10 12 2 4 6 8 10 12 3 3 6 9 12 3 6 9 12 3 6 9 12 4 4 8 12 4 8 12 4 8 12 4 8 12 5 5 10 3 8 1 6 11 4 9 2 7 12 6 6 12 6 12 6 12 6 12 6 12 6 12 7 7 2 9 4 11 6 1 8 3 10 5 12 8 8 4 12 8 4 12 8 4 12 8 4 12 9 9 6 3 12 9 6 3 12 9 6 3 12 10 10 8 6 4 2 12 10 8 6 4 2 12 11 11 10 9 8 7 6 5 4 3 2 1 12 12 12 12 12 12 12 12 12 12 12 12 12 12 37 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão (-1) . a + a = 0 . a ((-1) + 1 = 0) (-1) . a + a = 0, (proposição anterior) b) Temos (-a) . b = ((-1) . a) . b = (-1) . (a . b) = -(a . b). Para a outra igualdade, temos a . (-b) = (-b) . a e, então, a . (-b) = -(b . a) = -(a . b). c) A igualdade segue das seguintes aplicações do item (b) e do fato de que -(-a) = a. (-a) . (-b) = -(a . (-b)) = -(-(a . b)) = a . b 3.3 Elementos inversíveis Seja A um anel. Vamos discutir agora a existência de elemento simétrico em relação à multiplicação. Ou seja, vamos discutir o caso em que dado um elemento a ∈ A, existe b ∈ A tal que a . b = 1. Neste caso dizemos que a é inversível e b é chamado inverso de a. Como mostrado no capítulo primeiro, o inverso de um elemento inversível a é único e será representado por a-1. No anel I12 do exemplo acima temos que 1, 5, 7 e 11 são inversíveis (1 -1 = 1, 5-1 = 5, 7-1 = 7 e 11-1 = 11) e 0, 2, 3, 4, 6, 8, 9, 10 não são inversíveis. No anel I 7, todos os elementos não nulos são inversíveis, sendo, por exemplo, 2-1 = 4 e 3-1 = 5. Devido ao fato de que a . 0 = 0, para todo a ∈ A, conforme visto na proposição 1.3, o elemento neutro da adição de um anel nunca é inversível. Por sua vez, como 1 . 1 = 1, o elemento neutro da multiplicação é sempre inversível e 1-1 = 1. Como o item (c) da proposição 2.3 mostra que (-1) . (-1) = 1 . 1, temos que –1 é inversível e (-1) -1 = -1. Claramente, se a é inversível, a-1 também o é e (a-1)-1 = a. 3.4 Igualdade de anéis: anéis isomorfos Como já foi dito e redito, ao se definir um novo ente matemático é necessário que se estabeleça quando dois representantes deste ente são considerados iguais. É o que faremos agora em relação a anéis. Embora a igualdade de dois representantes de um ente matemático seja estabelecida por uma definição, é natural que esta definição vá ao encontro da lógica do senso comum. É fácil aceitar que não havia sentido uma definição de igualdade de anéis que tornasse iguais os anéis I12 e I7. É razoável aceitar que a igualdade de anéis deva passar pela “mesma cardinalidade” dos conjuntos envolvidos, o que pode ser exigido pela existência de uma função bijetiva, e, em consequência, da preservação das operações respectivas em relação aos objetos e suas imagens. Ou seja, é razoável esperar que dois anéis (A, +, .) e (B, #, *) serão iguais se existir uma função bijetiva f de A em B que satisfaça às seguintes propriedades: a) f(a + b) = f(a) # f(b). b) f(a . b) = f(a) ∗ f(b). c) f(1A) = 1B. d) f(0A) = 0B. e) f(a - b) = f(a) ∼ f(b), com ~ indicando a subtração em B. f) f(-a) = ∼f(a). É interessante observar que, como mostra a proposição a seguir, os itens d, e, e f da observação acima são corolários dos itens a, b e c. Proposição 3.3. Sejam (A, +, .) e (B, #, *) dois anéis e f uma função de A em B tal que f(a + b) = f(a) # f(b), f(a . b) = f(a) ∗ f(b) e f(1A) = 1B. Então 40 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão a) f(0A) = 0B. b) f(-a) = ∼f(a), qualquer que seja a ∈ A. c) f(a - b) = f(a) ∼ f(b), quaisquer que sejam a, b ∈ A. Demonstração a) Temos que f(0A) = f(0A + 0A) = f(0A) # f(0A) e então, pela observação anterior à proposição 1.3, f(0A) = 0B. b) Temos que 0B = f(0A) = f(a + (-a)) = f(a) # f(-a) e então f(-a) = ~ f(a). c) Utilizando o item b, temos f(a - b) = f(a + (-b)) = f(a) # f(-b) = f(a) ∼ f(b). De um modo geral, se E e F são duas estruturas algébricas de um mesmo tipo, uma função bijetiva de E em F que preserve as operações das estruturas é chamada de isomorfismo de E em F. A proposição acima afirma que para que uma função bijetiva f de um anel (A, +, .) num anel (B, #, *) seja um isomorfismo de A em B basta que f(a + b) = f(a) # f(b), f(a . b) = f(a) ∗ f(b) e f(1A) = 1B (caso em que f é dita um homomorfismo do anel A no anel B). A proposição a seguir mostra que a função inversa de um isomorfismo é também um isomorfismo, o que nos permite falar em anéis isomorfos. Proposição 4.3 Sejam os anéis (A, +, .) e (B, #, *). Se a função f é um isomorfismo de A em B, então a função inversa de f é um isomorfismo de B em A. Demonstração Como f é um isomorfismo de A em B, f é bijetiva e, portanto, tem uma inversa f-1. Sejam c e d dois elementos do anel B. Como f é bijetora existem únicos a e b em A tais que f(a) = c e f(b) = d. Temos então f -1(c # d) = f -1(f(a) # f(b)) = f -1(f(a + b)) = a + b e, portanto, f -1(c # d) = f -1(c) + f -1(d). Claramente, a igualdade f-1(c ∗ d) = f -1(c) . f -1(d) se demonstra de forma semelhante. Finalmente, a igualdade f(1A) = 1B implica f -1(f(1A)) = f -1(1B) e então 1A = f -1(1B). Dessa forma, se dois anéis são isomorfos há uma correspondência biunívoca entre os dois conjuntos que preserva as operações “nos dois sentidos”. Assim, a existência de um isomorfismo entre dois anéis implica que eles, mesmo que tenham elementos distintos e que as operações neles definidas sejam diferentes, algebricamente eles têm a mesma estrutura. Por esta razão, a existência de um isomorfismo entre dois anéis é utilizado para definir igualdade de dois anéis: dois anéis são iguais quando eles são isomorfos. 3.5 Domínios de integridade Se o leitor observar a tabela de multiplicação do anel I12 e se lembrar que neste anel 12 = 0, verificará, ao contrário do que estamos habituados, que 3 . 8 = 0. Ou seja, o produto de dois elementos não nulos é igual a zero! Observe que tal fato não ocorre no anel I7. Um anel em que este fato não acontece é chamado domínio de integridade, que pode ser formalmente definido da seguinte forma. Seja A um anel. Diz-se que A é um domínio de integridade se a multiplicação do anel satisfizer à seguinte propriedade. (M4) Quaisquer que sejam a, b ∈ A, se a . b = 0, então a = 0 ou b = 0. Assim o anel I12 não é um domínio de integridade, pois, como já vimos, 3 . 8 = 0 e 3 ≠ 0 e 8 ≠ 0. Já o anel I7 é um domínio de integridade. Claramente, a propriedade (M4) acima é equivalente à seguinte propriedade. 41 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão (M4’) Quaisquer que sejam a, b ∈ A, se a ≠ 0 e b ≠ 0, então a . b ≠ 0. Um domínio de integridade satisfaz a uma propriedade adicional, conhecida como lei do cancelamento ou lei do corte. Proposição 5.3 Seja D um domínio de integridade. Quaisquer que sejam a, b, c ∈ D, se a ≠ 0 e a . b = a . c, então b = c. Demonstração De a . b = a . c segue que a . b + (-a . c) = 0 o que implica a . b + (a . (-c)) = 0. Daí, a . (b + (-c)) = 0 e, então, como D é um domínio de integridade e a ≠ 0, b + (-c) = 0 o que implica b = c. Ao aplicarmos a lei do cancelamento em a . b = a . c (se a ≠ 0) obtendo b = c, dizemos que dividimos a igualdade a . b = a . c por a ou que a igualdade a . b = a . c foi simplificada por a. 3.6 Anéis ordenados Um anel A é dito anel ordenado se nele for definida uma relação de ordem (ou seja, uma relação binária reflexiva, antissimétrica, transitiva e total), simbolizada por ≤, que satisfaz às seguintes propriedades. a) Compatibilidade com a adição Quaisquer que sejam a, b, c ∈ A, se a ≤ b, então a + c ≤ b + c. b) Compatibilidade com a multiplicação Quaisquer que sejam a, b, c ∈ A, se a ≤ b e 0 ≤ c, então a . c ≤ b . c. A expressão x ≤ y é lida x é menor do que ou igual a y e é equivalente à notação y ≥ x, que é lida y maior do que ou igual a x. Usamos a notação x < y (que é lida x menor do que y) para indicar que x ≤ y e x ≠ y. Da mesma forma, utilizamos x > y (x maior do que y) significando que x ≥ y e x ≠ y. Como ≤ é transitiva, podemos usar x ≤ y ≤ z para indicar que x ≤ y e que y ≤ z. Um exercício proposto (de solução facílima) mostrará que x < y é também transitiva. Assim podemos usar x < y < z para indicar que x < y e y < z. Neste caso dizemos que y está entre x e z. Além da expressão x ≠ y, qualquer das expressões x ≥ y, x ≤ y, x > y e x < y é chamada desigualdade. Se x > 0, diz-se que x é positivo e se x < 0, diz-se que x é negativo. A positividade ou negatividade de um elemento de um anel ordenado também é citada como o sinal do elemento. A multiplicação num anel ordenado satisfaz às propriedades abaixo, que, combinadas com as propriedades estabelecidas na proposição 2.3, são conhecidas como regra de sinais da multiplicação. Proposição 6.3 Sejam A um anel ordenado e a e b dois elementos de A. a) Se a ≥ 0, então -a ≤ 0. b) Se a ≤ 0, então -a ≥ 0. c) Se a ≥ 0 e b ≥ 0, então a . b ≥ 0. d) Se a ≥ 0 e b ≤ 0, então a . b ≤ 0. e) Se a ≤ 0 e b ≤ 0, então a . b ≥ 0. 42 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão z × a = onde ~ está indicando a subtração em D e – a subtração em A. Por exemplo, 1D  a = a + (1D ~ 1D)  a = a + 0D  a = a + 0A = a. 2D  a = a + (2D ~ 1D)  a = a + 1D  a = a + a = 2A. Proposição 8.3 Sejam (A, +, .) um anel e (D, #, *) um domínio bem ordenado. Quaisquer que sejam a, b ∈ A e m, n ∈ D, temos a) (~m)  a = -(m  a). b) (m # n)  a = (m  a) + (n  a). c) m  (a + b) = (m  a) + (m  b). d) (m * n)  a = m  (n  a). e) m  (a . b) = (m  a) . b. Demonstração a) Se m > 0D, ~m < 0D e então (~m)  a = -((~(~m))  a) = -(m  a) pois ~(~m) = m. Se m = 0D a igualdade é evidente, pois ambos os seus termos ficam iguais a zero e se m < 0D, da própria definição segue que m  a = -((~m)  a) o que implica a igualdade pretendida. b) Suponhamos que m # n > 0, fixemos m e provemos a igualdade para todo n ≥ 1D. (para n negativo, fixaríamos n e faríamos a indução em relação a m que, forçosamente, seria positivo) (i) É claro que a igualdade é verdadeira para n = 1D, pois (m # 1D)  a = a + ((m # 1 ~ 1)  a) = a + (m  a) = (m  a) + a = (m  a) + 1D  a, onde a última igualdade decorre da igualdade 1D  a = a mostrada no exemplo acima. (ii) Suponhamos que (m # n)  a = (m  a) + (n  a) e provemos que (m # (n # 1D))  a = m  a + ((n # 1D)  a). Temos (m # (n # 1D))  a = a + ((m # (n # 1D) ~ 1D)  a) (definição) (m # (n # 1D))  a = a + ((m # n)  a) (1D ~ 1D = 0D) (m # (n # 1D))  a = a + (m  a) + (n  a) (hipótese de indução) (m # (n # 1D))  a = (m  a) + (n  a) + a (comutatividade) (m # (n # 1D))  a = (m  a) + ((n # 1D)  a) (base de indução). Se m + n < 0D, temos (m # n)  a = -((~(m # n))  a) = -((~m ~ n)  a) o que implica (m # n)  a = -(((~m)  a) + ((~n)  a)), já que ~m ~ n > 0D. Daí, (m # n)  a = -((~m)  a) - - ((~n)  a)) = -(-(m  a) - (-(n  a)) = ma + na, onde na penúltima igualdade foi utilizado o item (a) da proposição. c) Provemos, por indução, que a igualdade é verdadeira para todo m ≥ 0D. (i) Para m = 0D os dois termos da igualdade tornam-se iguais a zero e a igualdade é verdadeira. (ii) Suponhamos que m  (a + b) = (m  a) + (m  b) e provemos que (m # 1D)  (a + b) = ((m # 1D)  a) + ((m # 1D)  b). Temos (m # 1D)  (a + b) = (m  (a + b)) + (1D  (a + b)) (item b) (m # 1D)  (a + b) = (m  a) + (m  b) + a + b (hipótese indutiva e exemplo acima) 45 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão (m # 1D)  (a + b) = ((m # 1D)  a) + ((m # 1D)  b) (definição). Para m < 0D, m  (a + b) = -((~m)  (a + b)) (definição) m  (a + b) = -(((-m)  a) + ((-m)  b)) (-m > 0D) m  (a + b) = -((~m)  a) + (-((-m)  b) (distributividade no anel) m  (a + b) = (m  a) + (m  b) (definição) d) Como na demonstração do item (b), suponhamos que m * n > 0, fixemos m e provemos a igualdade para todo n ≥ 1. (i) É claro que a igualdade é verdadeira para n = 1D, pois (m * 1D)  a = m  a = m  (1D  a) por que mostramos no exemplo acima que 1D  a = a. (ii) Suponhamos que (m * n)  a = m  (n  a) e provemos que (m * (n # 1D))  a = = m  ((n # 1D)  a). Temos (m * (n # 1D))  a = ((m * n) # m)  a (distributividade no domínio) (m * (n # 1D))  a = ((m * n)  a) + (m  a) (item b) (m * (n # 1D))  a = m  (n  a) + (m  a) (hipótese de indução) (m * (n # 1D))  a = m  ((n  a) + a) (item c) (m * (n # 1D))  a = m  ((n # 1D)  a) (item b) Se m . n = 0D, temos m = 0D ou n = 0D (D é um domínio) e os dois termos da igualdade são iguais a zero. Se m * n < 0D, (m * n)  a = -((~(m * n))  a) (definição) (m * n)  a = -(((~m) * n)  a) (-(m * n) = (-m) * n) (m * n)  a = -((~m)  (n  a)) ((-m) . n > 0) (m * n)  a = -(- (m  (n  a))) (item a) (m * n)  a = m  (n  a) (-(-x) = x no anel). e) Provemos que a igualdade é verdadeira para m ≥ 0D. (i) A igualdade é claramente verdadeira para m = 0D, pois ambos os termos se tornam iguais a zero. (ii) Suponhamos que m  (a . b) = (m  a) . b e provemos que (m # 1D)  (a . b) = = ((m # 1D)  a) . b. Temos (m + 1D)  (a . b) = m  (a . b) + a . b (item b) (m + 1D)  (a . b) = (m  a) . b + a . b (hipótese indutiva) (m + 1D)  (a . b) = (m  a + a) . b (distributividade no anel) (m + 1D)  (a . b) = ((m # 1D)  a) . b (item b) Para m < 0, m  (a . b) = -((~m)  (a . b)) = -(((~m)  a) . b) = (m  a) . b. Corolário 2.3 Nas condições da proposição anterior, (m * n)  (a . b) = (m  a) . (n  b). Demonstração Temos (m * n)  (a . b) = m  (n  (a . b)) = (m  (n  a)) . b = m  ((n  a) . b) = = m  (n  (a . b)) = m  (n  (b . a)) = m  ((n  b) . a) = m  (a . (n  b)) = (m  a) . (n  46 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão b). Corolário 3.3 Se A é um anel ordenado, D é um domínio bem ordenado e um elemento m de D é tal que m > 0D, então m  1A > 0A. Demonstração Por indução, para m = 1D temos que 1D  1A = 1A > 0, conforme o exercício 3.6. Suponhamos que m  1A > 0A e provemos que (m # 1D)  1A > 0A. Temos (m # 1D)  1A = m  1A + 1D  1A > 0, pois ambas as parcelas são maiores que zero, a primeira pela hipótese de indução e a segunda pela base de indução. Teorema 2.3 Se (D, +, .) e (E, #, *) são domínios bem ordenados, então a função ρ de E em D definida por ρ(z) = z 1D é um isomorfismo de anéis ordenados. Demonstração Inicialmente, temos i) ρ(z1 # z2) = (z1 # z2)  1D = (z1  1D) + (z2  1D) = ρ(z1) + ρ(z2). ii) ρ(z1 * z2) = (z1 * z2)  1D = (z1  1D) . (z1  1D) = ρ(z1) . ρ(z2), onde na segunda igualdade foi utilizado o corolário 2.3. iii) ρ(1E) = 1E 1D = 1D, Provemos agora ρ é sobrejetivo. Para tal devemos provar que todo elemento a ∈ D é da forma z  1D para algum z ∈ E. Suponhamos por contradição que existe a ∈ D tal que a ≠ z  1D, para todo z ∈ E e consideremos os conjuntos A’ = {z  1D ∈ D| z ∈ E e z  1D > a} e A” = {z  1D ∈ D| z ∈ E e z  1D < a}. Se A’ ≠ ∅, como ele é um conjunto limitado inferiormente e D é um domínio bem ordenado, pelo Princípio da Boa Ordenação, A’ tem um elemento mínimo b  1D. Assim, b  1D > a e b  1D - 1D ≤ a. Desta última, segue (b – 1D)  1D ≤ a, de que resulta (b – 1D)  1D < a, pois a ≠ z  1D, para todo z ∈ E. Desta última desigualdade e do corolário 3.1 segue que a ≥ (b – 1D)  1D + 1D = b  1D, o que contradiz a desigualdade b(1D) > a. Logo A’ = ∅. Utilizando raciocínio semelhante e a formulação do Princípio da Boa Ordenação dada no exercício 3.11, prova-se que A” também é um conjunto vazio, o que prova que não existe a ∈ D tal que a ≠ z  1D, para todo z ∈ E. Logo, ρ é sobrejetivo. Para provar que ρ é injetivo (e também que “preserva” as ordens dos domínios bem ordenados), sejam z, y ∈ E, com z > y. Daí, z - y > 0 e, como ρ(z) - ρ(y) = z  1D - y  1D = (z - y)  1D, temos ρ(z) > ρ(y). Assim, ρ é um isomorfismo de anéis ordenados e todos os domínios bem ordenados são iguais implicando a existência de um único domínio bem ordenado que, como foi dito no início da seção, é chamado conjunto dos números inteiros. Sendo o único domínio bem ordenado, o domínio dos números inteiros (representado por ℤ como estabelecido no início da seção) fica perfeitamente caracterizado: nele estão definidas duas 47 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão A não existência de n tal que xn = k implicaria que a sequência x1 – k > x2 – k > ... > xk - k > > ... > 0 contradiria a proposição. 3.11 Os naturais e os inteiros Consideremos o conjunto ℤ+ = {z ∈ ℤ|z > 0} e a função f, de ℤ+ em ℤ+, definida por f(z) = z + 1 . Observe que a compatibilidade com a adição da relação ≤ garante que f está bem definida e a aplicação da lei do corte dada na proposição 5.3 demonstra que f é injetiva. Além disso, da própria definição de f segue que f(ℤ+) = ℤ+ - {1}. Portanto ℤ+ satisfaz aos primeiro e segundo postulados de Peano. Além disso, o princípio da indução, dado no teorema 1.3, mostra que ℤ+ satisfaz também ao terceiro postulado de Peano. Ainda mais: (i) como são associativas e comutativas e a multiplicação é distributiva em relação à adição, as operações em ℤ+ coincidem com as operações em ℕ; (ii) se y, z ∈ ℤ+ e y < z temos z – y > 0 e y + (z – y) = z e as relações de ordem em ℤ+ e em ℕ coincidem. Logo, ℕ = ℤ+. Observe que desta igualdade também podemos concluir que o conjunto dos inteiros é um conjunto infinito. 3.12 Exercícios 3.0 Construa um anel (A, +, .), em que A é um conjunto finito de cardinalidade mínima. 3.1 Sejam A um anel e a, b, c ∈ A. Mostre que a) Se a + c = b + c, então a = b. b) Se a + b = a para algum a ∈ A, então b = 0. 3.2 Sejam A um anel e a, b ∈ A. Mostre que a) -(a + b) = -a - b. b) a2 – b2 = (a + b).(a – b) 3.3 Mostre que dois elementos a e b de um anel são inversíveis se e somente se a . b é inversível. 3.4 Sejam (A, +, .) um anel e A' um subconjunto de A. O subconjunto A' é dito um subanel de A se (A', +A', .A') é um anel tal que 1A' = 1A (naturalmente, as operações +A' e .A' são as restrições de + e de . ao conjunto A'xA'). a) Sejam A um anel e A' um subconjunto de A. Mostre que A' é um subanel de A se e somente se i) 1A ∈ A'. ii) a – b ∈ A' e a . b ∈ A' quaisquer que sejam a, b ∈ A b) Sejam A e B dois anéis e f um homomorfismo de A em B. Mostre que f(A) é um subanel de B. 3.5. Alguns autores não incluem a comutatividade da multiplicação como axioma para a construção de um anel. Para estes, quando a comutatividade existe, o anel é dito comutativo ou booleano. Para aqueles que incluem a comutatividade da multiplicação como axioma, um conjunto munido de duas operações que gozem das propriedades (A1), (A2), (A3), (A4), (M1), (M3,), (M4) e (AM) é um anel não comutativo. Seja A um conjunto não vazio e ℑ(A) o conjunto das funções de A em A. Dadas f, g em ℑ(A), defina a adição f + g pela função dada por (f + g)(x) = f(x) + g(x). Verifique se ℑ(A) munido da operação definida acima e da composição de funções é um anel não comutativo. 3.6. Seja D um domínio de integridade. Mostre que a) Se a2 = 0, então a = 0. b) Se a . b = a então a = 0 ou b = 1. c) Se a2 = a, então a = 0 ou a = 1. 3.7. Sejam A um anel e a ∈ A, com a ≠ 0. Considere a função fa : A → A, definida por 50 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão fa(x) = a . x. a) Mostre que fa é sobrejetora se e somente se a é inversível. b) Mostre que se A é um domínio de integridade, então fa é injetora. 3.8 Sejam A um anel ordenado e a, b, c, d ∈ A. Mostre que a) Se a + c ≤ b + c, então a ≤ b. b) Se a ≤ b e c ≤ d, então a + c ≤ b + d. c) Se a ≤ b e c ≤ 0, então a . c ≥ b . c. d) Se a < b e b < c, então a < c. e) Se a < b e b ≤ c, então a < c. f) Se a < b, então a + k < b + k, para todo k ∈ A. g) Se a < b e c < d, então a + c < b + d. h) Se a ≤ b e c < d, então a + c < b + d. 3.9. Seja A um anel ordenado. Mostre que a) a2 ≥ 0, qualquer que seja a ∈ A. b) 1 > 0. c) -1 < 0. d) Qualquer que seja a ∈ A, a < a + 1. 3.10. Mostre que não se pode munir o anel I12 de uma relação de ordem que o transforme num anel ordenado. 3.11. Sejam A um domínio de integridade ordenado e a, b, c ∈ A. Mostre que a) Se a < b e c > 0, então a . c < b . c. b) Se a . c ≤ b . c e c > 0, então a ≤ b. c) Se a . c ≤ b . c e c < 0, então a ≥ b. 3.12. Sejam A um anel ordenado e S um subconjunto de A. Diz-se que S é limitado superiormente se existir a ∈ A tal que x ≤ a, qualquer que seja x ∈ S. Diz-se que S tem elemento máximo se existir b ∈ S tal que x ≤ b, qualquer que seja x ∈ S. Mostre que a) Se S tem elemento máximo, então este elemento é único. b) O Princípio da Boa Ordenação é equivalente à seguinte propriedade. Todo subconjunto não vazio limitado superiormente possui elemento máximo. 3.13. Como fixamos anteriormente, 2 = 1 + 1 e, portanto, 2 ≠ 1. Entretanto, pode-se "provar" que 2 = 1 da seguinte forma. Sejam a e b dois inteiros tais que a = b. Multiplicando ambos os termos por a temos a2 = a . b donde se conclui, somando a ambos os termos a2 – 2 . a . b, a igualdade a2 + a2 – 2 . a . b = a2 – 2 . a . b + a . b. Daí, 2 . a2 – 2 . a . b = a2 – a . b, e, então, 2 . (a2 – a . b) = 1 . (a2 – a . b). Pela lei do cancelamento, 2 = 1. Evidentemente, esta "demonstração" está errada! Verifique qual o erro cometido na "demonstração" acima. 3.14. Seja z ∈ ℤ. Mostre que se z < 0, então z ≤ -1 3.15. Sejam z, y ∈ ℤ. Mostre que 51 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão a) |z + y| ≤ |z| + |y| (desigualdade triangular). b) ||z| - |y|| ≤ |z + y| ≤ |z| + |y|. c) ||z| - |y|| ≤ |z - y| ≤ |z| + |y|. 3.16. Dados z, n ∈ ℤ, z ≠ 0 e n ≥ 0, definimos potência de base z e expoente n pela seguinte igualdade. Mostre que para todos a, b, m, n ∈ ℤ, com a, b ≠ 0 e m, n ≥ 0 temos a) am . bm = (a . b)m. b) am . an = am+n. c) (am)n = am. n. 3.17. Sejam a e b dois inteiros. Mostre que a) se a < b, então a3 < b3. b) a2 – a . b + b2 ≥ 0. c) se a > 1 e m e n são dois inteiros positivos, então am > an se e somente se m > n. 3.18 Sejam x1 e q dois números inteiros não nulos. A Progressão Geométrica (PG) de primeiro termo x1 e razão q é a sequência de números inteiros (x1, x2, x3, …) tal que xk + 1 = xk . q, qualquer que seja o valor de k = 1, 2, 3, … . Mostre que, nestas condições, o termo geral de uma PG é dado por xn = x1 . q(n - 1) . 3.19. Sejam a, b e n números inteiros, com n > 1. Mostre que an – bn = (a – b) . (an-1 + an-2 . b + an-3 . b2 + … + a . bn-2 + bn-1). 3.20. Seja z2 o número inteiro y (se existir) tal que 2 . y = z. Considerando as condições de existência, mostre que, z 2 + w = z+2 . w 2 . 3.21. Mostre que, para todo inteiro z ≥ 1, 1 + 2 + ... + z = z .  z+1  2 . 3.22. Mostre que, para todo inteiro k ≥ 0, 1 + 2 + 4 + ... + 2k = 2k+1 – 1. 3.23. Dados n ∈ ℤ, n ≥ 0, definimos o fatorial de n por Mostre que se A e B são dois conjuntos finitos não vazios e |A| = |B| = n, então o número de bijeções de A em B é n!. 3.24. Seja um inteiro z tal que z ≥ -1. Mostre que se n é um inteiro positivo, então (1 + z)n ≥ 1 + n . z, desigualdade conhecida como Desigualdade de Bernoulli. 3.25. O jogo conhecido como Torre de Hanói consiste de n discos de diâmetros diferentes, perfurados, e dispostos numa haste vertical origem na ordem decrescente dos seus diâmetros. . O objetivo do jogo é mover todos os discos da haste origem para uma outra haste destino, utilizando uma terceira haste auxiliar, devendo-se mover um disco de cada vez e não sendo permitir dispor um disco sobre outro de diâmetro maior. Por exemplo, se n = 1, basta se deslocar este disco da origem para o destino; se n = 2, os movimentos seriam: origem → auxiliar origem → destino auxiliar → destino. Mostre que, se an é o número mínimo de movimentos para se concluir a Torre de Hanói, então, 52 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão algoritmo será dada através do comando escreva(x/mensagem); que exibirá o conteúdo da variável x ou a mensagem pretendida (quando se tratar de uma mensagem, ela será colocada entre apóstrofos). Variáveis também serão utilizadas para armazenar valores durante a execução do algoritmo. Para isto, utilizaremos a instrução variável := valor;. Por exemplo, uma instrução x := 1; significa que, a partir da execução desta instrução, o conteúdo da variável x é 1. Uma instrução deste tipo é chamada comando de atribuição e o segundo membro pode conter expressões aritméticas. Por exemplo, ao final da execução da sequência de instruções x := 1; y := 1; w := x + y; y := y - w; em x estará armazenado 1, em w, o valor 2 e em y, o valor -1. Outra instrução que consideraremos, chamada comando de decisão, é a instrução se p então execute estas instruções senão execute estas instruções; onde p é um predicado no universo do problema que se está tratando. É fácil perceber que a execução de um comando de decisão seleciona, dependendo do valor do predicado p, a sequência de instruções que será executada. A opção senão é facultativa e quando ela não aparece e o predicado é falso nada é executado e passa-se à execução da instrução seguinte. Finalmente, necessitaremos de instruções que permitam a repetição da execução de uma sequência de instruções. Estas instruções são chamadas comandos de repetição e utilizaremos dois tipos com objetivos autoexplicativos: 1) repita N vezes sequência de instruções 2) repita enquanto p sequência de instruções Neste segundo tipo, p é um predicado e a sequência de instruções será executada enquanto o valor de p for V. Nos comandos de seleção e de repetição a utilização de tabulações distintas indicará qual a sequência de instruções que está vinculada àquele comando. Nos comandos de repetição, cada execução da sequência de instruções é chamada iteração ou laço. Apresentaremos a seguir alguns exemplos de algoritmos. Para ser possível a compreensão de alguns destes exemplos, vamos considerar conhecidos o conjunto dos números reais e as operações neste conjunto. 4.2 Exemplos 1. Considerando conhecido o conceito de média aritmética o algoritmo abaixo recebe como entrada três números e fornece como saída a média aritmética de três números. algoritmo Media de três números; leia(x, y, z); media := (x + y + z)/3; escreva(media); 2. Naturalmente, a extensão do algoritmo acima para o cálculo da média de muitos números 55 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão (5 000, por exemplo), seria impraticável (imagine como ficariam as primeira e segunda instruções!). A solução seria utilizar uma única variável x para receber todos os números, só recebendo um próximo quando o anterior já estivesse sido processado (somado com os anteriores). Para isto utiliza-se uma outra variável que vai armazenado as somas parciais, recebendo esta variável o valor inicial zero, para que o primeiro número possa ser somado. algoritmo Média de n números; leia(n); soma := 0; repita n vezes leia(x); soma := soma + x; média := soma/n; escreva(média); 3. O algoritmo abaixo calcula a potência an, a e n dados, definição dada no exercício 3.16. algoritmo Potência; leia(a, n); potência := 1; se n > 0 então repita n vezes potência := potência . a; escreva(potência); Observe que se o expoente é zero (n = 0) o comando de repetição não é executado e a saída da potência é 1, de acordo com a definição (o algoritmo não "está preparado" para valores negativos de n). Observe também que o número de iterações deste algoritmo é n. Isto significa que o número de multiplicações necessária para se calcular an é n. Naturalmente o número de operações necessárias para a execução de um algoritmo é uma medida de sua eficiência. No capítulo seguinte, discutiremos um algoritmo mais eficiente para o cálculo de potências. 4. O algoritmo abaixo retorna o fatorial de um número inteiro positivo dado, conforme definido no exercício 3.21. algoritmo Fatorial; leia(n); fatorial := 1; se n < 0 então escreva('Não existe fatorial de número negativo') senão se n > 1 então i := 2; repita enquanto i ≤ n fatorial := fatorial . i; i := i + 1; escreva(fatorial); 5. O exemplo que vamos discutir agora foge um pouco da matemática, mas é importante para a compreensão de algoritmos. Imagine que queremos receber dois números e armazená-los em ordem crescente em duas variáveis x e y fixadas. Isto significa que queremos “receber” os dois 56 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão números em qualquer ordem e pretendemos que ao final da execução do algoritmo o menor deles esteja armazenado na variável x e outro na variável y. Naturalmente, a ordem em que aparecem no algoritmo os comandos leia(x); e leia(y); indicará o armazenamento dos números fornecidos. Se a ordem for esta e o menor dos números for digitado inicialmente nada precisa ser feito; se isto não acontecer devemos trocar os conteúdos de x e de y. algoritmo Ordena dois números leia(x); leia(y); se x > y então aux := x; x := y; y := aux; escreva(x, y); 6. O nosso último de exemplo de “algoritmo” é uma sequência de instruções que não se sabe ainda (http://mathworld.wolfran.com/CollatzProblem.html, acessado em 11/02/2010) se ela constitui um algoritmo. Como foi dito acima, uma condição para que uma sequência de instruções seja um algoritmo é que sua execução pare, retornando uma saída, qualquer que seja a entrada compatível. algoritmo (?) de Collatz leia(z); repita enquanto z > 1 se z é ímpar então z := 3 . z + 1 senão z := z/2; escreva(z); Este é um dos problemas de Matemática que ainda não tem solução, embora todos os matemáticos concordam que, de fato, se trata de uma algoritmo. Tomás Oliveira e Silva, da Universidade de Aveiro, Portugal, executou (num computador, é claro) este algoritmo para todos os inteiros menores que 19 . 255 e não encontrou nenhum contraexemplo. 4.3 Exercícios 4.1. O algoritmo Ordena dois números acima possui uma sequência de comandos que troca o conteúdo de duas variáveis x e y. Para tal era utilizada uma variável aux como variável auxiliar, que armazenava temporariamente o conteúdo de x, para que este não fosse “perdido” quando x recebesse o conteúdo de y. Escreva uma sequência de comandos de atribuição que, sem utilizar uma terceira variável, realiza a troca de conteúdos de duas variáveis. 4.2. Escreva um algoritmo que ordena três números dados. 4.3. Um inteiro positivo z é dito quadrado perfeito se existe um inteiro x tal que x2 = z, caso em que x é chamado raiz quadrada de z, indicado por  z Por exemplo, 9 = 3. Escreva um algoritmo que verifica se um inteiro dado é um quadrado perfeito e retorne sua raiz quadrada. 4.4 Escreva um algoritmo que forneça o maior de três números dados. 57 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão q := q - 1; r := a - b . q; escreva(q, r); A propriedade arquimediana (corolário 5.3) nos garante que este algoritmo para, pois ela assegura a existência de um inteiro z tal que z . b > a. A interrupção do comando de repetição ocorre na primeira vez que b . q > a, porém o comando q := q - 1 faz com que se retorne à desigualdade b . q ≤ a. Do comando r := a - b . q segue que a = b . q + r e o fato de que b . q ≤ a tem como consequência r ≥ 0. Resta mostrar que r < b. Se r ≥ b, a - b . q ≥ b e, então, a ≥ b . (q + 1). Mas isso é uma contradição, pois q é o maior inteiro tal que b . q ≤ a. Para exemplificar, a tabela abaixo simula a execução do algoritmo Divisão euclidiana para a = 11 e b = 2. a b q r 11 2 1 2 3 4 5 6 5 1 O exercício 5.2 dará indicação para determinação de quocientes e restos de divisões a ÷ b quando a < 0 ou b < 0. Dois resultados a respeito do quociente e do resto da divisão euclidiana de dois inteiros positivos são imediatos, mas são indispensáveis para o estabelecimento de uma forma de se representar os inteiros. Proposição 4.5 Sejam dois inteiros a e b, com a, b > 0, e q = q(a, b). Então a) q ≥ 0. b) Se b > 1, então a > q. Demonstração a) De a = b . q + r, com 0 ≤ r < b, segue que a < b . q + b o que implica a < b . (q + 1). Por redução ao absurdo, se q < 0, temos q ≤ -1 e, então, q + 1 ≤ 0. Daí e da desigualdade anterior a < b . (q + 1) segue a ≤ 0, o que contraria a hipótese. b) Do item anterior segue que q ≥ 0. Se q = 0, a hipótese a > 0 já diz que a > q. Se q > 0, de b > 1 segue que b . q > q. Daí e de r ≥ 0, segue que b . q + r > q e portanto a > q. 5.4 Sistemas de numeração Seja b um inteiro maior que 1. Uma forma de se representar os números inteiros consiste em se adotar símbolos, chamados algarismos, para representar os b menores inteiros maiores do que ou iguais a zero e utilizá-los de acordo com a sua posição na representação para indicar os demais inteiros. Isto será mais bem esclarecido após o entendimento do seguinte teorema. Teorema 2.5 60 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Sejam os inteiros a e b, com a > 0 e b > 1. Então existem inteiros positivos n, c0, c1, ..., cn, com 0 ≤ ci < b, para todos i = 0, 1, ..., n, tais que a = cn . bn + cn-1 . bn-1 + ... + c1 . b + c0. Além disso, c0, c1, ..., cn são únicos. Demonstração Pela divisão euclidiana temos que existem únicos q0 e c0 tais que a = b . q0 + c0, 0 ≤ c0 < b. Da mesma forma existem únicos q1 e c1 tais que q0 = b . q1 + c1, 0 ≤ c1 < b. Seguindo este raciocínio obtemos q1 = b . q2 + c1, 0 ≤ c2 < b; q2 = b . q3 + c1, 0 ≤ c3 < b; …; qn-2 = b . qn-1 + cn-1, 0 ≤ cn-1 < b; qn-1 = b . qn + cn, 0 ≤ cn < b; …, com cada ci e cada qi únicos. Pela proposição 1.5, como a > 0 e b > 1, temos que qi ≥ 0 e qi+1 < qi, para todo i = 0, 1, ..., n, .... Assim obtemos uma sequência q0 > q1 > ... > qn > ... ≥ 0 e então pelo corolário 6.3, existe n tal qn = 0. Logo, qn-1 = cn e, por substituição, qn-2 = b . cn + cn-1 qn-3 = b . (b . cn + cn-1) + cn -2 = cn . b2 + cn-1 . b + cn-2 . . . a = cn . bn + cn-1 . bn-1 + ... + c1 . b + c0 com c0, c1, ..., cn únicos, como queríamos demonstrar. A expressão a = cn . bn + cn-1 . bn-1 + ... + c1 . b + c0, com 0 ≤ ci < b, i = 0, 1, ..., n é chamada expansão b-ádica do inteiro a, com denominações particulares para alguns valores de b: para b = 2, expansão binária; para b = 3, expansão ternária. Por exemplo, como 11 = 2 . 5 + 1, 5 = 2 . 2 + 1, 2 = 2 . 1 + 0, 1 = 2 . 0 + 1, temos 5 = 2 . 2 + 1 = 2 . (2 . 1 + 0) + 1 = 1 . 22 + 0 . 2 + 1. 11 = 2 . 5 + 1 = 2 . (1 . 22 + 0 . 2 + 1) + 1 = 1 . 23 + 0 . 22 + 1 . 2 + 1, e, assim 1 . 23 + 0 . 22 + 1 . 2 + 1 é a expansão binária de 11. Dado um inteiro b > 1, o sistema de numeração de base b é obtido definindo-se um conjunto de b símbolos (os símbolos 0 e 1 incluídos) para representar os inteiros ci, i = 0, 1, ..., b - 1, com 0 ≤ ci < b, representando-se então um inteiro positivo a de expansão b-ádica a = cn . bn + cn-1 . bn-1 + ... + c1 . b + c0 por a = (cncn-1...c1c0)b, onde, aí, estamos identificando ci com o símbolo que o representa. O inteiro (0cncn-1...c1c0)b é identificado com o inteiro (cncn-1...c1c0)b e um inteiro negativo é representado pelo seu simétrico precedido do sinal – (lido menos). Em a = (cncn-1...c1c0)b, dizemos que c0, ..., cn são os dígitos ou algarismos de a no sistema de base b e n + 1 é dito número de dígitos de a. Dizemos também que c0 é o algarismo da casa das unidades. É interessante observar que, como b = 1 . b + 0, a base b sempre é representada no sistema de base b por 10, ou seja (b)b = 10. O sistema de numeração mais utilizado é o sistema decimal, onde a base b é a cardinalidade do conjunto dos dedos das mãos da maioria dos seres humanos e os algarismos são 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, chamados, respectivamente, zero, um, dois, três, quatro, cinco, seis, sete, oito e nove, como 61 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão já utilizamos no conjunto dos números naturais. Da mesma forma que 2 = 1 + 1, temos 3 = 2 + 1, 4 = 3 + 1, 5 = 4 + 1, 6 = 5 + 1, e assim sucessivamente. Observe que ao se escrever 2 = 1 + 1, estamos usando os números inteiros representados pelos algarismos 2 e 1. A base do sistema decimal é chamada dez e, como foi dito acima, é representada por 10. Geralmente se omite a indicação da base quando o sistema decimal é utilizado. Dessa forma, (324)10 é escrito, simplesmente, 324 e é a representação do inteiro 3 . 102 + 2 . 10 + 4. Quando a representação do número inteiro no sistema decimal tem mais de três algarismos, espaços em branco podem ser utilizados para separar, da direita para a esquerda, grupos de três algarismos. Assim, 4 324 591 é a representação do número 4 . 106 + 3 . 105 + 2 . 104 + 4 . 103 + + 5 . 102 + 9 . 101 + 1. Naturalmente, se a base b é menor do que dez, ela será representada pelo algarismo que representa o seu valor e os símbolos adotados são aqueles que representam os inteiros menores que a base. Assim, se a base é 7, os símbolos utilizados são 0, 1, 2, 3, 4, 5 e 6. Se a base é 2, os símbolos são 0 e 1 e o sistema é chamado sistema binário, fundamental para representação de inteiros em computadores. Se a base é maior que 10 é comum se utilizar letras para indicar os algarismos que representam os inteiros maiores que 9. Assim se a base é 16, os símbolos adotados são 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Como 323 = 5 . 64 + 3, 64 = 5. 12 + 4, 12 = 5 . 2 + 2, 2 = 5 . 0 + 2. temos, 64 = 5. 12 + 4 = 5 . (5 . 2 + 2) + 4 = 2 . 52 + 2 . 5 + 4, 323 = 5 . 64 + 3 = 5 . (2 . 52 + 2. 5 + 4) + 3 = 2 . 53 + 2. 52 + 4 . 5 + 3; e, então, 323 = (2243)5. Dizemos que fizemos a conversão do 323 do sistema decimal para o sistema de base cinco. Observe que o próprio enunciado do teorema 2.5 e o conceito de sistema de numeração fornecem um algoritmo para a conversão de um inteiro escrito no sistema decimal para o sistema de uma base qualquer: z = (cncn-1...c1c0)b, c0 = r(z, b), c1 = r(q(z, b), b) e, assim, sucessivamente. Por exemplo, para se converter 45 para o sistema binário, temos 45 = 2 . 22 + 1, 22 = 2 . 11 + 0, 11 = 2 . 5 + 1, 5 = 2 . 2 + 1, 2 = 2 . 1 + 0, 1 = 2 . 0 + 1, e, então, 45 = (101101)2. A conversão de um inteiro escrito num sistema de base b qualquer para o sistema decimal é mais simples, bastando calcular, no sistema decimal, a expressão b-ádica do número. Por exemplo, como (23501)7 = 2 . 74 + 3 . 73 + 5 . 72 + 0 . 7 + 1, temos que (23501)7 = 4 802 + 1 029 + 245 + 0 + + 1 e, então, (23501)7 = 6 077. 5.5 Somas e produtos de inteiros Tendo aprendido a representar os inteiros, vamos discutir agora algoritmos para a realização de operações com inteiros, os quais nos são ensinados (ou ensinamos) nas séries iniciais do ensino 62 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão para que sejam muitos leitores), são utilizados como símbolos básicos as letras do alfabeto; na linguagem falada, os símbolos básicos são os fonemas. Para os computadores, considerando que os símbolos são obtidos através da ocorrência ou não de fenômenos físicos (tem corrente/não tem corrente, está magnetizado/não está magnetizado, etc.), foram adotados dois símbolos, cada um deles chamado bit (acrossemia de binary digit ), representados por 0 (zero) e por 1 (um). Assim, a comunicação entre as unidades é feita através de sequências de zeros e uns, da mesma forma que os dados são armazenados na memória também como sequências de zeros e uns. A linguagem onde as palavras são sequências deste tipo é chamada linguagem de máquina e um computador só é capaz de executar instruções (e, por consequência, algoritmos) escritas em linguagem de máquina. Como esta linguagem não é corriqueira para o ser humano, cientistas da computação desenvolveram sistemas, chamados compiladores, capazes de traduzir instruções escritas numa linguagem comum para linguagem de máquina. Surgiram então as chamadas linguagens de alto nível, como Pascal, C, Fortran, Java e muitas outras. Aí, a expressão alto nível não está no sentido de qualidade e sim no sentido de que a linguagem está mais "próxima" do ser humano. Normalmente, um algoritmo escrito numa linguagem de alto nível é chamado programa. Para que a linguagem do ser humano possa ser traduzida para a linguagem de máquina (por exemplo, este livro foi editado num processador de texto e quando estava sendo digitado, o processador de texto traduzia cada palavra para a linguagem de máquina), é necessário se estabelecer uma codificação que fixa uma sequência de bits para cada símbolo da nossa linguagem. Uma codificação utilizada é o Código ASCII (acrossemia de American Standard Code for Information Interchange). Neste código, cada caractere é codificado como uma sequência de 8 bits. A sequência correspondente à letra A é 01000001, a correspondente a B é 01000010, enquanto que a sequência correspondente à letra a é 01100001. Naturalmente, a referência aos códigos de cada letra é facilitada vendo-se cada sequência de bits como um inteiro no sistema binário de numeração e se associando o inteiro correspondente do sistema decimal. Assim, como (1000001)2 = 65, dizemos que o código ASCII decimal de A é 65. O código ASCII decimal de B é 66 e assim sucessivamente, sendo o código ASCII de Z igual a 90. Por outro lado, o código de a é (1100001)2 = 97 e o da letra z é 122. Observe a necessidade de codificações diferentes para os padrões maiúsculo e minúsculo de uma mesma letra para que os sistemas possam encará-los como objetos distintos. Observe também que o código ASCII decimal pode ser visto como uma função do conjunto dos caracteres no conjunto dos naturais. Daqui por diante, esta função será representada por Ascii(x). Uma questão a ser levantada: sendo o código Ascii(Z) = 90, por que Ascii(a) = 97 e não Ascii(a) = 91, como uma “lógica sequencial” induziria?. Observe que as representações das letras maiúsculas variam de 01000001 (letra A) até 01011011 (letra Z) e o código ASCII decimal de uma letra minúscula difere de 32 do código ASCII decimal da letra maiúscula correspondente. Isto não foi obra do acaso. Como 32 = (100000)2, a diferença entre as representações dos padrões minúsculo e maiúsculo de uma mesma letra se dá apenas no segundo bit (da esquerda para direita) da representação. Levando em conta o fato de que a mudança entre os padrões maiúsculo e minúsculo é uma operação bastante utilizada nos sistemas de computação e que a mudança de um bit é uma operação muito simples de ser realizada em computadores, a escolha acima referida contribui para programas mais rápidos. 5.6.2 Representação de inteiros em computadores Um número inteiro positivo é armazenado através da sua representação no sistema binário com uma quantidade de bits que depende do sistema de computação. Naturalmente, como o conjunto dos bits a serem utilizados é finito (suponhamos, de cardinalidade n), o subconjunto dos inteiros que podem ser armazenados tem um elemento máximo: o maior inteiro cuja representação 65 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão no sistema binário tem n dígitos. A proposição a seguir fornece uma fórmula para a determinação deste maior elemento. Proposição 4.5 O maior número inteiro do sistema decimal que possui n dígitos no sistema binário é z =2n – 1. Demonstração Para que z seja o maior inteiro com n dígitos no sistema binário devemos ter z = (11...1)2, com os n dígitos iguais a 1. Assim, a expansão binária de z é z = 2n-1 + 2n-2 + ... + 2 + 1. Como, pelo exercício 3.17, an – bn = (a – b) . (an-1 + an-2 . b + an-3 . b2 + … + a . bn-2 + bn-1), quaisquer que sejam os inteiros a, b e n, com n > 1, temos, para a = 2 e b = 1, 2n - 1n = (2 - 1) . (2n-1 + 2n-2 + ... + 2 + 1) e, assim, z = 2n - 1. As formas de armazenamento de um inteiro negativo fogem ao escopo deste livro. 5.6.3 Divisão por dois em computadores Seja um inteiro b, maior que 1, e seja um inteiro positivo z, cuja representação no sistema de base b é z = (cncn-1...c1c0)b. Desta forma temos z = cn . bn + cn-1 . bn-1 + ... + c1 . b + c0 o que implica z = (cn . bn-1 + cn-1 . bn-2 + ... + c1 ) . b + c0. Assim, como 0 ≤ c0 < b, temos que q(z, b) = (cncn-1...c1)b e r(z, b) = c0. Conclusão: como os números inteiros positivos são representados em computadores pelas suas representações no sistema binário, o quociente da divisão de um inteiro positivo por dois é obtido internamente num computador por um deslocamento de uma posição para direita dos bits e o resto da divisão de um inteiro por dois é igual ao bit da casa das unidades. Como o deslocamento para direita e a determinação do bit casa das unidades são “operações” de realizações fáceis, a divisão euclidiana por dois em computadores é uma operação bastante eficiente. 5.6.4 Um algoritmo rápido para potências No exercício 3.16 definimos, para z, n ∈ ℤ, z ≠ 0 e n ≥ 0, a potência de base z e expoente n por No exercício referido se pedia para provar que a) am . an = am+n. b) (am)n = am. n. c) am . bm = (a . b)m. Estas propriedades permitem que se estabeleça facilmente um algoritmo para calcular um potência zn, dados z e n, como vimos no capítulo 4. Algoritmo potencia leia(z, n); p := 1; i := 1; repita enquanto n ≥ i p := p . z; 66 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão i := i + 1; escreva(p); Por exemplo, a tabela abaixo mostra a execução deste algoritmo para z = 3 e n = 5. z n p i 3 5 1 1 3 2 9 3 27 4 81 5 243 6 Quando i = 6, a estrutura de repetição é interrompida e o algoritmo fornece para 35 o valor p = 243. Observe que o número de iterações da estrutura de repetição é igual ao expoente n. A representação do expoente no sistema binário e as propriedades acima podem ser utilizadas para se obter um algoritmo como um número de iterações sensivelmente menor. Para se calcular x5, podemos pensar em x5=x1.2 2+1=x2 2 . x1 , e necessitaríamos de apenas três multiplicações: uma para calcular x2, outra para calcular x4 = x2 . x2 e outra para calcular x4. x. De um modo geral, se queremos calcular zn e temos n = as . 2s + as-1 . 2s-1 + ... + a1 . 2 + a0, com ai = 1 ou ai = 0, para todo i = 0, 1, ..., s, teremos . Fazendo p1 = z a0 , teremos Observe que, se a0 = 0, teremos p1 = 1 e p1 não influirá no cálculo de zn. Observe também que a0 = 0 se e somente se r(n, 2) = 0. Da igualdade acima, temos e, fazendo p2= z2  a1. p1 , obtemos Naturalmente, obtemos uma sequência p1, p2, ..., ps tal que ps = zn. Observe que se qi = as . 2s-i + as-1 . 2s-(i+1) + ... + ai então, se qi-1 é par, q i= qi−1 2 e, se qi-1 é ímpar, q i= qi−1−1 2 . Para z = 3 e n = 13, por exemplo, teríamos, 313 = 31.2 31.220.211=321.2 21 .20 .1 . 31 e, então, p1 = 3. Continuando, 313 = 3221.2 11.1 .320 . p1 ; p2 = 1 . p1 = 3 e 3 13 = 342 1 .1 . 32 21 . p2 o que dá p3 = 32 2 . p2=92 . 3=243 . Finalmente, p4 = 3 4 2 . 243 . Temos o seguinte algoritmo. algoritmo PotênciaVersao2; 67 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão 6. Números primos 6.1 Introdução Tendo construído axiomaticamente o conjunto dos números inteiros e sido apresentada uma maneira de representá-los, neste capítulo estudaremos alguns inteiros especiais, que, além de terem aplicações naturais na Matemática, são aplicados no Sistema de Criptografia RSA, objeto de estudo do capítulo seguinte. Além de estudar propriedades dos inteiros, serão vistos vários aspectos atuais e históricos da Matemática. 6.2 Máximo divisor comum No capítulo anterior apresentamos o conceito de divisor de um número inteiro dado: y é divisor de z (simbologia y|z) se existe q tal que z = y . q. Nesta seção, procuraremos analisar os divisores comuns de dois inteiros dados, em particular, o maior destes divisores comuns, chamado, por razões óbvias, de máximo divisor comum dos dois números e indicado por mdc(z, y). Por exemplo, como os divisores positivos de 20 são 1, 2, 4, 5, 10 e 20 e os divisores de 24 são 1, 2, 3, 4, 6, 8, 12 e 24, temos que mdc(20, 24) = 4. Observe que este exemplo já indica um algoritmo para se determinar o máximo divisor comum de dois inteiros z e y: 1. Determina-se os conjuntos D(z) e D(y) contendo todos os divisores de z e de y; 2. Determina-se o conjunto D(z) ∩ D(y); 3. Determina-se o maior elemento de D(z) ∩ D(y). O problema com este algoritmo é que, como será mostrado adiante, não existe algoritmo eficiente para obtenção de divisores de um número muito grande (aí, algoritmo eficiente significa que seja um algoritmo que forneça sua saída num tempo razoável). Apresentaremos a seguir um algoritmo (concebido pelo matemático grego Euclides, que viveu de 330 a. C. a 275 a. C., na cidade de Alexandria, na Grécia) que calcula de forma eficiente o máximo divisor comum de dois números dados. A demonstração do algoritmo de Euclides requer o resultado dado no seguinte lema. Lema 1.6 Se z, y são inteiros positivos, então mdc(z, y) = mdc(y, z - y . m), qualquer que seja o inteiro m. Demonstração Sejam d1 = mdc(z, y) e d2 = mdc(y, z - y . m). Vamos mostrar que d2 ≤ d1 e que d1 ≤ d2 . De d2 = mdc(y, z - y . m) temos que d2|y e d2|(z - y . m). Daí, d2|z. Assim, d2 é divisor comum de z e y e então d2 ≤ d1, já que d1 = mdc(z, y). Mutatis mutandis se demonstra que d1 ≤ d2 (mutatis mutandis é uma expressão latina que significa mudando o que se deve). Observe que se tomarmos m = q( z, y), temos que z - y . m = r, onde r = r(z, y). Dessa forma, temos o seguinte corolário do lema 1.6. Corolário 1.6 Se z, y são inteiros positivos e r = r(z, y), então mdc(z, y) = mdc(y, r). Com a utilização deste corolário, a determinação de mdc(20, 24) seria: mdc(20, 24) = mdc(24, 20) = mdc(20, 4) = mdc(4, 0) = 4, sendo esta última igualdade explicada pelo fato de que 4|0 e 4 é, obviamente, o maior divisor de 4. A aplicação do corolário pode ser simplificada pelo fato de que o máximo divisor satisfaz às seguintes propriedades que decorrem imediatamente da definição e cujas demonstrações serão 70 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão deixadas como exercício. Propriedades do máximo divisor comum a) mdc(a, b) = mdc(|a|, |b|). b) mdc(a, b) = mdc(b, a). c) Se b|a, então mdc(a, b) = |b|. Por exemplo, mdc(504, 540) = mdc(540, 504) = mdc(504, 36) = 36, pois 36|504. Outro exemplo: mdc(200, 73) = mdc(73, 54) = mdc(54, 19) = mdc(19, 16) = mdc(16, 3) = = mdc(3, 1) = 1. Teorema 1.6 (algoritmo de Euclides) Sejam z e y dois inteiros positivos. Se z = y . q1 + r1, com 0 ≤ r1 < y y = r1 . q2 + r2, com 0 ≤ r2 < r1 r1 = r2 . q3 + r3, com 0 ≤ r3 < r2 r2 = r3 . q4 + r4, com 0 ≤ r4 < r3 . . . rn-4 = rn-3 . qn-2 + rn-2, com 0 ≤ rn-2 < rn-3 rn-3 = rn-2 . qn-1 + rn-1, com 0 ≤ rn-1 < rn-2 rn-2 = rn-1 . qn + rn, com 0 ≤ rn < rn-1 . . ., então existe n tal que rn = 0 e rn-1 = mdc(z, y). Além disso, existem inteiros t e u tais que t . z + u . y = mdc(z, y). Demonstração Das desigualdades relativas aos restos, temos que y > r1 > r2 > r3 > ... > rn > ... ≥ 0 e então, pelo corolário 5.3, existe n tal que rn = 0. Por outro lado, pelo corolário 1.6, mdc(z, y) = mdc(y, r1) = = mdc(r1, r2) = mdc(r2, r3) = … = mdc(rn-3, rn-2) = mdc(rn-2, rn-1) = rn-1. Além disso, de mdc(z, y) = rn-1 segue mdc(z, y) = rn-3 - rn-2 . qn-1, na qual podemos substituir rn-2 = rn-4 - rn-3 . qn-2, obtendo mdc(z, y) = rn-3 - (rn-4 - rn-3 . qn-2). qn-1. Nesta igualdade podemos substituir rn-3 = rn-5 - rn-4 . qn-3, e, seguindo substituindo retroativamente, encontraremos t e u tais que t . z + u . y = mdc(z , y). A aplicação deste algoritmo “na mão” (isto é, com lápis e papel) pode ser feita no esquema abaixo, onde calculamos mdc( 396, 84): 396 84 60 24 12 0 4 1 2 2 concluindo que mdc(396, 84) = 12. Observe que este esquema é simplesmente uma maneira prática de se realizar as divisões 396 = 84 . 4 + 60, 84 = 60 . 1 + 24, 60 = 24 . 2 + 12, 24 = 12 .2 e r4 = 0. Para encontrar os inteiros m e n tais que m . 396 + n . 84 = 12 temos as seguintes igualdades: 12 = 60 – 2 . 24, 12 = 60 – 2 . (84 – 1 . 60) = -2 . 84 + 3 . 60, 12 = -2 . 84 + 3 . (396 - 84 . 4) = 3 . 396 – 14 . 84, 71 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão e, portanto, m = 3 e n = -14. É interessante observar que a recíproca da segunda parte do teorema anterior não é verdadeira. Isto é, se z, y e d são inteiros e existem inteiros t e u tais t . z + u . y = d não se tem necessariamente d = mdc(z, y). Por exemplo, existem inteiros t e u (t = 2 e u = -2) tais que 15 . t + 10 . u = 10 mas mdc(15, 10) = 5. Mostraremos na próxima seção que esta recíproca é verdadeira quando o máximo divisor comum dos dois inteiros é igual 1. Na linguagem algorítmica estabelecida no capítulo 4, a parte do Algoritmo de Euclides que trata da determinação do máximo divisor comum de dois inteiros (quando ambos são positivos) seria escrita da seguinte forma: algoritmo deEuclides; leia(a, b); r := resto(a, b); repita enquanto r > 0 a := b; b := r; r := resto(a, b); mdc := b; escreva(mdc); A eficiência deste algoritmo, que é medida pelo números de iterações do comando repita enquanto, será discutida no capítulo 9. A escrita da segunda parte do Algoritmo de Euclides (a que trata da existência de inteiros t e u tais que t . z + u . y = mdc(z, y)) na linguagem algorítmica foge ao escopo do livro. 6.3 Inteiros primos entre si Na seção anterior afirmamos que a recíproca da segunda parte do Algoritmo de Euclides (se d = mdc(z, y), então existem inteiros t e u tais que t . z + u . y = d) só era verdadeira se d = 1. Ou seja, como veremos na proposição seguinte, se existem inteiros t e u tais que t . z + u . y = 1, então mdc(z, y) = 1. Além da veracidade desta recíproca, o fato de o máximo divisor comum de dois inteiros ser igual a 1 é importante pois ele gera outras propriedades interessantes. Para facilitar a linguagem, quando mdc(z, y) = 1, dizemos que os dois inteiros z e y são primos entre si (ou co- primos) ou que um dos inteiros é primo em relação ao outro. Observe que desta definição decorre que dois inteiros primos entre si não possuem divisores positivos comuns diferentes de 1 (um). Proposição 1.6 Sejam z e y dois inteiros. Se existem inteiros t e u tais que z . t + y . u = 1, então mdc(z, y) = 1. Demonstração Seja d = mdc(z, y). Assim, d|z e d|y o que implica d|(z . t + y . u). Daí, d|1 o que acarreta d = 1, já que d > 0. As outras propriedades de pares de inteiros primos entre si são apresentadas na seguinte proposição. Proposição 2.6 Sejam a, b e c inteiros positivos, com a e b primos entre si. Então a) Se b|(a . c), então b|c. b) Se a|c e b|c, então (a . b)|c. Demonstração 72 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Demonstração Como d|z, existe q tal que z = d . q. Como d é o menor divisor de z, temos que d ≤ q. Daí, de d > 1 segue d . d ≤ d . q o que resulta d2 ≤ z. Esta proposição implica que se um inteiro z, maior do que 1, não possui um divisor primo p tal que p2 ≤ z, então ele z é primo. Assim o algoritmo acima poderia ser modificado para o seguinte algoritmo, que retorna um divisor primo de z, se z for composto, ou a constatação de que z é primo. Ou seja, o algoritmo abaixo, procurando o menor dos seus fatores (fatorando-o), verifica se um inteiro dado é ou não primo. algoritmo DivisorPrimo leia(z); d := 2; repita enquanto (d não divide z) e (d2 ≤ z) d := d + 1; se (d divide z) escreva(d ‘é divisor primo de’ z) senão escreva(z ‘é primo’); Representando ⌊z ⌋ o maior inteiro n tal que n2 ≤ z, temos que o número de laços do algoritmo acima é, no máximo, ⌊z ⌋ , o que ocorre quando z é primo. Mesmo com esta melhora o algoritmo fica muito ineficiente se z é um número primo muito grande. Observe que em cada laço são efetuadas um divisão (para verificar se d é divisor de z), uma multiplicação (para calcular d2) e uma soma (para incrementar d), sem falar em comparações. Preocupando-nos apenas com a divisão - esta é a operação de realização mais demorada -, suponhamos um computador que realize 1020 divisões por segundo. Se z possui 81 algarismos, então z ≥ 1080 e portanto ⌊z ⌋ ≥ 1040. Assim o algoritmo realizaria, no mínimo, 1040 laços e levaria, apenas para efetuar as divisões, 10 40 10 20 =10 20 segundos. Este intervalo de tempo corresponde a “aproximadamente” 1012 anos! Na verdade, não existe ainda um algoritmo eficiente para encontrar um fator primo de um inteiro. Vale observar que o sistema de criptografia RSA, que será estudado no capítulo seguinte, trabalha com primos com cerca de 300 algarismos. O resultado da proposição anterior também pode ser usado para justificar o mais antigo método de geração de todos os primos positivos menores que um inteiro positivo dado, o Crivo de Eratóstenes (Eratóstenes foi um matemático grego que viveu, estimadamente falando, nos anos de 284 a. C. a 250 a. C.). Vamos descrever o crivo de Eratóstenes para determinar todos os primos positivos menores que 300, sendo as ações solicitadas apresentadas no quadro a seguir. 1. Escreva o número 2 e todos os inteiros ímpares maiores do que 1 e menores que 300 (os números pares maiores que dois não são primos). 2. O número 2 é primo. Como 22 = 4, todos os números menores do que 4 são primos. Daí, 3 é primo. Risque todos os múltiplos de 3: 9, 15, ..., 297. 3. Como 32 = 9, todos os números menores do que 9 não riscados são primos. Daí, 2, 3, 5 e 7 também são primos. Risque todos os múltiplos de 5: 15, 25, 35, ..., 295 e todos os múltiplos de 7: 21, 35, 49, ..., 287. 4. Como 72 = 49, todos os números menores do que 49 não riscados são primos. Daí, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 são primos. Risque todos os múltiplos destes números. 5. Como 472 > 300, todos os números do crivo não riscados são primos. 75 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177 179 181 183 185 187 189 191 193 195 197 199 201 203 205 207 209 211 213 215 217 219 221 223 225 227 229 231 233 235 237 239 241 243 245 247 249 251 253 255 257 259 261 263 265 267 269 271 273 275 277 279 281 283 285 287 289 291 293 295 297 299 Evidentemente, a garantia de que todos os números não riscados são primos é dada pela proposição 6.6, pois cada número y não riscado não possui um divisor primo p tal que p2 ≤ y. Uma simplificação pode ser efetuada neste algoritmo, tornando-o mais eficiente (ou menos ineficiente). A simplificação proposta a seguir é justificada pela observação de que ao se riscar os múltiplos de um primo p, os múltiplos de p que possuem divisores menores que p já foram riscados. Dessa forma, pode-se começar a riscar os múltiplos de p a partir de p2. Há um algoritmo que, sem determinações de fatores, verifica se um inteiro dado é primo. Este algoritmo é baseado no Pequeno Teorema de Fermat, que será discutido a seguir Para sua demonstração, necessitamos do seguinte lema. Lema 1.6 Se p é um número primo e i é um inteiro tal que 1 ≤ i < p, então p é divisor de Cp,i. Demonstração Pela definição dada no exercício 5.15, i! . (p - i)!. Cp,i = p! o que mostra que p é divisor do produto do primeiro membro. Então, pela proposição anterior, p|i! ou p|(p - 1)! ou p| Cp,i. Se ocorresse a primeira ou a segunda teríamos, pela proposição citada, p|1 ou p|2 ou ... p|i ou … p|(p - 1) o que é um absurdo pois k < p, qualquer que seja k ∈ {1, 2, ..., i, ..., p - 1}. Logo p| Cp,i. Teorema 2.6 (Pequeno Teorema de Fermat) Se p é primo, então p|(ap – a), qualquer que seja o inteiro não nulo a. Demonstração Por indução, provemos inicialmente que o teorema é verdadeiro para todo inteiro a > 0. Para isto, seja então p um número primo e considere o predicado definido no conjunto dos inteiros positivos P(a) = V se p|(ap – a). Temos que P(1) = V pois 1p – 1 = 0 e p|0 sempre. Suponhamos que P(a) = V e provemos que P(a + 1) = V. Pela fórmula do binômio de Newton (exercício 5.17), temos que (a + 1)p - (a + 1) = (ap. + Cp,1 . ap - 1 + ... + Cp,,i . ap - i + ... + Cp,p-1 . a + 1) - (a + 1) = = (ap. - a) + (Cp,1 . ap - 1 + ... + Cp,,i . ap - i + ... + Cp,p-1 . a), e a hipótese de indução e o lema anterior implicam p|((a + 1)p - (a + 1)), como queríamos. Agora, analisemos o caso a < 0. Se p = 2, como a2 - a é sempre par, temos p|(a2 - a); se p ≠ 2, temos que p ímpar e, então, |a|p - |a| = (-a)p - (-a) = -(ap - a). Assim, como p|(|a|p - |a|), temos p|(ap – a). 76 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Corolário 1.6 Se p é primo e a é um inteiro primo em relação a p, então p|(ap-1 – 1). Demonstração De p|(ap – a) segue que p|(a . (ap-1 – 1)) e, então, como p e a são primos entre si, a proposição 2.6 garante a afirmação. Corolário 2.6 Se k é um inteiro positivo tal que k > 1 e k|(ak-1 – 1) para todo inteiro a, com 0 < a < k – 1, então k é primo. Demonstração Se k é composto, então existe um primo p tal que 1 < p < k – 1 e p|k. Como p < k – 1 temos k|(pk-1 – 1). Daí e de p|k temos p|(pk-1 – 1), o que implica p|1, uma contradição. Dessa forma o algoritmo abaixo verifica, sem fatorações, se um inteiro dado é primo. algoritmo Primo leia(k) a := 2; repita enquanto (Resto(ak-1 – 1, k) = 0) e (a < k – 1)) a := a + 1; se (a = k – 1) escreva(k ‘é primo') senão escreva(k ‘é composto’); Infelizmente (ou felizmente, dependendo do ângulo do olhar), o algoritmo acima também não é eficiente. Há bastante tempo, muitos matemáticos brilhantes vinham perseguindo a descoberta de um algoritmo que, de forma eficiente, verificasse a primalidade de um inteiro. Os esforços dispendidos foram tantos que já havia dúvidas da existência de um tal algoritmo. Em 2002, de forma surpreendente, os cientistas indianos Manindra Agrawal, Neeraj Kayal e Nitin Saxena encontraram uma solução para esta questão (Coutinho, S. C. - 2004). Agora mostraremos que os primos “geram” todos os números inteiros, no sentido de que todo inteiro é o produto de potências de primos. Teorema 3.6 (Teorema Fundamental da Aritmética) Todo inteiro z ≥ 2 se escreve, de modo único, na forma z = p1 e1 . p2 e2 . . . . . p k ek , onde p1, p2, ..., pk são números primos tais que p1 < p2 < ... < pk e e1, e2, ..., ek são inteiros positivos. Demonstração Consideremos o seguinte algoritmo: algoritmo Fatoração leia(z); i := 1; ni := z; qi := 2; repita enquanto ni > 1 repita enquanto (qi não divide ni) qi := qi + 1; escreva qi; 77 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Na História da Ciência, um sonho que sempre esteve (e sempre estará) presente na mente dos matemáticos foi (é) encontrar fórmulas que gerassem (gerem) números primos. A primeira ilusão na procura de alguma fórmula geradora de primos incluía o conceito de fatorial primo. Como para p > 2, p# é sempre par temos que o único fatorial primo é 2#. É interessante observar, porém, que para todo primo p menor do que 11, (p#) + 1 é primo, conforme mostra a seguinte tabela p p# (p#) +1 2 2 3 3 6 7 5 30 31 7 210 211 11 2310 2311 Entretanto, (13#) + 1 = 30030 + 1 = 30031 = 59 . 509 e, então, (13#) + 1 é composto. Na verdade, são conhecidos apenas outros vinte números primos da forma (p#) + 1, sendo o maior deles (392113#)+1, que possui 169.966 dígitos (http://primes.utm.edu/top20/page.php?id=5, acessada em 16/11/2011). Uma outra fórmula tentada foi a fórmula polinomial que foi descartada em função de um teorema cuja demonstração de um caso particular é solicitada no exercício 6.15 abaixo. Outras fórmulas tentadas foram as fórmulas exponenciais do tipo zn – 1 e zn + 1. Sobre o primeiro tipo temos a seguinte proposição. Proposição 8.6 Sejam z e n inteiros maiores que 1. Se zn – 1 é primo então z = 2 e n é primo. Demonstração: Do exercício 5.12 temos que (z – 1)|(zn – 1) e, daí, como zn – 1 é primo, z – 1 = 1 ou z – 1 = zn – 1. Se a segunda destas igualdades ocorresse teríamos zn = z, o que implica zn-1 = 1. Assim teríamos, z = 1 ou n = 1, valores que contrariam a hipótese “z e n inteiros maiores que 1”. Logo, z – 1 = 1 o que implica z = 2. Para provar a segunda parte da proposição, suponhamos que n não é primo. Assim, existem inteiros n1 e n2, com 1 < n1 < n e 1 < n2 < n, tais que n = n1 . n2. Porém, pelo exercício 5.12 e pela igualdade 2n1 n 2−1=2n−1 , temos 2n1−1 ∣2n−1  e isto contraria o fato de que 2n – 1 é primo, pois 12n 1−12n−1 . Os números da forma M(n) = 2n – 1 são chamados números de Mersenne. O matemático amador Marin Mersenne (França, 1588) conjecturou que M(n) seria primo para n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 e seria composto para os outros quarenta e quatro valores primos menores do que 257. Um primeiro erro desta lista foi encontrado em 1886 quando se descobriu que M(61) é primo. Além deste erro, também já foi provado que M(89) e M(107) são primos e que M(67) e M(257) são compostos. Um primo da forma M(n) é chamado primo de Mersenne e a procura por primos de Mersenne é um campo de pesquisa muito fértil em Matemática, pelo fato de que há fortes suspeitas de que os primos "gigantes" sejam desta forma ou que, pelo menos, esta é a melhor maneira de se encontrar primos muito grandes. Há um projeto de pesquisa envolvendo pesquisadores de várias partes do mundo denominado GIMPS (Great Internet Mersenne Primes Searh-www.mersenne.org, acessada em 21/07/2011) cujo objetivo é encontrar primos de Mersenne. Em 23 de agosto de 2008, foi encontrado o 45° primo de Mersenne conhecido: 243.112.609- 1, com 12.978.189 dígitos, feito que foi contemplado com um prêmio de cem mil dólares, dado pela 80 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Electronic Frontier Foundation, uma fundação norte-americana. Em 12 de abril de 2009, foi encontrado o 47º conhecido: 242.643.801 - 1, com 12.837.04 dígitos. Para fórmulas exponenciais do tipo zn + 1 temos a seguinte proposição. Proposição 9.6 Sejam z e n dois inteiros maiores que 1. Se zn + 1 é primo, então z é par e n = 2m para algum inteiro positivo m. Demonstração: Se z fosse ímpar zn + 1 seria par e então não seria primo. Pela fatoração de n temos que z = 2m . r, com m inteiro positivo e r ímpar e então, do exercício 5.12, z 2m1 ∣z 2 m r1 . Como z 2m r1 =zn1 e este é primo, temos que r = 1 e n = 2m, como queríamos demonstrar. Os números da forma Fn = 22 n 1 são chamados números de Fermat, devido ao fato de que Fermat havia conjecturado que todo número da forma Fn era primo. Observe que F0 = 21 + 1 = 3, F1 = 22 + 1 = 5, F2 = 24 + 1 = 17, F3 = 28 + 1 = 257, F4 = 216 + 1 = 65.537 são todos primos. Porém, no século dezoito, o matemático alemão Leonard Euler provou que 641|F5 (F5 = 232 + 1 = = 4.294.967.297) mostrando que a conjectura de Fermat era falsa. Os únicos primos de Fermat conhecidos (http://mathworld.wolfram.com/FermatPrime.html, acessada em 21/07/2011) são F0, F1, F2, F3 e F4. Todos os números de Fermat Fn com n > 4 estudados até agora são compostos. 6.7 A Conjectura de Goldbach Nesta seção, falaremos brevemente sobre um dos mais antigos problemas em aberto (problemas para os quais não se tem uma solução) da Teoria dos Números. Em 7 de julho de 1742, Christian Goldbach, matemático prussiano, numa carta que escreveu ao matemático suíço Leonard Euler fez a seguinte observação: qualquer número par maior que seis parecia ser a soma de três números primos (nesta época, o inteiro 1 (um) era considerado número primo). Euler verificou então que a veracidade da hipótese de Goldbach implicaria na veracidade da seguinte afirmação (bem mais simples que a original): todo número par maior que 2 é a soma de dois números primos (agora, já não incluindo o 1 (um) como primo). Embora a afirmação de Euler (conhecida hoje como a Conjectura de Goldbach) já tenha sido verificada para todos os inteiros pares menores que 22 . 1017 (www.ieeta.pt/~tos/goldbach.html, acessada em 21/07/2011), até hoje não foi provada, mesmo considerando os esforços dispendidos por muitos matemáticos. 6.8 O Último Teorema de Fermat Embora o assunto a ser discutido aqui não tenha relação com o título do capítulo, vamos aproveitar a discussão a respeito de fatos históricos e atuais da Matemática para tecer alguns comentários sobre o Último Teorema de Fermat que, segundo Singh, S. (Singh 1998), foi "o enigma que confundiu as maiores mentes do mundo durante 358 anos" ou "o problema mais difícil da Terra", segundo Lynch, J. prefaciador da referência bibliográfica citada. Pierre de Fermat nasceu na França em 1.601 e era matemático amador, estudando e criando matemática por puro diletantismo. Diofante de Alexandria, matemático que viveu, provavelmente, nos anos 250 d. C. escreveu treze livros sobre a teoria dos números, coleção chamada de Aritmética. Quando estudava o Livro II da Aritmética de Diofante, Fermat ficou entusiasmado com o estudo dos trios pitagóricos, inteiros x, y e z tais que x2 + y2 = z2. Séculos atrás, Euclides já havia demonstrado 81 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão que existe uma infinidade de trios pitagóricos (veja exercício 6.17). Num instante de genialidade, Fermat percebeu que não existiriam inteiros x, y e z tais que x3 + y3 = z3. Evidentemente, esta percepção foi espetacular: uma pequena modificação de uma equação que possui uma infinidade de soluções produzia uma equação sem soluções. Fermat tentou equações com expoentes maiores e observou que elas também não tinham solução. Na margem da Aritmética Fermat escreveu: É impossível para um cubo ser escrito como a soma de dois cubos ou uma quarta potência ser escrita como uma soma de dois números elevado a quatro, ou, em geral, para qualquer número que seja elevado a uma potência maior do que dois ser escrito como a soma de duas potências semelhantes. Eu tenho uma demonstração realmente maravilhosa para esta proposição mas esta margem é muito estreita para contê-la. Nos últimos 350 anos, muitos matemáticos famosos tentaram demonstrar o teorema de Fermat, o que só foi conseguido por Andrew Wiles em 1995. Este feito ganhou manchetes na mídia internacional, tendo sido noticiado em todos os principais telejornais dos grandes países. Além disso, Wiles recebeu um prêmio de 50 mil libras de uma fundação alemã. 6.9 Exercícios 6.1. Mostre que, qualquer que seja o inteiro n maior que 1, os pares de inteiros abaixo são primos entre si. a) 2 . n + 1 e 3 . n + 1. b) n e n2 + 1. c) n! + 1 e (n + 1)! + 1. 6.2. Mostre que 361 e 160 são primos entre si e encontre os inteiros t e u tais que 361 . t + 160 . u = 1. 6.3. Por uma generalização muito razoável, o máximo divisor comum de vários números é o maior inteiro que é divisor dos números. Mostre que, se a1, a2, ..., an são inteiros, então mdc(a1, a2, ..., an) = mdc(mdc(a1, a2), a3, ..., an). 6.4. Sejam z e y inteiros não nulos e d = mdc(z, y). Mostre que z d e y d são primos entre si. 6.5. Sejam a, b e c números inteiros. Mostre que se a e c são primos entre si, então mdc(a . b, c) = mdc(b, c). 6.6. Sejam a e b inteiros. Mostre que, se a e b são primos entre si, então am e bn são primos entre si, quaisquer que sejam os inteiros positivos m e n. 6.7. Mostre que se p é primo, então p e (p-1)! são primos entre si. 6.8. Mostre que se n > 4 é composto, então n|(n – 1)!. 6.9. O mínimo múltiplo comum de dois inteiros z e y (simbologia: mmc(z, y)) é o menor inteiro que é múltiplo de z e múltiplo de y. a) Mostre que mmc(z, y) = z . y mdc  z, y  b) Mostre que se a é um inteiro tal que z|a e y|a, então mmc(z, y)|a. 6.10. Sejam a e b dois inteiros. Mostre que se a e b forem positivos então o conjunto das soluções positivas da equação a . x + b . y = c é finito. 6.11. Uma pessoa foi ao banco para descontar um cheque no valor de x reais e y centavos. O caixa do banco errou na leitura do valor do cheque e pagou y reais e x centavos. A pessoa guardou 82 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Por exemplo, 25 ≡ 13 mod 4, pois r(25, 4) = r(13, 4) = 1, 35 ≡ 2 mod 3, 23 ≡ (-1) mod 6, 42 ≡ 0 mod 7. Por seu turno, 36 ≢ 7 mod 2, pois r(36, 2) = 0 enquanto que r(7, 2) = 1 (a simbologia a ≢ b mod n indica, naturalmente, que a e b não são congruentes módulo n). Vale observar que num contexto no qual o valor de n está fixado a expressão mod n pode ser omitida da simbologia. Vale observar também que a verificação de uma congruência pela definição exige que se efetuem duas divisões. A proposição a seguir mostra que uma congruência pode ser verificada com uma subtração e uma divisão. Nesta proposição, e daqui por diante, n sempre representará um inteiro maior que 1. Proposição 1.7 Quaisquer que sejam os inteiros a e b, a ≡ b mod n se e somente se n|(a – b). Demonstração Se a ≡ b mod n, então r(a, n) = r(b, n) e, portanto, existem inteiros q1 e q2 tais que a = n . q1 + r e b = n . q2 + r. Daí, a – b = n . (q1 - q2) e, então, n|(a – b). Reciprocamente, suponhamos que n|(a – b) e sejam r1 = r(a, n) e r2 = r(b, n). Assim a = n . q1 + r1, com 0 ≤ r1 < n e b = n . q2 + r2, com 0 ≤ r2 < n. Daí, a – b = n . (q1 – q2) + r1 – r2 e, então, como n|(a – b), n|(r1 – r2). Logo, n|(|r1 – r2|) o que implica |r1 – r2| = 0, pois |r1 – r2| < n. Assim, r1 = r2 e a ≡ b mod n. Uma consequência imediata desta proposição relaciona a congruência módulo n com a divisão euclidiana com divisor n. Corolário 1.7 Sejam a e r inteiros, com 0 ≤ r < n. Então a ≡ r mod n se e somente se r = r(a, n). Demonstração Suponhamos inicialmente que a ≡ r mod n. Daí, n|(a – r) e então existe um inteiro q tal que a – r = n . q. Assim, a = n . q + r e, como 0 ≤ r < n, temos r = r(a, n). Reciprocamente, se r = r(a, n), existe um inteiro q tal que a = n . q + r e, então, a – r = n . q o que implica n|(a – r) e a ≡ r mod n. Como de r = r(a, n) segue que a ≡ r mod n é comum se dizer que r = r(a, n) é o valor de a módulo n. Dessa forma, podemos escrever r(a, n) = a mod n. Também poderemos escrever a mod n = b mod n no lugar de a ≡ b mod n. Naturalmente, para r = 0, o corolário anterior poderia ser enunciado: n|a se e somente se a ≡ 0 mod n. Outra consequência imediata da proposição anterior, que será usada explicitamente numa aplicação a seguir, é dada no seguinte corolário. Corolário 2.7 Se a e b são inteiros e a ≡ b mod n, então n|a se e somente se n|b. Demonstração De a ≡ b mod n segue que n|(a – b) e, portanto, se n|a então n|b e reciprocamente. 85 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Lembramos que uma relação ≈ num conjunto A é dita reflexiva se a ≈ a, qualquer que seja a ∈ A; é dita simétrica se a ≈ b implicar b ≈ a, quaisquer que sejam a, b ∈ A; é dita transitiva se a ≈ b e b ≈ c implicar a ≈ c, quaisquer que sejam a, b, c ∈ A. Lembramos também que uma relação que é reflexiva, simétrica e transitiva é chamada uma relação de equivalência. Proposição 2.7 A relação de congruência é uma relação de equivalência. Demonstração Para mostrar a reflexividade basta ver que, como n|0, temos que n|(a – a), qualquer que seja o inteiro a. Logo, a ≡ a mod n. Para a simetria basta ver que se a ≡ b mod n, temos n|(a – b), o que implica n|(b – a). Daí, b ≡ a mod n. Finalmente, para a transitividade, temos que se a ≡ b mod n e b ≡ c mod n, então n|(a – b) e n|(b – c). Logo, n|((a – b) + (b – c)) o que dá n|(a – c). Isto mostra que a ≡ c mod n. Além de gozar das propriedades acima, a congruência goza de propriedades que podem ser relacionadas com a compatibilidade com as operações no conjunto dos inteiros, conforme mostra a seguinte proposição. Proposição 3.7 Sejam a, b, c e d inteiros quaisquer. a) Se a ≡ b mod n e c ≡ d mod n, então (a + c) ≡ (b + d) mod n. b) Se a ≡ b mod n e c ≡ d mod n, então (a . c) ≡ (b . d) mod n. c) Se m é um inteiro positivo e a ≡ b mod n, então am ≡ bm mod n. Demonstração a) De a ≡ b mod n e c ≡ d mod n segue que n|(a – b) e n|(c – d). Daí, n|(a – b + c – d) o que implica (a + c) ≡ (b + d) mod n, pois a – b + c – d = (a + c) – (b + d). b) De a ≡ b mod n e c ≡ d mod n segue que n|(a – b) e n|(c – d). Daí, n|(d . (a – b) + a . (c – d)) o que implica a . c ≡ b . d mod n. c) Provemos esta propriedade por indução sobre m. i) A própria hipótese mostra que a afirmação é verdadeira para m = 1. ii) Suponhamos que ak ≡ bk mod n e provemos que ak+1 ≡ bk+1 mod n. Para isto basta aplicar o item (b) às congruências a ≡ b mod n (hipótese da proposição) e ak ≡ bk mod n (hipótese indutiva). O item (a) gera um corolário que será utilizado adiante. Corolário 3.7 Se a e b são inteiros e r1 = a mod n e r2 = b mod n, então (a + b) mod n = (r1 + r2) mod n. Demonstração De r1 = a mod n e r2 = b mod n segue que a ≡ r1 mod n e b ≡ r2 mod n o que implica (a + b) ≡ (r1 + r2) mod n e, então, (a + b) mod n = (r1 + r2) mod n. Esse corolário permite que um resto do tipo (a + b) mod n seja calculado a partir da soma dos restos a mod n e b mod n. Basta que, no final, se calcule o valor desta soma módulo n. Por exemplo, (22 + 19) mod 5 = (2 + 4) mod 5 = 1. Proposição 4.7 Sejam m e n inteiros maiores que 1 e a, b, c e d inteiros quaisquer. a) Se a ≡ b mod n e m|n então a ≡ b mod m. 86 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão b) Se (a . c) ≡ (b . c) mod n e mdc(c, n) = 1, então a ≡ b mod n. c) Se (a . b) ≡ (c . d) mod n, a ≡ c mod n e mdc(a, n) = 1, então b ≡ d mod n. Demonstração a) De a ≡ b mod n segue que n|(a – b). Daí, como m|n, temos que m|(a – b) e, portanto, a ≡ b mod m. b) De (a . c) ≡ (b . c) mod n, temos que n|(c . (a – b)). Daí, como mdc(c, n) = 1, pela proposição 2.6, n|(a – b) e a afirmação segue. c) Das duas primeiras hipóteses segue que existem inteiros i e j tais que a . b – c . d = i . n e a – c = j . n. Substituindo c = a – j . n na primeira destas equações obtemos a . b – a . d + j . n . d = i . n o que implica a . (b – d) = (i – j . d) . n. Daí, n|(a . (b – d)) e então, como mdc(a, n) = 1, n|(b – d). Naturalmente, as assertivas dos itens (b) e (c) podem ser encaradas como leis de cancelamento para congruências, sendo que a assertiva do item (c) uma generalização afirmação do item (b). 7.3 Uma aplicação: critérios de divisibilidade Sabemos desde nossos estudos do ensino fundamental que para verificar se um número dado é divisível por 9 basta verificar se a soma dos seus algarismos é divisível por 9. Nesta seção provaremos este e outros critérios de divisibilidade. Seja um inteiro z representado no sistema decimal por z = anan-1...a2a1a0. Assim, z = an . 10n + an-1 . 10n-1 + ... + a2 . 102 + a1 . 10 + a0. Para o critério de divisibilidade por 9, observe que 10 ≡ 1 mod 9 e, então, pelo item (c) da proposição 3.7, 10i ≡ 1 mod 9, qualquer que seja o inteiro i. Daí, pelo item (b) da proposição citada, ai . 10i ≡ ai mod 9, para todo i = 0, 1, ..., n. Assim, somando estas congruências, (an . 10n + an-1 . 10n-1 + ... + a1 . 10 + a0) ≡ (an + an-1 + ... + a1 + a0) mod 9 e, portanto, pelo corolário 2.7, 9|z se e somente se 9|(an + an-1 + ... + a1 + a0). Observe que o raciocínio desenvolvido acima continua válido para a divisibilidade por 3 já que 10 ≡ 1 mod 3. Assim, um número é divisível por 3 se e somente se a soma dos seus algarismos o é. Para a divisibilidade por 11, observe que 10 ≡ (-1) mod 11 e, então, 10i ≡ 1 mod 11 se i é par e 10i ≡ (-1) mod 11 se i é ímpar. Logo (an . 10n + an-1 . 10n-1 + ... + a1 . 10 + a0) ≡ (a0 - a1+ a2 - a3 + ... ) mod 11 e, portanto, um número é divisível por 11 se e somente se a soma alternada dos seus algarismos é divisível por 11. 7.4 Duas mágicas matemáticas Da congruência (an . 10n + an-1 . 10n-1 + ... + a1 . 10 + a0) ≡ (an + an-1 + ... + a1 + a0) mod 9 mostrada acima e das propriedades das congruências módulo n segue que: a) Se z = anan-1 ...a2a1a0, então (z - (an + an-1 + ... + a1 + a0)) ≡ 0 mod 9 donde se conclui que 9|(z - (an + an-1 + ... + a1 + a0)). b) Se z = anan-1 ...a2a1a0 e y = bnbn-1 ...b2b1b0 são tais que bi = aj , para algum i e algum j, com 0 ≤ i ≤ n e 0 ≤ j ≤ n (ou seja, z e y possuem exatamente os mesmos algarismos), então 9|(z – y). Utilizando estas conclusões e o critério de divisibilidade por 9, é fácil, mentalmente, se 87 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão repita enquanto m ≠ 0 se resto(m, 2) ≠ 0 p := b . p mod n; m := quociente(m, 2); b := (b . b) mod n; escreva(p); A tabela a seguir apresenta a execução deste algoritmo para o cálculo de 399 mod 29. a e n b m p 3 99 29 3 99 1 r(3 . 3, 29) = 9 q(99, 2) = 49 r(1 . 3, 29) = 3 r(9 . 9, 29) = 23 q(49, 2) = 24 r(9 . 3, 29) = 27 r(23 . 23 , 29) = 7 q(24, 2) = 12 r(7 . 7, 29) = 20 q(12, 2) = 6 r(20 . 20, 29) = 23 q(6, 2) = 3 r(23 . 23, 29) = 7 q(3, 2) = 1 r(23 . 27, 29) = 12 r(7 . 7, 29) = 20 q(1, 2) = 0 r(7 . 12, 29) = 26 e, assim, 399 mod 29 = 26. 7.7 Os inteiros módulo n De um modo geral, se A é um conjunto, ≈ é uma relação de equivalência em A e a é um elemento de A, a classe de equivalência de a pela relação ≈ é o conjunto a = {x ∈ A|x ≈ a}. Por exemplo, para a relação definida no exercício 2.4 (definida em ℕx por ℕ (m, n) ≈ (p, q) se e somente se m + q = n + p) temos: 1, 1  = {(n, m) ∈ ℕx |ℕm = n}. 1, 2  = {(n, m) ∈ ℕx |ℕm = n + 1}. Proposição 5.7 Sejam A um conjunto e a e b classes de equivalência em relação a uma relação de equivalência ≈. Então a) a ∈ a. b) a=b se e somente se a ≈ b. c) Se a ≠ b , então a  b = ∅. Demonstração a) Decorre imediatamente da reflexividade de ≈. b) Suponhamos que a=b . Como, pelo item (a), a ∈ a temos que a ∈ b . Daí, a ≈ b. Reciprocamente, suponhamos a ≈ b e tomemos x ∈ a . Daí, x ≈ a e, por transitividade, x ≈ b, o que implica x ∈ b . Assim a ⊂ b . Mutatis mutandis, se mostra que b ⊂ a . c) Se a  b ≠ ∅, existe x ∈ a e x ∈ b o que implica que existe x ∈ A tal que x ≈ a e x ≈ b. Daí, por reflexividade e transitividade, a ≈ b e, então, pelo item (b), a=b . Porém, isto contraria a hipótese. As classes de equivalência da relação congruência módulo n são chamadas classes residuais módulo n e qualquer inteiro b tal que a=b é dito um representante da classe residual a . Por exemplo, existem duas classes residuais módulo 2: 0={. . .−4, −2, 0, 2, 4 .. .} 1= {.. .−3, −1, 1, 3, . . .} 90 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão o que mostra que qualquer número par é representante da classe 0 e qualquer número ímpar é representante da classe 1 . De forma semelhante, existem três classes residuais módulo 3. A classe 0 que contém os múltiplos de 3, a classe 1 que tem como representantes os inteiros da forma 3 . q + 1 e a classe 2 com representantes da forma 3 . q + 2. O fato de existirem duas classes residuais módulo 2 e três classes residuais módulo 3 não é privilégio destes dois inteiros como mostra a seguinte proposição. Proposição 6.7 Existem exatamente n classes residuais módulo n: 0 , 1 , . . . , n−1  . Demonstração Provemos inicialmente as n classes listadas acima são diferentes. Ou seja, provemos que se 0 ≤ a < n, 0 ≤ b < n e a ≠ b, então a≠b . De fato, se a=b , então, pela proposição anterior, a ≡ b mod n e daí, como 0 ≤ b < n, b = r(a, n). Da mesma forma, como 0 ≤ a < n, temos que a = r(a, n) e, portanto, pela unicidade do resto, a = b, o que é uma contradição. Agora, dado qualquer a inteiro, pela divisão euclidiana, existem inteiros q e r tais que a = n . q + r, com 0 ≤ r < n. Assim, a ≡ r mod n, o que implica a=r . Portanto, como 0 ≤ r < n, a é uma das classes 0 , 1 , . . . , n−1  . O conjunto das classes residuais módulo n { 0 , 1 , . . . , n−1  } é indicado por ℤn e é denominado conjunto dos inteiros módulo n. É habitual, num contexto em que n está fixado, omitirmos as barras nas indicações das classes residuais, identificando, então, os conjuntos ℤn e In, já que n=0 . Em ℤn definimos as seguintes operações, utilizando os mesmos operadores + e . das operações em ℤ, utilizadas nos segundos membros. Adição: ab=a+b Multiplicação: a . b=a . b Evidentemente, é necessário garantir que estas operações estão bem definidas no sentido de que uma soma ou um produto de classes residuais independem do particular representante da classe que foi utilizado. Isto significa que devemos provar que se x ∈ a e y ∈ b , então x+y=a+b e x . y=a . b . Estas igualdades, porém, decorrem da proposição 3.7, pois x ∈ a e y ∈ b implicam x ≡ a mod n e y ≡ b mod n e, então, a referida proposição garante que (x + y) ≡ (a + b) mod n e (x . y) ≡ (a . b) mod n. Teorema 1.7 ℤn munido das operações definidas acima é um anel. Demonstração A associatividade e a comutatividade da adição e da multiplicação decorrem de imediato da associatividade e da comutatividade da adição e da multiplicação dos inteiros. De fato, por exemplo, ab=a+b=b+a=ba e a . b . c =a . b . c=a . b . c =a . b . c=a . b . c=a . b  . c . O elemento neutro da adição é 0 , pois a0=a+0=a e o elemento neutro da multiplicação é 1 , pois a . 1=a . 1=a . O simétrico de uma classe a é classe n−a , pois 91 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão an−a=a+n−a =n=0 . A distributividade da multiplicação em relação à adição também é simples de provar e decorre da propriedade respectiva do anel dos inteiros: a . b  c = a . b  c = a . b  c  = a . b  a . c = a . b  a . c = a . b  a . c As tabelas das operações em ℤ2 = {0, 1} são + 0 1 . 0 1 0 0 1 0 0 0 1 1 0 1 0 1 enquanto que as tabelas das operações em ℤ3 = {0, 1, 2} são + 0 1 2 . 0 1 2 0 0 1 2 0 0 0 0 1 1 2 0 1 0 1 2 2 2 0 1 2 0 2 1 Por seu turno, as tabelas para ℤ4 = {0, 1, 2, 3} são + 0 1 2 3 . 0 1 2 3 0 0 1 2 3 0 0 0 0 0 1 1 2 3 0 1 0 1 2 3 2 2 3 0 1 2 0 2 0 2 3 3 0 1 2 3 0 3 2 1 Observe que ℤ4 não é um domínio de integridade, pois 2 . 2=0 , enquanto que ℤ3 o é. Observe também que em ℤ4 o inverso de 3 é o próprio 3 e que 2 não tem inverso: não existe a tal que 2 . a = 1. É simples realizar operações em ℤn mesmo que n seja grande. Basta observar que, por exemplo, a . b=r , onde r = r(a . b, n). Foi assim que foram feitas as tabelas da multiplicação e da adição do ℤ 12 apresentadas no capítulo 3, representado na ocasião por I12 e sendo utilizado 12 para representar 0 . Se você observar as tabelas referidas vai observar que em ℤ12 2, 3, 4, 6, 8, 9 e 10 não têm inversos e que 5-1 = 5 e 7-1 = 7, 11-1 = 11. É fácil ver que em ℤ3 e em ℤ5 todo elemento não nulo tem inverso e que 2-1 = 2 em ℤ3 e 3-1 = 2 em ℤ5. A proposição a seguir estabelece as condições para que um elemento de ℤn seja inversível e sua demonstração fornece um algoritmo para a determinação do inverso de um elemento inversível. Proposição 7.7 Um elemento a ∈ ℤn é inversível se e somente se a e n são primos entre si. Demonstração Suponhamos que a ∈ ℤn é inversível. Então existe b ∈ ℤn tal que a . b ≡ 1 mod n. Assim, n|(a . b – 1) e, daí, existe t ∈ ℤ tal que a . b – 1 = n . t. Concluímos então que existem inteiros b e t tais que a . b + n . t = 1 o que implica, pela proposição 1.6, que a e n são primos entre si. Reciprocamente, se mdc(a, n) = 1, então existem inteiros b e t tais que a . b + n . t = 1. Daí, a . b = n . t + 1 o que implica a . b ≡ 1 mod n. Logo, em ℤn , a . b = 1 e a é inversível. Como foi dito acima, a demonstração anterior embute um algoritmo para se determinar o inverso de um elemento inversível a de ℤn: basta se determinar os inteiros b e t tais que 92 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão por 9 e por 12, respectivamente. Temos, como acima, que x ≡ 1 mod 9, x ≡ 2 mod 12. Da primeira segue que x = 9 . t + 1, para algum inteiro t, e da segunda, por substituição de x, 9 . t + 1 ≡ 2 mod 12. Daí, 9 . t ≡ 1 mod 12. Porém, como mdc(9, 12) = 3 e 3 não divide 1, temos que a congruência acima não tem solução e, portanto, não existe o inteiro procurado. O teorema a seguir (conhecido como teorema do resto chinês) discute as condições de existência de soluções de sistemas de congruências lineares. Teorema 2.7 (Teorema do resto chinês) Sejam n1, n2, ..., nk inteiros positivos tais que mdc(ni, nj) = 1 para i ≠ j. Se a1, a2, ..., ak são inteiros, então o sistema x ≡ a1 mod n1 x ≡ a2 mod n2 ... x ≡ ak mod nk tem uma única solução módulo n1 . n2 . ... . nk. Demonstração Demonstraremos o teorema para k = 2. O caso geral se demonstra de forma muito semelhante e será deixada como exercício. Sejam m e n inteiros tais que mdc(m, n) = 1 e a e b dois inteiros quaisquer. Queremos provar que o sistema x ≡ a mod n x ≡ b mod m tem uma única solução módulo m . n. Da primeira equação temos que x = n . t + a, para algum inteiro t, e da segunda, por substituição de x, temos que n . t + a ≡ b mod m ou, ainda, n . t ≡ (b – a) mod m. Como mdc(m, n) = 1, n tem inverso em ℤm e, então, chamando de i o tal inverso, a solução da congruência acima é t ≡ (i . (b – a)) mod m. Portanto, t = m . u + i . (b – a), com u inteiro. Daí, substituindo em x = n . t + a, temos x = n . m . u + n . i . (b – a) + a ou ainda x = (1 – n . i) . a + n . i . b + n . m . u. Como, n . i=1 em ℤm, temos que existe um inteiro j tal que 1 – n . i = m . j e, então, x = m . j . a + n . i . b + n . m . u, com u inteiro, é solução do sistema acima. Agora, se x0 e y0 são duas soluções do sistema, então x0 ≡ a mod n e y0 ≡ a mod n. Daí segue, por transitividade, que x0 ≡ y0 mod n e, assim, n|(x0 – y0). Mutatis mutandis, m|(x0 – y0). Assim, como mdc(m, n) = 1, segue da proposição 2.6, (m . n)|(x – y). Logo, x0 ≡ y0 mod (m . n) e o sistema tem uma única solução em ℤm. n. No exemplo x ≡ 1 mod 11, x ≡ 2 mod 13, discutido acima, temos x = 13 . j . 1 + 11 . i . 2 + 11 . 13 . u = 13 . j + 22 . i + 143 . u. Como 1 – 11 . i = 13 . j, é fácil determinar, pelo algoritmo de Euclides, valores para i e j. No caso, temos i = 6 e j = -5. Então, x = 67 + 143 . u é solução do sistema para todo inteiro u. Tomando u = 0 temos que x = 67 é a única solução módulo 13 . 11 = 143. 95 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão Observe que a demonstração do teorema do resto chinês fornece um algoritmo (algoritmo do resto chinês).para a solução de um sistema de congruências. Dados os inteiros positivos m e n, uma matriz de inteiros, de ordem mxn, é a imagem de uma função f de ℤmxℤn em ℤ, sendo indicada por M = (aij)mxn, onde aij = f(i, j) é a imagem do par (i, j) ∈ ImxIn,. O natural m é chamado número de linhas e o natural n é o número de colunas. Normalmente, uma matriz é exibida com os seus elementos dispostos como uma tabela (no sentido usual do termo) na qual a imagem do par (i, j) ocupa a linha i e a coluna j. Por exemplo, a matriz M = (aij)4x3 dada por aij = i + j pode ser exibida da seguinte forma 2 3 43 4 54 5 6 5 6 7  pois, a11 = 1 + 1, a12 = 1 + 2 = 3, a13 = 1 + 3 = 4, a21 = 2 + 1 = 3, e assim por diante. O teorema do resto chinês tem uma interpretação na forma de uma matriz. Seja M = (aij)mxn uma matriz de ordem mxn, m e n sendo inteiros tais que mdc(m, n) = 1. O que o teorema do resto chinês afirma é que podemos definir uma matriz definindo aij, para i = 1, 2, ..., m e j = 1, 2, ..., n, como sendo o inteiro x tal que 1 ≤ x ≤ m . n, x ≡ i mod m e x ≡ j mod n e que, neste caso, todos os elementos de M são distintos. 7.9 A função Φ de Euler Na proposição 7.7, vimos que um elemento a de ℤn é inversível se e somente se mdc(a, n) = 1. Naturalmente, o número de elementos de ℤn que são primos em relação a n fornecerá o número de elementos inversíveis de ℤn. A função Φ de Euler é a função que associa a cada inteiro positivo n > 1 o número de elementos inversíveis de ℤn. Por exemplo, Φ(2) = 1, Φ(3) = 2 e Φ(4) = 2, valores estes tirados da observação das tabelas da multiplicação de ℤ2, ℤ3 e ℤ4, apresentadas na seção 7.6. Já Φ(12) = 4, valor tirado da tabela da multiplicação em I12 apresentada no capítulo 3. Na verdade, podemos estabelecer uma fórmula para Φ(n), como mostra a seguinte proposição. Proposição 8.7 Sobre a função Φ de Euler são verdadeiras as seguintes afirmações: a) Φ(p) = p – 1 se e somente se p é primo. b) Se p é primo e n é um inteiro positivo, então Φ(pn) = (p – 1) . pn-1. c) Se m e n são primos entre si, então Φ(m . n) = Φ(m) . Φ(n). d) Se p1 e1 . .. . . pk ek é a decomposição em fatores primos de um inteiro positivo z, então Φ(z) = p1 e1−1 . . .. . pk ek− 1 .  p1−1 . . .. .  pk−1 Demonstração a) Se Φ(p) = p – 1, então 1 , 2 , . . . , p−1 são inversíveis e, portanto, para todo 1 < i < p, mdc(p, i) = 1. Isto mostra que p não tem divisores diferentes de 1 e de p e, por conseguinte, p é primo. A recíproca decorre de imediato do corolário 4.7. b) Seja k = pn. O corolário 5.7 afirma que os elementos não inversíveis de ℤk são p, 2 . p, 3 . p, ..., pn-1 . p e, portanto, existem pn-1 elementos de ℤk não inversíveis. Daí, Φ(pn) = pn – pn-1 = = pn-1 . (p – 1), como queríamos demonstrar. c) Seja M = (aij)mxn definida, para i = 0, 1, ..., m – 1 e j = 0, 1, ..., n – 1, por aij = x tal que 96 Introdução à Álgebra Abstrata – Jaime Evaristo/Eduardo Perdigão 0 ≤ x ≤ m .n – 1, x ≡ i mod m e x ≡ j mod n. Pelo teorema do resto chinês, a matriz M está bem definida e todos os seus elementos são distintos. Seja x = aij. Se x tem inverso em ℤm.n, então existe k tal que (x . k) ≡ 1 mod (m . n) o que implica, pela proposição 4.7, (x . k) ≡ 1 mod m. Daí, multiplicando x ≡ i mod m por k e aplicando a transitividade, temos que (i . k) ≡ 1 mod m e, então, i é inversível em ℤm. Da mesma maneira se prova que se x é inversível em ℤm.n, então j é inversível em ℤn. Reciprocamente, suponhamos que x = aij e i e j são inversíveis em ℤm e em ℤn, respectivamente. Sejam i , o inverso de i em ℤm e j, o inverso de j em ℤn. Pelo teorema do resto chinês existe um inteiro y tal que 0 ≤ y ≤ m . n – 1 com y ≡ i’ mod m e y ≡ j’ mod n. Daí, segue que (x . y) ≡ (i . i’) mod m ≡ 1 mod m, esta última congruência advindo do fato de que i , é o inverso de i em ℤm. Segue então que m|(x . y – 1). Com raciocínio idêntico, prova-se que n|(x . y – 1). Assim, pela proposição 2.6, (m . n)|(x . y – 1), o que prova que (x . y) ≡ 1 mod (m .n) e, ainda, que x é inversível em ℤm.n. Provamos então que se x = aij então x é inversível em ℤm.n se e somente se i é inversível em ℤm e j o é em ℤn. Daí, Φ(m . n) = Φ(m) . Φ(n), pois, Φ(m . n) é o número de elementos inversíveis de ℤm.n, Φ(m) é o número de elementos inversíveis de ℤm e Φ(n) é o número de elementos de ℤn. d) Segue de imediato do item (c) e da fórmula para Φ(pn) com p primo. Por exemplo, Φ(504) = Φ(23 . 32 . 7) = 22 . 31 . 70 . (2 – 1) . (3 –1) . (7 – 1) e, então, Φ(504) = 4 . 3 . 1 . 1 . 2 . 6 = 144. A função Φ de Euler é utilizada para uma generalização do pequeno teorema de Fermat para módulos compostos, como veremos a seguir. Para isto, necessitamos estabelecer o seguinte conceito. Seja n um inteiro maior que 1. O conjunto de inteiros S = {a1, a2, ..., aΦ(n)} é dito um sistema reduzido de resíduos módulo n se a1 , a2 , . .. , aΦ n  são os elementos inversíveis de ℤn. Por exemplo, S = {1, 17, 59, 67} é um sistema reduzido de resíduos módulo 12, pois, módulo 12, 17 = 5, 59 = 11 e 67 = 7. Lema 1.7 Seja S = {a1, a2, ..., aΦ(n)} um sistema reduzido de resíduos módulo n. Se a é um inteiro tal que mdc(a, n) = 1, então C ={a . a1, a . a2, ..., a . aΦ(n)} também é um sistema reduzido de resíduos módulo n. Demonstração Inicialmente, precisamos mostrar que, de fato, |C| = |S| = Φ(n). Isto não aconteceria se existissem dois inteiros positivos i e j, menores que Φ(n) e distintos, tais que a . a i=a . a j . Porém, se isto acontecesse, teríamos a . a i=a . a j , o que implicaria a i=a j , pois, como mdc(a, n) = 1, a é inversível em ℤn. Porém, a i=a j não pode acontecer porque i e j são menores que n. Falta mostrar que a . a i é inversível para todo i. Mas isto é imediato, pois a . a i . a  −1 . a i −1=a . a i . a  −1 . a i −1=1 Teorema 3.7 (Teorema de Euler) Sejam a e n inteiros, com n maior que 1 e mdc(a, n) = 1. Então aΦ(n) ≡ 1 mod n. Demonstração Se S = {a1, a2, ..., aΦ(n)} é um sistema reduzido de resíduos módulo n, então, pelo lema acima, o conjunto C ={a . a1, a . a2, ..., a . aΦ(n)} também o é, já que uma das nossas hipóteses é que 97