Álgebra Moderna - 4ª Edição Reformulada

ÁLGEBRA MODERNA Hygino H Domingues Gelson Iezzi Hygino H Domingues Gelson Iezzi 4ª edição reformulada ÁLGEBRA MODERNA Hygino H Domingues Gelson Iezzi Copyright desta edição SARAVIA SA Livreiros Editores São Paulo 2003 Dados Internacionais de Catalogação na Publicação CIP Câmara Brasileira do Livro SP Brasil Domingues Hygino H 1934 Álgebra moderna volume único Hygino H Domingues Gelson Iezzi 4 ed reform São Paulo Atual 2003 Bibliografia ISBN 8535704019 1 Álgebra I Iezzi Gelson 1939 II Título 034930 Índices para catálogo sistemático 1 Álgebra moderna 512 Álgebra moderna Gerente editorial Wilson Roberto Gambeta Editora Teresa Christina W P de Mello Dias Assistente editorial Teresa Cristina Duarte Ana Maria Alvares Preparação de texto Ana Maria Alvares Revisão de texto Pedro Cunha Jr coordMarcel0 Zanon Gerente de arte Nair de Medeiros Barbosa Assistente de produção Grace Alves Supervisor de arte Marco Aurélio Sismoto Colaboradores Projeto gráfico e diagramação Ulhôa Cintra Comunicação Visual e Arquitetura Ltda Visite nosso site wwwatualeditoracombr Central de atendimento ao professor 0xx11 36133030 O presente trabalho é uma nova versão bastante reformulada e com algumas am pliações de Álgebra moderna dos mesmos autores Dois motivos principalmente levaram a essas mudanças de um lado a constatação de um certo desgaste da versão anterior no que se refere à redação e à abordagem inevitável quando se considera o tempo há que a obra está em circulação cerca de duas décadas e meia e que ela foi escrita ainda sob alguma influência da corrente da matemática moderna de outro o fato de ter alcançado ao longo desse tempo uma boa aceitação por parte de estudantes e professores de cursos de matemática comprovada pelas várias edições e reimpressões alcançadas durante esses anos Levando em conta o primeiro desses motivos o livro foi totalmente reescrito numa linguagem muito menos permeada de simbolismos que a das edições anteriores com vis tas a tornar a leitura mais leve e agradável e com muito mais exemplos e ilustrações Procurouse também na medida do possível evitar a iniciação a um dado assunto sem algum comentário ou observação inicial que pudesse servir de motivação para seu estudo Também a título de motivação todos os capítulos apresentam notas eou observações histó ricas referentes às origens de alguns dos tópicos tratados importantes ao nosso ver em face do caráter abstrato da álgebra moderna Não se tratando de obra que prioriza as aplicações até pelo seu caráter introdutório buscase com essas notas eou observações mostrar de onde vem à álgebra moderna o que pode constituir uma pista importante para o leitor vislumbrar a origem e o alcance de alguns dos métodos desse campo da matemática Efetivamente apenas um dos tópicos focalizados na presente edição não figurava de alguma maneira nas anteriores aquele contemplado no capítulo I com o título Noções sobre conjuntos e demonstrações Talvez desnecessário quando da primeira redação esse tópico nos parece muito importante na presente conjuntura das licenciaturas em matemática área para a qual se destina principalmente a obra De fato apesar de ser bastante moderado no uso do formalismo matemático o livro faz um estudo sistemático do assunto e portant o compreende um número considerável de teoremas e respectivas demonstrações Ora é bem sabido que hoje poucos alunos chegam à universidade com alguma experiência em de monstrações e que essa lacuna às vezes não é preenchida antes de iniciarem um curso de álgebra Mas não se vai ao assunto nesse capítulo além do mínimo necessário como prérequisito para um entendimento suficiente do método matemático e a abordagem é propositadamente desprestensiosa e informal Como nas edições anteriores o capítulo III Relações aplicações operações é muito es miuçado abundante em detalhes talvez mais do que nenhum dos outros porque além de também ser um dos prérequisitos básicos para os capítulos centrais do livro envolve assun tos que fazem parte do ensino de matemática no ciclo básico que cumpre valorizar por si mesmos e ajustar às necessidades do desenvolvimento da matéria Os capítulos IV e V focalizam respectivamente a teoria básica das estruturas algébricas de grupo e anel com seus subcasos mais importantes O capítulo IV Grupos além das mu danças de caráter geral já mencionadas no que se refere à linguagem e abordagem com ên fase maior nos exemplos apresenta como novidade um estudo mais abrangente e sis témico dos grupos de permutações Quanto ao capítulo V Anéis e corpos houve incor poração do tópico destinado ao estudo da compatibilidade de uma relação de ordem com a estrutura de anel que na versão anterior constituía um capítulo à parte O capítulo VI Anéis de polinômios foi totalmente reformulado Nas edições anteriores introduziase o conceito de polinômio sobre um anel como uma sequência quasenula de ele mentos desse anel Essa definição se tem a vantagem da generalidade e até de proporcionar uma certa facilidade algébrica para desenvolver a teoria que segue tem o inconveniente para quem está iniciando o estudo do assunto de ser muito artificial Preferimos considere rando o objetivo da obra definir polinômio sobre um anel de integridade infinito como uma aplicação função polinomial e depois considerando a hipótese feita sobre o anel provar e explorar o princípio de identidade de polinômios Entre as propostas da obra uma era a de incluir um tópico final que digamos assim fugisse um pouco ao básico Inúmeras escolhas poderiam ser feitas Mas optamos por Anéis principais e fatoriais título do capítulo VII considerando tratarse de uma generalização natu ral da teoria da divisibilidade no anel dos inteiros que por isso mesmo não exige muito em termos de conceitos novos não obstante dá uma boa ideia inicial do alcance dos métodos da álgebra moderna No que se refere à redação do livro o trabalho foi dividido entre os autores da seguinte maneira Professor Hygino H Domingues Toda a teoria e exemplos dos capítulos I II IV V VI e VII Os exercícios propostos e resolvidos dos capítulos I e II inclusive respostas Todas as notas históricas Professor Gelson Iezzi Toda a teoria e exemplos do capítulo III em parceria com o professor Hygino Os exercícios propostos e resolvidos dos capítulos III IV V VI e VII inclusive respostas Finalmente nossos agradecimentos a todos os colegas que usaram a obra em suas edi ções anteriores especialmente os da PUCSP e Unesp de São José do Rio Preto com os quais compartilhamos o uso desse material por certo tempo e que com seus comentários even tuais nos deram algumas pistas para as mudanças presentes SUMÁRIO CAPÍTULO I NOÇÕES SOBRE CONJUNTOS E DEMONSTRAÇÕES I1 Sobre conjuntos 7 1 Nota histórica 7 2 Conjuntos 8 I2 Sobre demonstrações 16 3 Nota histórica 16 4 Demonstrações 17 CAPÍTULO II INTRODUÇÃO À ARITMÉTICA DOS NÚMEROS INTEIROS 1 Introdução 29 2 Indução 30 3 Divisibilidade em ℤ 33 4 Máximo divisor comum 39 5 Números primos 45 6 Equações diofantinas lineares 49 7 Congruências 53 8 Problema chinês do resto 58 CAPÍTULO III RELAÇÕES APLICAÇÕES OPERAÇÕES III1 Relações binárias 63 1 Conceitos básicos 63 2 Relações de equivalência 63 3 Relações de ordem 78 III2 Aplicações 92 4 Nota histórica a formação do conceito de função 92 5 Aplicação Função 93 6 Imagem direta Imagem inversa 96 7 Aplicações inteiras Aplicações sobrejetoras 98 8 Aplicação inversa 101 9 Aplicação idêntica 103 10 Restrição e prolongamento de uma aplicação 106 III3 Operações Leis de composição internas 110 13 Exemplos preliminares 110 14 Conceituação 111 15 Propriedades das operações 112 16 Parte fechada para uma operação 121 17 Tábua de uma operação 124 18 Operações em ℤₘ 135 CAPÍTULO IV GRUPOS IV1 Grupos e subgrupos 137 1 Nota histórica 137 2 Grupos e subgrupos 138 IV2 Homomorfismos e isomorfismos de grupos 161 3 Introdução 161 4 Homomorfismos de grupos 164 5 Propriedades sobre homomorfismos de grupos 167 6 Núcleo de um homomorfismo 169 7 Isomorfismos de grupos 171 IV3 Grupos cíclicos 174 9 Potências e múltiplos 174 10 Grupos cíclicos 177 11 Classificação dos grupos cíclicos 182 IV4 Classes laterais Teorema de Lagrange 13 Classes laterais 14 O teorema de Lagrange IV5 Grupos normais Grupos quocientes 15 Introdução 16 Multiplicação de subconjuntos 17 Subgrupos normais 18 Grupos quocientes 19 O teorema do homomorfismo IV6 Permutações 20 Ciclos e notação cíclica 21 Assinatura de uma permutação CAPÍTULO ANÉIS E CORPOS V1 Anéis 1 Nota histórica 2 Anéis e subanéis 3 Tipos de anéis V2 Homomorfismos e isomorfismos de anéis 4 Introdução 5 Homomorfismos de anéis 6 Proposições sobre homomorfismos de anéis 7 Núcleo de um homomorfismo de anéis 8 Isomorfismo de anéis V3 Corpo de frações de um anel de integridade 9 Quocientes em um corpo 10 Corpo de frações de um anel de integridade V4 Característica de um anel 11 Múltiplos de um elemento de um anel 12 Característica de um anel 13 Característica de um corpo V5 Ideais em um anel comutativo 15 Nota histórica 16 Ideais em um anel comutativo 17 Ideais gerados por um número finito de elementos 18 Operações com ideais 19 Ideais primos e maximais V6 Anéis quocientes V7 Ordem em um anel de integridade 20 Anéis de integridade ordenados 21 Propriedades imediatas de um anel de integridade ordenado 22 Anéis de integridade bem ordenados 23 Corpos ordenados CAPÍTULO VI ANÉIS DE POLINÔMIOS 1 Nota histórica 2 Construção do anel de polinômios 3 Polinômios idênticos 4 Divisibilidade em Ax 5 Sobre raízes 6 Polinômios irreduzíveis CAPÍTULO VII ANÉIS PRINCIPAIS E FATORIAIS 1 Nota histórica 2 Divisibilidade em um anel de integridade 3 Anéis principais fatoriais e euclideanos 4 Polinômios sobre anéis fatoriais RESPOSTAS ÍNDICE REMISSIVO BIBLIOGRAFIA CAPÍTULO I NOÇÕES SOBRE CONJUNTOS E DEMONSTRAÇÕES I1 SOBRE CONJUNTOS 1 NOTA HISTÓRICA A teoria dos conjuntos foi criada por G Cantor 18451918 com uma série de artigos publicados a partir de 1874 Embora russo de nascimento Cantor fez carreira na Alemanha para onde sua família se mudara quando ele era criança Depois de doutorarse na Universidade de Berlim em 1867 com uma tese sobre teoria dos números passou a trabalhar na Universidade de Halle onde ficaria até o fim de sua carreira acadêmica Por volta de 1870 quando estudava o problema da representação das funções reais por meio de séries trigonométricas sua atenção se voltou para uma questão com a qual seu espírito tinha uma afinidade natural muito grande a natureza do infinito Esse foi o ponto de partida da criação da teoria dos conjuntos Além de tudo os trabalhos de Cantor sobre teoria dos conjuntos exigiram uma boa dose de coragem científica De fato ao estender a idéia de cardinal para conjuntos infinitos Cantor estava considerando a infinidade destes como algo efetivamente atual e não apenas potencial como se aceitava até então Dizse que dois conjuntos têm o mesmo cardinal ou a mesma cardinalidade se seus elementos podem ser postos em correspondência biunívoca O grande mérito de Cantor foi perceber a existência de uma hierarquia para os cardinais transfinitos Assim todos os conjuntos cujos elementos podem ser postos em correspondência biunívoca com os elementos do conjunto dos números naturais têm o mesmo e o menor cardinal transfinitos Tratase dos conjuntos enumeráveis Entre estes encontramse por exemplo o conjunto dos números inteiros e surpreendentemente o conjunto dos números racionais Cantor mostrou ainda que o conjunto dos números reais tem cardinal maior que os conjuntos enumeráveis e que esse cardinal é igual ao do conjunto dos irracionais algo que contrariava a velha idéia de que o todo tinha de ser maior que a parte E mostrou que a escala dos cardinais transfinitos não tem limite sempre há cardinais maiores e maiores Tão surpreendentes eram alguns dos resultados encontrados por Cantor que ele chegou a dizer sobre um deles Vejo mas não acredito Assim não é de espantar o fato de que grandes matemáticos tenham rejeitado seus trabalhos LKronecker 18231891 chegou a chamar Cantor de charlatão da ciência E até havia razão para algumas dessas críticas pois construída inicialmente sem preocupações com seus fundamentos lógicos a teoria dos conjuntos antes de ser satisfatoriamente axiomatizada no século XX gerou paradoxos que chegaram a confundir e inquietar os matemáticos até mesmo os cantoristas Mas para o progresso da matemática prevaleceram opiniões como a de B Russel 18721970 que considerava a teoria dos conjuntos como provavelmente a mais importante descoberta que a época pode ostentar ou a de D Hilbert 18621943 que disse Do paraíso criado por Cantor ninguém nos tirará 2 CONJUNTOS 21 Introdução O conceito de conjunto é certamente um dos mais importantes da matemática contemporânea Como sinônimo de conjunto no sentido aqui considerado podemos usar sem distinção os termos classe e coleção Um conjunto é formado por objetos de modo genérico chamados de elementos que por um motivo ou outro convém considerar globalmente Não há restrições quanto a escolha dos elementos de um conjunto salvo que excluirmos a possibilidade de um conjunto ser elemento dele mesmo Assim não há nenhum inconveniente em considerar por exemplo um conjunto formado por um número real uma bola de futebol e um automóvel Costumase indicar os conjuntos por letras maiúsculas e seus elementos por letras minúsculas de nosso alfabeto Se um objeto a é elemento de um conjunto U dizemos que a pertence a U e denotamos essa relação por a U Caso contrário dizemos que a não pertence a U e escrevemos a U 22 Descrição de um conjunto Comumente usamse três procedimentos para definir um conjunto Descrever seus elementos por uma sentença Por exemplo conjunto dos números reais conjunto dos planetas do sistema solar Listar seus elementos entre chaves Por exemplo 2 4 6 8 10 0 1 2 3 No segundo exemplo como se vê só os três primeiros elementos foram listados mas mesmo assim não há dúvida de que se trata do conjunto dos números naturais Dar uma propriedade que identifica seus elementos Por exemplo x x é inteiro e x 2 x x é real e 2 x 10 x x goza da propriedade P A propósito do último procedimento vale ressaltar que um dos pontos importantes do uso de conjuntos na matemática reside no fato de estes poderem substituir as propriedades com grande vantagem no que se refere à precisão de linguagem Por exemplo a propriedade Todos os números racionais são também números reais na linguagem de conjuntos pode ser escrita assim Se x Q então x R Ver notação abaixo Certos conjuntos por sua importância e pela frequência com que se repetem são indicados por notações especiais N 0 1 2 3 conjunto dos números naturais Z 2 1 0 1 2 conjunto dos números inteiros Q conjunto dos números racionais R conjunto dos números reais Se A indica um dos três últimos conjuntos indistintamente então A A 0 A x A x 0 conjunto dos números positivos de A A x A x 0 conjunto dos números negativos de A A x A x 0 conjunto dos números estritamente positivos de A A x A x 0 conjunto dos números estritamente negativos de A C conjunto dos números complexos 23 Subconjuntos Se A e B são conjuntos e todo elemento de A também é elemento de B dizse que A é um subconjunto de B ou uma parte de B e denotamos essa relação por A B A B lêse A está contido em B ou B A lêse B contém A Dois conjuntos A e B dizemse iguais se A B e B A evidentemente isso significa que os dois conjuntos constam exatamente dos mesmos elementos A igualdade de conjuntos é denotada pelo símbolo usual de igualdade Por exemplo se A x Z 1 x 5 e B 2 3 4 então A B A relação definida por X Y chamada inclusão goza das seguintes propriedades reflexiva X X antisimétrica se X Y e Y X então X Y transitiva se X Y e Y Z então X Z A demonstração da primeira dessas propriedades é imediata A segunda propriedade é decorrência da própria definição de igualdade de conjuntos Para provar a terceira temos que mostrar que todo elemento de X também é elemento de Z Ora se a X então a Y por hipótese mas pertencendo a Y a também pertence a Z pela segunda parte da hipótese isso prova a propriedade O exemplo seguinte ilustra o uso da transitividade na linguagem de conjuntos Denotamos por M N e S respectivamente o conjunto dos quadriláteros dos retângulos e dos quadrados de um dado plano Como S N todo quadrado é um retângulo e N M todo retângulo é um quadrilátero então S M Convém ressaltar que são equivalentes as três afirmações que seguem A B Se x A então x B Se x B então x A Se A e B indicam conjuntos tais que A B e A B dizse que A está contido propriamente em B ou que B contém propriamente A As notações usadas para indicar essas relações são respectivamente A B e B A Por exemplo o conjunto dos números naturais está contido propriamente no conjunto dos números inteiros ou seja N Z Ou dito de outra forma o conjunto dos números inteiros contém propriamente o conjunto dos números naturais ou seja Z N 25 Diagramas de Venn Para ilustrar e visualizar relações entre conjuntos e operações com conjuntos um instrumento bastante útil são os chamados diagramas de Venn A ideia é a seguinte primeiro traçase um retângulo de dimensões arbitrárias para representar o conjunto de todos os elementos considerados Depois para representar cada subconjunto próprio do universo com que se esteja lidando traçase um círculo no interior do retângulo Por exemplo a relação A B entre dois subconjuntos de U é representada pelo diagrama a seguir U B A 26 Interseção e união A interseção de dois conjuntos A e B é o conjunto indicado por A B e definido pela propriedade x A e x B Portanto A B x x A e x B A operação que consiste em associar a cada dois conjuntos dados numa certa ordem sua interseção goza das seguintes propriedades A B C A B C associatividade A B B A comutatividade Se A B então A B A A Provamos a terceira dessas propriedades Para tanto consideremos inicialmente um elemento x A B então x A e x B definição de interseção o que garante que A B A Seja agora x A como A B então x B logo x A B As duas inclusões demonstradas garantem que efetivamente A B A sempre que A B A união de dois conjuntos A e B é o conjunto indicado por A B e definido pela propriedade x A ou x B Portanto A B x x A ou x B Convém notar que o ou usado na definição não dá ideia de exclusividade um elemento da união pode pertencer a ambos os conjuntos se a interseção não for vazia A operação que consiste em associar a cada dois conjuntos dados numa certa ordem sua união cumpre as seguintes propriedades A B C A B C A B B A Se A B então A B B A A O conjunto U cuja fixação é pressuposta na definição de complementar é chamado universo do discurso ou conjunto universo No desenvolvimento da matemática trabalhase em cada situação com um conjunto universo específico Por exemplo numa primeira abordagem do cálculo o universo é o conjunto dos números reais e na mesma situação na teoria dos números aritmética teórica o universo é o conjunto dos números inteiros Quando não houver dúvidas sobre qual o universo em que se está trabalhando para simplificar a notação indicaremos o complemento de uma parte A desse universo apenas por Ac Da definição de complementar decorrem as propriedades que seguem para um dado conjunto U universo e para partes quaisquer A e B de U U c e A c c U A c c A A Ac e A Ac U A B c Ac B c e A B c Ac B c As duas últimas propriedades são conhecidas como leis de De Morgan ou leis de dualidade A título de exercício demonstramos que A B c Ac B c Seja x um elemento de U Se x A B c então x A B e portanto x A e x B Logo x Ac e x B c e fica provado que A B c Ac B c Agora se x Ac B c então x A e x B e portanto x A B c se pertencesse a esse conjunto teria de pertencer a A ou a B De onde x A B c o que prova a inclusão contrária 2 Construa um exemplo envolvendo dois conjuntos B e C para os quais se verifiquem as seguintes relações C B C B C C C 3 a Descubra conjuntos A B e C tais que B C e A B A C b Com um exemplo mostre que pode ocorrer o seguinte B C e A B A C 4 Se A B e C são conjuntos tais que A B A C e A B A C prove que B C 5 Sejam A e B conjuntos tais que A B A B Prove que A B 6 Se A e B são conjuntos arbitrários demonstre as seguintes propriedades conhecidas como leis de absorção a A A B A b A A B A 7 Dado um conjunto A chamase conjunto das partes de A e indicase por PA o conjunto de todos os subconjuntos de A Por exemplo se A 1 2 então PA 1 2 1 2 a Determine PA quando A 1 1 b Prove que se um conjunto A tem n elementos então PA tem 2n elementos c Se o número de subconjuntos binários formados dos elementos de um conjunto dado é 15 quantos subconjuntos tem esse conjunto Prove as seguintes propriedades envolvendo o conceito de diferença de conjuntos a A B A C A B C b A C B C A B C c A B B A se e somente se A B Ø Resolução b Se x A C B C então x A x C x B e x C Daí x A B x C e portanto x A B C Isso prova que A C B C A B C Para provar a inclusão contrária tomemos x A B C Então x A B e x C Daí x A x B e x C portanto x A C e x B C ou seja x A B B C como queríamos provar Encontre um exemplo para mostrar que pode ocorrer a desigualdade seguinte A B C A B A C I2 SOBRE DEMONSTRAÇÕES 3 NOTA HISTÓRICA A lógica como ciência foi criada por Aristóteles 384322 aC Mas embora Aristóteles considerasse sua criação uma ciência independente da matemática e anterior a esta as bases para a estruturação e sistematização da lógica empreendidas por ele já haviam sido lançadas antes pelos matemáticos gregos ao criarem e desenvolverem o método dedutivo De fato esse método pressupôs antes de tudo leis corretas para o raciocínio e isso se insere nos domínios da lógica Entre essas leis há que se destacar a lei da não contradição que estatuía que uma proposição não pode ser verdadeira e falsa ao mesmo tempo e a lei do terceiro excluído que estatuía que uma proposição só pode ser verdadeira ou falsa ambas introduzidas por Aristóteles A lógica de Aristóteles cujas fórmulas por exemplo silogismos se expressavam em palavras da linguagem comum sujeitas a regras sintáticas comuns reinou soberanamente até o século XIX quando foi criada a lógica matemática a despeito do significativo papel desempenhado pela lógica escolástica da Idade Média Mas há que registrar no século XVI o trabalho desenvolvido por G W Leibniz 16461716 no sentido de criar uma álgebra simbólica formal para a lógica A motivação para Leibniz foi a forte impressão que lhe causava o poder enorme da álgebra simbólica em campos diversos e o objetivo de sua álgebra da lógica seria o de conduzir o raciocínio mecanicamente e sem esforços demasiados em todos os campos do conhecimento Mas Leibniz deixou apenas escritos fragmentados sobre o assunto escritos que ademais só se tornaram conhecidos em 1901 Entre os matemáticos que contribuíram para a criação da lógica matemática no século cujo obra teve peso e repercussão maiores foi G Boole 18151864 graças soberto à The laws of thought As Leis do Pensamento de 1854 Uma ligeira ideia da obra de Boole pode ser dada por este fato ele usava letras minúsculas x y z para indicar partes de um conjunto tomado como universo e representado pelo símbolo 1 Se x y representam duas dessas partes ele denotava o que hoje chamamos de interseção e união dessas partes respectivamente por xy e x y O complementar de uma parte x era indicado por 1 x Na verdade as uniões consideradas por Boole pressupunham partes disjuntas a generalização para o conceito atual é devida a W S Jevons 18381882 Assim sendo evidente que xy yx x y y x xyz xyz essas leis foram tomadas como axiomas em sua álgebra Mas a nova álgebra apresenta diferenças fundamentais em relação à clássica haja vista as leis x² x e x x x para qualquer parte x do universo Como exemplo do uso da álgebra de Boole vejamos como se poderia colocar em símbolos a lei do terceiro excluído Suponhamos que 1 indique o conjunto de todos os seres humanos vivos e x o conjunto dos brasileiros vivos Então 1 x indica o conjunto dos seres humanos vivos que não são brasileiros e a equação x 1 x 1 expressa a ideia de que todo ser humano vivo ou é brasileiro ou não é brasileiro Não passou despercebida Boole a correspondência entre a álgebra dos conjuntos e a das proposições Se p indica uma proposição a equação p 0 indica que p é falsa e a equação p 1 que p é verdadeira Nesse contexto dadas duas proposições p e q ele indicava por pq e p q respectivamente a conjunção e a disjunção das duas Mas Boole não se alongou muito nessa questão Tão importante e inovadora foi a obra científica de Boole que grande matemático e filósofo galês B Russel 18721970 via nele o verdadeiro descobridor da matemática pura Mas talvez nada ateste mais fielmente a importância dessa obra do que as muitas pesquisas que nela se inspiraram e que levaram a uma axiomatização da álgebra do pensamento no século XX 4 DEMONSTRAÇÕES 41 Proposições e funções proposicionais A matemática é uma ciência dedutiva Isso significa entre outras coisas que a validade de um resultado matemático exige uma demonstração Não é fácil definir o que é uma demonstração matemática Basicamente é uma sucessão articulada de raciocínios lógicos que permite mostrar que um resultado proposto é consequência de princípios previamente fixados e de proposições já estabelecidas Nesse processo é preciso lidar e operar constantemente com proposições sentenças declarativas às quais se pode atribuir um valor lógico verdadeiro ou falso exclusivamente e funções proposicionais sentenças declarativas envolvendo variáveis Consideremos as sentenças 2 é um número primo 2 é um número racional e x é um número real maior que 1 Como se vê são sentenças declarativas Mas embora se possa dizer que a primeira é verdadeira e a segunda falsa nenhum valor lógico se pode atribuir à terceira já que ela envolve uma variável em R As duas primeiras são pois proposições ao passo que a terceira é uma função proposicional na variável x As variáveis de uma função proposicional sempre representam elementos de um conjunto previamente fixado seu domínio de validade ou universo As funções proposicionais na variável x são indicadas em geral por px qx Toda função proposicional pode ser transformada numa proposição bastando para isso substituir a variável por um elemento do universo Se a é um elemento do universo de px a proposição obtida com a substituição da variável por a é indicada por pa Por exemplo se px é a função proposicional x² 4 no universo dos números racionais então p3 é 3² 4 verdadeira e p1 é 1² 4 falsa Assim uma maneira de transformar uma função proposicional em proposição é substituir a variável ou variáveis por um elemento ou elementos arbitrários do universo Outra maneira de transformar uma função proposicional em proposição consiste em quantificar a variável ou variáveis o que pode ser feito de duas maneiras através do quantificador existencial existe um pelo menos ou do quantificador universal qualquer que seja ou qualquer ou todo No cálculo proposicional usamse os símbolos e para indicar os quantificadores existencial e universal respectivamente Por exemplo a função proposicional x 1 em que x é uma variável em R pode de ser quantificada das maneiras que seguem Existe um número real maior que 1 verdadeira ou Todo número real é maior que 1 falsa Se px é uma função proposicional cujo conjunto universo é U então os elementos de U que tornam verdadeira px constituem o que se chama conjunto verdade da proposição dada Por exemplo o conjunto verdade de x é um quadrado perfeito em que x é uma variável em N é 0 1 4 9 p ou q ambas as proposições p e q podem ser verdadeiras ou falsas Por exemplo em 2 é primo ou 2 é par ambas são verdadeiras As proposições do tipo se p então q serão entendidas aqui como p q Assim por exemplo é o mesmo dizer que Se uma pessoa é paulista então essa pessoa é brasileira ou Não pode ocorrer de uma pessoa ser paulista e não ser brasileira É o mesmo dizer também que Se x² é um número par então x é um número par ou Não pode acontecer de x² ser um número par e x não ser um número par Uma proposição do tipo p se e somente se q será entendida como se p então q e se q então p No que segue indicaremos por p a negação de uma proposição p Por exemplo se p indica a proposição 2 é primo e q a proposição 2 é par então p negação de p é 2 não é primo q negação de q é 2 não é par ou 2 é ímpar pois só há duas alternativas para um inteiro par ou ímpar p e q é 2 é primo e 2 é par p ou q é 2 é primo ou 2 é par se p então q é se 2 é primo então 2 é par p se e somente se q é 2 é primo se e somente se 2 é par Nesse contexto é importante saber determinar o valor lógico das proposições obtidas através da negação ou dos conectivos em função do valor lógico das proposições dadas Uma proposição p é verdadeira se p é falsa e viceversa As proposições do tipo p q só são verdadeiras quando p e q são verdadeiras As do tipo p ou q só são falsas quando p e q são falsas Para o estudo do valor lógico das condicionais se p então q é melhor considerálas na forma p e q No caso em que p e q são verdadeiras p e q é falsa pois q é falsa e então a negação dessa última ou seja se p então q é verdadeira segue então que quando p e q são verdadeiras se p então q é verdadeira Aplicandose esse raciocínio para os demais casos concluiuse que uma proposição do tipo se p então q só é falsa no caso em que p é verdadeira e q é falsa Como exemplo consideremos as proposições O menor número primo positivo é 2 que indicaremos por p e O menor número irracional positivo é 2 que indicaremos por q Obviamente a primeira é verdadeira e a segunda falsa Então 43 Implicação e equivalência Se p e q são proposições tais que a condicional se p então q é verdadeira dizse que p implica ou acarreta q Para indicar que p implica q usase a notação p q Por exemplo 1 2 4 é primo uma vez que a proposição se 1 2 então 4 é primo é verdadeira pois 1 2 é falsa Por outro lado não procedería escrever 2 1 4 é primo já que a primeira dessas proposições é verdadeira e a segunda falsa único caso em que uma proposição do tipo se então é falsa como vimos Sejam px e qx funções proposicionais com o mesmo universo U Se para todo a U tal que pa é verdadeira e a proposição qa também for verdadeira então se diz que px acarretou ou implica qx A notação é a mesma px qx Por exemplo se U R então x 2 x² 4 uma vez que todos os valores de x que tornam verdadeira a primeira função proposicional também tornam verdadeira a segunda Mas não procedería escrever x² 4 acarret a x 2 visto que há números reais que tornam verdadeira a primeira proposição e falsa a segunda todos os números reais menores que 2 Vale observar que se no exemplo anterior o universo fosse o conjunto dos números reais positivos então x² 4 x 2 Uma importante propriedade de que goza a relação é a transitividade Ou seja se p q e q r então p r De fato a proposição se p então r só não seria verdadeira no caso de p ser verdadeira e r falsa Mas como se p então q é verdadeira então q teria de ser verdadeira e como se q então r é verdadeira então q teria de ser falsa Impossível pois isso contraria o princípio da nãocontradição Então se p então r é verdadeira e portanto p r Duas proposições p e q dizemse logicamente equivalentes se p q e p Notação p q A definição de funções proposicionais equivalentes é análoga Por exemplo x² 4 0 x 2 ou x 2 De fato os números reais que tornam verdadeira a primeira proposição 2 e 2 também tornam verdadeira a segunda e viceversa Consideremos uma implicação p q poderia ser também uma implicação envolvendo funções proposicionais Outra maneira de ler essa relação é p é uma condição suficiente para q A explicação para isso é que a veracidade de p basta é suficiente para garantir a veracidade de q uma vez que estamos supondo se p então q verdadeira Outra maneira ainda é q é uma condição necessária para p A explicação no caso é que é necessária a veracidade de q para que se possa ter a veracidade de p Consideremos por exemplo a implicação x 2 x² 4 em que x é uma variável em ℝ Essa relação poderia portanto ser formulada de uma das seguintes maneiras x ser igual a 2 é suficiente para que x² seja igual a 4 ou x² 4 é condição necessária para x 2 Isso justifica por que uma equivalência p q é comumente expressa nos seguintes termos q é uma condição necessária e suficiente para p ou p é uma condição necessária e suficiente para q Por exemplo a equivalência x é par x² é par em que x representa um número inteiro poderia ser formulada da seguinte maneira uma condição necessária e suficiente para que x² seja par é que x seja par 44 Recíproca de uma proposição ou função proposicional A proposição se q então p é chamada recíproca de se p então q Para funções proposicionais a definição é análoga É fácil ver que a recíproca de uma proposição verdadeira pode não ser verdadeira e viceversa Ou seja se p e q são proposições tais que p q pode não valer a implicação contrária O mesmo acontece com as funções proposicionais Por exemplo a recíproca de Se X é um quadrado então X é um losango é Se X é um losango então X é um quadrado Obviamente a primeira é verdadeira mas a segunda não nem todo losango é quadrado Também pode acontecer de uma proposição e sua recíproca serem ambas verdadeiras ou falsas Por exemplo Se x² é ímpar então x é ímpar se sua recíproca Se x é ímpar então x² é ímpar são ambas verdadeiras 45 Demonstração indireta negação de funções proposicionais Nos raciocínios matemáticos muitas vezes é preciso negar uma proposição Isso acontece especialmente nas demonstrações indiretas ou demonstrações por redução ao absurdo de teoremas Um teorema é basicamente uma proposição que para ser admitida precisa ser demonstrada O enunciado de um teorema sempre explicita algumas hipóteses e pressupõe toda a teoria pertinente que o precede O resultado a ser provado é a tese Se a negação da tese levar a alguma contradição com as hipóteses ou com outros pressupostos da teoria o teorema estará provado Uma explicação mais rigorosa para esse fato requer um desenvolvimento do assunto fora dos objetivos deste texto e por isso não ateremos a um exemplo Suponhamos que se deseja provar que Se m² é ímpar então m também é ímpar m número inteiro Negando a tese suponhamos que m fosse par ou seja que pudesse ser escrito na forma m 2t em que t é inteiro Então m² 4t² 22t² também seria par contra a hipótese De onde m necessariamente é ímpar A seguir relacionaremos os procedimentos para as negações habitualmente necessárias na argumentação matemática Se px indica uma função proposicional a negação de xpx é xpx Por exemplo a negação de Qualquer que seja o número real x x² é positivo é Existe um número real x tal que x² é estritamente negativo Lembremos que por nossa convenção positivos são os números 0 e estritamente negativos os números 0 Se p e q indicam proposições ou funções proposicionais a negação de p e q é p ou q Por exemplo a negação de 2 é par e 2 é primo ou 2 é par e primo como se diria mais comum dizer é 2 não é par ou 2 não é primo Se p e q indicam proposições ou funções proposicionais a negação de p ou q é p e q Por exemplo a negação de Qualquer que seja o número real x x 0 ou x 0 é Existem um número real x tal que x 0 e x 0 A negação da negação de uma proposição ou função proposicional p é p Por exemplo a negação de 3 não é ímpar é 3 é ímpar Se p e q indicam proposições ou funções proposicionais então a negação de se p então q é p e q A explicação para isso vem do fato de que Se p então q tem formalmente o mesmo sentido de p e q e de que se s é uma proposição então s é s como vimos anteriormente Como exemplo consideremos a proposição Se um número é racional então também é um número real que tem o mesmo sentido de Todo número racional é real Sua negação é Existe um número que é racional e não é real 46 Demonstração de existência Na matemática são comuns os teoremas de existência Nesse caso a demonstração muitas vezes é feita simplesmente exibindose um objeto que cumpre as condiçãoões desejadas Como exemplo mostremos que dados dois números racionais a e b com a b então existe um número irracional α tal que a α b De fato o número α a fracb a2 cumpre as condições desejadas Observemos primeiro que pela própria maneira como foi definido o número α é maior que a e menor que b Por outro lado de 1 segue que sqrt2 fracb aα a Assim supondo que α fosse racional então o segundo membro da última igualdade também seria um número racional e teríamos o seguinte absurdo sqrt2 racional Logo α é irracional É claro que exibir um objeto que cumpre uma determinada condição em geral não é fácil pois isso pode depender bastante de insight e bagagem matemática Mas persistência e traquejo ajudam muito 47 Demonstração por contraexemplo Há situações também em que se tem de demonstrar que uma proposição ou propriedade é falsa Nesse caso basta evidentemente dar um contraexemplo A título de ilustração consideremos a seguinte proposição no conjunto dos números inteiros Se a é um divisor de b e e c então a é um divisor de b c Como é bem conhecido tratase de uma proposição verdadeira Mostremos que sua recíproca não é verdadeira Essa recíproca pode ser enunciada assim Se a é um divisor de b c então a é um divisor de b e c Para mostrar a falsidade dessa última proposição basta um contraexemplo E isso é fácil 5 é um divisor de 3 7 mas não é divisor de nenhuma das parcelas dessa soma Para a descoberta de um contraexemplo vale com as devidas mudanças a mesma observação feita ao final de 46 48 Contrapositiva de uma proposição ou função proposicional Através do raciocínio por redução ao absurdo podemos mostrar que toda condicional se p então q é logicamente equivalente à condicional se q então p chamada contraposita da condicional dada Mostremos usando o raciocínio mencionado que a primeira dessas condicionais implica a segunda Para isso tomamos como hipótese pe q maneira formal de escrever se p então q Observemos porém que a segunda condicional no caso a tese pode ser substituída por q e p ou seja por q e p cuja negação é q e p proposição nitidamente contraditória com a hipótese Essa contradição garante a validade da implicação considerada Analogamente se demonstra a implicação contrária Como exemplo consideremos uma proposição Se a soma de um número inteiro se seu quadrado é um número ímpar então o número dado é ímpar A contrapositiva dessa proposição é Se um número inteiro é par então a soma desses números com seu quadrado é um número par Pelo que vimos demonstrar esse último resultado equivale a demonstrar o primeiro E a vantagem como em muitos casos é que é mais fácil demonstrar essa última versão do teorema basta representar um número par genericamente por 2t e fazer os cálculos algébricos indicados no enunciado 2t 2t² 2t 4t² 2tt 2t² que é par 49 Funções proposicionais e diagramas de Venn Muitas vezes no estudo de questões envolvendo funções proposicionais é interessante representar ou imaginar o conjunto universo e os conjuntos verdade respeitados por meio de um diagrama de Venn pois isso pode ajudar bastante o raciocínio A figura a seguir mostra a representação do conjunto verdade A de uma proposição px cujo conjunto universo é U Para utilizar esse expediente é preciso primeiro estabelecer uma correspondência entre as funções proposicionais derivadas de uma ou duas funções proposicionais através da negação e dos conectivos e as partes correspondentes de U Se A e B são respectivamente os conjuntos verdade de duas funções proposicionais px e qx com o mesmo universo U a tabela a seguir mostra essa correspondência Como exemplo vejamos como se mostra a seguinte equivalência px e qx px ou qx Então os pontos que tornam verdadeira px e qx são os de A Bc Ac Bc Mas esse conjunto por sua vez é o conjunto verdade da função proposicional px ou qx o que completa nossa justificativa Exercícios 17 Qual é o valor lógico das seguintes proposições a 2 5 1 ou 3 1 b 2 é primo e 2 é par c Se 1 2 então 1 2 d Todo número primo é um número real e Qualquer que seja o número real x vale x² x f Existe um número real x tal que x³ 2 g Para que um triângulo seja retângulo é necessário e suficiente que o quadrado de um de seus lados seja igual à soma dos quadrados dos outros dois h Se f é uma função real de variável real então f é uma função par ou uma função ímpar i Se x é um número inteiro e x³ é ímpar então x é ímpar j Duas matrizes quadradas de mesma ordem são iguais se e somente se seus determinantes são iguais 18 Considere que numa universidade se tenha a seguinte situação há pesquisadores que não são professores e professores que não são pesquisadores mas alguns pesquisadores são professores Isso posto quais das seguintes afirmações relativas a essa universidade são verdadeiras a Existem professores que são pesquisadores b Se P indica o conjunto dos professores e Q o conjunto dos pesquisadores então P Q c Todo pesquisador é professor d O conjunto dos professores não está contido no conjunto dos pesquisadores e Existem pesquisadores que não são professores f O conjunto dos pesquisadores está contido no conjunto dos professores 19 Escreva na forma se então a Qualquer lado de um triângulo é menor que a soma dos outros dois lados b Todo número primo diferente de 2 é ímpar c Para um número real x tal que 2 x 2 vale x² 4 d Duas retas quaisquer paralelas entre si e não paralelas ao eixo das ordenadas têm o mesmo coeficiente angular e Sempre que uma função real de variável real é diferenciável num ponto ela é contínua nesse ponto f Um determinante é nulo quando uma de suas filas é formada de zeros 20 Sejam p q e r proposições as duas primeiras verdadeiras e a terceira falsa Indique o valor lógico de a p e q b r ou p c se p e r então q d p se e somente se r 21 Negue as seguintes proposições a Se x ℝ e x 2 então x² 4 b Nenhum triângulo retângulo é equilátero c Qualquer que seja o número real x existe um número inteiro n tal que n x d Existe um número complexo z tal que z⁵ 2 e Todo retângulo é um paralelogramo f Se dois planos são paralelos então toda reta de um deles é paralela ao outro plano Enuncie as recíprocas e as contrapositivas das seguintes propostas Classifique como verdadeiras ou falsas as recíprocas e as contrapositivas das propostas do exercício 27 Enuncie a contraposita da propriedade transitiva da relação maior que em ℝ ou seja da propriedade Se a b e b c então a c Enuncie a contraposita da seguinte proposição Sejam A B e C pontos distintos de um plano Se esses pontos não são colineares então AB BC AC havia matemáticos de alto gabarito que não aceitavam bem ou nem sequer aceitavam os números negativos A ideia intuitiva é que por exemplo todas as diferenças 0 1 1 2 2 3 3 4 de alguma maneira são equivalentes e representam o mesmo número um novo número que veio a ser indicado com o tempo por 1 De maneira análoga se introduzem os números 2 3 É claro que sob o ponto de vista do rigor esse procedimento deixa a desejar o que são essas diferenças afinal mas os primeiros matemáticos a usálo não estavam preocupados com isso e foram em frente Obtidos esses novos números é preciso ainda incorporálos consistentemente ao conjunto dos números naturais por uma questão de uniformidade os números 1 2 3 são representados respectivamente por 1 2 3 o que exige i Estender para o novo conjunto numérico ou seja Z 3 2 1 0 1 2 3 as operações adição e multiplicação de números naturais Isso significa por exemplo dar uma definição de adição no novo conjunto que quando aplicada ao subconjunto dos números naturais parte do novo conjunto leve aos mesmos resultados que a adição de números naturais Por exemplo como 2 3 3 1 4 1 3 4 1 1 7 5 5 é razoável esperar que 2 3 1 3 1 4 1 1 3 4 2 7 5 notar que 2 7 é uma das diferenças que definem 5 Ache um contraexemplo para cada uma das seguintes afirmações Exemplo 1 O conjunto L 2 1 0 1 2 3 é limitado inferiormente e seus limites inferiores são 2 3 4 E L tem mínimo o número 2 Exemplo 2 O conjunto S 6 4 2 0 dos múltiplos negativos de 2 não é limitado inferiormente Obviamente não há nenhum inteiro que seja menor que todo elemento de S O resultado a seguir é um teorema quando se desenvolve a teoria dos números inteiros sistematicamente a partir dos números naturais A palavra princípio que figura em sua designação deriva de razões históricas Princípio do menor número inteiro Se L é um subconjunto de Z não vazio e limitado inferiormente então L possui mínimo Por exemplo o conjunto dos números inteiros positivos é limitado inferiormente e seu mínimo é o número 0 Justifique a propriedade seguinte de duas maneiras a primeira através de sua contraposita e a segunda por redução ao absurdo Se m é um inteiro tal que m³ 2 é ímpar então m é ímpar Para n 1 o primeiro membro dessa igualdade é 1² 1 e o segundo 11 12 1 66 1 Portanto a função proposicional é verdadeira para n 1 Suponhamos que seja verdadeira para algum r 1 isto é suponhamos que 1² 2² r² rr 12r 16 seja verdadeira Então para n r 1 o primeiro membro da igualdade a ser provada é 1² 2² r 1² rr 12r 16 r 1² r 1r 22r 36 r 1r 22r 7 66 ao passo que o segundo é r 1r 22r 1 16 e portanto a função proposicional também é verdadeira para n r 1 Isso prova que a igualdade efetivamente vale para todo inteiro n 1 Prove por meio de um contraexemplo que n² n 41 em que n é um inteiro estritamente positivo nem sempre é um número primo 3 DIVISIBILIDADE EM Z 31 Divisão exata Dizse que o número inteiro a é divisor do número inteiro b ou que o número b é divisível por a se é possível encontrar c Z tal que b ac Nesse caso podese dizer também que b é múltiplo de a Para indicar que a divide b usaremos a notação a b Por exemplo 2 divide 6 porque 6 23 Também se pode afirmar que 0 divide 0 uma vez que para todo inteiro c 0 0 c Se a b e a 0 o número inteiro c tal que b ac será indicado por ba e chamado quociente de b por a A relação entre elementos de Z definida por x y que acabamos de introduzir goza das seguintes propriedades i a a reflexividade De fato a a 1 ii Se a b 0 a b e b a então a b Por hipótese b a c1 e a bc2 Se a 0b 0 então b 0a 0 Suponhamos pois a b 0 Como a ac1c2 segue que c1c2 1 Mas c1 e c2 são positivos e portanto essa igualdade só é possível para c1 c2 1 De onde a b iii Se a b e b c então a c transitividade iv Se a b e a c então a bx cy quaisquer que sejam os inteiros x e y Por hipótese b ad1 e c ad2 Daí bx axd1 e cy ayd2 Somando membro a membro essas igualdades obtemos bx cy axd1 ayd2 axd1 yd2 Então devido à definição dada a bx cy 32 Algoritmo euclidiano Evidentemente há infinitos casos de pares de inteiros tais que nenhum dos dois é divisor do outro Por exemplo nem 2 divide 3 nem viceversa O algoritmo euclidiano de que trataremos aqui estabelece uma divisão com resto e é a base da aritmética teórica teoria dos números Seu nome deriva do fato de Euclides o haver usado em seus Elementos c 300 aC para determinar o máximo divisor comum de dois números positivos Nesse ponto nada mudou de lá para cá como veremos Digase de passagem porém que Euclides só considerava números inteiros estritamente positivos Nosso contexto aqui é mais amplo Seja a um número inteiro estritamente positivo Tomandose algum inteiro b há duas possibilidades i b é múltiplo de a e portanto b aq para um conveniente inteiro q ii b está situado entre dois múltiplos consecutivos de a isto é existe um inteiro q tal que aq b aq 1 Dai 0 b aq a Então fazendo b aq r obtemos b aq r em que 0 r a Juntando as duas possibilidades podemos garantir o seguinte dados dos inteiros a e b com a 0 então sempre se pode encontrar dois inteiros q e r tais que b aq r em que 0 r a Evidentemente r 0 corresponde ao caso em que b é múltiplo de a Vamos imaginar por outro lado que se pudesse determinar outro par de inteiros q1 e r1 tais que b aq1 r1 com 0 r1 a Então aq r aq1 r1 e portanto aq q1 r1 r Suponhamos que r r1 digamos r r1 Dai o segundo membro da última igualdade seria estritamente negativo e como a 0 então q q1 também seria estritamente negativo e portanto q1 q 0 ou seja q1 q 1 Mas de aq q1 r1 r segue que r r1 aq1 q Levandose em conta que a 0 r1 0 e q1 q 1 da última igualdade segue que r a o que é absurdo Da mesma forma provase que a desigualdade r1 r também é impossível De onde r r1 e consequentemente q q1 O resultado acima conhecido como algoritmo euclidiano ou algoritmo da divisibilidade em Z garante a possibilidade de uma divisão aproximada em Z Um enunciado geral para ele é o seguinte Dados um inteiro b qualquer e um inteiro estritamente positivo a podemse determinar dois inteiros q e r tais que b aq r com 0 r a Ademais as condições impostas determinam os inteiros q e r unicamente Os elementos envolvidos no algoritmo têm nomes especiais b é o dividendo a é o divisor q é o quociente e r o resto na divisão euclidiana de b por a Na divisão de um inteiro n por 2 há duas possibilidades o resto ser 0 ou 1 No primeiro caso o número é divisível por 2 e chamado número par Consequentemente os números pares se apresentam sob a forma 2t em que t é um inteiro Se o resto for 1 o número pode ser expresso por n 2t 1 para algum inteiro t e é chamado número ímpar No caso da divisão de um inteiro n por 3 os restos possíveis são 0 1 ou 2 e portanto n 3t n 3t 1 ou n 3t 2 exclusivamente E assim por diante Exemplo 6 Vamos determinar usando o raciocínio da demonstração o quociente e o resto da divisão de 97 por 6 Os múltiplos estritamente positivos de 6 são 6 12 18 24 30 36 42 48 54 60 66 72 78 84 90 96 102 O número 97 está entre 96 6 16 e 102 6 17 Isso já nos dá o quociente 16 O resto de acordo com o algoritmo é r 97 6 16 1 Exemplo 7 Na divisão euclidiana de 345 por a 0 o resto é 12 Determinar os possíveis valores de a divisor e do quociente Se q indica o quociente então 345 a q 12 12 a Daí 357 aq em que a 12 Isso só é possível para a 357 e q 1 a 17 e q 21 a 21 e q 17 a 51 e q 7 a 119 e q 3 cada dez unidades de uma dada espécie constituem uma unidade da espécie imediata superior unidade essa que para efeito de numeração toma o lugar das dez que a formaram Dez unidades simples constituem uma dezena dez dezenas uma centena e assim por diante Posicional significa entre outras coisas que os números são escritos na forma de sequências finitas dos dez algarismos cuja grafia modernamente é 0 1 2 3 4 5 6 7 8 9 e que o valor de um algarismo na sequência depende de sua posição conforme ilustra o exemplo que segue Em 234 o valor de 4 é efetivamente 4 unidades ou de 3 é 3 10 30 e o 2 é 2 10² 200 Na verdad pequeno círculo no século XIII Essa pode ser uma das razões pelas quais comumente se atribuem aos hindus a paternidade de nosso sistema de numeração De fato o mais tardar no século IX os hindus já tinham desenvolvido um sistema de numeração posicional decimal completo essencialmente igual ao nosso pois o persa Muhamed alKhwarizmi um dos grandes sábios da cultura árabe o descreveu numa obra que data aproximadamente do ano 825 atribuindoo aos hindus Embora alKhwarizmi tenha simplesmente explicado os símbolos dos algarismos de 1 a 9 fez uso do zero em seu trabalho Um pequeno círculo que figura numa inscrição hindu do ano 878 parece ter sido o primeiro sinal usado para o zero na história de nosso sistema de numeração O fato de este ser chamado comummente de indoarábico deriva do povo árabe ser o responsável por sua disseminação no Ocidente na esteira da expansão de seus domínios territoriais depois de 1 Sejam m e n inteiros ímpares Prove que a 4 2m 2n b 8 m² n² c 8 m² n² 2 4 Mostre que entre dois números pares consecutivos um é divisível por 4 5 Mostre que a diferença entre os quadrados de dois inteiros consecutivos é sempre um número ímpar E a diferença entre os cubos de dois inteiros consecutivos 6 Demonstre por indução que a 7 23n 1 n 0 b 8 32n 7 n 0 c 11 22n 31² 1 n 1 d 7 32n1 2n2 n 1 e 17 34n1 2 43n1 n 0 7 Prove que a Um dos inteiros a a 2 a 4 é divisível por 3 b Um dos inteiros a a 1 a 2 a 3 é divisível por 4 8 Prove que o produto de dois números inteiros é ímpar se e somente se ambos os números são ímpares 9 Prove que quaisquer que sejam os inteiros a e b a expressão a b a² b² representa um número par Na divisão euclidiana de 802 por a o quociente é 14 Determine os valores possíveis de a e do resto É possível encontrar dois inteiros múltiplos de 5 tais que o resto da divisão euclidiana de um pelo outro seja 13 Justifique a resposta Quantos números naturais entre 1 e 1000 são divisíveis por 9 Justifique a resposta É claro que se acontecer de r1 ser nulo então b mdca b devido ao lema 1 e o processo termina na primeira etapa Se r1 0 passase à segunda e raciocinase da mesma maneira com relação a r2 Se r2 0 então r1 mdcb r1 devido ao lema 1 mas devido ao lema 2 mdcb r1 mdca b das duas conclusões obtidas segue que r1 mdca b E assim por diante Ocorre que como b r1 r2 0 então para algum índice n teremos com certeza rn 1 0 De fato se todos os elementos de r1 r2 r3 fossem nulos então esse conjunto que é limitado inferiormente não teria mínimo o que é impossível Assim para o índice n referido rn 2 rn 1 qn rn rn 1 rn qn 1 Portanto em virtude dos lemmas demonstrados rn mdcrn 1 rn mdcrn 2 rn 1 mdcb r1 mdca b Exemplo 9 Determinar pelo processo das divisões sucessivas mdc41 12 Devido ao papel especial que têm sublinharemos o dividendo o divisor e o resto em cada etapa do processo 41 12 3 5 12 5 2 2 5 2 2 1 2 1 2 Portanto mdc41 12 1 Usualmente porém procedese da seguinte maneira e 5 e continuamos com o processo até obter o máximo divisor comum 1 em função de 41 e 12 Vejamos como 1 5 2 5 12 5 2 2 5 5 12 2 41 12 3 5 12 2 41 5 12 17 Então um par de valores para x0 e y0 tal que 41x0 12y0 1 é 5 17 44 Dois inteiros a e b dizemse primos entre si se mdca b 1 Por exemplo os números 41 e 12 são primos entre si uma vez que como já vimos em 43 mdc41 12 1 Proposição 2 Para que os inteiros a e b sejam primos entre si é necessário e suficiente que se possam encontrar x0 y0 Z tais que ax0 by0 1 Demonstração Se a e b são primos entre si então a proposição 1 garante a existência do par de elementos x0 y0 conforme o enunciado Reciprocamente supomos que se possam encontrar x0 y0 Z tais que ax0 by0 1 Então qualquer divisor de a e b é também divisor de 1 Logo os únicos divisores comuns aos elementos a e b são 1 De onde o máximo divisor comum de a e b é 1 Proposição 4 Sejam a e b inteiros primos entre si Se a c e b c então ab c Demonstração Consideremos uma identidade de Bezout para a e b ax0 by0 1 Multiplicandose ambos os membros dessa igualdade por c acx0 bcy0 c Como a a e b c então ab ac e portanto ab acx0 de maneira análoga demonstrase que ab acx0 bcy0 ou seja ab c Exercícios 16 Encontre o máximo divisor dos pares de números que seguem e para cada caso dê uma identidade de Bezout a 20 e 74 b 68 e 120 c 42 e 96 17 O máximo divisor comum de dois números é 48 e o maior deles é 384 Encontre o outro número 18 O máximo divisor comum de dois números é 20 Para se chegar a esse resultado pelo processo das divisões sucessivas os quotientes encontrados foram pela ordem 2 1 3 e 2 Encontre os dois números 19 a Prove que mdca mdcb c mdca b c b Use esse fato para encontrar o máximo divisor comum de 46 64 e 124 Resolução a Seja d mdca b c e provemos que d mdca mdcb c i d 0 pela definição de máximo divisor comum ii Como d a d b e d c por hipótese então d a e d mdcb c visto que todo divisor de b e c é divisor do máximo divisor comum desses números iii Seja d um divisor de a e de mdcb c então d a d b e d c e portanto divide o máximo divisor comum desses números ou seja divide d b Fica provado 20 Prove que mdcn 2n 1 1 qualquer que seja o inteiro n 21 Sejam a e b números inteiros tais que mdca a b 1 Prove que mdca b 1 O recíproco desse resultado também é verdadeiro Enuncieo e demonstreo Sugestão Para a primeira parte tome um divisor c de a e b e mostre que ele também é divisor de a e a b Demonstre que se a c b c e mdca b d então ab cd Sugestão Use a identidade de Bezout para a b e d Se a e b são inteiros primos entre si demonstre que mdc2ab a2b 1 ou 3 Portanto 60 2 2 3 5 2² 3 5 De fato obviamente d é positivo além disso como γi αi e γi βi então d a e d b por último se d Z e d a e d b então d p1 γ1 p2 γ2 pr γr com γi αi e γi βi Portanto γi minαi βi De onde d d Por exemplo se a 28 e b 300 como 28 2² 3 5 7 e 300 2² 3 5² 7º então mdc28 300 2² 3 5 7 4 Exemplo 12 Através da decomposição canônica a p1 α1 p2 α2 pm αm podese obter uma fórmula para o número de divisores de a De fato um número positivo é divisor de a se e somente se b p1 B1 p2 B2 pm Bm em que 0 Bi αi i 0 1 2 m Como para cada expoente na decomposição de b há αi 1 possibilidades a fim de que b divida a então o número de divisores positivos de a é α1 1α2 1 αm 1 Por exemplo o número de divisores positivos de 300 2² 3 5² é 3 2 3 18 dois números primos positivos Por exemplo 4 2 2 6 3 3 8 3 5 10 3 7 etc Até hoje continua em aberto a questão de saber se essa proposição é falsa ou verdadeira Admitindo a conjectura de Goldbach prove que todo inteiro maior que 5 é soma de três números primos Por exemplo 6 2 2 2 7 2 2 3 8 2 3 3 etc Sugestão Devido à conjectura se n 3 2n 2 p q p e q primos Portanto 2n p q 2 soma de três números primos 29 Ache o menor número inteiro positivo n para o qual a expressão hn n² n 17 é um número composto 30 Se n² 2 é um número primo prove que n é múltiplo de 3 ou n 1 Sugestão Há três possibilidades de expressar um número inteiro n n 3q n 3q 1 n 3q 2 conforme o resto da divisão de n por 3 seja 0 1 ou 2 Mostre que as duas últimas são impossíveis no caso Qual é o menor número inteiro positivo que tem 15 divisores Sugestão Se a p1 α1 p2 α2 pm αm é a decomposição do número procurado em fatores primos então 15 α1 1α2 1αm 1 Observe que só há duas maneiras salvo quanto à ordem de decompor 15 em fatores inteiros positivos 32 Demonstre que o conjunto dos números primos positivos é infinito A primeira demonstração conhecida desse resultado aliás a mesma que esboçaremos a seguir foi dada por Euclides em seus Elementos Esboço da demonstração Suponha que esse conjunto fosse finito digamos que seus elementos fossem p1 p2 pn Construa o número p p1p2pn 1 Esse número não é nenhum dos pi por quê Logo é composto por quê Então é divisível por um dos pi 1 i n por quê Esse absurdo por quê garante a infinitude do conjunto dos primos Assim 1 26 5 5 26 31 26 1 5 26 6 31 5 Então x₀ y₀ 6 5 e portanto o par 2 6 2 5 12 10 é uma solução da equação dada Consequentemente 12 10 12 10 e 12 10 são soluções respectivamente de 26x 31y 2 26x 31y 2 e 26x 31y 2 Proposição 7 Se a equação diofantina ax by c tem uma solução x₀ y₀ então tem infinitas soluções e o conjunto destas é S x₀ bdt y₀ adt t ℤ em que d mdca b Demonstração Mostremos primeiro que todo par x₀ bdt y₀ adt é solução da equação considerada De fato ax₀ bdt by₀ adt ax₀ by₀ ab badt ax₀ by₀ c pois x₀ y₀ é solução por hipótese De outra parte seja x y uma solução genérica da equação Então ax by c ax₀ by₀ Daí ax x₀ by₀ y Mas como d é divisor de a e b então a dr e b ds para convenientes inteiros r e s primos entre si Logo drx x₀ dsy₀ y e portanto rx x₀ sy₀ y Essa igualdade mostra que r divide sy₀ y Mas como r e s são primos entre si então r divide y₀ y proposição 3 Logo y₀ y rt para algum t ℤ Levandose em conta que r ad então y y₀ adt Observandose agora que em consequência rx x₀ sy₀ y srt obtémse x x₀ bdt É interessante e talvez surpreendente observar que o fato de uma equação diofantina ax by c ter infinitas soluções quando tem uma significa geometricamente que a reta de equação ax by c possui uma infinidade de pontos de coordenadas inteiras do plano cartesiano Exemplo 14 Determinar todas as soluções da equação diofantina 43x 5y 250 Como mdc43 5 1 vêse que 250 a equação tem soluções É importante lembrar que se x₀ y₀ é uma solução de 43x 5y 1 então 250x₀ 250y₀ é solução da equação dada como já vimos Mas já vimos também como achar uma solução de 43x 5y 1 por divisões sucessivas Da sucessão 43 5 8 3 5 3 1 2 3 2 1 1 segue que 1 3 2 1 3 5 3 1 1 3 2 5 5 1 43 2 5 5 17 e portanto uma solução de 43x 5y 1 é 2 17 Logo uma solução de 43x 5y 250 é 500 4 250 De onde a solução geral da equação pode ser expressa por 500 5t 4250 43t em que t é uma variável no conjunto dos inteiros Conforme observação ao fim da demonstração da proposição 7 a reta de equação 43x 5y 250 possui uma infinidade de pontos de coordenadas inteiras do plano cartesiano Exercícios 33 Resolva as seguintes equações diofantinas lineares a 3x 4y 20 b 5x 2y 2 c 18x 20y 8 d 24x 138y 18 34 Decomponha o número 100 em duas parcelas positivas tais que uma é múltiplo de 7 e a outra de 11 Problema do matemático L Euler 17071783 35 Ache todos os números inteiros estritamente positivos com a seguinte propriedade dão resto 6 quando divididos por 11 e resto 3 quando divididos por 7 36 O valor da entrada de um cinema é R 800 e da meia entrada R 500 Qual é o menor número de pessoas que pode assistir a uma sessão de maneira que a bilheteira seja de R 50000 Em tempo a capacidade desse cinema é suficiente para esse número de pessoas 37 Ao entrar num bosque alguns viajantes avistam 37 montes de maçã Após serem retiradas 17 frutas o restante foi dividido igualmente entre 79 pessoas Qual a parte de cada pessoa Problema de Mahaviraracarya matemático hindu 7 CONGRUÊNCIAS 71 O conceito de congruência bem como a notação através da qual essa noção se tornou um dos instrumentos mais poderosos da teoria dos números foi introduzido por Karl Friedrich Gauss 17771855 em sua obra Disquisitiones arithmeticae 1801 Para dar uma ideia da noção de congruência consideremos a seguinte questão talvez ingênua mas ilustrativa se hoje é sextafeira que dia da semana será daqui a 1 520 dias Para organizar o raciocínio indiquemos por 0 o dia de hoje sextafeira por 1 o dia de amanhã sábado e assim por diante A partir dessa escolha podese construir o seguinte quadro Nossa questão agora se resume em saber em que coluna da tabela se encontra o número 1 520 Para isso basta observar que dois números da sequência 0 1 2 estão na mesma coluna se e somente se sua diferença é divisível por 7 Suponhamos que o número 1520 se encontre na coluna encabezada pelo número a 0 a 6 Então 1520 a 7q para algum inteiro positivo q Daí 1520 7q a 0 a 6 Ora pela unicidade do resto na divisão euclidiana segue dessa igualdade que a é o resto da divisão de 1520 por 7 Observando que 1520 7 12 217 50 1 concluise que esse resto é 1 e que portanto 1520 está na segunda coluna Logo daqui a 1520 dias será um sábado Questões como essa envolvendo periodicidade exigem uma aritmética diferente O conceito de congruência a ser dado a seguir é a chave dessa aritmética Definição 3 Sejam a b números inteiros quaisquer e m um inteiro estritamente positivo Dizse que a é congruó a b módulo m se m a b isto é se a b mq para um conveniente inteiro q Para indicar que a é congruente a b módulo m usase a notação a b mod m A relação assim definida sobre o conjunto ℤ chamase congruência módulo m Por exemplo na tabela construída na abertura deste tópico dois elementos quaisquer de uma mesma coluna são congruentes módulo 7 Para indicar que a b não é divisível por m ou seja que a não é côncuro a b módulo m escrevese a b mod m Seguem as propriedades básicas da congruência de inteiros C1 a a mod m reflexividade De fato a a 0 é divisível por m C2 Se a b mod m então b a mod m simetria Se a b mod m então m a b ou seja a b mq para algum q Daí b a mq e portanto m b a De onde b a mod m C3 Se a b mod m e b c mod m então a c mod m transitividade Por hipótese m b a e m c b Logo m b a c b ou seja m c a Daí m a c portanto a c mod m C4 Se a b mod m e 0 r m então b é o resto da divisão euclidiana de a por m Reciprocamente se r é o resto da divisão de a por m então a r mod m De fato por hipótese a b mq para algum inteiro q Dai a mq b 0 b m A conclusão decorre da unicidade do quociente e do resto no algoritmo euclidiano A demonstração da recíproca é imediata C5 a b mod m se e somente se a e b dão o mesmo resto na divisão euclidiana por m Por hipótese a b mq para algum inteiro q Portanto a b mq Sejam q1 e r o quociente e o resto da divisão euclidiana de a por m a mq1 r 0 r m Das duas últimas igualdades segue que b mq mq1 r e então b mq1 q r 0 r m Portanto r é o resto da divisão de b por m Por hipótese a e b dão o mesmo resto na divisão euclidiana por m a mq1 r e b mq2 r 0 r m Subtraindose membro a membro essas igualdades a b mq1 q2 De onde a b mod m Todo conjunto formado por um e um só elemento de cada classe de equiva lência módulo m é chamado sistema completo de restos módulo m Obviamente como o representante mais natural da classe r é o elemento r então o conjunto 0 1 2 m 1 é o sistema completo de restos módulo m mais natural Mas nem sempre é o mais conveniente São também sistemas completos de restos módulo m às vezes mais convenientes 0 1 2 m 1 2 se m é ímpar 0 1 2 m2 1 m2 se m é par Para mostrar por exemplo que a congruência x2 1 0 mod 8 não tem solução o uso deste último sistema facilita De fato como x 0 1 2 3 4 mod 8 então x2 0 1 4 9 16 mod 8 Mas 9 1 mod 8 e 16 0 mod 8 Portanto x2 0 1 4 mod 8 De onde x21 1 2 5 mod 8 C6 a b mod m se e somente se a c b c mod m Por hipótese a b mq para algum inteiro q Dai a c b c mq e portanto a c b c mod m Para demonstrar a recíproca é só inverter a ordem do raciocínio C7 a b mod m e c d mod m então a c b d mod m De fato como a b mod m então a c b c mod m devido à propriedade anterior Pelo mesmo motivo da hipótese c d mod m segue que c b d b mod m Devido à transitividade a c b d mod m Essa propriedade pode ser estendida por indução para r congruências se a1 b1 mod m a2 b2 mod m ar br mod m então a1 a2 ar b1 b2 br mod m Em particular se a1 a2 ar a e b1 b2 br b ra1 rb mod m Exemplo 15 Mostrar que 10200 1 é divisível por 11 Como 10 1 mod 11 então devido à propriedade anterior 10200 1200 mod 11 Ou seja 10200 1 mod 11 Dai pela definição de congruência 10200 1 é divisível por 11 Exemplo 16 Mostrar que qualque 72 Critérios de divisibilidade Entre outras coisas podese utilizar a congruência de inteiros para estabelecer critérios de divisibilidade Para isso é preciso usar o fato ver 33 deste capítulo de que todo número N pode ser representado de uma única maneira como um polinômio N a0 a1 10 a2 102 ar 10r em que os coeficientes das potências de 10 estão sujeitos à seguinte limitação 0 a0 a1 a2 ar 9 Isso dá origem à seguinte notação sequencial para indicar o número a0an1a1a0 A ideia quando se quer estabelecer um critério de divisibilidade para o número m é reduzir a expressão 5 módulo m Isto é descobrir uma expressão mais simples em termos dos dígitos a1 a2 ar à qual o polinômio de 5 é congruente módulo m e depois usar a propriedade C5 Vejamos alguns casos i Critério de divisibilidade por 2 Como 10t 0 mod 2 para todo t 1 então N a0 mod 2 Logo N e a0 têm o mesmo resto na divisão por 2 e consequência N é divisível por 2 se e somente se a0 é divisível por 2 Ou seja se a0 é par ii Critério de divisibilidade por 3 Como 10 1 mod 3 então 102 1 mod 3 103 1 mod 3 10t 1 mod 3 Então a1 10 a1 mod 3 a2 102 a2 mod 3 a3 103 a3 mod 3 ar 10t ar mod 3 Logo devido às propriedades C1 e C7 N a0 a1 a2 ar mod 3 Portanto N e a0 a1 a2 ar têm o mesmo resto na divisão por 3 De onde N é divisível por 3 se e somente se a0 a1 a2 ar é divisível por 3 Por exemplo o resto da divisão de 34567 por 3 é o mesmo da divisão de 3 4 5 6 7 25 por 3 ou seja é 1 E 34566 é divisível por 3 uma vez que 3 4 5 6 6 24 o é iii Critério de divisibilidade por 4 Para esse caso cumpre observar que 102 0 mod 4 103 0 mod 4 10t 0 mod 4 Portanto a2 102 0 mod 4 a3 103 0 mod 4 ar 10t 0 mod 4 De onde N a0 10a1 mod 4 Mas a0 10a1 a1a0 é o número formado pelos dois últimos algarismos de N Então N e a1a0 têm o mesmo resto na divisão por 4 e em particular N é divisível por 4 se e somente se a1a0 é Por exemplo o número 15424 é divisível por 4 porque 24 é divisível por 4 iv Critério de divisibilidade por 5 Um número é divisível por 5 se e somente se seu algarismo das unidades é 0 ou 5 A justificação fica como exercício v Critério de divisibilidade por 6 Um número é divisível por 6 se e somente se é divisível por 2 e 3 Se é divisível por 6 obviamente é divisível por 2 e por 3 Quanto à recíproca é só levar em conta a proposição 4 uma vez que 2 e 3 são primos entre si Exemplo 17 Provar que hn nn 1n 2 é divisível por 6 qualquer que seja o inteiro n Provaremos que é divisível por 2 e por 3 o que é suficiente Como n ou n 1 é par então um desses números é divisível por 2 e portanto hn é divisível por 2 Por outro lado há três possibilidades com relação ao 3 n 0 mod 3 n 1 mod 3 ou n 2 mod 3 No primeiro caso n não é divisível por 3 e portanto hn também o é no segundo caso somandose 2 a ambos os membros da congruência obtémse n 2 3 0 mod 3 o que mostra que n 2 é divisível por 3 e portanto hn também é divisível por 3 e no último caso somandose 1 a ambos os membros da congruência obtémse n 1 3 0 mod 3 o que mostra que n 1 é divisível por 3 e portanto o mesmo se pode dizer de hn Em resumo qualquer que seja n um dos fatores de hn é divisível por 3 e por consequência hn também é divisível por 3 8 PROBLEMA CHINÊS DO RESTO Nosso objetivo aqui é mostrar que um sistema de congruências simultâneas do tipo x a1 mod m1 x a2 mod m2 x ar mod mr em que mdcmi mj 1 sempre que i j é possível tem soluções e determinar sua solução geral Obviamente uma solução do sistema é um número inteiro que é solução de cada uma das congruências que o formam operações aritméticas a obra inclui o seguinte problema talvez o específico mais antigo do que modernamente se chama problema chinês do resto Temos uma certa quantidade de coisas cujo número desconhecemos Esse número quando dividido por 3 dá resto 2 quando dividido por 5 dá resto 3 e quando dividido por 7 dá resto 2 Qual o número de coisas Segue uma solução por substituição do problema Se N indica o número de coisas então N 3x 2 N 5y 3 N 7z 2 em que x y z são números inteiros A primeira dessas equações é equivalente à equação diofantina linear N 3x 2 cuja solução geral é N 8 3t x 2 t t ℤ Substituindose N por 8 3t na segunda equação do sistema obtémse 5y 3t 5 A solução geral desta última equação diofantina é y 5 3s t 10 5s s ℤ Portanto N 8 3t 8 310 5s 22 15s Substituindose N por 22 15s na terceira equação do sistema obtémse 7z 15s 24 cuja solução geral é z 48 15r s 24 7r r ℤ De onde N 22 15s 22 1524 7r 338 105r r ℤ que é a solução geral do problema Sun Tsu que provavelmente desconhecia um método geral para resolver esse problema e portanto devia ignorar que ele tem uma infinidade de soluções só encontrou a solução 23 número correspondente a r 3 na solução geral Proposição 8 teorema chinês do resto Sejam m1 m2 mr números inteiros maiores que 1 e tais que mdcmi mj 1 sempre que i j Assim sendo se a1 a2 an são números inteiros arbitrários então o sistema de congruências x a1 mod m1 x a2 mod m2 x ar mod mr é possível Ademais duas soluções quaisquer do sistema são congruentes módulo m1m2mr Demonstração As características do sistema sugerem que um número que possa ser escrito como y₁α₁ y₂α₂ yᵣαᵣ em que y₁ 1 mod m₁ y₁ 0 mod m₂ji y₂ 1 mod m₂ y₂ 0 mod m₁ij e assim por diante é uma solução do sistema Mostremos por exemplo que ele é solução da segunda congruência Como y₁ y₃ yᵣ 0 mod m₂ então y₁α₁ y₃α₃ yᵣαᵣ 0 mod m₂ Como y₂ 1 mod m₂ então y₂α₂ a₂ mod m₂ Portanto y₁α₁ y₂α₂ yᵣαᵣ a₂ mod m₂ Para encontrar um sistema de números que cumpra o papel dos yᵢ i 1 2 r façamos m₁m₂mᵣ m Então mdcm₁ m₂m₁ 1 pois um divisor primo de m₁ é mm₁ teria também de ser divisor de algum mᵢ com j 1 o que é impossível pela hipótese Portanto a congruência linear mm₁y 1 mod m₁ tem solução Se b₁ é uma de suas soluções então mm₁b₁ 1 mod m₁ Mas como m₂ m₃ mᵣ são divisores de mm₁ então mm₁ 0 mod m₂ mm₁ 0 mod m₃ mm₁ 0 mod mᵣ Analogamente se b₂ é solução de mm₂y 1 mod m₂ então mm₂b₂ 1 mod m₂ e mm₁b₁ 0 mod m₁ mmᵣb₂ 0 mod mᵣ E assim por diante Portanto mm₁b₁ mm₂b₂ mmᵣbᵣ cumprem o papel exigido para os números y₁ y₂ yᵣ conforme colocação inicial e b mm₁b₁α₁ mm₂b₂α₂ mmᵣbᵣαᵣ é uma solução do sistema Se c é uma outra solução então c b mod mᵢ i 1 2 r Portanto m₁ m₂ mᵣ são divisores de c b Mas como m₁ m₂ mᵣ são primos entre si dois a dois então m₁m₂mᵣ também é um divisor de c b De onde c b mod m₁m₂mᵣ Portanto a solução geral do sistema é x b mod m₁m₂mᵣ Exemplo 18 O teorema anterior é construtivo como se nota pela demonstração Vejamos como utilizála na resolução do sistema x 1 mod 2 x 2 mod 3 x 3 mod 5 Nesse caso m 30 e as congruências lineares a resolver são 15y 1 mod 2 10y 1 mod 3 e 6y 1 mod 5 Como o número 1 é solução particular de cada uma delas então uma solução do sistema é 15 1 1 10 1 2 6 1 3 53 Logo a solução geral do sistema é dada por x 53 23 mod 30 Exercícios 38 Ache os restos das seguintes divisões a 2⁴⁵ por 7 b 11¹⁰⁰ por 100 Resolução c Como 3 2 mod 5 então 3² 4 mod 5 3³ 8 2 mod 5 3⁴ 16 1 mod 5 dai para a frente os resultados se repetem ciclicamente de quatro em quatro Como 10 2 mod 4 então 3¹⁰ 4 mod 5 Por outro lado como 42 2 mod 5 então 42² 4 1 mod 5 42³ 2 mod 5 42⁴ 1² 1 mod 5 e dai para a frente os resultados se repetem também de quatro em quatro Observandose que 5 1 mod 4 deduzse 42⁵ 2 mod 5 Por último como 6 1 mod 5 então 6⁸ 1 mod 5 Juntando as conclusões parciais 3¹⁰ 4²⁵ 6⁸ 4 2 1 4 mod 5 Portanto o resto é 4 39 Mostre que o número 2²⁰ 1 é divisível por 41 40 Qual é o resto da divisão euclidiana de 1⁵ 2⁵ 3⁵ 99⁵ 100⁵ por 4 Justifique Sugestão Dividir a soma dada em 25 grupos de 4 parcelas 41 a Mostre que o resto da divisão de um número por 10 é seu algarismo das unidades e que o resto da divisão por 100 é o número formado pelos dois últimos algarismos do número dado b Ache o algarismo das unidades de 7¹⁰⁰ c Ache os dois últimos algarismos de g9⁹ 42 Se p e p 2 são números primos então eles se denominam primos gêmeos É o caso por exemplo de 3 e 5 Se p 3 e os números p e p 2 são primos gêmeos prove que a soma p p 2 2p 2 é múltiplo de 12 Sugestão Sendo a soma um número par então a princípio essa soma poderia ser congrua a 0 2 4 6 8 10 módulo 12 Mostrar que todas essas possibilidades exceto a primeira levam a uma contradição 43 Prove que se a b mod m e n é um divisor de m maior que 1 então a b mod n 44 Demonstre a a³ a mod 6 b a³ 0 1 ou 8 mod 9 c Se a é um inteiro que não é divisível por 2 nem por 3 então a² 1 mod 24 d Se a é um cubo perfeito então a 0 1 ou 1 mod 9 Resolução d Por hipótese a b³ para algum inteiro b Mas b 0 1 2 3 4 mod 9 Portanto b³ 0 1 8 27 64 mod 9 Como 8 1 mod 9 então 27 0 mod 9 27 0 mod 9 64 1 mod 9 então a b³ 0 1 ou 1 mod 9 Isso significa que o resto da divisão de um cubo perfeito por 9 é 0 1 ou 8 que corresponde a 1 45 a Encontre um inteiro x tal que x 3 mod 10 x 11 mod 13 e x 15 mod 17 Regiomantanus século XVI b Encontre um inteiro x tal que x 3 mod 11 x 5 mod 19 e x 10 mod 29 Euler século XVIII 46 Resolva mediante o teorema chinês do resto os seguintes sistemas a x 1 mod 10 x 4 mod 11 x 6 mod 13 b x 5 mod 7 x 1 mod 9 x 6 mod 10 47 Um bando de 17 piratas ao tentar dividir igualmente entre si as moedas de uma arca verificou que haveria uma sobra de 3 moedas Seguiuse uma discussão na qual um pirata foi morto Na nova tentativa de divisão já com um pirata a menos verificouse que haveria uma sobra de 10 moedas Nova confusão e mais um pirata foi morto Então por fim eles conseguiram dividir igualmente as moedas entre si Qual o menor número de moedas que a arca poderia conter CAPÍTULO III RELAÇÕES APLICAÇÕES OPERAÇÕES III1 RELAÇÕES BINÁRIAS 1 CONCEITOS BÁSICOS 11 Produto cartesianodefinição 1 Dados dois conjuntos E e F não vazios chamase produto cartesianono de E por F o conjunto formado por todos os pares ordenados x y com x em E e y em F O conceito de par ordenado é tomado aqui como primitivo postulandose que x y u v se e somente se x u e y v Costumase indicar o produto cartesiano de E por F com a notação E x F lêse E cartesian F Assim temos E x F x y x E e y F 12 Relação binária Na matemática e até no diaadia temos de lidar frequentemente com relações entre elementos de um conjunto E ou entre elementos de dois conjuntos distintos E e F Por exemplo se E indica os membros de uma família pais e filhos apenas são relações entre elementos de E x é irmão de y x é pai de y No terreno da matemática se E F ℝ conjunto dos números reais são relações entre elementos de ℝ a igualdade x y a desigualdade x y x é menor que y x y x y 10 Para outro exemplo consideremos E 0 1 2 3 e F 3 2 1 Então é uma relação entre elementos de E e F x y 0 em que x representa um elemento de E e um elemento de F De situações como essa decorre naturalmente uma ideia informal de relação é um sistema R constituído de 1 um conjunto E chamado conjunto de partida 2 um conjunto F chamado conjunto de chegada 3 uma sentença aberta px y em que x é uma variável em E e uma variável em F sentença essa tal que para todo par ordenado a b F a proposição pa b é verdadeira ou falsa Quando pa b é verdadeira dizse que a está relacionado com b mediante ou através de R e escrevese aRb Se pa b é falsa dizse que a não está relacionado com b mediante ou através de R e escrevese aRb Por exemplo se R indica a relação em que o conjunto de partida e o conjunto de chegada são iguais a a b m n r Obviamente o domínio da relação considerada é a e o conjunto imagem é m n r Outro exemplo se indicarmos por R a relação que tem como conjunto de partida 0 1 2 3 conjunto de chegada 3 2 1 e função proposicional dada por y 2x então DR 1 2 3 ao passo que ImR 2 4 6 Segue uma definição mais precisa da relação usandose apenas a linguagem de conjuntos Definição 2 Chamase relação binária de E em F todo subconjunto R de E x F Logo R é relação de E em F se e somente se R E x F Conforme essa definição R é um conjunto de pares ordenados a b pertencentes a E x F Para indicar que a b R usaremos algumas vezes a notação aRb lêse a erre b ou a relacionase com b segundo R Se a b R escreveremos aRb Os conjuntos E e F são denominados respectivamente conjunto de partida e conjunto de chegada da relação R Vale notar que essa definição pode ser considerada equivalente à ideia de relação dada no início desde que admitamos a existência para cada parte R de E x F de uma função proposicional px y com x variável em E e y variável em F função essa que tem como conjunto verdade R No que segue até por simplicidade ao considerar ou ao nos referirmos a uma relação R estaremos presumindo a definição 2 Exemplos 1 1 Se E 0 1 2 3 e F 4 5 6 então E x F 0 4 0 5 0 6 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6 Qualquer subconjunto de E x F é uma relação de E em F São exemplos de relações Ø R1 0 4 0 5 0 6 R2 0 4 1 4 1 5 2 6 R3 2 5 3 6 2 Se E F ℤ então E x F é o conjunto formado por todos os pares ordenados dos números inteiros Um exemplo de relação de ℤ em ℤ é R x y ℤ x ℤ x y n n 2 2 1 1 0 0 1 1 n n 13 Domínio e imagem Seja R uma relação de E em F Definição 3 Chamase domínio de R o subconjunto de E constituído pelos elementos x para cada um dos quais existe algum y em F tal que x R y DR x E y F x R y Definição 4 Chamase imagem de R o subconjunto de F constituído pelos elementos y para cada um dos quais existe algum x em E tal que x R y ImR y F x E x R y Em outros termos DR é o conjunto formado pelos primeiros termos dos pares ordenados que constituem R e ImR é formado pelos segundos termos dos pares de R Assim voltando aos exemplos anteriores temos 1 DR₁ 0 e ImR₁ 4 5 6 DR₂ 0 1 2 e ImR₂ 4 5 6 DR₃ 2 3 e ImR₃ 5 6 2 DR Z e ImR Z 3 DR R e ImR R 14 Representações a Gráfico cartesianо Grande parte das relações estudadas em matemática são relações em que E conjunto de partida e F conjunto de chegada são subconjuntos de R Nesses casos o gráfico cartesiano da relação é o conjunto dos pontos de um plano dotado de um sistema de coordenadas cartesianas ortogonais cujas abscissas são os primeiros termos e as ordenadas os segundos termos dos pares que constituem a relação Exemplos 2 1 R₁ 0 4 0 5 0 6 R₂ 0 4 1 4 1 5 2 6 2 E Z F Z e R x y Z x Z x y 3 E R F R e R x y R x R x 0 e y 0 b Esquema de flechas Quando E e F são conjuntos finitos com poucos elementos podemos indicar uma relação de E em F da seguinte forma representamos E e F por meio de diagramas de Venn e indicamos cada x y R por uma flecha com origem x e extremidade y Exemplo 3 E 0 1 2 3 F 4 5 6 R 0 4 1 4 1 5 2 6 Inversa de uma relação Definição 5 Seja R uma relação de E em F Chamase relação inversa de R e indicase por R1 a seguinte relação de F em E R1 y x F x E x y R Exemplos 4 1 E 0 1 2 3 F 4 5 6 e R 0 4 0 5 0 6 então R1 4 0 5 0 6 0 2 E R F R e R x y R2 y 2x então R1 y x R2 y 2x x y R2 x 2y 3 E R F R e R x y R2 y x2 então R1 y x R2 y x2 x y R2 x y2 Representação de R1 a Se a relação R admite um gráfico cartesiano então o mesmo ocorre com R1 Notandose que x y R se e somente se y x R1 então o gráfico de R1 é simétrico do gráfico de R relativamente à reta de equação y x Exemplos b Dado o diagrama de EulerVenn de uma relação R obtemos o diagrama de R1 simplesmente invertendo o sentido das flechas Por exemplo se E 0 1 2 3 F 4 5 6 e R 0 4 1 4 1 5 2 6 temos E 0 R 4 1 5 2 6 3 isto é R1 4 0 4 1 5 1 6 2