Álgebra Moderna - 4ª Edição Reformulada

ÁLGEBRA MODERNA Hygino H Domingues Gelson Iezzi 4ª edição reformulada Domingues Hygino H 1934 Álgebra moderna volume único Hygino H Domingues Gelson Iezzi 4 ed reform São Paulo Atual 2003 ISBN 8535704019 1 Álgebra I Iezzi Gelson 1939 II Título 034930 CDD512 Í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 coordMarcelo 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 Uilhã Cintra Comunicação Visual e Arquitetura Ltda Visite nosso site wwwatualeditoracombr Central de atendimento ao professor 0xx11 36133030 APRESENTAÇÃO O presente trabalho é uma nova versão bastante reformulada e com algumas ampliaçõ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 vistas 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 abstracto 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 figurado 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 conjunctura das licenciaturas em matemática área para a qual se destina principalmente a obra De fato apesar de ser bastante moderno no uso do formalismo matemático o livro faz um estudo sistemático do assunto e portanto 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 demonstrações e que essa lacuna às vezes não é preenchida antes de iniciarem um curso de álgebra Mas no que se vai ao assunto neste 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 desprensiosa e informal O capítulo II Introdução à aritmética dos números inteiros sofreu dois tipos de alterações em relação às edições anteriores além de ter sido ampliado com um estudo das equações diofantinas lineares de primeiro grau em duas incógnitas e do problema chinês do resto recebeu na presente versão uma abordagem mais pormenorizada e mais rica em exemplos e aplicações Sem falar no seu papel como prérequisito para os capítulos que o seguem a ênfase maior dada à esse tópico deriva de duas razões que se integram i à importância crescente de suas aplicações na criptografia por exemplo ii o fato de o assunto muitas vezes ser ignorado nos cursos de matemática com prejuízo considerável para a formação dos futuros professores e pesquisadores Como nas edições anteriores o capítulo III Relações aplicações operações é muito esmiuç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 assuntos 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 mudanças de caráter geral já mencionadas no que se refere à linguagem e abordagem com ênfase maior nos exemplos apresenta como novidade um estudo mais abrangente e temático dos grupos de permutações Quanto ao capítulo V Anéis e corpos houve incorporaçã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 elementos 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 artificiosa Preferimos considerando 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 natural 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 e VI 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 Os autores 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 63 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 85 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 sobejatras 98 8 Aplicação inversa 101 9 Aplicação idêntica 103 10 Restrições 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 CAPÍTULO IV GRUPOS 137 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 165 5 Proposições sobre homomorfismos de grupos 167 6 Núcleo de um homomorfismo 169 7 Isomorfismos de grupos 171 8 O teorema de Cayley 174 IV3 Grupos cíclicos 177 9 Potências e múltiplos 177 10 Grupos cíclicos 179 11 Classificação dos grupos cíclicos 182 IV4 Classes laterais Teorema de Lagrange 13 Classes laterais 186 14 O teorema de Lagrange 189 IV5 Grupos normais Grupos quotients 15 Introdução 192 16 Multiplicação de subconjuntos 193 17 Subgrupos normais 193 18 Grupos quotients 195 19 O teorema do homomorfismo 196 IV6 Permutações 20 Ciclos e notação cíclica 200 21 Assinatura de uma permutação 204 CAPÍTULO ANÉIS E CORPOS V1 Anéis 1 Nota histórica 210 2 Anéis e subanéis 211 3 Tipos de anéis 211 V2 Homomorfismos e isomorfismos de anéis 4 Introdução 232 5 Homomorfismos de anéis 232 6 Proposições sobre homomorfismos de anéis 234 7 Núcleo de um homomorfismo de anéis 235 8 Isomorfismos de anéis 236 V3 Corpo de frações de um anel de integridade 9 Quotientes em um corpo 243 10 Corpo de frações de um anel de integridade 244 V4 Característica de um anel 11 Múltiplos de um elemento de um anel 247 12 Característica de um anel 248 13 Característica de um corpo 249 V5 Ideais em um anel comutativo 15 Nota histórica 255 16 Ideais em um anel comutativo 255 17 Ideais gerados por um número finito de elementos 257 18 Operações com ideais 259 19 Ideais primos e maximais 260 V6 Anéis quotients 265 V7 Ordem em um anel de integridade 20 Anéis de integridade ordenados 270 21 Propriedades imediatas de um anel de integridade ordenado 271 22 Anéis de integridade bem ordenados 275 23 Corpos ordenados 276 CAPÍTULO VI ANÉIS DE POLINÔMIOS 1 Nota histórica 281 2 Construção do anel de polinômios 281 3 Polinômios idênticos 282 4 Divisibilidade em Ax 285 5 Sobre raízes 297 6 Polinômios irreduzíveis 312 CAPÍTULO VII ANÉIS PRINCIPAIS E FATORIAIS 1 Nota histórica 321 2 Divisibilidade em um anel de integridade 322 3 Anéis principais fatoriais e euclidianos 330 4 Polinômios sobre anéis fatoriais 340 RESPOSTAS 347 ÍNDICE REMISSIVO 362 BIBLIOGRAFIA 368 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 ideia de cardinal para conjuntos infinitos Cantor estava considerando a infinitude destes como algo efetivamente atual e não apenas potencial como se aceitava até então 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 transfínito 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 conjunto dos irracionais algo que contrariava a velha ideia de que 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 axiomatzada 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 à escolha dos elementos de um conjunto salvo que excluiremos 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 C C 0 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 de 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 indicamos 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 Provemos 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 27 Complementar Dados um conjunto U e um subconjunto A U chamase complementar de A em relação a U e denotase por AᶜU a parte de U formada pelos elementos de U que não pertencem a A Ou seja AᶜU x U x 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 complementar de uma parte A desse universo apenas por Aᶜ 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ᶜ Ø e Øᶜ U Aᶜᶜ A A Aᶜ Ø e A Aᶜ U A Bᶜ Aᶜ Bᶜ e A Bᶜ Aᶜ Bᶜ 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ᶜ Aᶜ Bᶜ Seja x um elemento de U Se x A Bᶜ então x A B e portanto x A e x B Logo x Aᶜ e x Bᶜ e fica provado que A Bᶜ Aᶜ Bᶜ Agora se x Aᶜ Bᶜ então x A e x B e portanto x A B se pertencesse a esse conjunto teria de pertencer a A ou a B De onde x A Bᶜ 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 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 Resolução Seja x A B Então x A C Temos aqui duas possibilidades x A ou x C Mas se x A então x A B A C e portanto x C Assim todo elemento de B é também elemento de C De maneira análoga provese que todo elemento de C é elemento de B De onde 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 Ø 11 b Prove que se um conjunto A tem n elementos então PA tem 2ⁿ elementos c Se o número de subconjuntos binários formados de dois 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 Encontre um exemplo para mostrar que pode ocorrer a desigualdade seguinte A B C A B A C 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 estatui que uma proposição não pode ser verdadeira e falsa ao mesmo tempo e a lei do terceiro excluído que estatui 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 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 ℝ 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 ℝ pode 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 ℕ é 0 1 4 9 disjuntiva 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 propostas 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 e 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 concluise 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 procederia 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 acarreta ou implica qx A notação é a mesma px qx Por exemplo se U ℝ 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 procederia escrever x² 4 acarreta 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 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 vos deste texto e por isso nos atemos a um exemplo Suponhamos que se deseje 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 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 asqrt2 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 se 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 cumpra 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 de 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 contrapositiva 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 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 Enuncie as recíprocas e as contrapositas das seguintes proposições Classifique como verdadeiras ou falsas as recíprocas e as contrapositas das proposições 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 ℤ 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 2 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 ii Estender para ℤ a ideia de menor e maior a partir das coerentemente com as ideias correspondentes em ℕ Feito isso podemos por fim nos referir à ℤ como o sistema ou campo dos números inteiros Obviamente essas considerações visam apenas dar uma ideia despretensiosa da construção dos números inteiros Esse desenvolvimento que quando feito com rigor e formalismo é bastante trabalhoso e até tedioso foge ao plano traçado para este trabalho e por isso não será feito aqui Começaremos considerando toda essa construção já feita bem como conhecidas as propriedades básicas das operações e da relação de ordem em ℤ 2 INDUÇÃO 21 Princípio do menor número inteiro Seja ℒ um subconjunto não vazio de ℤ Dizemos que ℒ é limitado inferiormente se existe um número a ℤ tal que a x qualquer que seja o elemento x ℒ Ou seja a menor que ou igual a qualquer elemento de ℒ Todo elemento a ℤ que cumpre essa condição chamase limite inferior de ℒ Obviamente se um inteiro a é limite inferior de ℒ então todo inteiro menor que a também o é Um limite inferior de ℒ que pertença a esse conjunto chamase mínimo de ℒ Podese provar que um subconjunto não vazio de ℤ não pode possuir mais do que um mínimo Ache um contraexemplo para cada uma das seguintes afirmações Exemplo 1 O conjunto ℒ 2 1 0 1 2 3 é limitado inferiormente e seus limites inferiores são 2 3 4 e ℒ 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 ℒ é um subconjunto de ℤ não vazio e limitado inferiormente então ℒ possui mínimo Por exemplo o conjunto dos números inteiros positivos é limitado inferiormente e seu mínimo é o número 0 22 Indução Usando o princípio do menor número inteiro podemse deduzir duas proposições bastante úteis para provar a veracidade de funções propositivas definidas numa parte de ℤ limitada inferiormente Primeiro princípio de indução Seja pn uma função proposicional cujo universo é o conjunto dos inteiros maiores que ou iguais a um inteiro dado a Suponhamos que se consiga provar o seguinte i pa é verdadeira ii Se r a e pr é verdadeira então pr 1 também é verdadeira Então pn é verdadeira para todo n a Demonstração Seja ℒ x ℤ x a e px é falsa Se mostramos que ℒ o princípio estará justificado Para isso vamos raciocinar por redução ao absurdo Suponhamos ℒ Então uma vez que ℒ é limitado inferiormente a é um limite inferior ℒ possui mínimo i₀ Como pi₀ é verdadeira é claro que i₀ a então i₀ 1 a Por outro lado pi₀ 1 é verdadeira já que i₀ 1 está fora de ℒ Então levando em conta a hipótese ii pi₀ 1 1 pi₀ é verdadeira Mas isso é absurdo pois i₀ está em ℒ 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 Exemplo 3 Mostremos que 1² 2² n² nn 12n 1 6 sempre que n 1 No caso a função proposicional pn é a igualdade do enunciado Para n 1 o primeiro membro dessa igualdade é 1² 1 e o segundo 11 121 1 6 1 Portanto a função proposicional é verdadeira para n 1 Supomos que seja verdadeira para algum r 1 isto é suponhamos que 1² 2² r² rr 12r 1 6 seja verdadeira Então para n r 1 o primeiro membro da igualdade a ser provada é 1² 2² r 1² rr 12r 1 6 r 1² r 1r 22r 1 6 r 12r² 7r 6 6 ao passo que o segundo é r 1r 22r 1 6 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 Segundo princípio de indução Seja pn uma função proposicional cujo universo é o conjunto dos inteiros maiores que ou iguais a um inteiro dado a Suponhamos que se consiga prover o seguinte i pa é verdadeira ii Se r a e pk é verdadeira e para todo k tal que a k r então pr também é verdadeira Então pn é verdadeira para todo n a A demonstração desse princípio é análoga à do primeiro e não será feita aqui ver exercício 2 Prove por meio de um contraexemplo que n² n 41 em que n é um inteiro estritamente positivo nem sempre é um número primo Exercícios 1 Demonstre por indução a 1 2 n nn 1 2 n 1 b 1 3 5 2n 1 n² n 1 c 1³ 2³ n³ 1 2 n² n 1 d 1 2 2 3 n n 1 nn 1n 2 3 n 1 e n² n 1 n 2 2 Demonstre o segundo princípio de indução 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 c₁ e a bc₂ Se a 0b 0 então b 0a 0 Suponhamos pois a b 0 Como a ac₁c₂ segue que c₁c₂ 1 Mas c₁ e c₂ são positivos e portanto essa igualdade só é possível para c₁ c₂ 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 ad₁ e c ad₂ Dai bx axd₁ e cy ayd₂ Somando membro a membro essas igualdades obtemos bx cy axd₁ yd₂ axd₁ yd₂ Dessa propriedade segue em particular que Se a b e a c então a b c e a b c Se a b então a bx qualquer que seja o inteiro x v Se a c e c d então ac bd Por hipótese b ar e d cs para convenientes inteiros r e s Multiplicandose membro a membro essas igualdades obtémse bd acrs De onde ac bd Exemplo 5 Vamos provar que hn 2²ⁿ 15n 1 é divisível por 9 qualquer que seja o inteiro n 1 A demonstração será feita por indução sobre n Como h1 2²¹ 15 1 1 18 2 9 então a afirmação é verdadeira para n 1 Seja r 1 e suponhamos hr divisível por 9 Então hr 2²ʳ 15r 1 9 q para algum inteiro q Segue daí que 2²ʳ 15r 1 2²ʳ 15r 15 49q 15r 18 94q 5r 2 o que mostra que hr 1 é múltiplo de 9 Pelo primeiro princípio de indução a propriedade está demonstrada 32 Algoritmo euclidiano Evidentemente há infinitos casos de pares de inteiros tais que nenhum dos dois é divisor do outro Por exemplo nem 2 é divisor de 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 r 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 Ademais as condições impostas determinam os inteiros q e r univocamente 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 impar 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 Dai 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 33 Sobre o nosso sistema de numeração Como é bem conhecido nosso sistema de numeração o mesmo usado hoje praticamente em todo o mundo civilizado é decimal posicional Decimal significa em resumo que para escrever todos os números bastam dez algarismos ou dígitos que cada dez unidades de uma dada espécie constituem uma unidade da espécie imediatamente 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 de 2 é 2 10² 200 Na verdade 234 4 3 10 2 10² Obviamente a adoção desse sistema pressupõe que se possa fazer com qualquer número positivo ou mesmo que se fez com o número do exemplo Aliás o objetivo principal deste tópico é dar uma ideia do porquê disso Na verdade como poderemos observar ainda que de passagem é possível construir um sistema de numeração posicional tomando como base qualquer número natural b 2 No curso da história os sistemas posicionais plenos representam o ponto alto de um longo desenvolvimento Mas certamente há bem mais de quatro milênios os babilônios já tinham introduzido um sistema de numeração posicional embora incompleto Na verdade esse povo por razões difíceis de explicar criou um sistema de numeração misto muito avançado para a época Até o número 59 era decimal aditivo com apenas um símbolo para a unidade e um para a dezena Por exemplo o símbolo podia indicar o 11 ou 1 10 60 601 ou mesmo outros números dependendo do contexto ou até da proximidade dos símbolos O primeiro sistema de numeração decimal posicional surgiu na China por volta do século XV aC Ele tinha porém características diferentes do nosso e mesmo tendo evoluído ao longo do tempo só há registro do uso de um símbolo para o zero um 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 não 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 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 suponhamos 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 quocientes 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 proposto 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 22 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 23 Se a e b são inteiros primos entre si demonstre que mdc2a b a 2b 1 ou 3 5 NÚMEROS PRIMOS 51 Um número inteiro a 0 1 tem pelo menos quatro divisores 1 e a Esses são os divisores triviais de a Alguns números diferentes de 0 e 1 só têm os divisores triviais são os chamados números primos Por exemplo o número 2 é primo pois seus únicos divisores são 1 e 2 Um número inteiro diferente de 0 e 1 que tem divisores não triviais é chamado número composto O 6 por exemplo cujos divisores são 1 2 3 e 6 Definição 2 Um número inteiro p é chamado número primo se as seguintes condições se verificam i p 0 ii p 1 iii Os únicos divisores de p são 1 p Um número inteiro a 0 1 é chamado número composto se tem outros divisores além dos triviais Lema 3 lema de Euclides Sejam a b p Z Se p é primo e p ab então p a ou p b Demonstração Suponhamos que p não seja um divisor de a Logo p também não é divisor de a Como os divisores de p são apenas 1 e p então os divisores comuns a p e a são apenas 1 Daí mdcp a 1 e portanto existem x₀ y₀ Z tais que px₀ ay₀ 1 Multiplicandose ambos os membros dessa igualdade por b obtémse pbx₀ aby₀ b Como p p e p ab hipótese então p pbx₀ aby₀ ou seja p b Analogamente se mostra que se p não divide b então divide a Por indução podese demonstrar sem dificuldades maiores que se p é primo e divide a₁a₂aₙ n 1 então p divide um dos fatores aᵢ número inteiro L possui mínimo o qual será denotado por p Se p não fosse primo então seria composto já que é maior que 1 teria um divisor não trivial q e portanto também q seria divisor de p Resumindo p teria um divisor q₁ tal que 1 q₁ p q₁ q ou q₁ q Juntando as conclusões p a e q₁ p do que segue que q₁ a e portanto q₁ L Absurdo já que p é o mínimo de L e 1 q₁ p Proposição 5 teorema fundamental da aritmética Seja a 1 um número inteiro Então é possível expressar a como um produto a p₁p₂pᵣ em r 1 e os inteiros p₁ p₂ pᵣ são números primos positivos Além disso se a q₁q₂qₖ em que q₁ q₂ qₖ são também números primos positivos então s r e cada pᵢ é igual a um dos qⱼ Demonstração i Para demonstrar a possibilidade da decomposição a rigor se deveria raciocinar por indução Mas nossa explicação será meio informal Devido ao lema 4 a tem um divisor primo positivo p₁ Logo a p₁q₁ para um conveniente q₁ Z Como a e p₁ são estritamente positivos o mesmo acontece com q₁ que além disso é menor que a é um fator positivo de a Se q₁ 1 demonstração concluída a p₁ é primo positivo Se q₁ 1 repetese o raciocínio com esse número tomase um divisor primo p₂ de q₁ o que é garantido pelo lema 4 e portanto q₁ p₂q₂ para um conveniente inteiro positivo q₂ q₂ q₁ Nesta altura a p₁p₂q₂ em que p₁ e p₂ são primos e q₂ 1 Agora repetese o raciocínio o que permitirá cancelar um fator do primeiro membro com um igual a ele do segundo E assim por diante Como evidentemente não se pode ter uma situação do tipo pₛ₁ pₛ₂pᵣ 1 pois isso significaria que os números primos do primeiro membro seriam divisores de 1 o que é impossível então r s e cada fator do primeiro membro é igual a um do segundo como na demonstração o menor divisor primo do quociente que no caso novamente te é 2 e assim por diante O algoritmo prático costuma ser ensinado da maneira que segue 60 2 30 2 15 3 5 5 1 Portanto 60 2 2 3 5 2² 3 5 52 Sobre a decomposição em fatores primos A proposição anterior dada sua importância merece alguns comentários e especificações Na decomposição de um inteiro estritamente positivo a em fatores primos positivos conforme o teorema pode ocorrer de um fator se repetir algumas vezes Nesse caso podemse reunir esses fatores repetidos numa só potência mediante a notação exponencial Supondo que os fatores primos distintos sejam p₁ p₂ pₘ m 1 e que eles apareçam respectivamente α₁ α₂ αₘ vezes αᵢ 1 i 1 2 m a decomposição poderá ser escrita assim a p₁α₁ p₂α₂ pₘαₘ Essa decomposição com os fatores primos em ordem crescente será tratada como decomposição canônica de a em fatores primos Mas muitas vezes lidase numa mesma questão com dois ou mais inteiros estritamente positivos Quando isso acontece pode ser convenientemente ampliar a ideia de decomposição canônica para que em todas figurem os mesmos fatores primos Isso é sempre possível recorrendose ao uso do expoente nulo Assim se um fator primo aparece na primeira decomposição com expoente não nulo e não aparece explicitamente na segunda nós o inserimos nesta com expoente igual a 0 Com essa convenção supondo que os inteiros sejam a e b podemos escrevêlos assim a p₁α₁ p₂α₂ pᵣ e a p₁β₁ p₂β₂ pᵣ αᵢ βᵢ 0 Por exemplo os números 28 e 300 podem ser representados da seguinte forma 28 2² 3 5 7 e 300 2² 3 5² 7⁰ Através desse expediente podese construir o máximo divisor comum de dois elementos estritamente positivos e por consequência de qualquer par de inteiros 0 1 De fato supondo que esses elementos sejam a e b e que sejam dados por 3 então o elemento d p₁γ₁ p₂γ₂ pᵣ em que γᵢ minαᵢ βᵢ é o máximo divisor comum de a e b 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 p₁γ₁p₂γ₂pᵣγᵣ 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 p₁ α₁ p₂ α₂ pₖ αₖ 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 p₁ B₁ p₂ B₂ pₖ Bₖ 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αₖ 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 2 3 3 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 31 Qual é o menor número inteiro positivo que tem 15 divisores Sugestão Se a p₁ α₁ p₂ α₂ pₖ αₖ é a decomposição do número procurado em fatores primos então 15 α₁ 1α₂ 1αₖ 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 p₁ p₂ pₙ Construa o número p p₁p₂pₙ 1 Esse número não é nenhum dos pᵢ por quê Logo é composto por quê Então é divisível por um dos pᵢ 1 i n por quê Segue então que p 1 por quê Esse absurdo por quê garante a infinidade do conjunto dos primos Devido à Arithmetica hoje são chamadas equações diofantinas todas as equações polinomiais não importa o número de incógnitas com coeficientes inteiros sempre que seu estudo seja feito tomando como universo das variáveis o conjunto dos números inteiros Isso não obstante Diofanto só ter trabalhado com alguns poucos casos particulares dessas equações e seu universo numérico ter sido o dos números racionais estritamente positivos Aqui só estudaremos as equações diofantinas lineares em duas incógnitas Ou seja equações do tipo ax by c em que a e b são inteiros não nulos Uma solução de 4 é nesse contexto um par x₀ y₀ de inteiros tais que a sentença ax₀ by₀ c é verdadeira Inicialmente deduziremos uma condição para que 4 tenha uma solução Proposição 6 Uma equação diofantina linear ax by c tem solução se e somente se d mdca b é um divisor de c Demonstração Se x₀ y₀ é uma solução vale a igualdade ax₀ by₀ c Como d a e d b então d c devido à propriedade iv 31 Como d mdca b então devido à proposição 1 podemse determinar x₀ y₀ Z tais que ax₀ by₀ d Mas por hipótese d c e portanto c dq para algum inteiro q De onde c dq ax₀ by₀q ax₀q by₀q o que mostra que o par x₀q y₀q é solução da equação considerada É importante observar que se x₀ y₀ é uma solução de ax by c com a b 0 então x₀ y₀ e x₀ y₀ são soluções respectivamente de ax by c ax by c e ax by c Exemplo 13 Encontrar uma solução da equação diofantina 26x 31y 2 Como mdc26 31 1 então a equação tem solução Usaremos o método das divisões sucessivas para exprimir o máximo divisor de 26 e 31 por meio de uma identidade de Bezout 31 26 1 5 26 5 5 1 5 1 5 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 de 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 que obviamente divide 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 1 43 2 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 Mahaviracara 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 idéia 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 1 520 se encontre na coluna encabezada pelo número a 0 a 6 Então 1 520 a 7q para algum inteiro positivo q Daí 1 520 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 1 520 por 7 Observando que 1 520 7 12 217 50 1 concluise que esse resto é 1 e que portanto 1 520 está na segunda coluna Logo daqui a 1 520 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 é congruente 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 Z chamase congruência módulo m Por exemplo na tabela construída na abertura deste tópico dois elementos quais quer 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 é congru 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 Reciprocalmente 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 Daí 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 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 12 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 ra 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 Daí pela definição de congruência 10200 1 é divisível por 11 Exemplo 16 Mostrar que qualquer que seja o inteiro ímpar a o resto da divisão de a2 por 8 é 1 Os restos possíveis da divisão de a por 8 são 1 3 5 ou 7 Se por exemplo o resto fosse 2 então a 8q 2 24q 1 seria par o que não é possível Portanto a 1 3 5 ou 7 mod 8 Então a2 1 9 25 ou 49 mod 8 Mas 9 1 mod 8 25 1 mod 8 e 49 1 mod 8 Daí a2 1 1 1 ou 1 mod 8 Ou seja a2 1 mod 8 qualquer que seja o inteiro ímpar a e portanto devido à propriedade C4 o resto da divisão de a2 por 8 é 1 C10 Se ca cb mod m e mdcc m d 0 então a b mod md Por hipótese ca cb mq ou ca b mq para algum inteiro q Dai dividindose os dois membros dessa igualdade por d o que é possível em Z pois d é divisor de c e m cda b mdq o que mostra que md é divisor de cda b Mas por propriedade já vista cd e md são primos entre si Logo md divide a b Isso significa que a b mod md como queríamos provar Por exemplo como 14 2 mod 4 e mdc2 4 2 podese cancelar o 2 em cada um dos números que figuram na congruência daí resultando que 7 1 mod 2 Convém observar porém que o cancelamento puro e simples do primeiro e do segundo membros não vale de um modo geral pois voltandose ao exemplo considerado 142 7 não é congruente a 22 1 módulo 4 Mas há uma importante situação particular expressa no corolário a seguir em que vale Corolário Se ca cb mod m e mdcc m 1 então a b mod m A demonstração é imediata 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 5 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 a n a n1 a 1 a0 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 a0 a1 ar à qual o polinômio de 5 é côncavo 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 consequentemente N é divisível por 2 se 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 10r ar mod 3 Logo devido às propriedades C1 e C7 N a0 a1 a2 ar 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 a3 103 0 mod 4 ar 10r 0 mod 4 De onde N a0 10a1 mod 4 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 Os sistemas de congruência lineares foram introduzidos na China em épocas remotas talvez já fossem utilizados no século I em questões ligadas ao calendário Mas eles aparecem também em obras matemáticas chinesas em versões mais simples a mais antiga das quais é o Manual de matemática de Sun Tsu escrita provavelmente no fim do século III e cujo conteúdo veio a se tornar parte do curso exigido para os servidores públicos civis Embora consistindo basicamente em métodos para operações aritméticas a obra inclui o seguinte problema talvez o especime 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 obtense 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 mn 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 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 8 1 mod 9 então a b³ 0 1 ou 1 mod 9 Ach e os restos das seguintes divisões a 245 por 7 b 11100 por 100 c 310425 68 por 5 d 524841 285 por 3 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 CAPÍTULO III RELAÇÕES APLICAÇÕES OPERAÇÕES III1 RELAÇÕES BINÁRIAS 1 CONCEITOS BÁSICOS 11 Produto cartesiano Definiçã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 cartesiano F Assim temos E x F x y x E e y 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 escrevemos 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 variando em E e y variando 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 presupondo 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 DR1 0 e ImR1 4 5 6 DR2 0 1 2 e ImR2 4 5 6 DR3 2 3 e ImR3 5 6 2 DR Z e ImR Z 3 DR R e ImR R 14 Representações a Gráfico cartesiano 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 R1 0 4 0 5 0 6 R2 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 R¹ a seguinte relação de F em E R¹ y x F 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 R¹ 4 0 5 0 6 0 2º E ℝ F ℝ e R x y ℝ² y 2x então R¹ y x ℝ² y 2x 3º E ℝ F ℝ e R x y ℝ² y x² então R¹ y x ℝ² y x² Representação de R¹ a Se a relação R admite um gráfico cartesiano então o mesmo ocorre com R¹ Notandose que x y R se e somente se y x R¹ então o gráfico de R¹ é 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 R¹ 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 isto é R¹ 4 0 4 1 5 1 6 2