Algebra Moderna - Domingues e Iezzi - 4a Edicao Reformulada

ÁLGEBRA MODERNA Hygino H Domingues Gelson Iezzi ATUAL EDITORA Hygino H Domingues Gelson Iezzi ÁLGEBRA MODERNA 4ª edição reformulada UFPEL Lic em Matemática a Distância Apoio FINEP ATUAL EDITORA Hygino H Domingues Gelson Iezzi Copyright desta edição SARAIVA SA Livreiros Editores São Paulo 2003 Av Marquês de São Vicente 1697 Barra Funda 01139904 São Paulo SP Fone 0xx11 36133000 Fax 0xx11 36113308 Fax vendas 0xx11 36113268 wwweditorasaraivacombr Todos os direitos reservados Dados Internacionais de Catalogação na Publicação CIP Câmara Brasileira do Livro SP Brasil Domingues Hygino H 1934 Álgebra moderna volume único Higino H Domingues Gelson Iezzi 4 ed reform São Paulo Atual 2003 Bibliografia ISBN 8535704019 I Álgebra I Iezze Gelson 1939 II Título 034930 CDD512 Índices para catálogo sistemático I Á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 Sismotto 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 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 e mantido 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 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 a á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 alvo 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 não se vai no 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 despretensiosa 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 a esse tópico deriva de duas razões que se integram i a 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 sistemático dos grupos de permutações Quanto ao capítulo V Anéis e corpos houve a 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 mas não obstante dá uma boa idéia 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 eventuais nos deram algumas pistas para as mudanças presentes Os autores SUMÁRIO CAPÍTULO I NOÇÕES SOBRE CONJUNTOS E DEMONSTRAÇÕES 7 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 29 1 Introdução 29 2 Indução 30 3 Divisibilidade em Z 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 78 3 Relações de ordem 85 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 injetoras Aplicações sobrejetoras 98 8 Aplicação inversa 101 9 Composição de aplicações 103 10 Aplicação idêntica 106 11 Restrição e prolongamento de uma aplicação 108 12 Aplicações monótonas 108 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 Z 135 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 162 5 Proposições sobre homomorfismos de grupos 164 6 Núcleo de um homomorfismo 165 7 Isomorfismos de grupos 167 8 O teorema de Cayley 169 IV3 Grupos cíclicos 174 9 Potências e múltiplos 174 10 Grupos cíclicos 177 11 Classificação dos grupos cíclicos 179 12 Grupos de tipo finito 182 IV4 Classes laterais Teorema de Lagrange 186 13 Classes laterais 186 14 O teorema de Lagrange 189 IV5 Subgrupos normais Grupos quocientes 192 15 Introdução 192 16 Multiplicação de subconjuntos 193 17 Subgrupos normais 193 18 Grupos quocientes 195 19 O teorema do homomorfismo 196 IV6 Permutações 200 20 Ciclos e notação cíclica 200 21 Assinatura de uma permutação 204 CAPÍTULO V ANÉIS E CORPOS 210 V1 Anéis 210 1 Nota histórica 210 2 Anéis e subanéis 211 3 Tipos de anéis 218 V2 Homomorfismos e isomorfismos de anéis 232 4 Introdução 232 5 Homomorfismos de anéis 233 6 Proposições sobre homomorfismos de anéis 234 7 Núcleo de um homomorfismo de anéis 235 8 Isomorfismo de anéis 236 V3 Corpo de frações de um anel de integridade 243 9 Quocientes em um corpo 243 10 Corpo de frações de um anel de integridade 244 V4 Característica de um anel 247 11 Introdução 247 12 Múltiplos de um elemento de um anel 248 13 Característica de um anel 249 14 Característica de um corpo 252 V5 Ideais em um anel comutativo 255 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 quocientes 265 V7 Ordem em um anel de integridade 270 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 281 1 Nota histórica 281 2 Construção do anel de polinômios 282 3 Polinômios idênticos 285 4 Divisibilidade em Ax 291 5 Sobre raízes 297 6 Polinômios irredutíveis 312 CAPÍTULO VII ANÉIS PRINCIPAIS E FATORIAIS 321 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 INDICE 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 idéia 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 ¹ 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 transfinito 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 o dos 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 L Kronecker 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 poderemos 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 assimSe 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 dizemos que A é um subconjunto de B ou uma parte de B e denotamos essa relação por 9 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 Indiquemos 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 da outra forma o conjunto dos números inteiros contém propriamente o conjunto dos números naturais ou seja Z N 24 Conjunto vazio Com vistas a poder lidar com a linguagem de conjuntos mais uniformemente aceitase a existência de um conjunto sem elementos o conjunto vazio que pode ser definido por qualquer propriedade contraditória e que é denotado pelo símbolo Por exemplo x Q x R Uma decorrência lógica mas estranha da aceitação da existência de conjunto vazio é que A qualquer que seja o conjunto A De fato supor A para algum A significaria admitir o seguinte existe um objeto x tal que x e x A Como não pode ocorrer x então devese aceitar 10 que A Convém notar ainda que pois o segundo desses conjuntos possui um elemento o conjunto vazio ao passo que o primeiro não possui nenhum 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 idéia é 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 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 11 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 e portanto A 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á idéia 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 AcU a parte de U formada pelos elementos de U que não pertencem a A Ou seja AcU 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 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 Uc e c U Acc A A Ac e A Ac U A Bc Ac Bc e A Bc Ac Bc As duas últimas propriedades são conhecidas como leis de De Morgan ou leis de dualidade A título de exercício demonstremos que A Bc Ac Bc Seja x um elemento de U Se x A Bc então x A B e portanto x A e x B Logo x Ac e x Bc ou seja x Ac Bc e fica provado que A Bc Ac Bc Agora se x Ac Bc 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 Bc 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 B Então x A B 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 provase 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 A o conjunto de todos os subconjuntos de A Por exemplo se A 1 2 então A 1 2 1 2 a Determine A quando A 1 1 b Prove que se um conjunto A tem n elementos então A tem 2n elementos c Se o número de subconjuntos binários formados de dois elementos de um conjunto dado é 15 quantos subconjuntos tem esse conjunto Resolução b Como nos ensina a análise combinatória o número de subconjuntos de A com um elemento é n choose 1 o número de subconjuntos com dois elementos é n choose 2 etc Como n choose 0 1 e n choose n 1 podem ser usados para contar o conjunto vazio e o próprio A então o total de subconjuntos de A é n choose 0 n choose 1 n choose 2 n choose n Mas essa soma como nos ensina também a combinatória é 2n 8 Para indicar o número de elementos de um conjunto finito X adotemos a notação nX Mostre então que se A e B são conjuntos finitos verificase a importante relação nA B nA nB nA B Resolução De fato se indicarmos por A e B respectivamente as partes de A e B formadas pelos elementos que não estão em A B então nA B nA nA B nB Mas nA nA nA B e nB nB nA B Substituindo estas duas últimas igualdades na anterior obtemos a igualdade proposta 9 Numa pesquisa a respeito da assinatura das revistas A e B foram entrevistadas 500 pessoas Verificouse que 20 delas assinavam a revista A 14 a revista B e 4 as duas revistas Quantas das pessoas entrevistadas não assinavam nenhuma das revistas 10 Se A B e C são conjuntos finitos mostre que nABC nA nB nC nA B nA C nB C nABC 11 Definese a diferença entre dois conjuntos A e B da seguinte maneira A B x x A e x B Ache a diferença A B nos seguintes casos a A ℚ e B ℝ b A ℝ e B ℚ c A x ℝ 2 x 5 e B x ℝ x 2 d A n n 1 2 3 e B 2n n 1 2 3 e A x ℝ 1 x 3 e B x ℝ x² 3x 4 0 12 Sejam A e B conjuntos finitos tais que nA B 40 nA B 10 e nA B 26 Determine nB A 13 Denominase diferença simétrica entre dois conjuntos A e B e denotase por A Δ B o seguinte conjunto A Δ B A B B A Isso posto a ache a diferença simétrica entre os pares de conjuntos do exercício 11 b mostre que qualquer que seja o conjunto A valem A Δ A e A Δ A c mostre que para quaisquer conjuntos A e B vale A Δ B B Δ A 14 Sejam A e B subconjuntos de um conjunto U Prove as seguintes propriedades a Se A B e A B U então B Aᶜ e A Bᶜ b Se A B então B Aᶜ e A Bᶜ c B A se e somente se Aᶜ Bᶜ 15 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 e 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 e portanto x A C e x B C ou seja x A B A C como queríamos provar 16 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õe 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 Mas há que registrar no século XVII 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 XIX aquele cuja obra teve peso e repercussão maiores foi G Boole 18151864 graças sobretudo a The laws of thought As Leis do Pensamento de 1854 Uma ligeira idéia 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 representavam 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 18351882 Assim sendo evidente que xy yx x y y x xy yx 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 idéia de que todo ser humano vivo ou é brasileiro ou não é brasileiro Não passou despercebida a 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 o 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 levariam 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 ℝ 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 42 Conectivos Na linguagem matemática a negação de proposições ou funções proposicionais e a combinação de proposições ou funções proposicionais através dos conectivos e conjunção ou disjunção se então condicional e se e somente se bicondicional são operações que têm interesse fundamental A respeito dos conectivos convém esclarecer o seguinte O ou usado na matemática não tem sentido exclusivo Assim numa proposição 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 proposições do tipo se p então q serão entendidas aqui como p e 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 p é falsa q é verdadeira p e q é falsa p ou q é verdadeira se p então q é falsa se q então p é verdadeira p se e somente se q é falsa por quê 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 q 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 R 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 e 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 formal rigorosa para esse fato requer um desenvolvimento do assunto fora dos objetivos deste texto e por isso nos 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 px indica uma função proposicional a negação de xpx é xpx Por exemplo a negação de Existe um número real x tal que x² 4 0 é Qualquer que seja o número real x vale x² 4 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 seria 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 é Existe 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 b a 2 1 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 2 b 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 2 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 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 contraposítiva da condicional dada Mostremos usando o raciocínio mencionado que a primeira dessas condicionais implica a segunda Para isso tomamos como hipótese p e q a 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 a proposição Se a soma de um número inteiro com 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 desse número 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 2t2 2t 4t2 2t 2t2 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 respectivos 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 se px então qx no caso px qx A c B px se e somente se qx no caso px qx A B px Ac px e qx A B px ou qx A B Como exemplo vejamos como se mostra a seguinte equivalência px e qx px ou qx Para isso indiquemos por A e B respectivamente os conjuntos verdade de px e 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 justificacão 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 x2 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 x2 4 b Nenhum triângulo retângulo é eqüilá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 z5 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 27 Enuncie as recíprocas e as contrapositas das seguintes proposições a Se dois números inteiros são ímpares então a soma deles é um número par b Se uma função real de variável real é contínua num ponto então ela é diferenciável nesse ponto c Se uma matriz quadrada é inversível então seu determinante é diferente de zero d Se o grau de um polinômio real é 2 então esse polinômio tem duas e apenas duas raízes complexas e Se dois planos são perpendiculares então toda reta de um deles é perpendicular ao outro 28 28 Classifique como verdadeiras ou falsas as recíprocas e as contrapositas das proposições do exercício 27 29 CAPÍTULO II INTRODUÇÃO À ARITMÉTICA DOS NÚMEROS INTEIROS 1 INTRODUÇÃO No conjunto dos números naturais que segundo o matemático Leopold Kronecker 18231891 foi criado por Deus o resto foi criado pelo homem complementava ele a diferença entre a e b só está definida se a b Mas há questões envolvendo a idéia de subtração de números naturais em que o minuendo é menor que o subtraendo por exemplo gastar mais do que se tem Para enfrentar essas questões foi preciso ampliar o conjunto dos números naturais com a adução de novos números os números negativos introduzidos a princípio para possibilitar uma resposta a uma subtração qualquer de dois elementos de N Esse passo gerou naturalmente a necessidade de estender as operações e a relação de ordem de N ao novo conjunto formado pelos números naturais e os números negativos Historicamente os inteiros negativos não foram os primeiros números a surgir dos naturais as frações positivas vieram antes Nem foram introduzidos de maneira bem estruturada e com bom acabamento matemático Muito pelo contrário Simplesmente surgiram e de maneira bastante informal em decorrência de questões práticas inicialmente na China provavelmente bem antes do século III aC e mais tarde na Índia em torno do século VI dC Mas na Europa ocidental do século XVII ainda havia matemáticos de alto gabarito que não aceitavam bem ou nem sequer aceitavam os números negativos A idéia 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 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 Z a idéia de menor e maior a partir das e coerentemente com as idéias correspondentes em N Feito isso podemos por fim nos referir a Z como o sistema ou campo dos números inteiros Obviamente essas considerações visam apenas dar uma idéia 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 Z 2 INDUÇÃO 21 Princípio do menor número inteiro Seja L um subconjunto não vazio de Z Dizemos que L é limitado inferiormente se existe um número a Z tal que a x qualquer que seja o elemento x L Ou seja a menor que ou igual a qualquer elemento de L Todo elemento a Z que cumple essa condição chamase limite inferior de L Obviamente se um inteiro a é limite inferior de L então todo inteiro menor que a também o é Um limite inferior de L que pertença a esse conjunto chamase mínimo de L Podese provar que um subconjunto não vazio de Z não pode possuir mais do que um mínimo 30 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 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 proposicionais definidas numa parte de Z 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 L x Z x a e px é falsa Se mostrarmos que L o princípio estará justificado Para isso vamos raciocinar por redução ao absurdo Suponhamos L Então uma vez que L é limitado inferiormente a é um limite inferior L possui mínimo l₀ Como pa é verdadeira é claro que l₀ a e então l₀ 1 a Por outro lado pl₀ 1 é verdadeira já que l₀ 1 está fora de L Então levando em conta a hipótese ii pl₀ 1 1 pl₀ é verdadeira Mas isso é absurdo pois l₀ está em L Como imagem para ilustrar o primeiro princípio de indução costumase usar o efeito dominó Suponhamos uma fileira infinita de pedrinhas de dominó Se a primeira pedra tomba para a frente e o fato de uma pedra tombar faz com que a da frente também tombe então todas as pedrinhas tombarão 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 31 Para n 1 o primeiro membro dessa igualdade é 1² 1 e o segundo 11 121 1 6 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 1 6 seja verdadeira Então para n r 1 o primeiro membro da igualdade a ser provada é 1² 2² r² r 1² rr 12r 16 r 1² rr 12r 1² 6r 1²6 r 12r² r 6r 66 r 12r² 7r 66 ao passo que o segundo é r 1r 22r 1 16 r 1r 22r 36 r 12r² 7r 66 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 provar 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 Exemplo 4 Provemos usando o segundo princípio de indução que n² 2n para todo inteiro n 2 Para n 2 o primeiro membro da desigualdade vale 2² 4 e o segundo 2 2 4 Portanto a função proposicional é verdadeira para n 2 Seja r 2 e suponhamos que se tenha k² 2k para todo inteiro k tal que 2 k r Façamos r k t do que segue r k t em que t 0 Daí r² k t² k² 2kt t² 2k 2kt t² 2k 2kt Mas como k 2 e t 0 então 2k 2 e portanto 2kt 2t De onde r² 2k 2t 2k t 2r 32 Exercícios 1 Demonstre por indução a 1 2 n nn 1 2 n 1 b 1 3 5 2n 1 n2 n 1 c 13 23 n3 1 2 n2 n 1 d 1 2 2 3 n n 1 nn 1n 2 3 n 1 e n2 n 1 n 2 2 Demonstre o segundo princípio de indução 3 DIVISIBILIDADE EM ℤ 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 ℤ 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 ℤ 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 b c₂ Se a 0b 0 então b 0a 0 Suponhamos pois a b 0 Como a a c₁ c₂ segue que c₁ c₂ 1 Mas c₁ e c₂ são positivos e por tanto 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₂ Daí bx axd₁ e cy ayd₂ Somando membro a membro essas igualdades obtemos bx cy axd₁ ayd₂ axd₁ yd₂ Então devido à definição dada a bx cy 35 portanto aq q₁ r₁ r Suponhamos que r r₁ digamos r r₁ Daí o segundo membro da última igualdade seria estritamente negativo e como a 0 então q q₁ também seria estritamente negativo e portanto q₁ q 0 ou seja q₁ q 1 Mas de aq q₁ r₁ r segue que r r₁ aq₁ q Levandose em conta que a 0 r₁ 0 e q₁ q 1 da última igualdade seguiria que r a o que é absurdo Da mesma forma provase que a desigualdade r₁ r também é impossível De onde r r₁ e consequentemente q q₁ O resultado acima conhecido como algoritmo euclidiano ou algoritmo da divisão em ℤ garante a possibilidade de uma divisão aproximada em ℤ 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 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 í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 a q 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 34 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 b 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 22n 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 221 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 22r 15r 1 9 q para algum inteiro q Segue daí que 22r 9q 15r 1 Logo hr 1 22r 1 15r 1 1 22r 22 15r 15 1 4 22r 15r 14 49q 15r 1 15r 14 94q 60r 15r 18 94q 95r 9 2 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 Di gase 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 a q para um conveniente inteiro q ii b está situado entre dois múltiplos consecutivos de a isto é existe um in teiro q tal que aq b aq 1 Daí 0 b aq a Então fazendo b qa r obtemos b aq r em que 0 r a Juntando as duas possibilidades podemos garantir o seguinte dados dois intei ros 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 in teiros q₁ e r₁ tais que b aq₁ r₁ com 0 r₁ a Então aq r aq₁ r₁ e 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 o 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 o mesmo que se fez com o número do exemplo Aliás o objetivo principal deste tópico é dar uma idéia 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 A fim de formar o numeral desejado esses símbolos eram adicionados convenientemente por exemplo o símbolo do 10 ao lado do símbolo do 1 formava o símbolo do 11 A partir do número 60 era sexagesimal de base 60 posicional mas incompleto uma vez que não utilizava sessenta símbolos mas tão somente os mesmos dois já referidos e num período final um símbolo para o zero mas mesmo assim só no interior de um numeral não no fim 1 10 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 36 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 alKhowarizmi um dos grandes sábios da cultura árabe o descreveu numa obra que data aproximadamente do ano 825 atribuindoo aos hindus Embora alKhowarizmi só tivesse explicitado 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 comumente de indoarábico deriva de o povo árabe ser o responsável por sua disseminação no Ocidente na esteira da expansão de seus domínios territoriais depois de o haver assimilado na Índia uma de suas primeiras conquistas Na verdade o que dá sustentação matemática ao uso de um sistema de numeração posicional é um teorema que enunciaremos a seguir para a base 10 mas que pode ser estendido como se perceberá para qualquer base naturalmente 2 Digase de passagem porém que os hindus não tinham um conhecimento da teoria envolvendo o sistema de numeração que criaram e que se deram esse grande passo no desenvolvimento da matemática foi unicamente com base no empirismo e na engenhosidade de seus matemáticos Qualquer que seja o número natural N é possível encontrar uma única sequência a₀ a₁ aᵣ de números naturais com 0 aᵢ 9 i 1 2 r tal que N a₀ a₁ 10 a₂ 10² aᵣ 10ʳ Esse resultado é uma decorrência do algoritmo euclidiano e vamos fazer um esboço de justificação supondo N 10 o caso N 10 é imediato De fato aplicando esse algoritmo para o número N como dividendo e 10 como divisor obtemos N 10 q r em que 0 r 9 1 Se 0 q 9 justificação encerrada pois a igualdade N r q 10 está de acordo com o enunciado uma vez que 0 q r 9 Se q 9 aplicase novamente o algoritmo agora com q como dividendo e 10 como divisor q 10 q₁ r₁ em que 0 r₁ 9 Desta última igualdade e de 1 segue que N 1010q₁ r₁ r r r₁ 10 q₁ 10² Se 0 q₁ 9 justificação encerrada pois 0 r r₁ q₁ 9 Caso contrário usase o algoritmo para q₁ e 10 Prosseguindo nesse raciocínio chegamos a uma 37 expressão do tipo da que foi dada para N no enunciado A questão da unicidade embora também essencial não será focalizada aqui O fato de um número N poder ser expresso univocamente por uma expressão polinomial N a₀ a₁ 10 a₂ 10² aᵣ 10ʳ permite que se represente esse número pela sequência aᵣ aᵣ₁ a₂ a₁ naturalmente subentendida a base dez Por exemplo o número N 5 10³ 3 10² 9 nove unidades três centenas e cinco milhares é representado por 5309 em que o 0 indica a ausência de dezenas Exercícios 3 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 2³ⁿ 1 n 0 b 8 3²ⁿ 7 n 0 c 11 2²ⁿ 1 3ⁿ² 1 n 1 d 7 3²ⁿ¹ 2ⁿ² n 1 e 17 3⁴ⁿ 12 2 4³ⁿ¹ 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 38 10 Na divisão euclidiana de 802 por a o quociente é 14 Determine os valores possíveis de a e do resto 11 É 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 12 Quantos números naturais entre 1 e 1000 são divisíveis por 9 Justifique a resposta 13 Seja m um inteiro cujo resto da divisão por 6 é 5 Mostre que o resto da divisão de m por 3 é 2 Resolução Por hipótese m 6q 5 Seja r o resto da divisão de m por 3 portanto m 3q r Então r 0 1 ou 2 Basta mostrar que as duas primeiras alternativas são impossíveis De fato se r 0 teríamos m 6q 5 3q Daí 3 q 2q 5 igualdade essa que teria como consequência o seguinte absurdo 3 5 Logo o resto não pode ser 0 Analogamente se demonstra que não pode ser 1 Portanto r 2 14 Se o resto na divisão euclidiana de um inteiro m por 8 é 5 qual é o resto da divisão de m por 4 15 Se m é um inteiro ímpar mostre que o resto da divisão de m² por 4 é 1 4 MÁXIMO DIVISOR COMUM 41 Consideremos a título de ilustração os inteiros 4 e 6 Os divisores de 4 são os elementos do conjunto D4 1 2 4 e os de 6 os do conjunto D6 1 2 3 6 Os divisores comuns são os elementos da interseção desses dois conjuntos D4 D6 1 2 O maior elemento dessa interseção ou seja o número 2 é o máximo divisor comum de 4 e 6 Essa forma de introduzir o máximo divisor comum embora muito interessante sob o ponto de vista didático principalmente nos níveis elementares não é a mais conveniente para os objetivos deste trabalho Por isso a definição que segue equivalente é óbvio à que foi esboçada acima em termos de conjuntos de divisores Definição 1 Sejam a e b dois números inteiros Um elemento d Z se diz máximo divisor comum de a e b se cumpre as seguintes condições i d 0 ii d a e d b iii Se d é um inteiro tal que d a e d b então d d ou seja todo divisor comum a a e b também é divisor de d A definição de máximo divisor comum pode ser estendida de maneira natural para n números inteiros a₁ a₂ aₙ n 2 Exemplo 8 É fácil comprovar que no caso em que a 4 e b 6 o número 2 é o único inteiro que passa pelo crivo das condições da definição dada No caso de iii por exemplo os divisores comuns a 4 e 6 são 1 2 todos divisores de 2 Seguem algumas propriedades imediatas do conceito de máximo divisor comum Se d e d₁ são máximos divisores comuns de a e b então d d₁ De fato devido à definição d d₁ e d₁ d Como se trata de números positivos isso só é possível se d d₁ Fica garantido então que um dado par de inteiros não pode ter mais de um máximo divisor comum O número 0 é o máximo divisor comum de a 0 e b 0 É só lembrar da definição Qualquer que seja a 0 a é o máximo divisor comum de a e 0 De fato Primeiro a é positivo Depois a divide 0 porque todo inteiro é divisor de 0 como já vimos e a divide a pois a a1 Finalmente se c divide a e c 0 então c a pois a a1 Se d é máximo divisor comum de a e b então d também é máximo divisor comum de a e b a e b e a e b Basta lembrar que todo divisor de x é divisor de x e viceversa 42 Obviamente a definição de máximo divisor comum de dois números inteiros não garante por si só sua existência A intuição nos diz que isso é verdade mas a rigor é preciso demonstrar que é o que faremos a seguir A demonstração que daremos se justifica principalmente porque garante a possibilidade de exprimir de maneira aritmética o máximo divisor comum de a e b como uma soma envolvendo esses elementos Proposição 1 Para quaisquer inteiros a e b existem inteiros x₀ e y₀ tais que d ax₀ by₀ é o máximo divisor comum de a e b Demonstração Levando em conta a última propriedade imediata relacionada acima podemos nos ater ao caso em a 0 e b 0 Consideremos o conjunto L ax by x y Z L possui elementos estritamente positivos por exemplo a b obtido ao se fazer x y 1 Seja d o menor entre todos os elementos estritamente positivos de L Portanto d ax₀ by₀ para convenientes elementos x₀ y₀ Z Mostremos que d é o máximo divisor comum de a e b De fato i Obviamente d 0 ii Apliquemos o algoritmo euclidiano a a e d o que é possível pois d 0 a dq r 0 r d Mas como já vimos d ax₀ by₀ e então a ax₀ by₀q r Daí por transposições algébricas convenientes r a1 qx₀ bqy₀ o que mostra que r é um elemento de L Então r não pode ser estritamente positivo pois é menor que d mínimo de L Logo r 0 e portanto a dq Ou seja d a De maneira análoga se demonstra que d b iii Se d a e d b então d d uma vez que d ax₀ by₀ Nesta altura já mostramos que todo par de inteiros tem um máximo divisor comum e que este é único A notação que usaremos para exprimir o máximo divisor comum d de a e b é d mdca b Vale salientar ainda que esse máximo divisor comum pode ser expresso por uma igualdade envolvendo a e b d ax₀ by₀ em que x₀ e y₀ são convenientes inteiros como vimos Na verdade sempre há uma infinidade de pares de inteiros x y Z para os quais d ax by Cada uma dessas relações será chamada de identidade de Bezout para a b e d 43 A proposição anterior tem muitas vantagens mas a desvantagem de não ser construtiva Entretanto esse problema pode ser superado e a chave para isso é o algoritmo euclidiano O método de divisões sucessivas para a determinação do máximo divisor comum de dois inteiros que explicaremos a seguir é o mesmo usado por Euclides há mais de dois milênios e ainda ensinado no ensino básico Para tanto precisaremos de dois lemas fáceis de provar Sem prejuízo da generalidade podemos nos ater a números inteiros estritamente positivos Lema 1 Se a b então mdca b a Demonstração Primeiro a é estritamente positivo por hipótese Depois a a e a b hipótese E se d a e d b é claro que d a Lema 2 Se a bq r então d mdca b se e somente se d mdcb r Demonstração Suponhamos d mdca b e provemos que d mdcb r Primeiro d 0 por hipótese Depois como d a e d b então d b e d a bq Ou seja d b e d r Por último se d b e d r então d b e d bq r ou seja d b e d a mas como d mdca b então d d A demonstração da recíproca segue a mesma linha de raciocínio Método das divisões sucessivas O objetivo é encontrar o máximo divisor comum de dois inteiros a e b que podemos supor estritamente positivos por meio de aplicações sucessivas do algoritmo euclidiano Primeiro aplicase para a e b depois para b e o primeiro resto parcial e assim por diante Ou seja a bq1 r1 0 r1 b b r1q2 r2 r2 r1 r1 r2q3 r3 r3 r2 É 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 lemas 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 2 Portanto mdc4112 1 Usualmente porém procedese da seguinte maneira 3 2 2 2 41 12 5 2 1 5 2 1 0 Exemplo 10 O processo das divisões sucessivas também serve para determinar os inteiros x0 y0 tais que ax0 by0 d em que d mdca b Vamos ilustrar o procedimento para a 41 e b 12 Para isso aproveitaremos as divisões sucessivas já feitas em 2 Começaremos pela penúltima igualdade aquela em que o máximo divisor comum figura como resto pondo 1 em função de 5 e 2 por meio de transposições algébricas Na igualdade obtida substituímos 2 em função de 12 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 ℤ 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 ℤ 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 e 1 De onde o máximo divisor comum de a e b é 1 Exemplo 11 Mostremos que dois números inteiros consecutivos são primos entre si Sejam n e n 1 os números Se a n e a n 1 então a n 1 n ou seja a 1 Logo a 1 quer dizer os únicos divisores comuns a n e n 1 são 1 e 1 De onde mdcn n 1 1 Outra maneira de chegar a essa conclusão é observar que vale a seguinte identidade de Bezout para os números considerados n 1 1 n1 1 Corolário Se a e b são inteiros não simultaneamente nulos e se d mdca b então mdcad bd 1 Demonstração É só trabalhar com uma identidade de Bezout para a e b Como d mdca b então existem inteiros x0 e y0 tais que ax0 by0 d Daí dividindo ambos os membros por d adx0 bdy0 1 Então por causa da proposição ad e bd são primos entre si Proposição 3 Se a e b são inteiros primos entre si e a bc então a c Demonstração Devido à proposição anterior ax0 by0 1 para convenientes inteiros x0 e y0 Multiplicandose os dois membros dessa igualdade por c acx0 bcy0 c Como a divide a então a divide acx0 e como a divide bc por hipótese então divide bcy0 Logo a divide a soma acx0 bcy0 Ou seja a divide c como queríamos provar 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 bcy0 Logo 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 de c de a e b e mostre que ele também é divisor de a e a b 22 Demonstre que se a cb c e mdcab 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 ba 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 e 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 ℤ 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í mdcpa 1 e portanto existem x₀y₀ ℤ tais que p x₀ a y₀ 1 Multiplicandose ambos os membros dessa igualdade por b obtémse p b x₀ aby₀ b Como p p e p ab hipótese então ppb x₀ 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ₙ n1 então p divide um dos fatores aᵢ Lema 4 Seja a 0 1 um inteiro Então o conjunto L x ℤ x 1 e x é divisor de a possui um mínimo e esse mínimo é um número primo Demonstração O conjunto L não é vazio pois a e a são divisores de a e um desses números é necessariamente maior que 1 Então pelo princípio do menor 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 S 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 que 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₁ ℤ Como a e p₁ são estritamente positivos o mesmo acontece com q₁ que além é 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 com q₂ e assim por diante Como a q₁ q₂ 1 em alguma etapa desse procedimento se terá qᵣ 1 e então a p₁ p₂ pᵣ como queríamos provar ii Também aqui não nos preocuparemos com o rigor formal Suponhamos p₁ p₂ pᵣ q₁ q₂ qₛ nas condições enunciadas Então p₁ por exemplo divide o segundo membro e portanto devido ao lema 3 divide um dos fatores Digamos que p₁ q₁ Como q₁ é primo e seu único divisor primo positivo é ele mesmo então p₁ q₁ Então podese cancelar p₁ na igualdade da hipótese obtendose p₂ p₃ pᵣ q₂ q₃ qₛ 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 Convém frisar que a demonstração da possibilidade da decomposição é construtiva como se pôde observar Mais a idéia dessa demonstração é usada no algoritmo prático com o qual normalmente se aprende na escola a decomposição em fatores primos De fato suponhamos que se queira decompor em fatores primos o número 60 O algoritmo usado começa como ocorre na demonstração considerandose o menor divisor primo de 60 que no caso é 2 Depois se considera também como na demonstração o menor divisor primo do quociente que no caso novamente é 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 conveniente ampliar a idéia de decomposição canônica para que em todas figurem os mesmo 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 3 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 supondose 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 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 22 30 50 7 e 300 22 3 52 70 então mdc28 300 22 30 50 70 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β1 p2β2 pmβm em que 0 βj αj j 0 1 2 m Como para cada expoente na decomposição de b há αj 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 22 3 52 é 3 2 3 18 Exercícios 24 Decomponha em fatores primos 234 456 e 780 25 Ache o máximo divisor comum dos seguintes pares de números através da decomposição desses números em fatores primos a 234 e 456 b 456 e 780 c 200 e 480 26 Determine todos os números primos que podem ser expressos na forma n2 1 Sugestão Suponha p n2 1 um número primo e fator e o segundo membro dessa igualdade 27 Se n é um inteiro e n3 1 é primo prove que n 2 ou n 1 28 Em 1742 o russo Christian Goldbach formulou a seguinte conjectura conhecida como conjectura de Goldbach Todo inteiro par maior que 2 é igual à soma de 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 n2 n 17 é um número composto 30 Se n2 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 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 p1 p2 pn 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ê Segue então que p 1 por quê Esse absurdo por quê garante a infinitude do conjunto dos primos 6 EQUAÇÕES DIOFANTINAS LINEARES 61 Diofanto de Alexandria viveu provavelmente no século III dC De sua produção matemática conhecemse apenas os fragmentos de uma obra que trata de números poligonais e a extremamente original e criativa Arithmetica graças à qual ele é às vezes considerado o pai da álgebra Da Arithmetica restam seis livros em grego e quatro em árabe estes últimos descobertos recentemente segundo o prefácio da obra o número total de livros seria treze Tratase de uma coletânea de problemas para resolução dos quais Diofanto usava em vez de métodos gerais engenhosos artifícios algébricos Com isso a obra se distingue radicalmente da matemática grega clássica de Euclides por exemplo cujas raízes estavam fincadas na geometria e no método dedutivo 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 4 em que a e b são inteiros não nulos Uma solução de 4 é nesse contexto um par x0 y0 de inteiros tais que a sentença ax0 by0 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 x0 y0 é uma solução vale a igualdade ax0 by0 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 x0 y0 Z tais que ax0 by0 d Mas por hipótese d c e portanto c dq para algum inteiro q De onde c dq ax0 by0 q ax0 q by0 q o que mostra que o par x0 q y0 q é solução da equação considerada É importante observar que se x0 y0 é uma solução de ax by c com a b 0 então x0 y0 x0 y0 e x0 y0 são soluções respectivamente de a x by c ax b y c e a x b y 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 x0 y0 6 5 e portanto o par 2 6 2 5 12 10 é uma solução da equação dada Conseqüentemente 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 x0 y0 então tem infinitas soluções e o conjunto destas é S x0 bdt y0 adt t Z em que d mdca b Demonstração Mostremos primeiro que todo par x0 bdt y0 adt é solução da equação considerada De fato ax0 bdt by0 adt ax0 by0 ab badt ax0 by0 c pois x0 y0 é solução por hipótese De outra parte seja x y uma solução genérica da equação Então ax by c ax0 by0 Daí ax x0 by0 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 x0 dsy0 y e portanto rx x0 sy0 y Essa igualdade mostra que r divide sy0 y Mas como r e s são primos entre si então r divide y0 y proposição 3 Logo y0 y rt para algum t Z Levandose em conta que r ad então y y0 adt Observandose agora que em conseqüência rx x0 sy0 y srt obtémse x x0 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 É i importante lembrar que se x0 y0 é uma solução de 43x 5y 1 então 250x0 250y0 é 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 su c essivas 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 5 8 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 c 18x 20y 8 b 5x 2y 2 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 bilheteria 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 Mahaviracarya 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 1520 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 sexta sábado domingo segunda terça quarta quinta 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Nossa questão agora se resume em saber em que coluna da tabela se encontra o número 1520 Para isso basta observar que dois números da seqüê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 encabeçada 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 é côngruo a b módulo m se m a b isto é se a b mq para um conveniente inteiro q Para indicar que a é côngruo 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 quaisquer de uma mesma coluna são cõngruos módulo 7 Para indicar que a b não é divisível por m ou seja que a não é cõngruo 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 e portanto a c mod m C4 Se a b mod m e 0 b 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 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 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 12 se m é ímpar 0 1 2 m2 1 m2 se m é par Para mostrar por exemplo que a congruência x² 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 x² 0 1 4 9 16 mod 8 Mas 9 1 mod 8 e 16 0 mod 8 Portanto x² 0 1 4 mod 8 De onde x² 1 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 Daí 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 C8 Se a b mod m então ac bc mod m Por hipótese a b mq Daí multiplicandose ambos os membros dessa igualdade por c ac bc mqc De onde ac bc mod m C9 Se a b mod m e c d mod m então ac bd mod m Como a b mod m então devido à propriedade anterior ac bc mod m Analogamente de c d mod m segue que bc bd mod m Então devido à transitividade ac bc mod m Essa propriedade pode ser generalizada 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 ar br 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 a² 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 a² 1 9 25 ou 49 mod 8 Mas 9 1 mod 8 25 1 mod 8 e 49 1 mod 8 Daí a² 1 1 1 ou 1 mod 8 Ou seja a² 1 mod 8 qualquer que seja o inteiro ímpar a e portanto devido à propriedade C4 o resto da divisão de a² 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 Daí 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 é cõngruo 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 a₀ a₁ 10 a₂ 10² aᵣ 10ʳ 5 em que os coeficientes das potências de 10 estão sujeitos à seguinte limitação 0 a₀ a₁ a₂ aᵣ 9 Isso dá origem à seguinte notação seqüencial para indicar o número aᵣaₙ 1a₂a₁a₀ A idéia 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 a₁ a₂ aᵣ à qual o polinômio de 5 é cõngruo módulo m e depois usar a propriedade C₅ Vejamos alguns casos i Critério de divisibilidade por 2 Como 10ᵗ 0 mod 2 para todo t 1 então N a₀ mod 2 Logo N e a₀ têm o mesmo resto na divisão por 2 e em conseqüência N é divisível por 2 se e somente se a₀ é divisível por 2 Ou seja se a₀ é par ii Critério de divisibilidade por 3 Como 10 1 mod 3 então 10² 1 mod 3 10³ 1 mod 3 10ʳ 1 mod 3 Então a₁ 10 a₁ mod 3 a₂ 10² a₂ mod 3 a₃ 10³ a₃ mod 3 aᵣ 10ʳ aᵣ mod 3 Logo devido às propriedades C₁ e C₇ N a₀ a₁ 10 a₂ 10² aᵣ 10ʳ a₀ a₁ a₂ aᵣ mod 3 Portanto N e a₀ a₁ a₂ aᵣ têm o mesmo resto na divisão por 3 De onde N é divisível por 3 se e somente se a₀ a₁ a₂ aᵣ é 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 10² 0 mod 4 10³ 0 mod 4 10ʳ 0 mod 4 Portanto a₂10² 0 mod 4 a₃ 10³ 0 mod 4 aᵣ 10ʳ 0 mod 4 De onde N a₀ 10a₁ mod 4 Mas a₀ 10a₁ a₁a₀ é o número formado pelos dois últimos algarismos de N Então N e a₁a₀ têm o mesmo resto na divisão por 4 e em particular N é divisível por 4 se e somente se a₁a₀ o é 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 é 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 que 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 conseqüê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 a₁ mod m₁ x a₂ mod m₂ x aᵣ mod mᵣ em que mdcmᵢ mⱼ 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 do final 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 espécime 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 m₁ m₂ mᵣ números inteiros maiores que 1 e tais que mdcmᵢ mⱼ 1 sempre que i j Assim sendo se a₁ a₂ aₙ são números inteiros arbitrários então o sistema de congruências x a₁ mod m₁ x a₂ mod m₂ x aᵣ mod mᵣ é possível Ademais duas soluções quaisquer do sistema são cõngruas módulo m₁m₂mᵣ