Fundamentos de Algebra I - UFMG - Livro

fundamentos de álgebra I fundamentos de álgebra I2012indd 1 26012012 180323 Fundamentos de Álgebra I Universidade Federal de Minas Gerais Reitor Clélio Campolina Diniz ViceReitora Rocksane de Carvalho Norton Próreitoria de Graduação PróReitora Antônia Vitória Soares Aranha PróReitor Adjunto André Luiz dos Santos Cabral Diretor do CAED Fernando Fidalgo Coordenador da UABUFMG Wagner José Corradi Barbosa Coordenador Adjunto UABUFMG Hormindo Pereira de Souza Júnior editora UFMG Diretor Wander Melo Miranda ViceDiretor Roberto Alexandre do Carmo Said Conselho editorial Wander Melo Miranda presidente Flavio de Lemos Carsalade Heloisa Maria Murgel Starling Márcio Gomes Soares Maria das Graças Santa Bárbara Maria Helena Damasceno e Silva Megale Paulo Sérgio Lacerda Beirão Roberto Alexandre do Carmo Said fundamentos de álgebra I2012indd 2 26012012 180323 AnA CristinA VieirA fundamentos de álgebra I Belo Horizonte editorA UFMG 2011 fundamentos de álgebra I2012indd 3 26012012 180323 ASSISTÊNCIA EDITORIAL Eliane Sousa e Euclídia Macedo EDITORAÇÃO DE TEXTOS Maria do Carmo Leite Ribeiro REVISÃO E NORMALIZAÇÃO Danivia Wolff REVISÃO DE PROVAS Danivia Wolff PROJETO GRÁFICO E CAPA Eduardo Ferreira FORMATAÇÃO Sérgio Luz PRODUÇÃO GRÁFICA Warren Marilac IMPRESSÃO Imprensa Universitária da UFMG editora UFMG Av Antônio Carlos 6627 Ala direita da Biblioteca Central Térreo Campus Pampulha 31270901 Belo Horizonte MG Tel 55 31 34094650 Fax 55 31 34094768 wwweditoraufmgbr editoraufmgbr 2011 Ana Cristina Vieira 2011 Editora UFMG 2012 REIMPRESSÃO Este livro ou parte dele não pode ser reproduzido por qualquer meio sem autorização escrita do Editor Vieira Ana Cristina Fundamentos de Álgebra I Ana Cristina Vieira Belo Horizonte Editora UFMG 2011 75 p il Educação a Distância ISBN 9788570418425 1 Álgebra 2 Matemática I Título II Série CDD 512 CDU 512 V657f Elaborada pela DITTI Setor de Tratamento da Informação Biblioteca Universitária da UFMG PrÓreitoria de GradUaÇÃo Av Antônio Carlos 6627 Reitoria 6º andar Campus Pampulha 31270901 Belo Horizonte MG Tel 55 31 34094054 Fax 55 31 34094060 wwwufmgbr infoprogradufmgbr educacaoadistanciaufmgbr Este livro recebeu apoio financeiro da Secretaria de Educação a Distância do MEC fundamentos de álgebra I2012indd 4 26012012 180324 A Educação a Distância EAD é uma modalidade de ensino que busca promover inserção social pela disseminação de meios e processos de democratização do conhecimento A meta é elevar os índices de esco laridade e oferecer uma educação de qualidade disponibilizando uma formação inicial eou continuada em particular a professores que não tiveram acesso a esse ensino Não se pode ignorar que é fundamental haver sempre plena conexão entre educação e aprendizagem A modalidade a distância é um tipo de aprendizagem que em especial na Universidade Federal de Minas Gerais UFMG já está concretizada como um ensino de qualidade Hoje a aprendizagem tornouse para todos os profissionais dessa universidade envolvidos no programa de Educação a Distância sinô nimo de esforço e dedicação de cada um Este livro visa desenvolver no curso a distância os mesmos conheci mentos proporcionados num curso presencial Os alunos estudarão o material nele contido e muitos outros que lhe serão sugeridos em bibliografia complementar É importante terem em vista que essas leituras são de extrema importância para com muita dedicação avan çarem em seus estudos Cada volume da coletânea está dividido em aulas e em cada uma delas tratase de determinado tema que é explorado de diferentes formas textos apresentações reflexões e indagações teóricas experimenta ções ou orientações para atividades a serem realizadas pelos alunos Os objetivos propostos em cada uma das aulas indicam as competências e habilidades que os alunos ao final da disciplina devem ter adquirido Os exercícios indicados ao final de cada aula possibilitam aos alunos avaliarem sua aprendizagem e seu progresso em cada passo do curso Esperase que assim eles se tornem autônomos responsáveis críticos e decisivos capazes sobretudo de desenvolver a própria capacidade intelectual Os alunos não podem se esquecer de que toda a equipe de professores e tutores responsáveis pelo curso estará a distância ou presente nos polos pronta a ajudálos Além disso o estudo em grupo a discussão e a troca de conhecimentos com os colegas serão nessa modalidade de ensino de grande importância ao longo do curso Agradeço aos autores e à equipe de produção pela competência pelo empenho e pelo tempo dedicado à preparação deste e dos demais livros dos cursos de EAD Espero que cada um deles possa ser valioso para os alunos pois tenho certeza de que vão contribuir muito para o sucesso profissional de todos eles em seus respectivos cursos na área da educação em geral do país Ione Maria Ferreira de Oliveira Coordenadora do Sistema Universidade Aberta do Brasil UABUFMG fundamentos de álgebra I2012indd 5 26012012 180324 fundamentos de álgebra I2012indd 6 26012012 180324 sumário Introdução 9 Aula 1 Princípio de Indução Matemática 11 Aula 2 PIM e PBO 21 Aula 3 Lema de Euclides 29 Aula 4 Divisibilidade 35 Aula 5 Números primos 41 Aula 6 Teorema Fundamental da Aritmética 49 Aula 7 Máximo divisor comum 53 Aula 8 Equações diofantinas lineares e MMC 63 Referências 73 Sobre a autora 75 fundamentos de álgebra I2012indd 7 26012012 180324 fundamentos de álgebra I2012indd 8 26012012 180324 Introdução Por Teoria dos Números entendemos a área da Matemática que se destina ao estudo de propriedades dos números inteiros Euclides de Alexandria 360 aC 295 aC criador da famosa geometria eucli diana foi o autor do mais antigo texto matemático conhecido como Os elementos dividido em um total de treze volumes cada um deles denominado Livro Os Livros VII VIII e IX de Os elementos são sobre Teoria dos Números Neste texto apresentamos uma introdução à Teoria dos Números escrita em linguagem acessível a alunos a partir do segundo ano de graduação Demonstramos resultados básicos que são muito impor tantes em diversos ramos da matemática incluindo muitos dos teoremas clássicos provados por Euclides Vários resultados importantes são precedidos e seguidos de exem plos com o objetivo de ilustrar as ideias utilizadas nas demonstra ções e motivar o leitor para a importância delas Além dos problemas propostos há um significativo número de problemas resolvidos Na Aula 1 apresentaremos o Princípio de Indução Matemática PIM em sua primeira forma esclarecendo ao aluno a necessidade das demonstrações de afirmações a respeito de números naturais feitas a partir da indução após uma observação Faremos isso cautelosamente já que o PIM é um dos princípios fundamentais na construção dos números naturais A segunda forma do PIM será apresentada na Aula 2 onde também apresentaremos o Princípio de Boa Ordem PBO Estes princípios serão ferramentas valiosíssimas em demonstrações nas aulas poste riores de resultados que envolvem números inteiros Ainda nessa aula introduziremos a importante sequência dos números de Fibonacci cujas propriedades são interessantes e podem ser provadas com o uso do PIM e do PBO Na Aula 3 vamos demonstrar o Lema de Euclides tanto para números naturais quanto para inteiros Este Lema é o carrochefe da divisão de números inteiros garantindo a existência do resto e do quociente em qualquer situação As propriedades elementares da divisibilidade no conjunto dos números inteiros serão estudadas na Aula 4 onde também vamos estabelecer alguns critérios de divisibilidade A Aula 5 é destinada ao estudo de números inteiros particulares os números primos Daremos a definição de primos e compostos e desta caremos a importância dos números primos na vida cotidiana Vamos fundamentos de álgebra I2012indd 9 26012012 180324 10 Fundamentos de Álgebra I ver resultados que dizem respeito à sua distribuição entre os naturais e faremos a demonstração da infinitude dos primos Comentaremos alguns problemas em aberto sobre primos que são curiosamente estu dados até hoje Daremos continuidade ao estudo de números primos na Aula 6 onde demonstraremos o Teorema Fundamental da Aritmética que garante que todos os naturais a partir de 2 podem ser escritos como um produto de números primos A unicidade desta fatoração implica em conse quências interessantes na Teoria dos Números conforme veremos Na Aula 7 nos ocuparemos do estudo de divisores comuns de dois inteiros sendo destacado o máximo divisor comum MDC Veremos quais são as alternativas para calculálo e estudaremos suas principais propriedades Na Aula 8 introduziremos as chamadas equações diofantinas lineares que se destinam a resolver problemas que tenham como soluções pares de números inteiros e veremos que a existência de tais soluções está relacionada com propriedades do MDC Finalizaremos estudando o mínimo múltiplo comum MMC de dois inteiros e sua relação com o MDC Nas referências no fim deste texto destacamos alguns livros recentes em Teoria de Números que podem servir como bibliografia comple mentar para os estudantes Lá também destacamos a página da web onde foram consultadas as informações históricas sobre os matemá ticos citados no texto fundam2Cpia 201061 1350 page 5 5 Capıtulo 1 Aula 1 Princıpio de Inducao Matematica Objetivos Vamos apresentar um dos postulados que caracterizam os numeros naturais o Princıpio de Inducao Matematica Em seguida veremos como utilizalo para demonstrar afirmacoes a respeito destes numeros Na matematica tal como numa ciˆencia fısica podemos utilizar a observacao para descobrir leis gerais Mas ha uma diferenca marcante Nas ciˆencias fısicas nem sempre ha uma autoridade superior a observacao enquanto que na matematica essa autoridade existe a prova rigorosa A prova ou demonstracao de um resultado e feita de maneira geral utilizandose outros resultados previamente estabelecidos mas existem sen tencas que nao sao provadas ou demonstradas e sao consideradas como obvias ou como um consenso inicial necessario para a construcao ou aceitacao de uma teoria Nesse contexto usaremos axioma postulado e princıpio como sinˆonimos de uma hipotese inicial que nao sera demonstrada a partir da qual outros enunciados sao logicamente derivados Aqui vamos considerar o conjunto dos numeros naturais como o conjunto N 0 1 2 O Princıpio de Inducao Matematica que e um postulado baseado no ultimo axioma de Giuseppe Peano 1858 1932 praticamente define este conjunto Foi August de Morgan que em 1883 descreveu o princıpio cuidadosamente e deu a ele o nome de Inducao Matematica Vamos entender como e este princıpio e ver como utilizalo na demonstracao de afirmacoes a respeito de numeros naturais Problema 11 O que e inducao e o que e inducao matematica 5 fundamentos de álgebra I2012indd 10 26012012 180324 AULA 1 Princípio de Indução matemática objetIvos Vamos apresentar um dos postulados que caracterizam os números naturais o Princípio de Indução Matemática Em seguida veremos como utilizálo para demonstrar afirmações a respeito desses números fundam2Cpia 201061 1350 page 5 5 Capıtulo 1 Aula 1 Princıpio de Inducao Matematica Objetivos Vamos apresentar um dos postulados que caracterizam os numeros naturais o Princıpio de Inducao Matematica Em seguida veremos como utilizalo para demonstrar afirmacoes a respeito destes numeros Na matematica tal como numa ciˆencia fısica podemos utilizar a observacao para descobrir leis gerais Mas ha uma diferenca marcante Nas ciˆencias fısicas nem sempre ha uma autoridade superior a observacao enquanto que na matematica essa autoridade existe a prova rigorosa A prova ou demonstracao de um resultado e feita de maneira geral utilizandose outros resultados previamente estabelecidos mas existem sen tencas que nao sao provadas ou demonstradas e sao consideradas como obvias ou como um consenso inicial necessario para a construcao ou aceitacao de uma teoria Nesse contexto usaremos axioma postulado e princıpio como sinˆonimos de uma hipotese inicial que nao sera demonstrada a partir da qual outros enunciados sao logicamente derivados Aqui vamos considerar o conjunto dos numeros naturais como o conjunto N 0 1 2 O Princıpio de Inducao Matematica que e um postulado baseado no ultimo axioma de Giuseppe Peano 1858 1932 praticamente define este conjunto Foi August de Morgan que em 1883 descreveu o princıpio cuidadosamente e deu a ele o nome de Inducao Matematica Vamos entender como e este princıpio e ver como utilizalo na demonstracao de afirmacoes a respeito de numeros naturais Problema 11 O que e inducao e o que e inducao matematica 5 fundamentos de álgebra I2012indd 11 26012012 180325 12 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 6 6 6 CAPITULO 1 AULA 1 PRINCIPIO DE INDUC AO MATEM ATICA Solucao A inducao ou deducao e o processo de descoberta de leis gerais pela observacao e combinacao de exemplos particulares E usada em todas as ciˆencias mesmo na matematica A inducao matematica e usada especi ficamente na matematica para provar teoremas de um certo tipo Vamos ilustrar ambos os metodos por intermedio do mesmo exemplo Iniciamos observando que 1 8 9 e reconhecendo os cubos e os quadrados podemos dar ao fato observado a forma mais interessante 13 23 32 Como e que isto acontece Sera que com frequˆencia uma tal soma de cubos sucessivos a partir do numero 1 e um quadrado De fato 13 23 33 1 8 27 36 62 Em geral sera que e verdade que 13 23 33 n3 e um quadrado para todo natural n Fomos levados a esta pergunta pelos exemplos particulares n 2 3 e po demos investigar outros casos especiais Os casos n 4 e n 5 sao os proximos Acrescentemos para garantir um passo inicial o caso n 1 Arranjando elegantemente todos estes casos obtemos 13 12 13 23 32 13 23 33 62 13 23 33 43 102 13 23 33 43 53 152 11 E difıcil acreditar que todas estas somas de cubos consecutivos sejam qua drados por mero acaso De fato uma pessoa que nao esteja muito preo cupada com formalismos teria poucas duvidas de que a lei geral sugerida pelos casos especiais ate entao observados nao seja correta e a consideraria provada por inducao O matematico expressase com maior reserva pois sente a necessidade de uma demonstracao Ele diria que o seguinte teorema e fortemente sugerido por inducao A soma dos primeiros n cubos e um quadrado Vamos obsevar as bases dos quadrados que aparecem em 11 1 3 6 10 15 Podemos ver aqui uma notavel regularidade nestas bases 1 1 3 12 6 123 10 1234 15 12345 Se esta regularidade for geral e o contrario e difıcil de acreditar a conjec tura que fizemos toma uma forma mais precisa Para n 1 2 3 temos 13 23 33 n3 1 2 3 n2 fundam2Cpia 201061 1350 page 7 7 7 A lei que acabamos de enunciar foi encontrada por inducao A inducao tenta encontrar regularidade e coerˆencia para alem das observacoes Mas conforme ja foi dito e necessario uma demonstracao formal para que um resultado em matematica seja aceito como verdadeiro Podemos fazer uma pequena simplificacao no enunciado da nossa conjectura pois e facil de verificar que 1 2 3 n nn 1 2 para todo n 1 2 12 Para ver isto tomamos um retˆangulo com lados n e n 1 e fazemos o seguinte Dividimos o retˆangulo em nn 1 quadrados de lados iguais a 1 como na Figura 1a que mostra o caso n 4 e temos 20 quadrados de lado 1 Preenchemos os quadrados com da seguinte maneira o primeiro qua drado da primeira coluna os dois primeiros quadrados da segunda coluna os trˆes primeiros quadrados da terceira coluna e assim por diante ate pre enchermos os n primeiros quadrados da nesima coluna como na Figura 1b para n 4 Notamos que a area da regiao preenchida e igual a area da regiao nao preenchida e e dada por 1 2 n para n 4 este valor e 1 2 3 4 ver Figura 1b Figura 1a Figura 1b Ora a area total do retˆangulo e nn 1 da qual a area preenchida e metade Isto prova a formula 12 acima Assim podemos transformar o resultado que encontramos por inducao em 13 23 33 n3 nn 1 2 2 para todo n 1 2 13 Muito provavelmente a formula e geralmente verdadeira isto e verdadeira para todos os valores de n Problema 12 Sera que a afirmacao continua verdadeira quando passamos de algum valor de n para o valor seguinte n 1 Solucao Nao sabemos ainda se 13 e verdadeira para um n k arbitrario mas se soubessemos que era verdade terıamos 13 23 33 k3 kk 1 2 2 e poderıamos adicionar k 13 aos membros da equacao obtendo 13 23 33 k3 k 13 kk1 2 2 k 13 k 12 k24k1 4 k1k2 2 2 fundamentos de álgebra I2012indd 12 26012012 180325 13 aula 1 fundam2Cpia 201061 1350 page 6 6 6 CAPITULO 1 AULA 1 PRINCIPIO DE INDUC AO MATEM ATICA Solucao A inducao ou deducao e o processo de descoberta de leis gerais pela observacao e combinacao de exemplos particulares E usada em todas as ciˆencias mesmo na matematica A inducao matematica e usada especi ficamente na matematica para provar teoremas de um certo tipo Vamos ilustrar ambos os metodos por intermedio do mesmo exemplo Iniciamos observando que 1 8 9 e reconhecendo os cubos e os quadrados podemos dar ao fato observado a forma mais interessante 13 23 32 Como e que isto acontece Sera que com frequˆencia uma tal soma de cubos sucessivos a partir do numero 1 e um quadrado De fato 13 23 33 1 8 27 36 62 Em geral sera que e verdade que 13 23 33 n3 e um quadrado para todo natural n Fomos levados a esta pergunta pelos exemplos particulares n 2 3 e po demos investigar outros casos especiais Os casos n 4 e n 5 sao os proximos Acrescentemos para garantir um passo inicial o caso n 1 Arranjando elegantemente todos estes casos obtemos 13 12 13 23 32 13 23 33 62 13 23 33 43 102 13 23 33 43 53 152 11 E difıcil acreditar que todas estas somas de cubos consecutivos sejam qua drados por mero acaso De fato uma pessoa que nao esteja muito preo cupada com formalismos teria poucas duvidas de que a lei geral sugerida pelos casos especiais ate entao observados nao seja correta e a consideraria provada por inducao O matematico expressase com maior reserva pois sente a necessidade de uma demonstracao Ele diria que o seguinte teorema e fortemente sugerido por inducao A soma dos primeiros n cubos e um quadrado Vamos obsevar as bases dos quadrados que aparecem em 11 1 3 6 10 15 Podemos ver aqui uma notavel regularidade nestas bases 1 1 3 12 6 123 10 1234 15 12345 Se esta regularidade for geral e o contrario e difıcil de acreditar a conjec tura que fizemos toma uma forma mais precisa Para n 1 2 3 temos 13 23 33 n3 1 2 3 n2 fundam2Cpia 201061 1350 page 7 7 7 A lei que acabamos de enunciar foi encontrada por inducao A inducao tenta encontrar regularidade e coerˆencia para alem das observacoes Mas conforme ja foi dito e necessario uma demonstracao formal para que um resultado em matematica seja aceito como verdadeiro Podemos fazer uma pequena simplificacao no enunciado da nossa conjectura pois e facil de verificar que 1 2 3 n nn 1 2 para todo n 1 2 12 Para ver isto tomamos um retˆangulo com lados n e n 1 e fazemos o seguinte Dividimos o retˆangulo em nn 1 quadrados de lados iguais a 1 como na Figura 1a que mostra o caso n 4 e temos 20 quadrados de lado 1 Preenchemos os quadrados com da seguinte maneira o primeiro qua drado da primeira coluna os dois primeiros quadrados da segunda coluna os trˆes primeiros quadrados da terceira coluna e assim por diante ate pre enchermos os n primeiros quadrados da nesima coluna como na Figura 1b para n 4 Notamos que a area da regiao preenchida e igual a area da regiao nao preenchida e e dada por 1 2 n para n 4 este valor e 1 2 3 4 ver Figura 1b Figura 1a Figura 1b Ora a area total do retˆangulo e nn 1 da qual a area preenchida e metade Isto prova a formula 12 acima Assim podemos transformar o resultado que encontramos por inducao em 13 23 33 n3 nn 1 2 2 para todo n 1 2 13 Muito provavelmente a formula e geralmente verdadeira isto e verdadeira para todos os valores de n Problema 12 Sera que a afirmacao continua verdadeira quando passamos de algum valor de n para o valor seguinte n 1 Solucao Nao sabemos ainda se 13 e verdadeira para um n k arbitrario mas se soubessemos que era verdade terıamos 13 23 33 k3 kk 1 2 2 e poderıamos adicionar k 13 aos membros da equacao obtendo 13 23 33 k3 k 13 kk1 2 2 k 13 k 12 k24k1 4 k1k2 2 2 fundamentos de álgebra I2012indd 13 26012012 180325 14 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 8 8 8 CAPITULO 1 AULA 1 PRINCIPIO DE INDUC AO MATEM ATICA Por virtude do que acabamos de dizer a conjectura ao ser verdadeira para n 6 tem tambem de ser verdadeira para n 7 ao ser verdadeira para n 7 e verdadeira para n 8 e assim sucessivamente Ou seja o resultado esta provado em geral A prova precedente pode servir como padrao em muitos casos semelhantes Se tivermos uma afirmacao sobre numeros naturais que afirmamos ser ver dadeira para todo natural n a partir de um natural a podemos ser capazes de usar a experiˆencia do exemplo anterior para concluir que a assercao sera verdadeira se for provada para n a e se puder ser provada para k 1 desde que seja admitida verdadeira para n k Este processo e usado tantas vezes que merece um nome Podıamos chamar lhe prova de n para n1 mas o termo tecnico aceito e inducao matema tica Em muitos casos como no discutido acima em detalhes a fonte e a inducao ou seja a assercao e encontrada experimentalmente Deste modo a prova surge como um complemento matematico a inducao o que explica o nome Problema 13 Como fazer uma demonstracao por inducao Solucao A demonstracao de uma afirmacao a respeito de numeros naturais baseada no Princıpio de Inducao Matematica PIM e chamada uma prova por inducao Ela consiste de duas etapas etapa 1 a demonstracao de que a afirmacao vale para um numero natural inicial a esta etapa e mais comumente chamada de etapa inicial etapa 2 a demonstracao de que a afirmacao vale para o sucessor k 1 de um numero natural arbitrario k a depois de termos suposto que a afirmacao vale para k Esta suposicao e chamada hipotese de inducao Vamos agora estabelecer formalmente o PIM em sua forma mais simples PIM primeira forma Seja a um numero natural Suponha que para cada natural n se tenha uma afirmativa Pn que satisfaca as seguintes propriedades i Pa e verdadeira ou seja a afirmativa vale para n a ii se a afirmativa for verdadeira para um natural k a qualquer entao ela e verdadeira para o seu sucessor k 1 Entao Pn e verdadeira para todo n a E importante destacarmos que a inducao matematica e constituıda de duas etapas cada uma de consideravel importˆancia pois a primeira garante que estamos partindo de um fato verdadeiro para o natural inicial a a segunda garante que ao assumir que a afirmacao e verdadeira para um natural k a qualquer entao devemos garantir que ela e verdadeira para o seu sucessor esta etapa consiste em demonstrar uma implicacao Como um primeiro exercıcio vocˆe pode observar que de fato provamos que 13 e verdadeira a partir do PIM primeira forma fundam2Cpia 201061 1350 page 9 9 9 Exemplo 11 Vamos provar por inducao que a afirmacao Pn abaixo e verdadeira 1 2 2 3 3 4 nn 1 nn 1n 2 3 n 1 a Etapa inicial verificar que vale P1 Mas isto e claro pois 1 2 11112 3 b Hipotese de inducao admitimos que vale Pk ou seja 1 2 2 3 kk 1 kk 1k 2 3 c Temos que provar que Pk 1 e verdadeira Para isto somamos k 1k 2 em ambos os membros da igualdade acima pois queremos a soma ate n k 1 e obtemos 1 2 2 3 kk 1 k 1k 2 kk1k2 3 k 1k 2 kk1k23k1k2 3 k1k2k3 3 e assim o resultado esta provado Cuidado E extremamente importante que todas as etapas de inducao sejam cumpridas para se evitar erros comuns entre os alunos que chegam a provar conjecturas falsas pela falta do cumprimento dessa propriedade em suas demonstracoes Por exemplo se nao testamos a etapa inicial corremos o risco de cometer este erro Exemplo 12 Vamos mostrar como e importante cumprir as etapas da inducao atraves de um exemplo Se fizermos a seguinte afirmacao 1 2 n 1 82n 12 n 1 14 e iniciarmos uma demonstracao por inducao a partir da etapa 2 ignorando a etapa inicial teremos como hipotese de inducao que a afirmativa vale para n k ou seja que 1 2 k 1 82k 12 e verdadeira e a partir daı somando k 1 em ambos os membros da igual dade temos 1 2 k k 1 1 82k 12 k 1 ou seja 1 2 k k 1 1 84k2 4k 1 8k 1 1 82k 1 12 e portanto a afirmacao vale para n k 1 Terıamos de fato provado que 14 e verdadeira se tivessemos garantida a etapa inicial Mas para n 1 em 14 temos 1 1 82 12 o que e obviamente falso Logo a afirmacao 14 nao e verdadeira fundam2Cpia 201061 1350 page 9 9 9 Exemplo 11 Vamos provar por inducao que a afirmacao Pn abaixo e verdadeira 1 2 2 3 3 4 nn 1 nn 1n 2 3 n 1 a Etapa inicial verificar que vale P1 Mas isto e claro pois 1 2 11112 3 b Hipotese de inducao admitimos que vale Pk ou seja 1 2 2 3 kk 1 kk 1k 2 3 c Temos que provar que Pk 1 e verdadeira Para isto somamos k 1k 2 em ambos os membros da igualdade acima pois queremos a soma ate n k 1 e obtemos 1 2 2 3 kk 1 k 1k 2 kk1k2 3 k 1k 2 kk1k23k1k2 3 k1k2k3 3 e assim o resultado esta provado Cuidado E extremamente importante que todas as etapas de inducao sejam cumpridas para se evitar erros comuns entre os alunos que chegam a provar conjecturas falsas pela falta do cumprimento dessa propriedade em suas demonstracoes Por exemplo se nao testamos a etapa inicial corremos o risco de cometer este erro Exemplo 12 Vamos mostrar como e importante cumprir as etapas da inducao atraves de um exemplo Se fizermos a seguinte afirmacao 1 2 n 1 82n 12 n 1 14 e iniciarmos uma demonstracao por inducao a partir da etapa 2 ignorando a etapa inicial teremos como hipotese de inducao que a afirmativa vale para n k ou seja que 1 2 k 1 82k 12 e verdadeira e a partir daı somando k 1 em ambos os membros da igual dade temos 1 2 k k 1 1 82k 12 k 1 ou seja 1 2 k k 1 1 84k2 4k 1 8k 1 1 82k 1 12 e portanto a afirmacao vale para n k 1 Terıamos de fato provado que 14 e verdadeira se tivessemos garantida a etapa inicial Mas para n 1 em 14 temos 1 1 82 12 o que e obviamente falso Logo a afirmacao 14 nao e verdadeira fundam2Cpia 201061 1350 page 9 9 9 Exemplo 11 Vamos provar por inducao que a afirmacao Pn abaixo e verdadeira 1 2 2 3 3 4 nn 1 nn 1n 2 3 n 1 a Etapa inicial verificar que vale P1 Mas isto e claro pois 1 2 11112 3 b Hipotese de inducao admitimos que vale Pk ou seja 1 2 2 3 kk 1 kk 1k 2 3 c Temos que provar que Pk 1 e verdadeira Para isto somamos k 1k 2 em ambos os membros da igualdade acima pois queremos a soma ate n k 1 e obtemos 1 2 2 3 kk 1 k 1k 2 kk1k2 3 k 1k 2 kk1k23k1k2 3 k1k2k3 3 e assim o resultado esta provado Cuidado E extremamente importante que todas as etapas de inducao sejam cumpridas para se evitar erros comuns entre os alunos que chegam a provar conjecturas falsas pela falta do cumprimento dessa propriedade em suas demonstracoes Por exemplo se nao testamos a etapa inicial corremos o risco de cometer este erro Exemplo 12 Vamos mostrar como e importante cumprir as etapas da inducao atraves de um exemplo Se fizermos a seguinte afirmacao 1 2 n 1 82n 12 n 1 14 e iniciarmos uma demonstracao por inducao a partir da etapa 2 ignorando a etapa inicial teremos como hipotese de inducao que a afirmativa vale para n k ou seja que 1 2 k 1 82k 12 e verdadeira e a partir daı somando k 1 em ambos os membros da igual dade temos 1 2 k k 1 1 82k 12 k 1 ou seja 1 2 k k 1 1 84k2 4k 1 8k 1 1 82k 1 12 e portanto a afirmacao vale para n k 1 Terıamos de fato provado que 14 e verdadeira se tivessemos garantida a etapa inicial Mas para n 1 em 14 temos 1 1 82 12 o que e obviamente falso Logo a afirmacao 14 nao e verdadeira fundamentos de álgebra I2012indd 14 26012012 180326 15 aula 1 fundam2Cpia 201061 1350 page 8 8 8 CAPITULO 1 AULA 1 PRINCIPIO DE INDUC AO MATEM ATICA Por virtude do que acabamos de dizer a conjectura ao ser verdadeira para n 6 tem tambem de ser verdadeira para n 7 ao ser verdadeira para n 7 e verdadeira para n 8 e assim sucessivamente Ou seja o resultado esta provado em geral A prova precedente pode servir como padrao em muitos casos semelhantes Se tivermos uma afirmacao sobre numeros naturais que afirmamos ser ver dadeira para todo natural n a partir de um natural a podemos ser capazes de usar a experiˆencia do exemplo anterior para concluir que a assercao sera verdadeira se for provada para n a e se puder ser provada para k 1 desde que seja admitida verdadeira para n k Este processo e usado tantas vezes que merece um nome Podıamos chamar lhe prova de n para n1 mas o termo tecnico aceito e inducao matema tica Em muitos casos como no discutido acima em detalhes a fonte e a inducao ou seja a assercao e encontrada experimentalmente Deste modo a prova surge como um complemento matematico a inducao o que explica o nome Problema 13 Como fazer uma demonstracao por inducao Solucao A demonstracao de uma afirmacao a respeito de numeros naturais baseada no Princıpio de Inducao Matematica PIM e chamada uma prova por inducao Ela consiste de duas etapas etapa 1 a demonstracao de que a afirmacao vale para um numero natural inicial a esta etapa e mais comumente chamada de etapa inicial etapa 2 a demonstracao de que a afirmacao vale para o sucessor k 1 de um numero natural arbitrario k a depois de termos suposto que a afirmacao vale para k Esta suposicao e chamada hipotese de inducao Vamos agora estabelecer formalmente o PIM em sua forma mais simples PIM primeira forma Seja a um numero natural Suponha que para cada natural n se tenha uma afirmativa Pn que satisfaca as seguintes propriedades i Pa e verdadeira ou seja a afirmativa vale para n a ii se a afirmativa for verdadeira para um natural k a qualquer entao ela e verdadeira para o seu sucessor k 1 Entao Pn e verdadeira para todo n a E importante destacarmos que a inducao matematica e constituıda de duas etapas cada uma de consideravel importˆancia pois a primeira garante que estamos partindo de um fato verdadeiro para o natural inicial a a segunda garante que ao assumir que a afirmacao e verdadeira para um natural k a qualquer entao devemos garantir que ela e verdadeira para o seu sucessor esta etapa consiste em demonstrar uma implicacao Como um primeiro exercıcio vocˆe pode observar que de fato provamos que 13 e verdadeira a partir do PIM primeira forma fundam2Cpia 201061 1350 page 9 9 9 Exemplo 11 Vamos provar por inducao que a afirmacao Pn abaixo e verdadeira 1 2 2 3 3 4 nn 1 nn 1n 2 3 n 1 a Etapa inicial verificar que vale P1 Mas isto e claro pois 1 2 11112 3 b Hipotese de inducao admitimos que vale Pk ou seja 1 2 2 3 kk 1 kk 1k 2 3 c Temos que provar que Pk 1 e verdadeira Para isto somamos k 1k 2 em ambos os membros da igualdade acima pois queremos a soma ate n k 1 e obtemos 1 2 2 3 kk 1 k 1k 2 kk1k2 3 k 1k 2 kk1k23k1k2 3 k1k2k3 3 e assim o resultado esta provado Cuidado E extremamente importante que todas as etapas de inducao sejam cumpridas para se evitar erros comuns entre os alunos que chegam a provar conjecturas falsas pela falta do cumprimento dessa propriedade em suas demonstracoes Por exemplo se nao testamos a etapa inicial corremos o risco de cometer este erro Exemplo 12 Vamos mostrar como e importante cumprir as etapas da inducao atraves de um exemplo Se fizermos a seguinte afirmacao 1 2 n 1 82n 12 n 1 14 e iniciarmos uma demonstracao por inducao a partir da etapa 2 ignorando a etapa inicial teremos como hipotese de inducao que a afirmativa vale para n k ou seja que 1 2 k 1 82k 12 e verdadeira e a partir daı somando k 1 em ambos os membros da igual dade temos 1 2 k k 1 1 82k 12 k 1 ou seja 1 2 k k 1 1 84k2 4k 1 8k 1 1 82k 1 12 e portanto a afirmacao vale para n k 1 Terıamos de fato provado que 14 e verdadeira se tivessemos garantida a etapa inicial Mas para n 1 em 14 temos 1 1 82 12 o que e obviamente falso Logo a afirmacao 14 nao e verdadeira fundam2Cpia 201061 1350 page 9 9 9 Exemplo 11 Vamos provar por inducao que a afirmacao Pn abaixo e verdadeira 1 2 2 3 3 4 nn 1 nn 1n 2 3 n 1 a Etapa inicial verificar que vale P1 Mas isto e claro pois 1 2 11112 3 b Hipotese de inducao admitimos que vale Pk ou seja 1 2 2 3 kk 1 kk 1k 2 3 c Temos que provar que Pk 1 e verdadeira Para isto somamos k 1k 2 em ambos os membros da igualdade acima pois queremos a soma ate n k 1 e obtemos 1 2 2 3 kk 1 k 1k 2 kk1k2 3 k 1k 2 kk1k23k1k2 3 k1k2k3 3 e assim o resultado esta provado Cuidado E extremamente importante que todas as etapas de inducao sejam cumpridas para se evitar erros comuns entre os alunos que chegam a provar conjecturas falsas pela falta do cumprimento dessa propriedade em suas demonstracoes Por exemplo se nao testamos a etapa inicial corremos o risco de cometer este erro Exemplo 12 Vamos mostrar como e importante cumprir as etapas da inducao atraves de um exemplo Se fizermos a seguinte afirmacao 1 2 n 1 82n 12 n 1 14 e iniciarmos uma demonstracao por inducao a partir da etapa 2 ignorando a etapa inicial teremos como hipotese de inducao que a afirmativa vale para n k ou seja que 1 2 k 1 82k 12 e verdadeira e a partir daı somando k 1 em ambos os membros da igual dade temos 1 2 k k 1 1 82k 12 k 1 ou seja 1 2 k k 1 1 84k2 4k 1 8k 1 1 82k 1 12 e portanto a afirmacao vale para n k 1 Terıamos de fato provado que 14 e verdadeira se tivessemos garantida a etapa inicial Mas para n 1 em 14 temos 1 1 82 12 o que e obviamente falso Logo a afirmacao 14 nao e verdadeira fundam2Cpia 201061 1350 page 9 9 9 Exemplo 11 Vamos provar por inducao que a afirmacao Pn abaixo e verdadeira 1 2 2 3 3 4 nn 1 nn 1n 2 3 n 1 a Etapa inicial verificar que vale P1 Mas isto e claro pois 1 2 11112 3 b Hipotese de inducao admitimos que vale Pk ou seja 1 2 2 3 kk 1 kk 1k 2 3 c Temos que provar que Pk 1 e verdadeira Para isto somamos k 1k 2 em ambos os membros da igualdade acima pois queremos a soma ate n k 1 e obtemos 1 2 2 3 kk 1 k 1k 2 kk1k2 3 k 1k 2 kk1k23k1k2 3 k1k2k3 3 e assim o resultado esta provado Cuidado E extremamente importante que todas as etapas de inducao sejam cumpridas para se evitar erros comuns entre os alunos que chegam a provar conjecturas falsas pela falta do cumprimento dessa propriedade em suas demonstracoes Por exemplo se nao testamos a etapa inicial corremos o risco de cometer este erro Exemplo 12 Vamos mostrar como e importante cumprir as etapas da inducao atraves de um exemplo Se fizermos a seguinte afirmacao 1 2 n 1 82n 12 n 1 14 e iniciarmos uma demonstracao por inducao a partir da etapa 2 ignorando a etapa inicial teremos como hipotese de inducao que a afirmativa vale para n k ou seja que 1 2 k 1 82k 12 e verdadeira e a partir daı somando k 1 em ambos os membros da igual dade temos 1 2 k k 1 1 82k 12 k 1 ou seja 1 2 k k 1 1 84k2 4k 1 8k 1 1 82k 1 12 e portanto a afirmacao vale para n k 1 Terıamos de fato provado que 14 e verdadeira se tivessemos garantida a etapa inicial Mas para n 1 em 14 temos 1 1 82 12 o que e obviamente falso Logo a afirmacao 14 nao e verdadeira fundamentos de álgebra I2012indd 15 26012012 180327 16 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 10 10 10CAPITULO 1 AULA 1 PRINCIPIO DE INDUC AO MATEM ATICA Problema 14 Como demonstrar uma desigualdade usando PIM Solucao Devemos seguir as etapas da mesma forma como fizemos no Exemplo 11 Vamos provar o enunciado abaixo como exemplo 2n n n 4 a Etapa inicial verificar que vale para n 4 De fato vale pois 24 16 24 4 b Hipotese de inducao admitimos que vale para n k 4 ou seja 2k k c Temos que provar que vale para n k 1 Observamos que 2k1 2 2k e usando a hipotese de inducao temos 2 2k 2 k ou seja 2k1 2 k Agora temos que comparar 2 k com k 1 que e onde queremos chegar Mas sabemos que k 1 k 1k e como 2 k 1 lembre que k 4 multiplicando por k os dois lados da desigualdade sem alterala temos 2 k k 1 k o que mostra que 2k1 k 1 O exemplo acima foi importante pois mostrou que muitas vezes temos que lancar mao de propriedades que nao aparecem explicitamente para chegar mos a nossa conclusao No caso do exemplo precisamos do fato 2 k 1 para terminarmos a demonstracao Em geral esta necessidade surge naturalmente ao desen volvermos a expressao que queremos provar Portanto vocˆe sempre deve observar atentamente o que precisa ser feito na etapa 2 do PIM em cada um dos exercıcios Problema 15 Como fazer uma deducao Solucao Novamente vamos resolver este problema atraves de um exem plo Vamos deduzir a expressao geral que exprime de modo simplificado o produto 1 1 4 1 1 9 1 1 n2 Note que nao faz sentido considerarmos n 1 ja que comecamos com 1 1 4 Assim iniciamos com n 2 e verificamos o que acontece para valores pequenos de n Para n 2 temos 1 1 4 3 4 Para n 3 temos 1 1 4 1 1 9 3 4 8 9 2 3 fundam2Cpia 201061 1350 page 11 11 11 Para n 4 temos 1 1 4 1 1 9 1 1 16 2 3 15 16 5 8 Para n 5 temos 1 1 4 1 1 9 1 1 16 1 1 25 5 8 24 25 3 5 A princıpio parece que nao ha regularidade Mas observando bem parece que temos algo comum quando n e par Veja n 2 3 4 2 1 2 2 n 4 5 8 4 1 2 4 Note que e indicado deduzir que para n par o produto obtido corresponde a n 1 2n Por outro lado se observarmos bem a expressao obtida para os casos em que n e ımpar nos da n 3 3 1 2 3 4 6 2 3 n 5 5 1 2 5 6 10 3 5 ou seja isto indica que o resultado tambem e verdadeiro para n ımpar Deste modo somos induzidos a acreditar que 1 1 4 1 1 9 1 1 n2 n 1 2n n 2 A demonstracao de que a deducao e mesmo verdadeira vocˆe fara no primeiro exercıcio da lista a seguir fundamentos de álgebra I2012indd 16 26012012 180327 17 aula 1 fundam2Cpia 201061 1350 page 10 10 10CAPITULO 1 AULA 1 PRINCIPIO DE INDUC AO MATEM ATICA Problema 14 Como demonstrar uma desigualdade usando PIM Solucao Devemos seguir as etapas da mesma forma como fizemos no Exemplo 11 Vamos provar o enunciado abaixo como exemplo 2n n n 4 a Etapa inicial verificar que vale para n 4 De fato vale pois 24 16 24 4 b Hipotese de inducao admitimos que vale para n k 4 ou seja 2k k c Temos que provar que vale para n k 1 Observamos que 2k1 2 2k e usando a hipotese de inducao temos 2 2k 2 k ou seja 2k1 2 k Agora temos que comparar 2 k com k 1 que e onde queremos chegar Mas sabemos que k 1 k 1k e como 2 k 1 lembre que k 4 multiplicando por k os dois lados da desigualdade sem alterala temos 2 k k 1 k o que mostra que 2k1 k 1 O exemplo acima foi importante pois mostrou que muitas vezes temos que lancar mao de propriedades que nao aparecem explicitamente para chegar mos a nossa conclusao No caso do exemplo precisamos do fato 2 k 1 para terminarmos a demonstracao Em geral esta necessidade surge naturalmente ao desen volvermos a expressao que queremos provar Portanto vocˆe sempre deve observar atentamente o que precisa ser feito na etapa 2 do PIM em cada um dos exercıcios Problema 15 Como fazer uma deducao Solucao Novamente vamos resolver este problema atraves de um exem plo Vamos deduzir a expressao geral que exprime de modo simplificado o produto 1 1 4 1 1 9 1 1 n2 Note que nao faz sentido considerarmos n 1 ja que comecamos com 1 1 4 Assim iniciamos com n 2 e verificamos o que acontece para valores pequenos de n Para n 2 temos 1 1 4 3 4 Para n 3 temos 1 1 4 1 1 9 3 4 8 9 2 3 fundam2Cpia 201061 1350 page 11 11 11 Para n 4 temos 1 1 4 1 1 9 1 1 16 2 3 15 16 5 8 Para n 5 temos 1 1 4 1 1 9 1 1 16 1 1 25 5 8 24 25 3 5 A princıpio parece que nao ha regularidade Mas observando bem parece que temos algo comum quando n e par Veja n 2 3 4 2 1 2 2 n 4 5 8 4 1 2 4 Note que e indicado deduzir que para n par o produto obtido corresponde a n 1 2n Por outro lado se observarmos bem a expressao obtida para os casos em que n e ımpar nos da n 3 3 1 2 3 4 6 2 3 n 5 5 1 2 5 6 10 3 5 ou seja isto indica que o resultado tambem e verdadeiro para n ımpar Deste modo somos induzidos a acreditar que 1 1 4 1 1 9 1 1 n2 n 1 2n n 2 A demonstracao de que a deducao e mesmo verdadeira vocˆe fara no primeiro exercıcio da lista a seguir fundamentos de álgebra I2012indd 17 26012012 180328 18 Fundamentos de Álgebra I exercícios fundam2Cpia 201061 1350 page 12 12 12CAPITULO 1 AULA 1 PRINCIPIO DE INDUC AO MATEM ATICA 1 Demonstre a deducao feita no Problema 15 por inducao para n 2 2 Use inducao matematica para provar que cada uma das afirmacoes abaixo e verdadeira para todo natural n 1 a 1 2 2 3 3 4 nn 1 nn1n2 3 b 1 4 9 n2 nn12n1 6 c 2 2 3 22 4 23 n 12n n2n1 d 2 1 4 3 6 5 2n2n 1 nn14n1 3 3 Use inducao matematica para estabelecer cada desigualdade abaixo a 2n n2 para n 5 b 1 1 2n 1 n 2 para n N c 1 1 2 1 3 1 n n para n 2 4 Considere A 1 1 0 1 a Calcule A2 e A3 para determinar uma formula possıvel para An n 1 b Use inducao para mostrar que a formula obtida em a e verdadeira 5 Encontre o erro na seguinte prova em qualquer grupo com n pessoas todas elas tˆem a mesma idade Se um grupo consiste de uma pessoa todas tˆem a mesma idade Suponha que em qualquer grupo com k pessoas todas tˆem a mesma idade Sejam a1 a2 ak1 as pessoas em um grupo com k 1 pessoas Desde que as pessoas a1 a2 ak e a2 a3 ak1 formam grupos com k pessoas todas elas tˆem a mesma idade por hipotese de inducao Desde que a2 esta em cada um destes grupos segue que todas as k 1 pessoas a1 a2 ak1 tˆem a mesma idade 6 Encontre o erro na seguinte prova por inducao matematica que garante 2462n n 1n 2 para todos os numeros naturais n Se assumimos que 2 4 6 2k k 1k 2 para algum k entao 2 4 6 2k 1 k 1k 2 2k 1 k2 k 2 2k 2 kk 3 k 1 1k 1 2 o que significa que sendo verdadeiro para k e verdadeiro para k 1 e portanto e verdadeiro para todos os naturais fundam2Cpia 201061 1350 page 13 13 13 7 O que esta errado com o seguinte argumento que afirma que qualquer dıvida de n dolares n 4 pode ser paga com notas de apenas 2 dolares Logicamente a afirmacao e valida para n 4 Considerando k 4 suponhamos que a afirmacao seja verdadeira para todo l 4 l k Devemos provar que a afirmacao e verdadeira para n k Para isto aplicamos a hipotese de inducao a k 2 e vemos que uma dıvida de k 2 dolares pode ser paga com notas de apenas 2 dolares Adicionando mais uma nota de 2 dolares vemos que podemos pagar uma dıvida de k dolares com notas de apenas 2 dolares como desejamos fundamentos de álgebra I2012indd 18 26012012 180328 19 aula 1 fundam2Cpia 201061 1350 page 12 12 12CAPITULO 1 AULA 1 PRINCIPIO DE INDUC AO MATEM ATICA 1 Demonstre a deducao feita no Problema 15 por inducao para n 2 2 Use inducao matematica para provar que cada uma das afirmacoes abaixo e verdadeira para todo natural n 1 a 1 2 2 3 3 4 nn 1 nn1n2 3 b 1 4 9 n2 nn12n1 6 c 2 2 3 22 4 23 n 12n n2n1 d 2 1 4 3 6 5 2n2n 1 nn14n1 3 3 Use inducao matematica para estabelecer cada desigualdade abaixo a 2n n2 para n 5 b 1 1 2n 1 n 2 para n N c 1 1 2 1 3 1 n n para n 2 4 Considere A 1 1 0 1 a Calcule A2 e A3 para determinar uma formula possıvel para An n 1 b Use inducao para mostrar que a formula obtida em a e verdadeira 5 Encontre o erro na seguinte prova em qualquer grupo com n pessoas todas elas tˆem a mesma idade Se um grupo consiste de uma pessoa todas tˆem a mesma idade Suponha que em qualquer grupo com k pessoas todas tˆem a mesma idade Sejam a1 a2 ak1 as pessoas em um grupo com k 1 pessoas Desde que as pessoas a1 a2 ak e a2 a3 ak1 formam grupos com k pessoas todas elas tˆem a mesma idade por hipotese de inducao Desde que a2 esta em cada um destes grupos segue que todas as k 1 pessoas a1 a2 ak1 tˆem a mesma idade 6 Encontre o erro na seguinte prova por inducao matematica que garante 2462n n 1n 2 para todos os numeros naturais n Se assumimos que 2 4 6 2k k 1k 2 para algum k entao 2 4 6 2k 1 k 1k 2 2k 1 k2 k 2 2k 2 kk 3 k 1 1k 1 2 o que significa que sendo verdadeiro para k e verdadeiro para k 1 e portanto e verdadeiro para todos os naturais fundam2Cpia 201061 1350 page 13 13 13 7 O que esta errado com o seguinte argumento que afirma que qualquer dıvida de n dolares n 4 pode ser paga com notas de apenas 2 dolares Logicamente a afirmacao e valida para n 4 Considerando k 4 suponhamos que a afirmacao seja verdadeira para todo l 4 l k Devemos provar que a afirmacao e verdadeira para n k Para isto aplicamos a hipotese de inducao a k 2 e vemos que uma dıvida de k 2 dolares pode ser paga com notas de apenas 2 dolares Adicionando mais uma nota de 2 dolares vemos que podemos pagar uma dıvida de k dolares com notas de apenas 2 dolares como desejamos fundamentos de álgebra I2012indd 19 26012012 180328 fundam2Cpia 201061 1350 page 15 15 Capıtulo 2 Aula 2 PIM e PBO Objetivos Vamos estabelecer a segunda forma do PIM e introduzir a sequˆencia de Fibonacci que e uma sequˆencia de numeros naturais com propriedades bas tante importantes Alem disso vamos estabelecer o Princıpio de Boa Ordem PBO e provar a equivalˆencia entre o PIM e o PBO Vamos iniciar apresentando uma interessante sequˆencia de numeros naturais que constantemente aparece em problemas de matematica Esta sequˆencia foi estudada por Leonardo de Pisa conhecido como Fibonacci filius Bonacci matematico e comerciante da Idade Media que em 1202 escre veu um livro Liber abacci contendo uma grande quantidade de assuntos relacionados com a aritmetica e algebra da epoca e que realizou um papel importante no desenvolvimento matematico na Europa nos seculos seguin tes pois atraves desse livro os europeus vieram a conhecer os algarismos arabicos Um dos problemas que esta nesse livro e o problema dos pares de coelhos Um homem tem um casal de coelhos jovens em um ambiente intei ramente fechado Desejamos saber quantos casais de coelhos podem ser gerados deste casal em um ano se de um modo natural a cada mˆes ocorre a producao de um casal e um casal comeca a produzir coelhos quando completa dois meses de vida Comecando com um casal jovem eles continuam jovens nos dois primeiros meses Como o casal adulto produz um casal novo a cada 30 dias no terceiro mˆes existirao dois casais de coelhos 1 casal adulto 1 casal recemnascido No quarto mˆes o casal adulto produzira de novo mais um casal enquanto que o casal jovem tera completado 1 mˆes de vida e ainda nao estara apto a produzir assim no quarto mˆes existirao trˆes pares de coelhos sendo 1 casal adulto 1 casal com 1 mˆes de idade 1 casal recemnascido No quinto mˆes existirao dois casais adultos sendo que cada um ja produziu um novo casal e um casal novo que completou 1 mˆes logo teremos 5 casais 2 adultos 1 com 1 mˆes 2 recemnascidos Tal processo continua atraves dos diversos meses ate completar um ano Observase esta formacao na sequˆencia numerica conhecida como a sequˆencia de Fibonacci que indica o numero de casais a cada mˆes 1 1 2 3 5 8 13 21 34 15 fundamentos de álgebra I2012indd 20 26012012 180329 AULA 2 PIm e Pbo objetIvos Vamos estabelecer a segunda forma do PIM e introduzir a sequência de Fibonacci que é uma sequência de números naturais com propriedades bastante importantes Além disso vamos estabelecer o Princípio de Boa Ordem PBO e provar a equivalência entre o PIM e o PBO fundam2Cpia 201061 1350 page 15 15 Capıtulo 2 Aula 2 PIM e PBO Objetivos Vamos estabelecer a segunda forma do PIM e introduzir a sequˆencia de Fibonacci que e uma sequˆencia de numeros naturais com propriedades bas tante importantes Alem disso vamos estabelecer o Princıpio de Boa Ordem PBO e provar a equivalˆencia entre o PIM e o PBO Vamos iniciar apresentando uma interessante sequˆencia de numeros naturais que constantemente aparece em problemas de matematica Esta sequˆencia foi estudada por Leonardo de Pisa conhecido como Fibonacci filius Bonacci matematico e comerciante da Idade Media que em 1202 escre veu um livro Liber abacci contendo uma grande quantidade de assuntos relacionados com a aritmetica e algebra da epoca e que realizou um papel importante no desenvolvimento matematico na Europa nos seculos seguin tes pois atraves desse livro os europeus vieram a conhecer os algarismos arabicos Um dos problemas que esta nesse livro e o problema dos pares de coelhos Um homem tem um casal de coelhos jovens em um ambiente intei ramente fechado Desejamos saber quantos casais de coelhos podem ser gerados deste casal em um ano se de um modo natural a cada mˆes ocorre a producao de um casal e um casal comeca a produzir coelhos quando completa dois meses de vida Comecando com um casal jovem eles continuam jovens nos dois primeiros meses Como o casal adulto produz um casal novo a cada 30 dias no terceiro mˆes existirao dois casais de coelhos 1 casal adulto 1 casal recemnascido No quarto mˆes o casal adulto produzira de novo mais um casal enquanto que o casal jovem tera completado 1 mˆes de vida e ainda nao estara apto a produzir assim no quarto mˆes existirao trˆes pares de coelhos sendo 1 casal adulto 1 casal com 1 mˆes de idade 1 casal recemnascido No quinto mˆes existirao dois casais adultos sendo que cada um ja produziu um novo casal e um casal novo que completou 1 mˆes logo teremos 5 casais 2 adultos 1 com 1 mˆes 2 recemnascidos Tal processo continua atraves dos diversos meses ate completar um ano Observase esta formacao na sequˆencia numerica conhecida como a sequˆencia de Fibonacci que indica o numero de casais a cada mˆes 1 1 2 3 5 8 13 21 34 15 fundamentos de álgebra I2012indd 21 26012012 180329 Considerando Fn o nésimo termo da sequência de Fibonacci observamos que estes termos obedecem a uma regra de formação F11 F21 FnFn1Fn2 para n3 ou seja os dois primeiros termos sao iguais a 1 e a partir do terceiro termo cada termo é a soma dos dois termos anteriores desta forma esta sequência é recursivamente definida pois conhecemos cada termo a partir dos anteriores Com esta observação muitas são as propriedades da sequência de Fibonacci que podem ser provadas por indução Exemplo 21 Os termos da sequência de Fibonacci satisfazem F1F2FnFn21 Devido à formação da sequência a etapa inicial de indução deve ser testada para n1 e n2 em seguida usamos a recursividade Assim temos que a etapa inicial é válida pois F1121F31F121 e F1F21131F41F221 Agora assumimos por hipótese de indução que vale para nk2 ou seja F1F2FkFk21 Vamos ter F1F2FkFk1Fk21Fk1Fk31 Logo vale para nk1 e o resultado está provado Devido à recursividade da sequência de Fibonacci em alguns casos não conseguimos provar resultados a respeito de seus termos diretamente a partir da primeira forma do PIM Para estes casos existe uma forma alternativa que deve ser usada sempre que a prova para Pk1 não puder ser obtida diretamente da validade de Pk mas puder ser obtida a partir da validade de Pa Pa1Pk Ou seja quando pudermos provar que a afirmação é verdadeira para k1 se assumirmos verdadeira para todos os naturais m entre a e k Para esta situação vamos usar a segunda forma do princípio de indução matemática enunciado abaixo PIM segunda forma Seja a um número natural Suponha que para cada natural n se tenha uma afirmativa Pn que satisfaça as seguintes propriedades i Pa é verdadeira ii se Pm for verdadeira para todo natural m com amk então Pk1 é verdadeira Então Pn é verdadeira para todo na Exemplo 22 Prove por indução que Fn74n para todo n1 Considerando que Pn é a nossa afirmação temos i P1 e P2 são verdadeiras pois 174 ii Usamos a segunda forma do princípio tomando k2 e assumindo que Pm é verdadeira para todo 2mk Desta forma precisamos mostrar que Pk1 é verdadeira Como k13 temos a partir da recursividade e da hipótese de indução Fk1FkFk1 74k 74k1 74k1 74 1 74k1 114 74k1 742 74k1 E temos válido o resultado Note que no exemplo anterior foi necessário usar a segunda forma do PIM pois precisamos de informações sobre nk e nk1 Agora vamos ver que a segunda forma do PIM pode ser demonstrada a partir da primeira forma do PIM Demonstração da segunda forma do PIM Seja a um número natural Suponha que para cada natural n se tenha uma afirmativa Pn tal que i Pa é verdadeira ii se Pm for verdadeira para todo natural m com amk então Pk1 é verdadeira Queremos mostrar que Pn é verdadeira para todo natural na Para isto consideremos o seguinte conjunto AnN na Pa Pa1Pn são verdadeiras Pela condição i temos aA Agora vamos mostrar que se kA então k1A pois desta maneira usando a primeira forma do PIM todos os naturais na estarão em A De fato como kA temos ka e Pa Pa1Pk são verdadeiras Portanto pela condição ii garantimos que Pk1 é verdadeira ou seja k1A Desta forma A é formado de todos os naturais na o que termina a demonstração Como uma última observação a respeito da sequência de Fibonacci notamos que os termos desta sequência crescem indefinidamente mas existe um fato interessante tomando as razões divisões de cada termo pelo seu antecessor obtemos uma outra sequência numérica cujo termo geral é dado por An Fn1Fn 24 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 18 18 18 CAPITULO 2 AULA 2 PIM E PBO e notamos que A1 11 1 A2 21 2 A3 32 15 A4 53 1666 A5 85 16 A6 138 1625 As razoes vao se aproximando de um valor particular conhecido como Numero Aureo que e frequentemente representado pela letra grega φ e dado por φ 5 1 2 ou seja lim nAn φ Note que φ e uma das raızes da equacao x2 x 1 0 ou seja φ2 φ 1 Problema 21 Mostre por inducao que φn2 Fn φn1 n 2 Solucao Vamos provar que Fn φn1 n 2 Para o passo inicial de inducao temos n 2 φ21 φ 5 1 2 2 1 2 1 F2 ou seja e verdade que F2 φ21 Suponhamos que para qualquer 2 m k seja verdade que Fm φm1 Vamos ver o que ocorre quando n k 1 Fk1 Fk Fk1 φk1 φk2 φk2 φ 1 φk2 φ2 φk Com isso provamos a primeira desigualdade Agora prove vocˆe a desigual dade Fn φn2 n 2 Problema 22 O que e o Princıpio da Boa Ordem Solucao Para finalizar a aula vamos introduzir este princıpio e estabelecer sua equivalˆencia com o PIM Antes de mais nada observemos que para quaisquer dois numeros reais podemos estabelecer uma comparacao no sentido que a b ou a b ou a b isto e o conjunto dos numeros reais R e bem ordenado fundam2Cpia 201061 1350 page 19 19 19 Definicao 21 Dizemos que um subconjunto S R e limitado inferior mente por um elemento a R se a x x S E neste caso dizemos que e a uma cota inferior de S Exemplo 23 i O conjunto S1 1 0 1 e limitado inferiormente por 1 mas tambem e limitado inferiormente por qualquer real 1 ii O intervalo aberto S2 0 1 ou seja S2 x R 0 x 1 e limitado inferiormente por 0 Note que nos exemplos acima temos que a1 1 e uma cota inferior de S1 e a1 S1 mas a2 0 e uma cota inferior de S2 que nao pertence a S2 Definicao 22 Se a for uma cota inferior de um conjunto S e a S entao dizemos que a e o menor elemento de S Portanto pelo exemplo acima alguns subconjuntos de R nao possuem me nor elemento De fato o conjunto S2 0 1 nao possui menor elemento pois se a S2 fosse menor elemento de S2 entao terıamos 0 a 1 e a x x S2 o que nao e possıvel pois a 2 a e a 2 S2 ja que 0 a 2 1 2 1 Problema 23 Quando podemos garantir que um subconjunto de Z possui menor elemento Solucao A resposta vem com o PBO que garante que um subconjunto S de inteiros tem menor elemento quando ele e nao vazio e limitado inferiormente O PBO sera enunciado abaixo como um teorema pois pode ser demonstrado usando a segunda forma do PIM Teorema 21 Princıpio da Boa Ordem PBO Todo subconjunto S Z nao vazio e limitado inferiormente possui menor elemento Demonstracao Suponhamos que S Z seja um conjunto nao vazio e limitado inferiormente por a Z e suponhamos por absurdo que S nao possui menor elemento Vamos provar que S e vazio Para isto observamos primeiramente que a S pois caso contrario a seria o menor elemento de S Agora vamos assumir que a a 1 a 2 a k nao estejam em S e vamos provar que a k 1 S Desta maneira pela segunda forma do PIM vamos concluir que b S para todo b a e como todos os elementos em S sao maiores ou iguais a a pois a e cota inferior de S vamos ter S De fato se a k 1 S entao a k 1 sera o menor elemento de S pois todos os inteiros maiores que a e menores que a k 1 estao fora de S Isto nos diz que a k 1 S o que garante que S e vazio Este absurdo prova o resultado ou seja S possui menor elemento fundamentos de álgebra I2012indd 24 26012012 180331 25 aula 2 fundam2Cpia 201061 1350 page 18 18 18 CAPITULO 2 AULA 2 PIM E PBO e notamos que A1 11 1 A2 21 2 A3 32 15 A4 53 1666 A5 85 16 A6 138 1625 As razoes vao se aproximando de um valor particular conhecido como Numero Aureo que e frequentemente representado pela letra grega φ e dado por φ 5 1 2 ou seja lim nAn φ Note que φ e uma das raızes da equacao x2 x 1 0 ou seja φ2 φ 1 Problema 21 Mostre por inducao que φn2 Fn φn1 n 2 Solucao Vamos provar que Fn φn1 n 2 Para o passo inicial de inducao temos n 2 φ21 φ 5 1 2 2 1 2 1 F2 ou seja e verdade que F2 φ21 Suponhamos que para qualquer 2 m k seja verdade que Fm φm1 Vamos ver o que ocorre quando n k 1 Fk1 Fk Fk1 φk1 φk2 φk2 φ 1 φk2 φ2 φk Com isso provamos a primeira desigualdade Agora prove vocˆe a desigual dade Fn φn2 n 2 Problema 22 O que e o Princıpio da Boa Ordem Solucao Para finalizar a aula vamos introduzir este princıpio e estabelecer sua equivalˆencia com o PIM Antes de mais nada observemos que para quaisquer dois numeros reais podemos estabelecer uma comparacao no sentido que a b ou a b ou a b isto e o conjunto dos numeros reais R e bem ordenado fundam2Cpia 201061 1350 page 19 19 19 Definicao 21 Dizemos que um subconjunto S R e limitado inferior mente por um elemento a R se a x x S E neste caso dizemos que e a uma cota inferior de S Exemplo 23 i O conjunto S1 1 0 1 e limitado inferiormente por 1 mas tambem e limitado inferiormente por qualquer real 1 ii O intervalo aberto S2 0 1 ou seja S2 x R 0 x 1 e limitado inferiormente por 0 Note que nos exemplos acima temos que a1 1 e uma cota inferior de S1 e a1 S1 mas a2 0 e uma cota inferior de S2 que nao pertence a S2 Definicao 22 Se a for uma cota inferior de um conjunto S e a S entao dizemos que a e o menor elemento de S Portanto pelo exemplo acima alguns subconjuntos de R nao possuem me nor elemento De fato o conjunto S2 0 1 nao possui menor elemento pois se a S2 fosse menor elemento de S2 entao terıamos 0 a 1 e a x x S2 o que nao e possıvel pois a 2 a e a 2 S2 ja que 0 a 2 1 2 1 Problema 23 Quando podemos garantir que um subconjunto de Z possui menor elemento Solucao A resposta vem com o PBO que garante que um subconjunto S de inteiros tem menor elemento quando ele e nao vazio e limitado inferiormente O PBO sera enunciado abaixo como um teorema pois pode ser demonstrado usando a segunda forma do PIM Teorema 21 Princıpio da Boa Ordem PBO Todo subconjunto S Z nao vazio e limitado inferiormente possui menor elemento Demonstracao Suponhamos que S Z seja um conjunto nao vazio e limitado inferiormente por a Z e suponhamos por absurdo que S nao possui menor elemento Vamos provar que S e vazio Para isto observamos primeiramente que a S pois caso contrario a seria o menor elemento de S Agora vamos assumir que a a 1 a 2 a k nao estejam em S e vamos provar que a k 1 S Desta maneira pela segunda forma do PIM vamos concluir que b S para todo b a e como todos os elementos em S sao maiores ou iguais a a pois a e cota inferior de S vamos ter S De fato se a k 1 S entao a k 1 sera o menor elemento de S pois todos os inteiros maiores que a e menores que a k 1 estao fora de S Isto nos diz que a k 1 S o que garante que S e vazio Este absurdo prova o resultado ou seja S possui menor elemento fundamentos de álgebra I2012indd 25 26012012 180331 26 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 20 20 20 CAPITULO 2 AULA 2 PIM E PBO A resposta para o Problema 23 vem a partir do PBO ou seja quando temos um subconjunto de Z que e nao vazio e limitado inferiormente garantimos que ele tem menor elemento Em particular se S N for um conjunto nao vazio entao S tem menor elemento pois neste caso S e um subconjunto de Z limitado inferiormente por 0 Problema 24 Como provar resultados a respeito dos numeros naturais usando o PBO Solucao Vamos resolver o problema fazendo um exemplo Exemplo 24 Vamos mostrar usando PBO que para todo n 1 temos 1 2 3 n nn 1 2 Vocˆe pode notar que esta e exatamente a afirmacao 12 que na primeira aula provamos atraves de um argumento geometrico Vamos agora provalo por absurdo atraves do PBO Para isto queremos garantir que o conjunto dos naturais n 1 para os quais nao vale a igualdade acima e vazio Assumimos que o conjunto S n N n 1 1 2 3 n nn 1 2 e diferente de vazio Usando o PBO S tem um menor elemento ou seja existe um elemento a S tal que a x x S Antes de mais nada note que a 1 pois 1 2 1 1 1 e assim 1 S Temos a 2 e com isso a1 1 e a1 S pois a1 a Deste modo 1 2 3 a 1 a 1a 1 1 2 isto e 1 2 3 a 1 a 1a 2 Assim somando a aos membros da igualdade acima temos 1 2 3 a 1 a a 1a 2 a o que implica em 1 2 3 a 1 a a2 a 2a 2 a2 a 2 aa 1 2 Mas isto e um absurdo pois como a S temos 1 2 3 a 1 a aa 1 2 Esta contradicao aconteceu pois admitimos que S Logo vale o contrario quer dizer S e portanto 1 2 3 n nn1 2 n 1 fundam2Cpia 201061 1350 page 21 21 21 Lembre que usando a primeira forma do PIM provamos a segunda forma do PIM No Teorema 21 usamos a segunda forma do PIM para provar o PBO Agora vamos ver que usando o PBO podemos provar a primeira forma do PIM Isto significa que ao aceitar cada um dos princıpios como verdadeiro podemos provar os outros e neste caso dizemos que os princıpios de inducao primeira e segunda formas e o Princıpio de Boa Ordem sao equivalentes PIM primeira forma PIM segunda forma PBO Demonstracao da primeira forma do PIM usando PBO Vamos comecar com as hipoteses da primeira forma do PIM ou seja temos a um numero natural e uma afirmativa Pn para cada natural n que satisfaz as seguintes propriedades i Pa e verdadeira ou seja a afirmativa vale para n a ii se Pk for verdadeira para um natural k a qualquer entao Pk 1 e verdadeira para o seu sucessor k 1 Queremos mostrar que Pn e verdadeira para todo n a e para isto vamos usar o PBO Neste caso devemos mostrar que o conjunto dos naturais n a para os quais Pn e falsa e um conjunto vazio Vamos supor o contrario ou seja S n N n a Pn e falsa Pelo PBO existe um elemento s0 S que e o menor elemento de S ou seja Ps0 e falsa e s0 n n S Mas e claro que s0 a pois Pa e verdadeira pela condicao i Logo s0 a e assim s0 1 a Como s0 1 s0 devemos ter s0 1 S pois s0 e o menor elemento de S Portanto Ps0 1 e verdadeira e usando a condicao ii isto implica que Ps0 e verdadeira o que e absurdo Deste modo S e assim garantimos a validade do resultado fundamentos de álgebra I2012indd 26 26012012 180332 27 aula 2 fundam2Cpia 201061 1350 page 20 20 20 CAPITULO 2 AULA 2 PIM E PBO A resposta para o Problema 23 vem a partir do PBO ou seja quando temos um subconjunto de Z que e nao vazio e limitado inferiormente garantimos que ele tem menor elemento Em particular se S N for um conjunto nao vazio entao S tem menor elemento pois neste caso S e um subconjunto de Z limitado inferiormente por 0 Problema 24 Como provar resultados a respeito dos numeros naturais usando o PBO Solucao Vamos resolver o problema fazendo um exemplo Exemplo 24 Vamos mostrar usando PBO que para todo n 1 temos 1 2 3 n nn 1 2 Vocˆe pode notar que esta e exatamente a afirmacao 12 que na primeira aula provamos atraves de um argumento geometrico Vamos agora provalo por absurdo atraves do PBO Para isto queremos garantir que o conjunto dos naturais n 1 para os quais nao vale a igualdade acima e vazio Assumimos que o conjunto S n N n 1 1 2 3 n nn 1 2 e diferente de vazio Usando o PBO S tem um menor elemento ou seja existe um elemento a S tal que a x x S Antes de mais nada note que a 1 pois 1 2 1 1 1 e assim 1 S Temos a 2 e com isso a1 1 e a1 S pois a1 a Deste modo 1 2 3 a 1 a 1a 1 1 2 isto e 1 2 3 a 1 a 1a 2 Assim somando a aos membros da igualdade acima temos 1 2 3 a 1 a a 1a 2 a o que implica em 1 2 3 a 1 a a2 a 2a 2 a2 a 2 aa 1 2 Mas isto e um absurdo pois como a S temos 1 2 3 a 1 a aa 1 2 Esta contradicao aconteceu pois admitimos que S Logo vale o contrario quer dizer S e portanto 1 2 3 n nn1 2 n 1 fundam2Cpia 201061 1350 page 21 21 21 Lembre que usando a primeira forma do PIM provamos a segunda forma do PIM No Teorema 21 usamos a segunda forma do PIM para provar o PBO Agora vamos ver que usando o PBO podemos provar a primeira forma do PIM Isto significa que ao aceitar cada um dos princıpios como verdadeiro podemos provar os outros e neste caso dizemos que os princıpios de inducao primeira e segunda formas e o Princıpio de Boa Ordem sao equivalentes PIM primeira forma PIM segunda forma PBO Demonstracao da primeira forma do PIM usando PBO Vamos comecar com as hipoteses da primeira forma do PIM ou seja temos a um numero natural e uma afirmativa Pn para cada natural n que satisfaz as seguintes propriedades i Pa e verdadeira ou seja a afirmativa vale para n a ii se Pk for verdadeira para um natural k a qualquer entao Pk 1 e verdadeira para o seu sucessor k 1 Queremos mostrar que Pn e verdadeira para todo n a e para isto vamos usar o PBO Neste caso devemos mostrar que o conjunto dos naturais n a para os quais Pn e falsa e um conjunto vazio Vamos supor o contrario ou seja S n N n a Pn e falsa Pelo PBO existe um elemento s0 S que e o menor elemento de S ou seja Ps0 e falsa e s0 n n S Mas e claro que s0 a pois Pa e verdadeira pela condicao i Logo s0 a e assim s0 1 a Como s0 1 s0 devemos ter s0 1 S pois s0 e o menor elemento de S Portanto Ps0 1 e verdadeira e usando a condicao ii isto implica que Ps0 e verdadeira o que e absurdo Deste modo S e assim garantimos a validade do resultado fundamentos de álgebra I2012indd 27 26012012 180332 28 Fundamentos de Álgebra I exercícios fundam2Cpia 201061 1350 page 22 22 22 CAPITULO 2 AULA 2 PIM E PBO Exercıcios da Aula 2 1 Use o PIM para provar as propriedades abaixo entre os termos da sequˆencia de Fibonacci para todo natural n 1 a F1 F3 F2n3 F2n1 F2n b F2 F4 F2n2 F2n F2n1 1 c F 2 1 F 2 2 F 2 n FnFn1 2 Termine a solucao do Problema 21 ou seja prove a desigualdade Fn φn2 n 2 3 Note que 2 22 22 32 23 42 24 52 Deducao 2n n 12 para todo n 1 Se a deducao for verdadeira entao demonstre por inducao Se for falsa explique porque 4 Prove utilizando inducao que o numero de subconjuntos de um conjunto com n elementos e 2n n 1 5 Considere n p Z com 0 p n e o numero binomial definido por n p n pn p onde n nn 1321 e 0 1 a Demonstre a relacao de Stiefel n p n 1 p 1 n 1 p para n p 1 b Mostre que n p e um numero natural para todos n p nas condicoes da definicao c Mostre a formula do binˆomio de Newton por inducao x an n p0 n p apxnp n N 6 Refaca o Exercıcio 2 da Aula 1 usando PBO 7 Defina o que e um subconjunto limitado superiormente de numeros reais Defina o que e cota superior e o que e maior elemento de um conjunto 8 Use PBO para provar o seguinte se S Z e nao vazio e limitado superiormente entao S tem um maior elemento fundam2Cpia 201061 1350 page 23 23 Capıtulo 3 Aula 3 Lema de Euclides Objetivos Vamos apresentar nesta aula o Lema da divisao de Euclides que ja nos e bastante familiar e que e um otimo exemplo de como podemos usar inducao para fazer uma demonstracao Euclides de Alexandria 360 aC 295 aC foi professor matematico platˆo nico de origem desconhecida e o maior responsavel pelo desenvolvimento da famosa geometria euclidiana Teria sido educado em Atenas e frequentado a Academia de Platao em pleno florescimento da cultura helenıstica O mais antigo texto matematico Os elementos e de sua autoria e nele foi incorporado praticamente todo o conhecimento matematico acumulado por seus antecessores em um total de 13 volumes cada um deles denominado Livro Os Livros VII VIII e IX de Os elementos sao sobre teoria de numeros sendo que por numero os antigos gregos entendiam o que hoje denominamos numero natural Nestes Livros tambem sao encontrados resultados sobre os numeros inteiros com demonstracoes que sao utilizadas ate hoje e que obviamente foram reescritas em uma notacao moderna Lembremos que o conjunto dos numeros naturais e formado de numeros in teiros nao negativos N 0 1 2 O que o lema de Euclides basicamente faz e uma especie de comparacao entre dois numeros naturais Vejamos abaixo Lema 31 Euclides Dados dois numeros naturais a e b com b 0 existem naturais q quociente e r resto unicamente determinados tais que a bq r onde 0 r b Demonstracao A demonstracao sera feita por inducao sobre a E claro que se a 0 entao tomamos q 0 e r 0 ou seja a etapa inicial e verdadeira Vamos assumir como hipotese de inducao que vale para a 0 ou seja que existem q e r tais que a bq r onde 0 r b Agora vamos mostrar que vale para a 1 exibindo um quociente q e um resto r tais que a 1 bq r com 0 r b 31 Usando a hipotese de inducao temos a 1 bq r 1 com 1 r 1 b 1 23 fundamentos de álgebra I2012indd 28 26012012 180333 AULA 3 lema de euclides objetIvo Vamos apresentar nesta aula o lema da divisão de Euclides que já nos é bastante familiar e que é um ótimo exemplo de como podemos usar indução para fazer uma demonstração fundam2Cpia 201061 1350 page 22 22 22 CAPITULO 2 AULA 2 PIM E PBO Exercıcios da Aula 2 1 Use o PIM para provar as propriedades abaixo entre os termos da sequˆencia de Fibonacci para todo natural n 1 a F1 F3 F2n3 F2n1 F2n b F2 F4 F2n2 F2n F2n1 1 c F 2 1 F 2 2 F 2 n FnFn1 2 Termine a solucao do Problema 21 ou seja prove a desigualdade Fn φn2 n 2 3 Note que 2 22 22 32 23 42 24 52 Deducao 2n n 12 para todo n 1 Se a deducao for verdadeira entao demonstre por inducao Se for falsa explique porque 4 Prove utilizando inducao que o numero de subconjuntos de um conjunto com n elementos e 2n n 1 5 Considere n p Z com 0 p n e o numero binomial definido por n p n pn p onde n nn 1321 e 0 1 a Demonstre a relacao de Stiefel n p n 1 p 1 n 1 p para n p 1 b Mostre que n p e um numero natural para todos n p nas condicoes da definicao c Mostre a formula do binˆomio de Newton por inducao x an n p0 n p apxnp n N 6 Refaca o Exercıcio 2 da Aula 1 usando PBO 7 Defina o que e um subconjunto limitado superiormente de numeros reais Defina o que e cota superior e o que e maior elemento de um conjunto 8 Use PBO para provar o seguinte se S Z e nao vazio e limitado superiormente entao S tem um maior elemento fundam2Cpia 201061 1350 page 23 23 Capıtulo 3 Aula 3 Lema de Euclides Objetivos Vamos apresentar nesta aula o Lema da divisao de Euclides que ja nos e bastante familiar e que e um otimo exemplo de como podemos usar inducao para fazer uma demonstracao Euclides de Alexandria 360 aC 295 aC foi professor matematico platˆo nico de origem desconhecida e o maior responsavel pelo desenvolvimento da famosa geometria euclidiana Teria sido educado em Atenas e frequentado a Academia de Platao em pleno florescimento da cultura helenıstica O mais antigo texto matematico Os elementos e de sua autoria e nele foi incorporado praticamente todo o conhecimento matematico acumulado por seus antecessores em um total de 13 volumes cada um deles denominado Livro Os Livros VII VIII e IX de Os elementos sao sobre teoria de numeros sendo que por numero os antigos gregos entendiam o que hoje denominamos numero natural Nestes Livros tambem sao encontrados resultados sobre os numeros inteiros com demonstracoes que sao utilizadas ate hoje e que obviamente foram reescritas em uma notacao moderna Lembremos que o conjunto dos numeros naturais e formado de numeros in teiros nao negativos N 0 1 2 O que o lema de Euclides basicamente faz e uma especie de comparacao entre dois numeros naturais Vejamos abaixo Lema 31 Euclides Dados dois numeros naturais a e b com b 0 existem naturais q quociente e r resto unicamente determinados tais que a bq r onde 0 r b Demonstracao A demonstracao sera feita por inducao sobre a E claro que se a 0 entao tomamos q 0 e r 0 ou seja a etapa inicial e verdadeira Vamos assumir como hipotese de inducao que vale para a 0 ou seja que existem q e r tais que a bq r onde 0 r b Agora vamos mostrar que vale para a 1 exibindo um quociente q e um resto r tais que a 1 bq r com 0 r b 31 Usando a hipotese de inducao temos a 1 bq r 1 com 1 r 1 b 1 23 fundamentos de álgebra I2012indd 29 26012012 180333 30 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 24 24 24 CAPITULO 3 AULA 3 LEMA DE EUCLIDES Deste modo r 1 b Se r 1 b basta tomar q q e r r 1 e temos 31 Mas se r 1 b teremos a 1 bq b bq 1 e portanto tomamos q q 1 e r 0 tambem garantindo 31 Para provar a unicidade suponhamos que temos dois pares de naturais q1 r1 e q2 r2 tais que a bq1 r1 e a bq2 r2 com 0 r1 b e 0 r2 b Queremos mostrar que q1 q2 e r1 r2 Suponhamos que isto nao ocorra ou seja suponhamos que q1 q2 Se sao diferentes entao um deve ser maior ou menor que o outro Podemos assumir sem perda de generalidade que q2 q1 Neste caso como bq1 r1 bq2 r2 temos r1 r2 bq2 q1 b pois q2 q1 0 o que nao e possıvel ja que 0 r1 b e 0 r2 b Portanto q1 q2 e assim r1 a bq1 a bq2 r2 e o lema esta provado Uma observacao muito importante que podemos fazer apos a demonstracao do lema de Euclides e que existe uma maneira unica de se escrever um numero natural quando comparado com um outro natural Ou seja se a e b forem naturais nao nulos entao a e de uma das formas excludentes abaixo com relacao a b a bq ou a bq1 ou a bq2 ou a bqb2 ou a bqb1 bastando para isto considerar os possıveis restos na divisao de a por b 0 1 2 b 1 Quando o resto e zero dizemos que a e um multiplo de b ou seja a e multiplo de b quando existe q N tal que a bq Problema 31 Mostre que se a N entao a2 e da forma 3k ou 3k 1 com k N Solucao Pelo que observamos acima a e de uma das formas ou i a 3q ou ii a 3q 1 ou ii a 3q 2 Deste modo analisando cada caso ou i a2 3q2 33q2 forma 3k ou ii a2 3q 12 33q2 2q 1 forma 3k1 ou ii a2 3q 22 3q2 4q 1 1 forma 3k1 fundam2Cpia 201061 1350 page 25 25 25 Problema 32 Dados 3 numeros naturais consecutivos um e somente um deles e multiplo de 3 Solucao Os numeros dados podem ser escritos como a a 1 e a 2 Mas o numero a pode ser dividido por 3 deixando um e somente um resto ou seja existe q N tal que a 3q r onde 0 r 3 O resto r pode ser 0 ou 1 ou 2 i Se r 0 entao temos a 3q ou seja a e multiplo de 3 ii Se r 1 entao temos a 3q 1 Assim a 2 3q3 3q 1 ou seja a 2 e multiplo de 3 iii Se r 2 entao temos a 3q 2 Assim a 1 3q3 3q 1 ou seja a 1 e multiplo de 3 Observe que apenas uma das possibilidades i ii ou iii pode ocorrer pela unicidade do resto na divisao euclidiana Problema 33 Mostre que dados n numeros naturais consecutivos um e somente um deles e multiplo de n Solucao Faca O Lema 31 pode ser generalizado para o conjunto dos numeros inteiros Z 2 1 0 1 2 Sabemos que este conjunto pode ser representado sobre uma reta escolhendo um ponto arbitrario como zero e associando pontos a direita deste para serem os numeros positivos e os da esquerda para serem os negativos 2 1 0 1 2 Recordemos ainda que o valor absoluto de um inteiro b e definido por b b se b 0 b se b 0 Observe ainda que para qualquer inteiro b o numero b e natural e b b Assim ao considerar b 0 podemos dividir a reta de numeros inteiros considerando a partir do zero segmentos de comprimento b como abaixo 2b b 0 b 2b fundamentos de álgebra I2012indd 30 26012012 180334 31 aula 3 fundam2Cpia 201061 1350 page 24 24 24 CAPITULO 3 AULA 3 LEMA DE EUCLIDES Deste modo r 1 b Se r 1 b basta tomar q q e r r 1 e temos 31 Mas se r 1 b teremos a 1 bq b bq 1 e portanto tomamos q q 1 e r 0 tambem garantindo 31 Para provar a unicidade suponhamos que temos dois pares de naturais q1 r1 e q2 r2 tais que a bq1 r1 e a bq2 r2 com 0 r1 b e 0 r2 b Queremos mostrar que q1 q2 e r1 r2 Suponhamos que isto nao ocorra ou seja suponhamos que q1 q2 Se sao diferentes entao um deve ser maior ou menor que o outro Podemos assumir sem perda de generalidade que q2 q1 Neste caso como bq1 r1 bq2 r2 temos r1 r2 bq2 q1 b pois q2 q1 0 o que nao e possıvel ja que 0 r1 b e 0 r2 b Portanto q1 q2 e assim r1 a bq1 a bq2 r2 e o lema esta provado Uma observacao muito importante que podemos fazer apos a demonstracao do lema de Euclides e que existe uma maneira unica de se escrever um numero natural quando comparado com um outro natural Ou seja se a e b forem naturais nao nulos entao a e de uma das formas excludentes abaixo com relacao a b a bq ou a bq1 ou a bq2 ou a bqb2 ou a bqb1 bastando para isto considerar os possıveis restos na divisao de a por b 0 1 2 b 1 Quando o resto e zero dizemos que a e um multiplo de b ou seja a e multiplo de b quando existe q N tal que a bq Problema 31 Mostre que se a N entao a2 e da forma 3k ou 3k 1 com k N Solucao Pelo que observamos acima a e de uma das formas ou i a 3q ou ii a 3q 1 ou ii a 3q 2 Deste modo analisando cada caso ou i a2 3q2 33q2 forma 3k ou ii a2 3q 12 33q2 2q 1 forma 3k1 ou ii a2 3q 22 3q2 4q 1 1 forma 3k1 fundam2Cpia 201061 1350 page 25 25 25 Problema 32 Dados 3 numeros naturais consecutivos um e somente um deles e multiplo de 3 Solucao Os numeros dados podem ser escritos como a a 1 e a 2 Mas o numero a pode ser dividido por 3 deixando um e somente um resto ou seja existe q N tal que a 3q r onde 0 r 3 O resto r pode ser 0 ou 1 ou 2 i Se r 0 entao temos a 3q ou seja a e multiplo de 3 ii Se r 1 entao temos a 3q 1 Assim a 2 3q3 3q 1 ou seja a 2 e multiplo de 3 iii Se r 2 entao temos a 3q 2 Assim a 1 3q3 3q 1 ou seja a 1 e multiplo de 3 Observe que apenas uma das possibilidades i ii ou iii pode ocorrer pela unicidade do resto na divisao euclidiana Problema 33 Mostre que dados n numeros naturais consecutivos um e somente um deles e multiplo de n Solucao Faca O Lema 31 pode ser generalizado para o conjunto dos numeros inteiros Z 2 1 0 1 2 Sabemos que este conjunto pode ser representado sobre uma reta escolhendo um ponto arbitrario como zero e associando pontos a direita deste para serem os numeros positivos e os da esquerda para serem os negativos 2 1 0 1 2 Recordemos ainda que o valor absoluto de um inteiro b e definido por b b se b 0 b se b 0 Observe ainda que para qualquer inteiro b o numero b e natural e b b Assim ao considerar b 0 podemos dividir a reta de numeros inteiros considerando a partir do zero segmentos de comprimento b como abaixo 2b b 0 b 2b fundamentos de álgebra I2012indd 31 26012012 180335 32 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 26 26 26 CAPITULO 3 AULA 3 LEMA DE EUCLIDES E importante notar que dados dois inteiros a e b com b 0 podemos ter a como um multiplo de b ou podemos localizar a entre dois multiplos consecutivos de b qb a q 1b Esta informacao pode ser expressa de duas maneiras a qb r com 0 r b 32 ou a q 1b r com b r 0 33 Exemplo 31 Para a 7 e b 5 temos q 2 e 2 5 7 1 5 ou seja 7 2 q 5 3 r1 0 r1 5 ou 7 1 q1 5 2 r2 5 r2 0 Para nao dar margem a duvidas escolhemos sempre o resto na forma 32 acima Desta maneira assim como no caso dos naturais vamos provar que temos dois inteiros q quociente e r resto que serao unicamente determinados desde que escolhamos o resto para ser nao negativo Agora podemos generalizar o Lema 31 no seguinte Lema 32 Euclides Dados dois inteiros a e b com b 0 existem inteiros q e r unicamente determinados tais que a bq r onde 0 r b Demonstracao A prova da existˆencia de q e r sera feita considerando os quatro casos possıveis abaixo Caso 1 a 0 e b 0 Caso 2 a 0 e b 0 Caso 3 a 0 e b 0 Caso 4 a 0 e b 0 Claramente nao e necessario provar o caso 1 pois este e exatamente o Lema 31 Para o caso 2 observamos que b b 0 e recorremos novamente ao Lema 31 Deste modo existem naturais q1 e r1 tais que a bq1 r1 onde 0 r1 b fundam2Cpia 201061 1350 page 27 27 27 Tomamos r r1 e q q1 obtemos a bq r dentro das condicoes exigidas ou seja 0 r b No caso 3 temos a 0 e assim a bq1 r1 com 0 r1 b Logo a bq1 r1 e deste modo se r1 0 tomamos r 0 e q q1 Mas se 0 r1 b entao 0 b r1 b Tomamos r b r1 e q q1 1 pois deste modo a bq1 r1 b b bq1 1 b r1 bq r onde 0 r b Finalmente para o caso 4 temos a a 0 e b b 0 e assim ao usar o Lema 31 sabemos que existem naturais q1 e r1 tais que a bq1 r1 onde 0 r1 b e portanto a bq1r1 Novamente se r1 0 tomamos r 0 e q q1 Mas se 0 r1 b entao 0 b r1 b Deste modo tomamos r b r1 e q q1 1 pois com isso temos a bq1 r1 b b bq1 1 b r1 bq r onde 0 r b Apos garantir a existˆencia do quociente e do resto na divisao euclidiana vamos garantir a unicidade supondo que podemos escrever a bq1 r1 e a bq2 r2 com 0 r1 r2 b Primeiramente como r1 e r2 sao ambos 0 note que r1 r2 r1 r1 b Por outro lado temos bq1 r1 bq2 r2 e assim r1 r2 bq2 q1 Portanto r1 r2 bq2 q1 Mas assim r1r2 e um multiplo de b e e menor que b consequentemente r1 r2 0 Logo r1 r2 e q1 q2 como querıamos mostrar Exemplo 32 Explicitamos o quociente e o resto da divisao em cada caso abaixo Para a 17 b 5 17 4 5 3 quociente 4 resto 3 Para a 17 b 5 17 3 5 2 quociente 3 resto 2 Para a 17 b 5 17 4 5 3 quociente 4 resto 3 Problema 34 Se a for um numero inteiro entao mostre que exatamente um dos numeros a2 ou a2 2 e multiplo de 3 Solucao De fato o Problema 31 tambem e verdadeiro quando a Z e assim a2 e da forma 3k ou 3k 1 para algum inteiro k Assim se a2 3k temos a2 multiplo de 3 enquanto que a22 nao e multiplo de 3 Mas se a2 3k 1 entao a2 2 3k 1 e multiplo de 3 e a2 nao o e fundamentos de álgebra I2012indd 32 26012012 180335 33 aula 3 fundam2Cpia 201061 1350 page 26 26 26 CAPITULO 3 AULA 3 LEMA DE EUCLIDES E importante notar que dados dois inteiros a e b com b 0 podemos ter a como um multiplo de b ou podemos localizar a entre dois multiplos consecutivos de b qb a q 1b Esta informacao pode ser expressa de duas maneiras a qb r com 0 r b 32 ou a q 1b r com b r 0 33 Exemplo 31 Para a 7 e b 5 temos q 2 e 2 5 7 1 5 ou seja 7 2 q 5 3 r1 0 r1 5 ou 7 1 q1 5 2 r2 5 r2 0 Para nao dar margem a duvidas escolhemos sempre o resto na forma 32 acima Desta maneira assim como no caso dos naturais vamos provar que temos dois inteiros q quociente e r resto que serao unicamente determinados desde que escolhamos o resto para ser nao negativo Agora podemos generalizar o Lema 31 no seguinte Lema 32 Euclides Dados dois inteiros a e b com b 0 existem inteiros q e r unicamente determinados tais que a bq r onde 0 r b Demonstracao A prova da existˆencia de q e r sera feita considerando os quatro casos possıveis abaixo Caso 1 a 0 e b 0 Caso 2 a 0 e b 0 Caso 3 a 0 e b 0 Caso 4 a 0 e b 0 Claramente nao e necessario provar o caso 1 pois este e exatamente o Lema 31 Para o caso 2 observamos que b b 0 e recorremos novamente ao Lema 31 Deste modo existem naturais q1 e r1 tais que a bq1 r1 onde 0 r1 b fundam2Cpia 201061 1350 page 27 27 27 Tomamos r r1 e q q1 obtemos a bq r dentro das condicoes exigidas ou seja 0 r b No caso 3 temos a 0 e assim a bq1 r1 com 0 r1 b Logo a bq1 r1 e deste modo se r1 0 tomamos r 0 e q q1 Mas se 0 r1 b entao 0 b r1 b Tomamos r b r1 e q q1 1 pois deste modo a bq1 r1 b b bq1 1 b r1 bq r onde 0 r b Finalmente para o caso 4 temos a a 0 e b b 0 e assim ao usar o Lema 31 sabemos que existem naturais q1 e r1 tais que a bq1 r1 onde 0 r1 b e portanto a bq1r1 Novamente se r1 0 tomamos r 0 e q q1 Mas se 0 r1 b entao 0 b r1 b Deste modo tomamos r b r1 e q q1 1 pois com isso temos a bq1 r1 b b bq1 1 b r1 bq r onde 0 r b Apos garantir a existˆencia do quociente e do resto na divisao euclidiana vamos garantir a unicidade supondo que podemos escrever a bq1 r1 e a bq2 r2 com 0 r1 r2 b Primeiramente como r1 e r2 sao ambos 0 note que r1 r2 r1 r1 b Por outro lado temos bq1 r1 bq2 r2 e assim r1 r2 bq2 q1 Portanto r1 r2 bq2 q1 Mas assim r1r2 e um multiplo de b e e menor que b consequentemente r1 r2 0 Logo r1 r2 e q1 q2 como querıamos mostrar Exemplo 32 Explicitamos o quociente e o resto da divisao em cada caso abaixo Para a 17 b 5 17 4 5 3 quociente 4 resto 3 Para a 17 b 5 17 3 5 2 quociente 3 resto 2 Para a 17 b 5 17 4 5 3 quociente 4 resto 3 Problema 34 Se a for um numero inteiro entao mostre que exatamente um dos numeros a2 ou a2 2 e multiplo de 3 Solucao De fato o Problema 31 tambem e verdadeiro quando a Z e assim a2 e da forma 3k ou 3k 1 para algum inteiro k Assim se a2 3k temos a2 multiplo de 3 enquanto que a22 nao e multiplo de 3 Mas se a2 3k 1 entao a2 2 3k 1 e multiplo de 3 e a2 nao o e fundamentos de álgebra I2012indd 33 26012012 180336 34 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 28 28 28 CAPITULO 3 AULA 3 LEMA DE EUCLIDES Exercıcios da Aula 3 1 Na divisao de dois inteiros positivos o quociente e 16 e o resto e o maior possıvel Se a soma do dividendo e do divisor for 125 determine o resto 2 Mostre que se a N entao a2 8c ou a2 8c 1 ou a2 8c 4 com c N 3 Se a Z prove que exatamente um dos numeros a a 9 a 18 ou a 27 e multiplo de 4 4 Mostre que o cubo de um natural n mais o seu dobro e sempre divisıvel por 3 5 Mostre que se a b Z forem tais que a2 ab b2 deixa resto 0 na divisao por 3 entao a e b deixam o mesmo resto na divisao por 3 6 Suponha que a seja um inteiro que e simultaneamente um quadrado e um cubo por exemplo para a 64 temos a 82 43 Prove que a e da forma 7k ou 7k 1 para algum inteiro k 7 Suponha que quando vocˆe divide um numero ımpar a por 3 o resto seja igual a 1 Qual sera o resto da divisao de a por 6 8 Quantos sao os numeros naturais n maiores que 0 e menores que 2006 tais que a expressao n3 n 6n 6 e um numero natural 9 Os restos das divisoes de 247 e 315 por x sao 7 e 3 respectivamente Determine o maior valor possıvel para x fundam2Cpia 201061 1350 page 29 29 Capıtulo 4 Aula 4 Divisibilidade Objetivos Trataremos mais cuidadosamente da condicao ser divisıvel por e estuda remos as propriedades da divisibilidade de inteiros Vamos tambem estudar alguns criterios de divisibilidade Como vimos o resto dado pela divisao euclidiana e unico Euclides observou que o caso em que este resto e zero merece particular atencao Vamos estudalo agora Definicao 41 Dados dois inteiros a e b dizemos que b divide a se existe um inteiro q tal que a bq Usaremos a notacao b a para indicar que b divide a Observacao importante Preste muita atencao b a informa que b divide a nao quer dizer b dividido por a ou seja nao indica o numero racional b a Por exemplo 2 6 pois 6 23 e nao expressa o racional 2 6 1 3 Portanto b a se e somente se q Z tal que a bq Isto equivale a dizer que o resto da divisao de a por b e zero Neste caso dizemos que b e um divisor de a ou que a e divisıvel por b ou ainda que a e um multiplo de b como ja foi usado no caso dos numeros naturais Outra observacao importante Quando demos a Definicao 41 nao nos preocupamos se os inteiros a e b eram nulos ou nao Note que com a nossa notacao temos o seguinte Para a 0 b 0 b 0 e verdade pois existe um inteiro q 0 tal que 0 a b 0 q Para a 0 b 0 0 a e falso pois nao existe um inteiro q tal que a 0 b q 29 exercícios fundamentos de álgebra I2012indd 34 26012012 180336 AULA 4 divisibilidade objetIvos Trataremos mais cuidadosamente da condição ser divisível por e estudaremos as propriedades da divisibilidade de inteiros Vamos também estudar alguns critérios de divisibilidade fundam2Cpia 201061 1350 page 28 28 28 CAPITULO 3 AULA 3 LEMA DE EUCLIDES Exercıcios da Aula 3 1 Na divisao de dois inteiros positivos o quociente e 16 e o resto e o maior possıvel Se a soma do dividendo e do divisor for 125 determine o resto 2 Mostre que se a N entao a2 8c ou a2 8c 1 ou a2 8c 4 com c N 3 Se a Z prove que exatamente um dos numeros a a 9 a 18 ou a 27 e multiplo de 4 4 Mostre que o cubo de um natural n mais o seu dobro e sempre divisıvel por 3 5 Mostre que se a b Z forem tais que a2 ab b2 deixa resto 0 na divisao por 3 entao a e b deixam o mesmo resto na divisao por 3 6 Suponha que a seja um inteiro que e simultaneamente um quadrado e um cubo por exemplo para a 64 temos a 82 43 Prove que a e da forma 7k ou 7k 1 para algum inteiro k 7 Suponha que quando vocˆe divide um numero ımpar a por 3 o resto seja igual a 1 Qual sera o resto da divisao de a por 6 8 Quantos sao os numeros naturais n maiores que 0 e menores que 2006 tais que a expressao n3 n 6n 6 e um numero natural 9 Os restos das divisoes de 247 e 315 por x sao 7 e 3 respectivamente Determine o maior valor possıvel para x fundam2Cpia 201061 1350 page 29 29 Capıtulo 4 Aula 4 Divisibilidade Objetivos Trataremos mais cuidadosamente da condicao ser divisıvel por e estuda remos as propriedades da divisibilidade de inteiros Vamos tambem estudar alguns criterios de divisibilidade Como vimos o resto dado pela divisao euclidiana e unico Euclides observou que o caso em que este resto e zero merece particular atencao Vamos estudalo agora Definicao 41 Dados dois inteiros a e b dizemos que b divide a se existe um inteiro q tal que a bq Usaremos a notacao b a para indicar que b divide a Observacao importante Preste muita atencao b a informa que b divide a nao quer dizer b dividido por a ou seja nao indica o numero racional b a Por exemplo 2 6 pois 6 23 e nao expressa o racional 2 6 1 3 Portanto b a se e somente se q Z tal que a bq Isto equivale a dizer que o resto da divisao de a por b e zero Neste caso dizemos que b e um divisor de a ou que a e divisıvel por b ou ainda que a e um multiplo de b como ja foi usado no caso dos numeros naturais Outra observacao importante Quando demos a Definicao 41 nao nos preocupamos se os inteiros a e b eram nulos ou nao Note que com a nossa notacao temos o seguinte Para a 0 b 0 b 0 e verdade pois existe um inteiro q 0 tal que 0 a b 0 q Para a 0 b 0 0 a e falso pois nao existe um inteiro q tal que a 0 b q 29 fundamentos de álgebra I2012indd 35 26012012 180337 36 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 30 30 30 CAPITULO 4 AULA 4 DIVISIBILIDADE O caso mais estranho ocorre quando a 0 e b 0 Sera que podemos escrever 0 0 Olhando para nossa definicao parece que sim pois para qualquer inteiro q temos 0 a 0 b q Novamente neste ultimo caso temos que tomar cuidado pois o que infor mamos nao foi que e possıvel escrever 0 0 e sim que e possıvel usar a notacao 0 0 Vamos evitar estes casos estranhos considerando os inteiros como nao nulos Proposicao 41 Se a b c Z forem nao nulos entao 1 Se a b e b c entao a c 2 Se a b e a c entao a b c e a b c 3 Se a b entao a bz para todo z Z 4 Se a b e a c entao a bz ct para quaisquer z t Z Demonstracao A propriedade 1 garante a transitividade e isto e claro pois se a b e b c entao q Z tal que b aq e k Z tal que c bk Assim c aqk com qk Z e portanto c e um multiplo de a ou seja a c Para provar a propriedade 2 basta ver que se a b e a c entao q Z tal que b aq e k Z tal que c ak Portanto b c aq ak aq k o que garante que a b c A propriedade 3 e obvia e a propriedade 4 decorre de 2 e 3 Problema 41 Como decidir se um dado natural e divisıvel por outro Solucao Em algumas situacoes e importante ter condicoes para responder a esta questao e isto e feito atraves dos criterios de divisibilidade Vamos determinar alguns deles a partir de agora Quando escrevemos um numero inteiro a anan1 a1a0 estamos expres sando que a an 10n a2 102 a1 101 a0 100 onde cada ai e um algarismo entre 0 e 9 ou seja a representacao posicional considerada esta num sistema de numeracao de base 10 Por exemplo 1358 1 103 3 102 5 101 8 100 Para as demonstracoes dos criterios de divisibilidade que faremos nesta secao estaremos sempre considerando que o numero em questao esta representado na base 10 fundam2Cpia 201061 1350 page 31 31 31 Proposicao 42 Divisibilidade por 2 Um numero natural a e divi sıvel por 2 se e somente se o algarismo das unidades de a for divisıvel por 2 Demonstracao Escrevemos a an 10n a2 102 a1 10 a0 onde 0 ai 9 Assim a 10an 10n1 a2 10 a1 a0 ou seja a e da forma 10k a0 Deste modo se 2 a entao como 2 10k vamos ter 2 a 10k a0 Reciprocamente se 2 a0 entao a0 2q para algum q Z e assim a 10an 10n1 a2 10 a1 2q 2 5an 10n1 a2 10 a1 q m com m Z e portanto 2 a Para garantir o criterio de divisibilidade por 3 primeiramente provamos um lema Lema 41 Para todo natural n 1 10n e da forma 3q 1 Demonstracao Vamos provar este resultado por inducao Claramente vale para n 1 pois 10 3 3 1 Suponhamos que vale para n k 1 Agora vamos mostrar que vale para n k 1 Temos 10k1 10k 10 3q 1 10 30q 10 91 3 10q 3 m 1 Proposicao 43 Divisibilidade por 3 Um numero natural a e divisı vel por 3 se e somente se a soma de seus algarismos for divisıvel por 3 Demonstracao Escrevemos a an 10n a2102 a1 10 a0 onde 0 ai 9 e usamos o lema anterior reescrevendo a an 3qn 1 a2 3q2 1 a1 3q1 1 a0 3 an qn a2 q2 a1 q1 c an a2 a1 a0 s isto e a 3c s e claramente 3 a se se somente se 3 s fundamentos de álgebra I2012indd 36 26012012 180338 37 aula 4 fundam2Cpia 201061 1350 page 30 30 30 CAPITULO 4 AULA 4 DIVISIBILIDADE O caso mais estranho ocorre quando a 0 e b 0 Sera que podemos escrever 0 0 Olhando para nossa definicao parece que sim pois para qualquer inteiro q temos 0 a 0 b q Novamente neste ultimo caso temos que tomar cuidado pois o que infor mamos nao foi que e possıvel escrever 0 0 e sim que e possıvel usar a notacao 0 0 Vamos evitar estes casos estranhos considerando os inteiros como nao nulos Proposicao 41 Se a b c Z forem nao nulos entao 1 Se a b e b c entao a c 2 Se a b e a c entao a b c e a b c 3 Se a b entao a bz para todo z Z 4 Se a b e a c entao a bz ct para quaisquer z t Z Demonstracao A propriedade 1 garante a transitividade e isto e claro pois se a b e b c entao q Z tal que b aq e k Z tal que c bk Assim c aqk com qk Z e portanto c e um multiplo de a ou seja a c Para provar a propriedade 2 basta ver que se a b e a c entao q Z tal que b aq e k Z tal que c ak Portanto b c aq ak aq k o que garante que a b c A propriedade 3 e obvia e a propriedade 4 decorre de 2 e 3 Problema 41 Como decidir se um dado natural e divisıvel por outro Solucao Em algumas situacoes e importante ter condicoes para responder a esta questao e isto e feito atraves dos criterios de divisibilidade Vamos determinar alguns deles a partir de agora Quando escrevemos um numero inteiro a anan1 a1a0 estamos expres sando que a an 10n a2 102 a1 101 a0 100 onde cada ai e um algarismo entre 0 e 9 ou seja a representacao posicional considerada esta num sistema de numeracao de base 10 Por exemplo 1358 1 103 3 102 5 101 8 100 Para as demonstracoes dos criterios de divisibilidade que faremos nesta secao estaremos sempre considerando que o numero em questao esta representado na base 10 fundam2Cpia 201061 1350 page 31 31 31 Proposicao 42 Divisibilidade por 2 Um numero natural a e divi sıvel por 2 se e somente se o algarismo das unidades de a for divisıvel por 2 Demonstracao Escrevemos a an 10n a2 102 a1 10 a0 onde 0 ai 9 Assim a 10an 10n1 a2 10 a1 a0 ou seja a e da forma 10k a0 Deste modo se 2 a entao como 2 10k vamos ter 2 a 10k a0 Reciprocamente se 2 a0 entao a0 2q para algum q Z e assim a 10an 10n1 a2 10 a1 2q 2 5an 10n1 a2 10 a1 q m com m Z e portanto 2 a Para garantir o criterio de divisibilidade por 3 primeiramente provamos um lema Lema 41 Para todo natural n 1 10n e da forma 3q 1 Demonstracao Vamos provar este resultado por inducao Claramente vale para n 1 pois 10 3 3 1 Suponhamos que vale para n k 1 Agora vamos mostrar que vale para n k 1 Temos 10k1 10k 10 3q 1 10 30q 10 91 3 10q 3 m 1 Proposicao 43 Divisibilidade por 3 Um numero natural a e divisı vel por 3 se e somente se a soma de seus algarismos for divisıvel por 3 Demonstracao Escrevemos a an 10n a2102 a1 10 a0 onde 0 ai 9 e usamos o lema anterior reescrevendo a an 3qn 1 a2 3q2 1 a1 3q1 1 a0 3 an qn a2 q2 a1 q1 c an a2 a1 a0 s isto e a 3c s e claramente 3 a se se somente se 3 s fundamentos de álgebra I2012indd 37 26012012 180338 38 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 32 32 32 CAPITULO 4 AULA 4 DIVISIBILIDADE Proposicao 44 Divisibilidade por 9 Um numero natural e divisıvel por 9 se e somente se a soma dos seus algarismos for um numero divisıvel por 9 Demonstracao A prova e analoga a que fizemos para garantir a divisibi lidade por 3 usando o seguinte resultado que vocˆe pode provar facilmente como foi feito no Lema 41 Para todo natural n 1 o inteiro 10n e da forma 9q 1 Antes de enunciar o criterio de divisibilidade por 11 vamos provar um lema parecido com o Lema 41 Lema 42 Para todo natural n 1 10n e da forma 11q 1n Demonstracao Usaremos inducao para provar este resultado Claramente vale para n 1 pois 10 11 1 Vamos supor que vale para n k 1 e vamos mostrar que vale para n k 1 Temos 10k1 10k 10 11q 1k 10 11q 10 1k 10 111 11 10q 11 1k 11k 11 10q1k m 1k1 Proposicao 45 Divisibilidade por 11 Um natural a anan1 a1a0 e divisıvel por 11 se e somente se a soma alternada dos seus algarismos a0 a1 a2 1nan for um numero divisıvel por 11 Demonstracao Temos a an 10n a2 102 a1 10 a0 onde 0 ai 9 e usando o lema anterior escrevemos a an 11qn 1n a2 11q2 12 a1 11q1 1 a0 11 an qn a2 q2 a1 q1 k a0 a1 a2 1nan t isto e a 11k t e claramente 11 a se se somente se 11 t fundam2Cpia 201061 1350 page 33 33 33 Problema 42 Fica como exercıcio a demonstracao dos criterios abaixo e a pesquisa por outros que nao foram citados Divisibilidade por 4 Um numero natural e divisıvel por 4 se e somente se o numero formado pelos seus dois ultimos algarismos for divisıvel por 4 Divisibilidade por 5 Um numero natural e divisıvel por 5 se e somente se o seu ultimo algarismo e 0 ou 5 Divisibilidade por 6 Um numero natural e divisıvel por 6 se e somente se ele e par e a soma de seus algarismos e divisıvel por 3 fundam2Cpia 201061 1350 page 32 32 32 CAPITULO 4 AULA 4 DIVISIBILIDADE Proposicao 44 Divisibilidade por 9 Um numero natural e divisıvel por 9 se e somente se a soma dos seus algarismos for um numero divisıvel por 9 Demonstracao A prova e analoga a que fizemos para garantir a divisibi lidade por 3 usando o seguinte resultado que vocˆe pode provar facilmente como foi feito no Lema 41 Para todo natural n 1 o inteiro 10n e da forma 9q 1 Antes de enunciar o criterio de divisibilidade por 11 vamos provar um lema parecido com o Lema 41 Lema 42 Para todo natural n 1 10n e da forma 11q 1n Demonstracao Usaremos inducao para provar este resultado Claramente vale para n 1 pois 10 11 1 Vamos supor que vale para n k 1 e vamos mostrar que vale para n k 1 Temos 10k1 10k 10 11q 1k 10 11q 10 1k 10 111 11 10q 11 1k 11k 11 10q1k m 1k1 Proposicao 45 Divisibilidade por 11 Um natural a anan1 a1a0 e divisıvel por 11 se e somente se a soma alternada dos seus algarismos a0 a1 a2 1nan for um numero divisıvel por 11 Demonstracao Temos a an 10n a2 102 a1 10 a0 onde 0 ai 9 e usando o lema anterior escrevemos a an 11qn 1n a2 11q2 12 a1 11q1 1 a0 11 an qn a2 q2 a1 q1 k a0 a1 a2 1nan t isto e a 11k t e claramente 11 a se se somente se 11 t fundam2Cpia 201061 1350 page 32 32 32 CAPITULO 4 AULA 4 DIVISIBILIDADE Proposicao 44 Divisibilidade por 9 Um numero natural e divisıvel por 9 se e somente se a soma dos seus algarismos for um numero divisıvel por 9 Demonstracao A prova e analoga a que fizemos para garantir a divisibi lidade por 3 usando o seguinte resultado que vocˆe pode provar facilmente como foi feito no Lema 41 Para todo natural n 1 o inteiro 10n e da forma 9q 1 Antes de enunciar o criterio de divisibilidade por 11 vamos provar um lema parecido com o Lema 41 Lema 42 Para todo natural n 1 10n e da forma 11q 1n Demonstracao Usaremos inducao para provar este resultado Claramente vale para n 1 pois 10 11 1 Vamos supor que vale para n k 1 e vamos mostrar que vale para n k 1 Temos 10k1 10k 10 11q 1k 10 11q 10 1k 10 111 11 10q 11 1k 11k 11 10q1k m 1k1 Proposicao 45 Divisibilidade por 11 Um natural a anan1 a1a0 e divisıvel por 11 se e somente se a soma alternada dos seus algarismos a0 a1 a2 1nan for um numero divisıvel por 11 Demonstracao Temos a an 10n a2 102 a1 10 a0 onde 0 ai 9 e usando o lema anterior escrevemos a an 11qn 1n a2 11q2 12 a1 11q1 1 a0 11 an qn a2 q2 a1 q1 k a0 a1 a2 1nan t isto e a 11k t e claramente 11 a se se somente se 11 t fundam2Cpia 201061 1350 page 32 32 32 CAPITULO 4 AULA 4 DIVISIBILIDADE Proposicao 44 Divisibilidade por 9 Um numero natural e divisıvel por 9 se e somente se a soma dos seus algarismos for um numero divisıvel por 9 Demonstracao A prova e analoga a que fizemos para garantir a divisibi lidade por 3 usando o seguinte resultado que vocˆe pode provar facilmente como foi feito no Lema 41 Para todo natural n 1 o inteiro 10n e da forma 9q 1 Antes de enunciar o criterio de divisibilidade por 11 vamos provar um lema parecido com o Lema 41 Lema 42 Para todo natural n 1 10n e da forma 11q 1n Demonstracao Usaremos inducao para provar este resultado Claramente vale para n 1 pois 10 11 1 Vamos supor que vale para n k 1 e vamos mostrar que vale para n k 1 Temos 10k1 10k 10 11q 1k 10 11q 10 1k 10 111 11 10q 11 1k 11k 11 10q1k m 1k1 Proposicao 45 Divisibilidade por 11 Um natural a anan1 a1a0 e divisıvel por 11 se e somente se a soma alternada dos seus algarismos a0 a1 a2 1nan for um numero divisıvel por 11 Demonstracao Temos a an 10n a2 102 a1 10 a0 onde 0 ai 9 e usando o lema anterior escrevemos a an 11qn 1n a2 11q2 12 a1 11q1 1 a0 11 an qn a2 q2 a1 q1 k a0 a1 a2 1nan t isto e a 11k t e claramente 11 a se se somente se 11 t fundam2Cpia 201061 1350 page 32 32 32 CAPITULO 4 AULA 4 DIVISIBILIDADE Proposicao 44 Divisibilidade por 9 Um numero natural e divisıvel por 9 se e somente se a soma dos seus algarismos for um numero divisıvel por 9 Demonstracao A prova e analoga a que fizemos para garantir a divisibi lidade por 3 usando o seguinte resultado que vocˆe pode provar facilmente como foi feito no Lema 41 Para todo natural n 1 o inteiro 10n e da forma 9q 1 Antes de enunciar o criterio de divisibilidade por 11 vamos provar um lema parecido com o Lema 41 Lema 42 Para todo natural n 1 10n e da forma 11q 1n Demonstracao Usaremos inducao para provar este resultado Claramente vale para n 1 pois 10 11 1 Vamos supor que vale para n k 1 e vamos mostrar que vale para n k 1 Temos 10k1 10k 10 11q 1k 10 11q 10 1k 10 111 11 10q 11 1k 11k 11 10q1k m 1k1 Proposicao 45 Divisibilidade por 11 Um natural a anan1 a1a0 e divisıvel por 11 se e somente se a soma alternada dos seus algarismos a0 a1 a2 1nan for um numero divisıvel por 11 Demonstracao Temos a an 10n a2 102 a1 10 a0 onde 0 ai 9 e usando o lema anterior escrevemos a an 11qn 1n a2 11q2 12 a1 11q1 1 a0 11 an qn a2 q2 a1 q1 k a0 a1 a2 1nan t isto e a 11k t e claramente 11 a se se somente se 11 t fundamentos de álgebra I2012indd 38 26012012 180340 39 aula 4 fundam2Cpia 201061 1350 page 33 33 33 Problema 42 Fica como exercıcio a demonstracao dos criterios abaixo e a pesquisa por outros que nao foram citados Divisibilidade por 4 Um numero natural e divisıvel por 4 se e somente se o numero formado pelos seus dois ultimos algarismos for divisıvel por 4 Divisibilidade por 5 Um numero natural e divisıvel por 5 se e somente se o seu ultimo algarismo e 0 ou 5 Divisibilidade por 6 Um numero natural e divisıvel por 6 se e somente se ele e par e a soma de seus algarismos e divisıvel por 3 fundam2Cpia 201061 1350 page 32 32 32 CAPITULO 4 AULA 4 DIVISIBILIDADE Proposicao 44 Divisibilidade por 9 Um numero natural e divisıvel por 9 se e somente se a soma dos seus algarismos for um numero divisıvel por 9 Demonstracao A prova e analoga a que fizemos para garantir a divisibi lidade por 3 usando o seguinte resultado que vocˆe pode provar facilmente como foi feito no Lema 41 Para todo natural n 1 o inteiro 10n e da forma 9q 1 Antes de enunciar o criterio de divisibilidade por 11 vamos provar um lema parecido com o Lema 41 Lema 42 Para todo natural n 1 10n e da forma 11q 1n Demonstracao Usaremos inducao para provar este resultado Claramente vale para n 1 pois 10 11 1 Vamos supor que vale para n k 1 e vamos mostrar que vale para n k 1 Temos 10k1 10k 10 11q 1k 10 11q 10 1k 10 111 11 10q 11 1k 11k 11 10q1k m 1k1 Proposicao 45 Divisibilidade por 11 Um natural a anan1 a1a0 e divisıvel por 11 se e somente se a soma alternada dos seus algarismos a0 a1 a2 1nan for um numero divisıvel por 11 Demonstracao Temos a an 10n a2 102 a1 10 a0 onde 0 ai 9 e usando o lema anterior escrevemos a an 11qn 1n a2 11q2 12 a1 11q1 1 a0 11 an qn a2 q2 a1 q1 k a0 a1 a2 1nan t isto e a 11k t e claramente 11 a se se somente se 11 t fundam2Cpia 201061 1350 page 32 32 32 CAPITULO 4 AULA 4 DIVISIBILIDADE Proposicao 44 Divisibilidade por 9 Um numero natural e divisıvel por 9 se e somente se a soma dos seus algarismos for um numero divisıvel por 9 Demonstracao A prova e analoga a que fizemos para garantir a divisibi lidade por 3 usando o seguinte resultado que vocˆe pode provar facilmente como foi feito no Lema 41 Para todo natural n 1 o inteiro 10n e da forma 9q 1 Antes de enunciar o criterio de divisibilidade por 11 vamos provar um lema parecido com o Lema 41 Lema 42 Para todo natural n 1 10n e da forma 11q 1n Demonstracao Usaremos inducao para provar este resultado Claramente vale para n 1 pois 10 11 1 Vamos supor que vale para n k 1 e vamos mostrar que vale para n k 1 Temos 10k1 10k 10 11q 1k 10 11q 10 1k 10 111 11 10q 11 1k 11k 11 10q1k m 1k1 Proposicao 45 Divisibilidade por 11 Um natural a anan1 a1a0 e divisıvel por 11 se e somente se a soma alternada dos seus algarismos a0 a1 a2 1nan for um numero divisıvel por 11 Demonstracao Temos a an 10n a2 102 a1 10 a0 onde 0 ai 9 e usando o lema anterior escrevemos a an 11qn 1n a2 11q2 12 a1 11q1 1 a0 11 an qn a2 q2 a1 q1 k a0 a1 a2 1nan t isto e a 11k t e claramente 11 a se se somente se 11 t fundam2Cpia 201061 1350 page 32 32 32 CAPITULO 4 AULA 4 DIVISIBILIDADE Proposicao 44 Divisibilidade por 9 Um numero natural e divisıvel por 9 se e somente se a soma dos seus algarismos for um numero divisıvel por 9 Demonstracao A prova e analoga a que fizemos para garantir a divisibi lidade por 3 usando o seguinte resultado que vocˆe pode provar facilmente como foi feito no Lema 41 Para todo natural n 1 o inteiro 10n e da forma 9q 1 Antes de enunciar o criterio de divisibilidade por 11 vamos provar um lema parecido com o Lema 41 Lema 42 Para todo natural n 1 10n e da forma 11q 1n Demonstracao Usaremos inducao para provar este resultado Claramente vale para n 1 pois 10 11 1 Vamos supor que vale para n k 1 e vamos mostrar que vale para n k 1 Temos 10k1 10k 10 11q 1k 10 11q 10 1k 10 111 11 10q 11 1k 11k 11 10q1k m 1k1 Proposicao 45 Divisibilidade por 11 Um natural a anan1 a1a0 e divisıvel por 11 se e somente se a soma alternada dos seus algarismos a0 a1 a2 1nan for um numero divisıvel por 11 Demonstracao Temos a an 10n a2 102 a1 10 a0 onde 0 ai 9 e usando o lema anterior escrevemos a an 11qn 1n a2 11q2 12 a1 11q1 1 a0 11 an qn a2 q2 a1 q1 k a0 a1 a2 1nan t isto e a 11k t e claramente 11 a se se somente se 11 t fundamentos de álgebra I2012indd 39 26012012 180341 40 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 35 35 Capıtulo 5 Aula 5 Numeros Primos Objetivos Nesta aula nos preocuparemos com alguns numeros que sao especiais os numeros primos Veremos como estes se distribuem na sequˆencia de numeros naturais e a importˆancia destes numeros na vida moderna No Livro VII de Os elementos de Euclides encontrase a definicao de numeros primos Claramente dado qualquer numero inteiro n os numeros 1 n 1 e n sao divisores inteiros de n Vamos nos preocupar apenas com os divi sores positivos de n A pergunta e se existem outros alem de 1 e n Definicao 51 Um numero inteiro n 1 e primo se seus unicos divisores positivos sao 1 e n Assim n e primo se a n a 0 entao a 1 ou a n Caso o numero n 1 nao seja primo dizemos que ele e composto ou seja n e composto existe a n a 0 tal que a 1 e a n Neste caso n ab onde a e b sao inteiros e 1 a b n Note que o numero 1 nao e classificado nem como primo nem como composto Claro que 2 e um numero primo e e o unico primo que e par Nao e difıcil dar outros exemplos de numeros primos podemos listar os iniciais 2 3 5 7 11 13 17 19 e chegar ate certo ponto sem problemas mas podemos questionar se e possıvel determinar uma formula para gerar numeros primos ou seja Problema 51 E possıvel determinar uma funcao f tal que dado um numero natural nao nulo n fn seja um numero primo Solucao Vamos responder a esta questao considerando as situacoes em que isto pode ocorrer ou nao 35 fundam2Cpia 201061 1350 page 34 34 34 CAPITULO 4 AULA 4 DIVISIBILIDADE Exercıcios da Aula 4 1 Algumas das afirmacoes abaixo sao falsas F e outras sao verdadeiras V Em todas elas a b c d sao inteiros nao nulos Argumente convenientemente para verificar quais sao V e quais sao F a Se d a e d b entao d2 ab b a c e b d entao a b c d c a c e b d entao ab cd d a b c d entao a c e b d e d a e d b entao d a2 b2 f d a9 b e d a entao d b 2 Mostre que se a for um inteiro a2 2 nao e divisıvel por 4 3 Prove que se a N nao for divisıvel por 2 e tambem nao for divisıvel por 3 entao a2 1 e divisıvel por 24 4 Demonstre os criterios de divisibilidade por 4 por 5 e por 6 5 Determine criterios de divisibilidade por 7 por 8 e por 10 6 Mostre que um numero natural com trˆes algarismos todos eles iguais e divisıvel por 37 7 Mostre que para todo n 1 8 32n 1 sugestao use PIM 8 Mostre que se a for um inteiro que deixa resto 3 na divisao por 6 entao 72 a2 9 exercícios fundamentos de álgebra I2012indd 40 26012012 180342 AULA 5 números primos objetIvos Nesta aula nos preocuparemos com alguns números que são especiais os números primos Veremos como estes se distribuem na sequência de números naturais e a importância destes números na vida moderna fundam2Cpia 201061 1350 page 35 35 Capıtulo 5 Aula 5 Numeros Primos Objetivos Nesta aula nos preocuparemos com alguns numeros que sao especiais os numeros primos Veremos como estes se distribuem na sequˆencia de numeros naturais e a importˆancia destes numeros na vida moderna No Livro VII de Os elementos de Euclides encontrase a definicao de numeros primos Claramente dado qualquer numero inteiro n os numeros 1 n 1 e n sao divisores inteiros de n Vamos nos preocupar apenas com os divi sores positivos de n A pergunta e se existem outros alem de 1 e n Definicao 51 Um numero inteiro n 1 e primo se seus unicos divisores positivos sao 1 e n Assim n e primo se a n a 0 entao a 1 ou a n Caso o numero n 1 nao seja primo dizemos que ele e composto ou seja n e composto existe a n a 0 tal que a 1 e a n Neste caso n ab onde a e b sao inteiros e 1 a b n Note que o numero 1 nao e classificado nem como primo nem como composto Claro que 2 e um numero primo e e o unico primo que e par Nao e difıcil dar outros exemplos de numeros primos podemos listar os iniciais 2 3 5 7 11 13 17 19 e chegar ate certo ponto sem problemas mas podemos questionar se e possıvel determinar uma formula para gerar numeros primos ou seja Problema 51 E possıvel determinar uma funcao f tal que dado um numero natural nao nulo n fn seja um numero primo Solucao Vamos responder a esta questao considerando as situacoes em que isto pode ocorrer ou nao 35 fundam2Cpia 201061 1350 page 34 34 34 CAPITULO 4 AULA 4 DIVISIBILIDADE Exercıcios da Aula 4 1 Algumas das afirmacoes abaixo sao falsas F e outras sao verdadeiras V Em todas elas a b c d sao inteiros nao nulos Argumente convenientemente para verificar quais sao V e quais sao F a Se d a e d b entao d2 ab b a c e b d entao a b c d c a c e b d entao ab cd d a b c d entao a c e b d e d a e d b entao d a2 b2 f d a9 b e d a entao d b 2 Mostre que se a for um inteiro a2 2 nao e divisıvel por 4 3 Prove que se a N nao for divisıvel por 2 e tambem nao for divisıvel por 3 entao a2 1 e divisıvel por 24 4 Demonstre os criterios de divisibilidade por 4 por 5 e por 6 5 Determine criterios de divisibilidade por 7 por 8 e por 10 6 Mostre que um numero natural com trˆes algarismos todos eles iguais e divisıvel por 37 7 Mostre que para todo n 1 8 32n 1 sugestao use PIM 8 Mostre que se a for um inteiro que deixa resto 3 na divisao por 6 entao 72 a2 9 fundamentos de álgebra I2012indd 41 26012012 180342 42 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 37 37 37 Demonstracao Para provar este resultado usamos a segunda forma do PIM Se n 2 e claro que o resultado vale Suponhamos que k 2 e que o resultado vale para 2 m k ou seja dado qualquer natural m entre 2 e k m possui um divisor primo Vamos provar que vale para n k 1 Se k 1 for primo nao temos nada a fazer Caso contrario k 1 tem um divisor d tal que 1 d k 1 Deste modo usando a hipotese de inducao d possui um divisor primo e como este sera tambem divisor primo de k 1 o resultado esta demonstrado Problema 53 Existe uma maneira de testar se um numero e primo Solucao Existe uma grande quantidade de testes de primalidade que ga rantem se um determinado numero e primo ou nao Podemos exemplificar um destes testes com o resultado abaixo Proposicao 51 Se n for um numero natural composto entao n possui pelo menos um divisor primo p n Demonstracao Para um numero composto n existem divisores 1 a b n tais que n ab Alem disso nao podemos ter simultaneamente a n e b n caso contrario n ab nn n o que e absurdo Logo pelo menos um dos divisores digamos que seja a tem que ser n Mas pela proposicao anterior a possui um divisor primo e assim concluımos que n possui um divisor primo n Desta forma o resultado anterior nos informa que para um dado numero natural n 2 se constatarmos que todos os primos p n nao sao divisores de n entao podemos concluir que n e primo O inconveniente do teste acima e que se o numero for muito grande deter minar todos os primos anteriores a ele pode ser uma tarefa extremamente difıcil De fato mais a frente veremos como e o comportamento da funcao que da a quantidade de primos ate um inteiro fixado Uma lista de numeros primos Segundo a tradicao a primeira tabela de numeros primos foi criada pelo matematico grego Eratostenes c 285 194 aC o terceiro bibliotecariochefe da Biblioteca de Alexandria Ele desenvolveu um procedimento que mais tarde passou a se chamar de crivo de Eratostenes Vamos exemplificar o crivo determinando a lista de numeros primos entre 1 e 100 Inicialmente determinase o maior numero a ser checado Ele corresponde a raiz quadrada do valor limite arredondado para baixo de acordo com a Proposicao 51 No nosso caso a raiz de 100 que e 10 Em seguida faca o seguinte Crie uma lista de todos os numeros inteiros de 2 ate o valor limite 2 3 99 100 fundam2Cpia 201061 1350 page 36 36 36 CAPITULO 5 AULA 5 N UMEROS PRIMOS O celebre matematico Pierre de Fermat 16011665 saiu em busca de uma formula para primos e conjecturou que todos os numeros da forma Fn 22n 1 onde n e um inteiro positivo sao primos Por exemplo F1 5 F2 17 F3 257 F4 65537 sao todos primos Porem em 1732 Leonhard Euler 17071783 mostrou que F5 um inteiro de 10 algarismos e divisıvel por 641 e portanto nao e primo Um resultado bem conhecido da algebra afirma que nao existe um poli nˆomio com coeficientes racionais que produza somente numeros primos Embora estabeleca uma limitacao para a geracao de numeros primos este resultado nao exclui a existˆencia de a funcoes polinomiais em uma variavel que gere numeros primos mas nao todos b funcoes nao polinomiais que gerem numeros primos todos ou nao c funcoes polinomiais em mais de uma variavel que produzam numeros primos todos ou nao Muitos professores e estudantes de matematica desconhecem o fato de que existem funcoes com cada uma das caracterısticas acima como nos seguintes exemplos a Considere a funcao fn n2 n41 com n sendo um numero natural Ja sabemos que esta formula nao pode produzir todos os primos pois e um polinˆomio em uma variavel com coeficientes inteiros Mas o fato curioso e que para n 1 2 3 40 temos fn primo enquanto que para n 41 temse f41 412 ou seja nao e primo b Um exemplo do segundo tipo e a funcao dada em 1971 pelo matematico J M Gandhi que fornece o nesimo numero primo em funcao dos n 1 primos anteriores pn 1 1 log 2 log 1 2 dAn1 µd 2d 1 onde pn e o nesimo numero primo An1 p1p2pn1 e o produto dos n 1 primeiros primos x denota o maior inteiro menor ou igual a x e µ e funcao de Mobius dada por µn 1m caso n seja igual ao produto de m primos distintos q1 qm e µn 0 caso contrario c Exemplo em httpwwwmatpucriobr nicolaupapersmersenne node18html Problema 52 Qual o menor divisor positivo diferente de 1 de a 235 E de b 344 E de c 91 Solucao Note que as respostas sao d1 5 para a d2 2 para b e d3 7 para c Em qualquer caso foi um numero primo De fato temos que Teorema 51 Se n 2 for um numero natural entao n possui um divsor que e um numero primo fundamentos de álgebra I2012indd 42 26012012 180343 43 aula 5 fundam2Cpia 201061 1350 page 37 37 37 Demonstracao Para provar este resultado usamos a segunda forma do PIM Se n 2 e claro que o resultado vale Suponhamos que k 2 e que o resultado vale para 2 m k ou seja dado qualquer natural m entre 2 e k m possui um divisor primo Vamos provar que vale para n k 1 Se k 1 for primo nao temos nada a fazer Caso contrario k 1 tem um divisor d tal que 1 d k 1 Deste modo usando a hipotese de inducao d possui um divisor primo e como este sera tambem divisor primo de k 1 o resultado esta demonstrado Problema 53 Existe uma maneira de testar se um numero e primo Solucao Existe uma grande quantidade de testes de primalidade que ga rantem se um determinado numero e primo ou nao Podemos exemplificar um destes testes com o resultado abaixo Proposicao 51 Se n for um numero natural composto entao n possui pelo menos um divisor primo p n Demonstracao Para um numero composto n existem divisores 1 a b n tais que n ab Alem disso nao podemos ter simultaneamente a n e b n caso contrario n ab nn n o que e absurdo Logo pelo menos um dos divisores digamos que seja a tem que ser n Mas pela proposicao anterior a possui um divisor primo e assim concluımos que n possui um divisor primo n Desta forma o resultado anterior nos informa que para um dado numero natural n 2 se constatarmos que todos os primos p n nao sao divisores de n entao podemos concluir que n e primo O inconveniente do teste acima e que se o numero for muito grande deter minar todos os primos anteriores a ele pode ser uma tarefa extremamente difıcil De fato mais a frente veremos como e o comportamento da funcao que da a quantidade de primos ate um inteiro fixado Uma lista de numeros primos Segundo a tradicao a primeira tabela de numeros primos foi criada pelo matematico grego Eratostenes c 285 194 aC o terceiro bibliotecariochefe da Biblioteca de Alexandria Ele desenvolveu um procedimento que mais tarde passou a se chamar de crivo de Eratostenes Vamos exemplificar o crivo determinando a lista de numeros primos entre 1 e 100 Inicialmente determinase o maior numero a ser checado Ele corresponde a raiz quadrada do valor limite arredondado para baixo de acordo com a Proposicao 51 No nosso caso a raiz de 100 que e 10 Em seguida faca o seguinte Crie uma lista de todos os numeros inteiros de 2 ate o valor limite 2 3 99 100 fundam2Cpia 201061 1350 page 36 36 36 CAPITULO 5 AULA 5 N UMEROS PRIMOS O celebre matematico Pierre de Fermat 16011665 saiu em busca de uma formula para primos e conjecturou que todos os numeros da forma Fn 22n 1 onde n e um inteiro positivo sao primos Por exemplo F1 5 F2 17 F3 257 F4 65537 sao todos primos Porem em 1732 Leonhard Euler 17071783 mostrou que F5 um inteiro de 10 algarismos e divisıvel por 641 e portanto nao e primo Um resultado bem conhecido da algebra afirma que nao existe um poli nˆomio com coeficientes racionais que produza somente numeros primos Embora estabeleca uma limitacao para a geracao de numeros primos este resultado nao exclui a existˆencia de a funcoes polinomiais em uma variavel que gere numeros primos mas nao todos b funcoes nao polinomiais que gerem numeros primos todos ou nao c funcoes polinomiais em mais de uma variavel que produzam numeros primos todos ou nao Muitos professores e estudantes de matematica desconhecem o fato de que existem funcoes com cada uma das caracterısticas acima como nos seguintes exemplos a Considere a funcao fn n2 n41 com n sendo um numero natural Ja sabemos que esta formula nao pode produzir todos os primos pois e um polinˆomio em uma variavel com coeficientes inteiros Mas o fato curioso e que para n 1 2 3 40 temos fn primo enquanto que para n 41 temse f41 412 ou seja nao e primo b Um exemplo do segundo tipo e a funcao dada em 1971 pelo matematico J M Gandhi que fornece o nesimo numero primo em funcao dos n 1 primos anteriores pn 1 1 log 2 log 1 2 dAn1 µd 2d 1 onde pn e o nesimo numero primo An1 p1p2pn1 e o produto dos n 1 primeiros primos x denota o maior inteiro menor ou igual a x e µ e funcao de Mobius dada por µn 1m caso n seja igual ao produto de m primos distintos q1 qm e µn 0 caso contrario c Exemplo em httpwwwmatpucriobr nicolaupapersmersenne node18html Problema 52 Qual o menor divisor positivo diferente de 1 de a 235 E de b 344 E de c 91 Solucao Note que as respostas sao d1 5 para a d2 2 para b e d3 7 para c Em qualquer caso foi um numero primo De fato temos que Teorema 51 Se n 2 for um numero natural entao n possui um divsor que e um numero primo fundamentos de álgebra I2012indd 43 26012012 180343 44 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 38 38 38 CAPITULO 5 AULA 5 N UMEROS PRIMOS Encontre o primeiro numero da lista Ele e um numero primo 2 Remova da lista todos os multiplos do numero primo encontrado exceto o proprio numero No nosso exemplo a lista fica formada de 2 seguido de todos os ımpares ate 99 O proximo numero da lista e primo 3 Repita o procedimento removendo seus multiplos a lista fica 2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97 O proximo numero 5 tambem e primo repetindo o processo sucessivamente ate o ultimo numero a ser checado ou seja ate 10 a lista contendo todos os primos ate 100 sera 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 No Livro IX dos Elementos Euclides provou um importante resultado sobre a quantidade de primos existentes Teorema 52 Existem infinitos numeros primos Demonstracao Uma simples demonstracao pode ser dada por absurdo considerando que temos um numero finito de numeros primos e que p1 p2 pk sejam todos os primos existentes O inteiro m p1 p2 pk 1 nao e primo pois nao e igual a nenhum dos listados Portanto pelo Teorema 51 possui um divisor primo Porem este divisor nao e nenhum dos primos ja considerados pois caso seja algum dos pi temos pi p1 p2 pk 1 mas como pi p1 p2 pk chegarıamos ao absurdo que pi 1 Com este argumento garantimos que existem infinitos numeros primos Problema 54 Como os numeros primos se distribuem entre os naturais Solucao O problema da distribuicao dos primos entre os naturais foi con siderado por Gauss 17771855 que estudou o comportamento de uma funcao que fornece a quantidade de primos ate um fixado inteiro x Ele fez uma conjectura sobre esta funcao que foi provada por Hadamard e Poussin em 1896 Teorema 53 Se πx denota o numero de primos menores ou iguais a um dado inteiro x entao lim x πx log x x 1 Pelo teorema se x for muito grande temos πx x log x Exemplo 51 Vamos ver como se comportam os primos no intervalo 10100 10101 Para determinalos fazemos o seguinte Geramos um ımpar b 10100 10101 Verificamos se ele e primo Se nao for testamos b2 e assim por diante ate encontrarmos um primo fundam2Cpia 201061 1350 page 39 39 39 A questao e em media quantos serao os numeros testados ate encontrarmos um numero primo Pelo Teorema 53 temos π10100 10100 log 10100 π10101 10101 log 10101 Logo a probabilidade de um b ımpar no intervalo ser primo e π10100 π10101 2102 log 10 1 115 ou seja deverao ser gerados cerca de 115 numerosımpares no intervalo antes que um primo seja encontrado Problema 55 Para que precisamos determinar primos tao grandes Solucao Atualmente os fatores primos de numeros monstruosos sao usa dos como chaves de criptografia kryptos oculto graphos escrever que fazem parte da seguranca nacional de muitos paıses Isto porque ao multiplicarmos dois primos tremendamente grandes podemos considerar uma mensagem criptografada cuja quebra do sigilo consiste em fatorar o numero obtido e o processo de fatoracao neste caso pode ser praticamente impossıvel Exemplo 52 O numero 2193 1 e um numero gigantesco Seus fatores primos sao p 13821503 q 61654440233248340616559 r 14732265321145317331353282383 Para um numero da ordem de 10130 um computador comum levaria 50 anos para efetuar a sua fatoracao E para um numero da ordem de 10308 mesmo com os esforcos combinados de 100 milhoes de computadores seriam necessarios mais de 1000 anos Problema 56 Mostre que dado um numero natural n existe uma sequˆencia de n naturais con secutivos todos compostos Solucao Este problema parece incrıvel pois quando o numero n e muito grande temos uma sequˆencia enorme de numeros consecutivos onde nenhum deles e primo O problema pode ser resolvido ao verificarmos que os n numeros consecu tivos n 1 2 n 1 3 n 1 4 n 1 n n 1 n 1 sao todos compostos pois 2 divide n 1 2 3 divide n 1 3 n divide n 1 n e n 1 divide n 1 n 1 fundamentos de álgebra I2012indd 44 26012012 180344 45 aula 5 fundam2Cpia 201061 1350 page 38 38 38 CAPITULO 5 AULA 5 N UMEROS PRIMOS Encontre o primeiro numero da lista Ele e um numero primo 2 Remova da lista todos os multiplos do numero primo encontrado exceto o proprio numero No nosso exemplo a lista fica formada de 2 seguido de todos os ımpares ate 99 O proximo numero da lista e primo 3 Repita o procedimento removendo seus multiplos a lista fica 2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97 O proximo numero 5 tambem e primo repetindo o processo sucessivamente ate o ultimo numero a ser checado ou seja ate 10 a lista contendo todos os primos ate 100 sera 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 No Livro IX dos Elementos Euclides provou um importante resultado sobre a quantidade de primos existentes Teorema 52 Existem infinitos numeros primos Demonstracao Uma simples demonstracao pode ser dada por absurdo considerando que temos um numero finito de numeros primos e que p1 p2 pk sejam todos os primos existentes O inteiro m p1 p2 pk 1 nao e primo pois nao e igual a nenhum dos listados Portanto pelo Teorema 51 possui um divisor primo Porem este divisor nao e nenhum dos primos ja considerados pois caso seja algum dos pi temos pi p1 p2 pk 1 mas como pi p1 p2 pk chegarıamos ao absurdo que pi 1 Com este argumento garantimos que existem infinitos numeros primos Problema 54 Como os numeros primos se distribuem entre os naturais Solucao O problema da distribuicao dos primos entre os naturais foi con siderado por Gauss 17771855 que estudou o comportamento de uma funcao que fornece a quantidade de primos ate um fixado inteiro x Ele fez uma conjectura sobre esta funcao que foi provada por Hadamard e Poussin em 1896 Teorema 53 Se πx denota o numero de primos menores ou iguais a um dado inteiro x entao lim x πx log x x 1 Pelo teorema se x for muito grande temos πx x log x Exemplo 51 Vamos ver como se comportam os primos no intervalo 10100 10101 Para determinalos fazemos o seguinte Geramos um ımpar b 10100 10101 Verificamos se ele e primo Se nao for testamos b2 e assim por diante ate encontrarmos um primo fundam2Cpia 201061 1350 page 39 39 39 A questao e em media quantos serao os numeros testados ate encontrarmos um numero primo Pelo Teorema 53 temos π10100 10100 log 10100 π10101 10101 log 10101 Logo a probabilidade de um b ımpar no intervalo ser primo e π10100 π10101 2102 log 10 1 115 ou seja deverao ser gerados cerca de 115 numerosımpares no intervalo antes que um primo seja encontrado Problema 55 Para que precisamos determinar primos tao grandes Solucao Atualmente os fatores primos de numeros monstruosos sao usa dos como chaves de criptografia kryptos oculto graphos escrever que fazem parte da seguranca nacional de muitos paıses Isto porque ao multiplicarmos dois primos tremendamente grandes podemos considerar uma mensagem criptografada cuja quebra do sigilo consiste em fatorar o numero obtido e o processo de fatoracao neste caso pode ser praticamente impossıvel Exemplo 52 O numero 2193 1 e um numero gigantesco Seus fatores primos sao p 13821503 q 61654440233248340616559 r 14732265321145317331353282383 Para um numero da ordem de 10130 um computador comum levaria 50 anos para efetuar a sua fatoracao E para um numero da ordem de 10308 mesmo com os esforcos combinados de 100 milhoes de computadores seriam necessarios mais de 1000 anos Problema 56 Mostre que dado um numero natural n existe uma sequˆencia de n naturais con secutivos todos compostos Solucao Este problema parece incrıvel pois quando o numero n e muito grande temos uma sequˆencia enorme de numeros consecutivos onde nenhum deles e primo O problema pode ser resolvido ao verificarmos que os n numeros consecu tivos n 1 2 n 1 3 n 1 4 n 1 n n 1 n 1 sao todos compostos pois 2 divide n 1 2 3 divide n 1 3 n divide n 1 n e n 1 divide n 1 n 1 fundamentos de álgebra I2012indd 45 26012012 180344 46 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 40 40 40 CAPITULO 5 AULA 5 N UMEROS PRIMOS Numeros de Mersenne Marin Mersenne 15881648 estudou os numeros da forma Mn 2n 1 sendo n um numero primo Esses numeros sao chamados de numeros de Mersenne Sao conhecidos numeros de Mersenne tanto primos como com postos Por exemplo M2 3 M3 7 M5 31 M7 127 sao numeros primos enquanto M11 23 89 e composto Atualmente o maior numero primo conhecido e o primo de Mersenne 243112609 1 descoberto no dia 23 de agosto de 2008 num projeto de computacao distri buıdo pela internet o GIMPS que usa o tempo ocioso do processador de computadores pessoais procurando por numeros primos especıficos do tipo 2p1 em que p e primo O ultimo primo encontrado e o primo de Mersenne de numero 46 e tem 12978189 dıgitos Problemas a respeito de numeros primos encantam a humanidade ha muitos seculos muitos deles ainda estao em aberto ou seja nao foram provados ate hoje Vejamos alguns exemplos Definicao 52 Dois numeros primos dizemse gˆemeos se a sua diferenca for 2 Os primeiros pares de numeros primos gˆemeos sao 3 5 5 7 11 13 17 19 29 31 41 43 59 61 71 73 101 103 107 109 sequˆencia A001097 na OEIS veja Moreira Saldanha 1999 Os maiores numeros primos gˆemeos conhecidos sao 2003663613 2195000 1 descobertos em janeiro de 2007 Problema 57 em aberto Existe uma infinidade de numeros primos gˆemeos Este problema e muito antigo tendo Euclides conjecturado que sim Esta conjectura e chamada de conjectura dos primos gˆemeos Definicao 53 Um numero de Fermat Fn 22n 1 n N que e primo e dito um primo de Fermat Ate hoje sao conhecidos apenas cinco numeros primos de Fermat F0 F1 F2 F3 F4 Todos os numeros de Fermat Fn para 5 n 23 assim como numeros enormes tais como F23288 e F23471 sao comprovadamente compostos Problema 58 em aberto Serao finitos os numeros primos de Fermat Se forem finitos quantos sao fundam2Cpia 201061 1350 page 41 41 41 Exercıcios da Aula 5 1 Encontre todos os primos p e q tais que p q 3 2 Trˆes naturais ımpares consecutivos sao primos Mostre que estes numeros sao 3 5 e 7 3 Verifique se 38567 e um numero primo 4 Mostre que n4 4 e sempre um numero composto quando n Z e n 1 5 Verifique se e verdadeiro ou falso justificando a Se a e b forem ımpares entao a b nao e primo b Se a b for um primo 2 entao a e b nao podem ser simultaneamente ımpares c Se a e b forem dois primos e a b tambem e primo entao a 2 e b 3 6 Mostre que se a soma de dois primos gˆemeos for igual a 24 entao um dos primos e 13 7 Determine primos gˆemeos p e q tais que p2 q2 34 8 Mostre que a soma de dois primos gˆemeos p e p 2 com p 3 e um multiplo de 12 9 Se a 1 e a2 2 for um numero primo entao mostre que a e um multiplo de 3 fundamentos de álgebra I2012indd 46 26012012 180345 47 aula 5 fundam2Cpia 201061 1350 page 40 40 40 CAPITULO 5 AULA 5 N UMEROS PRIMOS Numeros de Mersenne Marin Mersenne 15881648 estudou os numeros da forma Mn 2n 1 sendo n um numero primo Esses numeros sao chamados de numeros de Mersenne Sao conhecidos numeros de Mersenne tanto primos como com postos Por exemplo M2 3 M3 7 M5 31 M7 127 sao numeros primos enquanto M11 23 89 e composto Atualmente o maior numero primo conhecido e o primo de Mersenne 243112609 1 descoberto no dia 23 de agosto de 2008 num projeto de computacao distri buıdo pela internet o GIMPS que usa o tempo ocioso do processador de computadores pessoais procurando por numeros primos especıficos do tipo 2p1 em que p e primo O ultimo primo encontrado e o primo de Mersenne de numero 46 e tem 12978189 dıgitos Problemas a respeito de numeros primos encantam a humanidade ha muitos seculos muitos deles ainda estao em aberto ou seja nao foram provados ate hoje Vejamos alguns exemplos Definicao 52 Dois numeros primos dizemse gˆemeos se a sua diferenca for 2 Os primeiros pares de numeros primos gˆemeos sao 3 5 5 7 11 13 17 19 29 31 41 43 59 61 71 73 101 103 107 109 sequˆencia A001097 na OEIS veja Moreira Saldanha 1999 Os maiores numeros primos gˆemeos conhecidos sao 2003663613 2195000 1 descobertos em janeiro de 2007 Problema 57 em aberto Existe uma infinidade de numeros primos gˆemeos Este problema e muito antigo tendo Euclides conjecturado que sim Esta conjectura e chamada de conjectura dos primos gˆemeos Definicao 53 Um numero de Fermat Fn 22n 1 n N que e primo e dito um primo de Fermat Ate hoje sao conhecidos apenas cinco numeros primos de Fermat F0 F1 F2 F3 F4 Todos os numeros de Fermat Fn para 5 n 23 assim como numeros enormes tais como F23288 e F23471 sao comprovadamente compostos Problema 58 em aberto Serao finitos os numeros primos de Fermat Se forem finitos quantos sao fundam2Cpia 201061 1350 page 41 41 41 Exercıcios da Aula 5 1 Encontre todos os primos p e q tais que p q 3 2 Trˆes naturais ımpares consecutivos sao primos Mostre que estes numeros sao 3 5 e 7 3 Verifique se 38567 e um numero primo 4 Mostre que n4 4 e sempre um numero composto quando n Z e n 1 5 Verifique se e verdadeiro ou falso justificando a Se a e b forem ımpares entao a b nao e primo b Se a b for um primo 2 entao a e b nao podem ser simultaneamente ımpares c Se a e b forem dois primos e a b tambem e primo entao a 2 e b 3 6 Mostre que se a soma de dois primos gˆemeos for igual a 24 entao um dos primos e 13 7 Determine primos gˆemeos p e q tais que p2 q2 34 8 Mostre que a soma de dois primos gˆemeos p e p 2 com p 3 e um multiplo de 12 9 Se a 1 e a2 2 for um numero primo entao mostre que a e um multiplo de 3 exercícios fundamentos de álgebra I2012indd 47 26012012 180345 fundam2Cpia 201061 1350 page 43 43 Capıtulo 6 Aula 6 Teorema Fundamental de Aritmetica Objetivos Vamos demonstrar o Teorema Fundamental da Aritmetica que e um dos principais teoremas a respeito de numeros primos Vamos apresentar tambem importantes aplicacoes que podemos fazer com o uso deste Os gregos foram os primeiros a perceber que qualquer numero natural ex ceto o 0 e o 1 pode ser gerado pela multiplicacao de numeros primos os chamados blocos de construcao Ou seja um numero natural n 2 pode ser escrito como um produto de primos e e claro a ordenacao dos primos neste produto nao modifica o resultado A demonstracao deste fato foi dada por Euclides que provou apenas a existˆencia da fatoracao de um natural em primos Acreditase que Euclides conhecesse a unicidade desta fatoracao e que nao fez sua demonstracao pela dificuldade em estabelecer uma notacao adequada No proximo teorema provaremos a existˆencia e a unicidade da fatoracao de um natural em primos utilizando o Princıpio de Inducao Matematica Teorema 61 Teorema Fundamental de Aritmetica TFA Dado um numero natural n 2 existem primos distintos p1 p2 pk tais que n pα1 1 pα2 2 pαk k onde os expoentes αi sao naturais 1 i k Alem disso se n qβ1 1 qβ2 2 qβt t onde qj sao primos distintos 1 j t entao t k e todo qj e igual a algum pi Demonstracao Usaremos a segunda forma do PIM para garantir a existˆen cia da fatoracao Para n 2 existe uma decomposicao trivial em numeros primos ja que 2 ja e um numero primo Consideremos k 2 e suponhamos que existe uma fatoracao para todo natural m tal que 2 m k Mostraremos agora que tambem vale para k 1 e como consequˆencia te remos que o resultado vale para todo n 2 43 fundamentos de álgebra I2012indd 48 26012012 180345 AULA 6 teorema fundamental da aritmética objetIvos Vamos demonstrar o Teorema Fundamental da Aritmética que é um dos principais teoremas a respeito de números primos Vamos apresentar também importantes aplicações que podemos fazer com o uso deste fundam2Cpia 201061 1350 page 43 43 Capıtulo 6 Aula 6 Teorema Fundamental de Aritmetica Objetivos Vamos demonstrar o Teorema Fundamental da Aritmetica que e um dos principais teoremas a respeito de numeros primos Vamos apresentar tambem importantes aplicacoes que podemos fazer com o uso deste Os gregos foram os primeiros a perceber que qualquer numero natural ex ceto o 0 e o 1 pode ser gerado pela multiplicacao de numeros primos os chamados blocos de construcao Ou seja um numero natural n 2 pode ser escrito como um produto de primos e e claro a ordenacao dos primos neste produto nao modifica o resultado A demonstracao deste fato foi dada por Euclides que provou apenas a existˆencia da fatoracao de um natural em primos Acreditase que Euclides conhecesse a unicidade desta fatoracao e que nao fez sua demonstracao pela dificuldade em estabelecer uma notacao adequada No proximo teorema provaremos a existˆencia e a unicidade da fatoracao de um natural em primos utilizando o Princıpio de Inducao Matematica Teorema 61 Teorema Fundamental de Aritmetica TFA Dado um numero natural n 2 existem primos distintos p1 p2 pk tais que n pα1 1 pα2 2 pαk k onde os expoentes αi sao naturais 1 i k Alem disso se n qβ1 1 qβ2 2 qβt t onde qj sao primos distintos 1 j t entao t k e todo qj e igual a algum pi Demonstracao Usaremos a segunda forma do PIM para garantir a existˆen cia da fatoracao Para n 2 existe uma decomposicao trivial em numeros primos ja que 2 ja e um numero primo Consideremos k 2 e suponhamos que existe uma fatoracao para todo natural m tal que 2 m k Mostraremos agora que tambem vale para k 1 e como consequˆencia te remos que o resultado vale para todo n 2 43 fundamentos de álgebra I2012indd 49 26012012 180346 50 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 44 44 44CAPITULO 6 AULA 6 TEOREMA FUNDAMENTAL DE ARITMETICA Se k 1 for primo admite a decomposicao trivial Caso contrario k 1 pode ser escrito como k 1 ab onde 1 a k 1 e 1 b k 1 Assim 2 a k e 2 b k e pela hipotese de inducao a e b podem ser escritos como produtos de primos Logo o resultado tambem vale para k 1 Para provar a unicidade devemos garantir que um natural n 2 nao admite mais de uma fatoracao em produto de fatores primos Esta demonstracao tambem sera feita usando a segunda forma do PIM Claro que n 2 possui uma unica fatoracao Vamos considerar k 2 e assumir que qualquer natural m tal que 2 m k tem uma fatoracao unica como produto de primos Agora suponhamos que k 1 tenha duas fatoracoes distintas como produto de primos os primos nao sao necessariamente distintos k 1 p1 pr q1 qs 61 Reordenando os primos se necessario podemos supor que p1 pr e q1 qs Note que p1 q1 pois se tivessemos p1 q1 entao o natural k1 p1 k teria duas fatoracoes distintas com produto de primos contrariando a hipotese de inducao Se assumimos sem perda de generalidade que p1 q1 e considerarmos o inteiro m k 1 p1q2 qs entao m k 1 e a partir de 61 temos que m se escreve como m p1p2 pr p1q2 qs e tambem como m q1q2 qs p1q2 qs Deste modo m p1p2 pr q2 qs 62 e m q1 p1q2 qs 63 Por 62 temos m 2 pois p1 m e assim ja que 2 m k por hipotese de inducao m tem fatoracao unica em primos Deste modo o primo p1 deve estar presente no produto em 63 pois esta presente em 62 e como p1 q1 qs devemos ter p1 como fator de q1 p1 ou seja p1 q1 p1 Portanto existe c Z tal que q1 p1 cp1 e com isso q1 c1p1 o que e absurdo pois p1 e q1 sao primos distintos Com esta contradicao concluımos que k 1 nao possui duas fatoracoes distintas como produto de primos o que mostra que qualquer natural n 2 tem uma fatoracao unica como produto de primos de acordo com a segunda forma do PIM fundam2Cpia 201061 1350 page 45 45 45 Problema 61 Mostre que nao existe um primo cujo dobro seja igual a um quadrado perfeito menos 1 Solucao Para resolver suponhamos que exista um primo p tal que 2p n2 1 Mas entao 2p n 1n 1 e assim usando o TFA 1 n 1 2 n 1 p ou 2 n 1 2 n 1 p Se 1 ocorre entao n 1 e p 0 o que e um absurdo Se 2 ocorre entao n 3 e assim p 4 o que e igualmente um absurdo Logo tal primo nao existe Problema 62 A quarta potˆencia de um natural e igual ao triplo de um primo p mais 1 Que primo e este Solucao Neste caso temos n4 3p 1 e assim 3p n4 1 ou seja 3p n2 1n2 1 Pelo TFA devemos ter 1 n2 1 3 n2 1 p ou 2 n2 1 3 n2 1 p No caso 1 temos n2 2 o que ja e um absurdo No caso 2 temos n2 4 ou seja n 2 e consequentemente p 5 Se nao prestarmos atencao quando analisarmos certas questoes sobre divi sibilidade poderemos cometer erros Por exemplo dados naturais a b e c e verdade que se c ab entao c a ou c b 64 Isto nao e sempre verdade Tomemos como exemplo c 12 a 6 e b 4 Claro que 12 c divide 24 ab mas 12 c nao divide 6 a e 12 c nao divide 4 b Como consequˆencia do TFA temos que 64 vale quando c p e um primo Corolario 61 Se p e primo tal que p ab entao p a ou p b Demonstracao Se p ab entao p e um primo que aparece na fatoracao de ab Quando fatoramos a e b em primos o primo p tem que aparecer em pelo menos uma das fatoracoes devido a unicidade garantida pelo TFA Ou seja p a ou p b Corolario 62 Se p for um primo tal que p ab mas p nao divide a entao p b fundamentos de álgebra I2012indd 50 26012012 180346 51 aula 6 fundam2Cpia 201061 1350 page 44 44 44CAPITULO 6 AULA 6 TEOREMA FUNDAMENTAL DE ARITMETICA Se k 1 for primo admite a decomposicao trivial Caso contrario k 1 pode ser escrito como k 1 ab onde 1 a k 1 e 1 b k 1 Assim 2 a k e 2 b k e pela hipotese de inducao a e b podem ser escritos como produtos de primos Logo o resultado tambem vale para k 1 Para provar a unicidade devemos garantir que um natural n 2 nao admite mais de uma fatoracao em produto de fatores primos Esta demonstracao tambem sera feita usando a segunda forma do PIM Claro que n 2 possui uma unica fatoracao Vamos considerar k 2 e assumir que qualquer natural m tal que 2 m k tem uma fatoracao unica como produto de primos Agora suponhamos que k 1 tenha duas fatoracoes distintas como produto de primos os primos nao sao necessariamente distintos k 1 p1 pr q1 qs 61 Reordenando os primos se necessario podemos supor que p1 pr e q1 qs Note que p1 q1 pois se tivessemos p1 q1 entao o natural k1 p1 k teria duas fatoracoes distintas com produto de primos contrariando a hipotese de inducao Se assumimos sem perda de generalidade que p1 q1 e considerarmos o inteiro m k 1 p1q2 qs entao m k 1 e a partir de 61 temos que m se escreve como m p1p2 pr p1q2 qs e tambem como m q1q2 qs p1q2 qs Deste modo m p1p2 pr q2 qs 62 e m q1 p1q2 qs 63 Por 62 temos m 2 pois p1 m e assim ja que 2 m k por hipotese de inducao m tem fatoracao unica em primos Deste modo o primo p1 deve estar presente no produto em 63 pois esta presente em 62 e como p1 q1 qs devemos ter p1 como fator de q1 p1 ou seja p1 q1 p1 Portanto existe c Z tal que q1 p1 cp1 e com isso q1 c1p1 o que e absurdo pois p1 e q1 sao primos distintos Com esta contradicao concluımos que k 1 nao possui duas fatoracoes distintas como produto de primos o que mostra que qualquer natural n 2 tem uma fatoracao unica como produto de primos de acordo com a segunda forma do PIM fundam2Cpia 201061 1350 page 45 45 45 Problema 61 Mostre que nao existe um primo cujo dobro seja igual a um quadrado perfeito menos 1 Solucao Para resolver suponhamos que exista um primo p tal que 2p n2 1 Mas entao 2p n 1n 1 e assim usando o TFA 1 n 1 2 n 1 p ou 2 n 1 2 n 1 p Se 1 ocorre entao n 1 e p 0 o que e um absurdo Se 2 ocorre entao n 3 e assim p 4 o que e igualmente um absurdo Logo tal primo nao existe Problema 62 A quarta potˆencia de um natural e igual ao triplo de um primo p mais 1 Que primo e este Solucao Neste caso temos n4 3p 1 e assim 3p n4 1 ou seja 3p n2 1n2 1 Pelo TFA devemos ter 1 n2 1 3 n2 1 p ou 2 n2 1 3 n2 1 p No caso 1 temos n2 2 o que ja e um absurdo No caso 2 temos n2 4 ou seja n 2 e consequentemente p 5 Se nao prestarmos atencao quando analisarmos certas questoes sobre divi sibilidade poderemos cometer erros Por exemplo dados naturais a b e c e verdade que se c ab entao c a ou c b 64 Isto nao e sempre verdade Tomemos como exemplo c 12 a 6 e b 4 Claro que 12 c divide 24 ab mas 12 c nao divide 6 a e 12 c nao divide 4 b Como consequˆencia do TFA temos que 64 vale quando c p e um primo Corolario 61 Se p e primo tal que p ab entao p a ou p b Demonstracao Se p ab entao p e um primo que aparece na fatoracao de ab Quando fatoramos a e b em primos o primo p tem que aparecer em pelo menos uma das fatoracoes devido a unicidade garantida pelo TFA Ou seja p a ou p b Corolario 62 Se p for um primo tal que p ab mas p nao divide a entao p b fundamentos de álgebra I2012indd 51 26012012 180347 52 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 46 46 46CAPITULO 6 AULA 6 TEOREMA FUNDAMENTAL DE ARITMETICA Exercıcios da Aula 6 1 Determine se e verdadeiro V ou falso F Justifique a Se p e um primo tal que p3 ab e p2 a entao p b b Se um primo p a2 b2 e p a entao p b c Se um primo p a b entao p a e p b d Se a divide um primo p entao a e primo 2 Responda com justificativa O triplo de um numero primo p e igual ao quadrado de um inteiro n menos 16 Que primo e este 3 Seja n um numero natural 1 Mostre que se n divide n 1 1 entao n e um numero primo 4 Seja n 5 um numero composto Mostre que n n 1 5 Mostre que se o triplo de um numero primo p e igual ao quadrado de um numero natural n menos 4 entao p so pode ser o primo 7 6 Mostre que todo inteiro positivo da forma 3k 2 tem um fator primo da mesma forma 7 Mostre que a Todo numero natural ımpar e da forma 4k 1 ou 4k 1 onde k N b Todo numero da forma 4k 1 possui pelo menos um divisor primo desta mesma forma c Existem infinitos primos da forma 4k 1 8 Seja a pα1 1 pα2 2 pαk k onde p1 p2 pk sao primos distintos e os expoentes αi sao naturais 1 i k a Mostre que todos os divisores positivos b de a sao da forma b pβ1 1 pβ2 2 pβk k em que 0 βi αi para todo 1 i k b Conclua que o numero dos divisores positivos de a incluindo 1 e a e dado pelo produto α1 1α2 1 αk 1 9 Se pn denota o nesimo primo entao prove que nao existe x Z tal que p1p2pn 1 x2 10 Suponha que p seja o menor fator primo de um inteiro n e que p np Prove que np e primo fundam2Cpia 201061 1350 page 47 47 Capıtulo 7 Aula 7 Maximo Divisor Comum Objetivos Estudaremos os divisores comuns de dois inteiros e veremos como calcular o maior dentre estes divisores o maximo divisor comum MDC Destaca remos as diversas propriedades do MDC entre dois inteiros Quando temos dois inteiros a e b podemos nos perguntar sobre seus divisores e multiplos comuns ou seja divisores simultˆaneos de a e b e multiplos simultˆaneos de a e b Claro que 1 e um divisor comum de a e b a questao e se existem outros e qual e o maior destes divisores Tambem podemos notar que ab e um multiplo comum de a e b e novamente nos perguntamos qual e o menor destes multiplos Foi no Livro VII de Os elementos que Euclides definiu o maximo divisor comum de dois inteiros conforme abaixo Definicao 71 Dados dois inteiros a e b nao simultaneamente nulos di zemos que um inteiro d e o maximo divisor comum de a e b e escrevemos d mdca b se i d a e d b ii Se existe um inteiro c tal que c a e c b entao c d Uma consequˆencia imediata da definicao acima e que mdca b 0 o MDC e o maior divisor comum e e claro que se x e divisor de a e b entao x tambem o e Alem disso mdca b mdcb a pois nao faz diferenca se trocamos a por b na Definicao 71 Definicao 72 Quando a e b sao inteiros tais que mdca b 1 entao dizemos que a e b sao primos entre si ou relativamente primos Exemplo 71 Se p e q forem primos distintos entao eles sao relativamente primos Isto e claro pois os divisores positivos de p sao 1 e p e os divisores positivos de q sao 1 e q Como p e q sao distintos com certeza p nao divide q e viceversa e portanto mdcp q 1 47 exercícios fundamentos de álgebra I2012indd 52 26012012 180348 AULA 7 máximo divisor comum objetIvos Estudaremos os divisores comuns de dois inteiros e veremos como calcular o maior dentre estes divisores o máximo divisor comum MDC Destacaremos as diversas propriedades do MDC entre dois inteiros fundam2Cpia 201061 1350 page 46 46 46CAPITULO 6 AULA 6 TEOREMA FUNDAMENTAL DE ARITMETICA Exercıcios da Aula 6 1 Determine se e verdadeiro V ou falso F Justifique a Se p e um primo tal que p3 ab e p2 a entao p b b Se um primo p a2 b2 e p a entao p b c Se um primo p a b entao p a e p b d Se a divide um primo p entao a e primo 2 Responda com justificativa O triplo de um numero primo p e igual ao quadrado de um inteiro n menos 16 Que primo e este 3 Seja n um numero natural 1 Mostre que se n divide n 1 1 entao n e um numero primo 4 Seja n 5 um numero composto Mostre que n n 1 5 Mostre que se o triplo de um numero primo p e igual ao quadrado de um numero natural n menos 4 entao p so pode ser o primo 7 6 Mostre que todo inteiro positivo da forma 3k 2 tem um fator primo da mesma forma 7 Mostre que a Todo numero natural ımpar e da forma 4k 1 ou 4k 1 onde k N b Todo numero da forma 4k 1 possui pelo menos um divisor primo desta mesma forma c Existem infinitos primos da forma 4k 1 8 Seja a pα1 1 pα2 2 pαk k onde p1 p2 pk sao primos distintos e os expoentes αi sao naturais 1 i k a Mostre que todos os divisores positivos b de a sao da forma b pβ1 1 pβ2 2 pβk k em que 0 βi αi para todo 1 i k b Conclua que o numero dos divisores positivos de a incluindo 1 e a e dado pelo produto α1 1α2 1 αk 1 9 Se pn denota o nesimo primo entao prove que nao existe x Z tal que p1p2pn 1 x2 10 Suponha que p seja o menor fator primo de um inteiro n e que p np Prove que np e primo fundam2Cpia 201061 1350 page 47 47 Capıtulo 7 Aula 7 Maximo Divisor Comum Objetivos Estudaremos os divisores comuns de dois inteiros e veremos como calcular o maior dentre estes divisores o maximo divisor comum MDC Destaca remos as diversas propriedades do MDC entre dois inteiros Quando temos dois inteiros a e b podemos nos perguntar sobre seus divisores e multiplos comuns ou seja divisores simultˆaneos de a e b e multiplos simultˆaneos de a e b Claro que 1 e um divisor comum de a e b a questao e se existem outros e qual e o maior destes divisores Tambem podemos notar que ab e um multiplo comum de a e b e novamente nos perguntamos qual e o menor destes multiplos Foi no Livro VII de Os elementos que Euclides definiu o maximo divisor comum de dois inteiros conforme abaixo Definicao 71 Dados dois inteiros a e b nao simultaneamente nulos di zemos que um inteiro d e o maximo divisor comum de a e b e escrevemos d mdca b se i d a e d b ii Se existe um inteiro c tal que c a e c b entao c d Uma consequˆencia imediata da definicao acima e que mdca b 0 o MDC e o maior divisor comum e e claro que se x e divisor de a e b entao x tambem o e Alem disso mdca b mdcb a pois nao faz diferenca se trocamos a por b na Definicao 71 Definicao 72 Quando a e b sao inteiros tais que mdca b 1 entao dizemos que a e b sao primos entre si ou relativamente primos Exemplo 71 Se p e q forem primos distintos entao eles sao relativamente primos Isto e claro pois os divisores positivos de p sao 1 e p e os divisores positivos de q sao 1 e q Como p e q sao distintos com certeza p nao divide q e viceversa e portanto mdcp q 1 47 fundamentos de álgebra I2012indd 53 26012012 180348 54 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 48 48 48 CAPITULO 7 AULA 7 M AXIMO DIVISOR COMUM Problema 71 Se a for um inteiro nao nulo qual e o mdca 0 Solucao Um divisor comum de a e 0 e a lembre que a 0 pois 0 a 0 Como mdca 0 0 devemos ter mdca 0 a Problema 72 Se p for um primo e a 0 e inteiro quais os possıveis valores para mdca p Solucao Neste caso mdca p 1 ou mdca p p pois este deve ser um divisor de p que e primo Como consequˆencia se p nao divide a entao mdca p 1 Problema 73 Devemos nos preocupar com numeros negativos Solucao Vamos ver que nao atraves deste exemplo Divisores de 12 Divisores de 12 1 2 3 4 6 12 1 2 3 4 6 12 Divisores de 18 Divisores de 18 1 2 3 6 9 18 1 2 3 6 9 18 Com isso temos mdc12 18 mdc12 18 mdc12 18 mdc12 18 6 O problema anterior pode ser resolvido geralmente com o resultado abaixo Proposicao 71 Se a e b forem inteiros nao nulos entao 1 mdca b mdca b 2 mdca b mina b Demonstracao A prova do item 1 e trivial pois os divisores comuns de a e b sao os mesmos divisores comuns de a e b Alem disso se d mdca b entao d e positivo e como divide a e tambem divide b com certeza vamos ter d a e d b provando o item 2 Para calcular o maximo divisor comum de dois inteiros podemos utilizar a fatoracao de cada um deles em primos dada pelo TFA Vejamos como isto pode ser feito no proximo resultado Proposicao 72 Se a pα1 1 pαk k rγ1 1 rγt t e b pβ1 1 pβk k sλ1 1 sλl l onde p1 pk r1 rt s1 sl sao primos distintos e os expoentes αi γj βi λv sao naturais 1 i k 1 j t 1 v l entao mdca b pθ1 1 pθk k onde θi minαi βi para i 1 k fundam2Cpia 201061 1350 page 49 49 49 Demonstracao Vamos mostrar que o inteiro d pθ1 1 pθk k com θi minαi βi i 1 k satisfaz os itens i e ii da Definicao 71 Como para todo i 1 k θi αi e θi βi temos αi θi 0 e βi θi 0 e assim os numeros a1 pα1θ1 1 pαkθk k e b1 pβ1θ1 1 pβkθk k sao naturais e alem disso a a1d e b b1d ou seja d a e d b o que garante o item i Agora para provar o item ii consideramos um inteiro c tal que c a e c b Desta forma a e b sao multiplos de c e assim pelo Teorema Fundamental da Aritmetica os primos que aparecem na fatoracao de c devem estar presentes tanto na fatoracao de a quanto na fatoracao de b Como os unicos primos comuns nas fatoracoes de a e b sao os p i teremos c pε1 1 pεk k com 0 εi minαi βi i 1 k portanto εi θi o que mostra que c d e finaliza a demonstracao deste resultado Exemplo 72 Temos 1508 22 13 29 e 442 2 13 17 Neste caso mdc1508 422 2 13 pois o maximo divisor comum e dado pelos primos comuns com menor expoente O metodo acima nao e sempre conveniente pois como ja observamos na Aula 5 a fatoracao pode ser muito difıcil quando trabalhamos com numeros grandes Existe um procedimento pratico que permite o calculo do maximo divisor comum de dois inteiros sem passar pela fatoracao em primos que esta presente em Os elementos de Euclides e e conhecido como algoritmo de Euclides Primeiramente vamos ver um exemplo Exemplo 73 Temos 221 2 91 39 ou seja o resto da divisao de 221 por 91 e 39 e notamos tambem que mdc221 91 mdc91 39 13 No exemplo anterior vimos que o maximo divisor comum de a 221 e b 91 e igual ao maximo divisor comum de b e o resto da divisao de a por b Isto ocorre de maneira geral Proposicao 73 Se a bqr onde 0 r b entao mdca b mdcb r Demonstracao Suponhamos que d mdca b Queremos mostrar que d mdcb r Usando a definicao de mdc ja temos que d a e d b Desta forma como r a bq vamos ter d r Logo ja concluımos que d e um divisor comum de b e r precisamos garantir agora que ele seja o maior de todos os divisores fundamentos de álgebra I2012indd 54 26012012 180349 55 aula 7 fundam2Cpia 201061 1350 page 48 48 48 CAPITULO 7 AULA 7 M AXIMO DIVISOR COMUM Problema 71 Se a for um inteiro nao nulo qual e o mdca 0 Solucao Um divisor comum de a e 0 e a lembre que a 0 pois 0 a 0 Como mdca 0 0 devemos ter mdca 0 a Problema 72 Se p for um primo e a 0 e inteiro quais os possıveis valores para mdca p Solucao Neste caso mdca p 1 ou mdca p p pois este deve ser um divisor de p que e primo Como consequˆencia se p nao divide a entao mdca p 1 Problema 73 Devemos nos preocupar com numeros negativos Solucao Vamos ver que nao atraves deste exemplo Divisores de 12 Divisores de 12 1 2 3 4 6 12 1 2 3 4 6 12 Divisores de 18 Divisores de 18 1 2 3 6 9 18 1 2 3 6 9 18 Com isso temos mdc12 18 mdc12 18 mdc12 18 mdc12 18 6 O problema anterior pode ser resolvido geralmente com o resultado abaixo Proposicao 71 Se a e b forem inteiros nao nulos entao 1 mdca b mdca b 2 mdca b mina b Demonstracao A prova do item 1 e trivial pois os divisores comuns de a e b sao os mesmos divisores comuns de a e b Alem disso se d mdca b entao d e positivo e como divide a e tambem divide b com certeza vamos ter d a e d b provando o item 2 Para calcular o maximo divisor comum de dois inteiros podemos utilizar a fatoracao de cada um deles em primos dada pelo TFA Vejamos como isto pode ser feito no proximo resultado Proposicao 72 Se a pα1 1 pαk k rγ1 1 rγt t e b pβ1 1 pβk k sλ1 1 sλl l onde p1 pk r1 rt s1 sl sao primos distintos e os expoentes αi γj βi λv sao naturais 1 i k 1 j t 1 v l entao mdca b pθ1 1 pθk k onde θi minαi βi para i 1 k fundam2Cpia 201061 1350 page 49 49 49 Demonstracao Vamos mostrar que o inteiro d pθ1 1 pθk k com θi minαi βi i 1 k satisfaz os itens i e ii da Definicao 71 Como para todo i 1 k θi αi e θi βi temos αi θi 0 e βi θi 0 e assim os numeros a1 pα1θ1 1 pαkθk k e b1 pβ1θ1 1 pβkθk k sao naturais e alem disso a a1d e b b1d ou seja d a e d b o que garante o item i Agora para provar o item ii consideramos um inteiro c tal que c a e c b Desta forma a e b sao multiplos de c e assim pelo Teorema Fundamental da Aritmetica os primos que aparecem na fatoracao de c devem estar presentes tanto na fatoracao de a quanto na fatoracao de b Como os unicos primos comuns nas fatoracoes de a e b sao os p i teremos c pε1 1 pεk k com 0 εi minαi βi i 1 k portanto εi θi o que mostra que c d e finaliza a demonstracao deste resultado Exemplo 72 Temos 1508 22 13 29 e 442 2 13 17 Neste caso mdc1508 422 2 13 pois o maximo divisor comum e dado pelos primos comuns com menor expoente O metodo acima nao e sempre conveniente pois como ja observamos na Aula 5 a fatoracao pode ser muito difıcil quando trabalhamos com numeros grandes Existe um procedimento pratico que permite o calculo do maximo divisor comum de dois inteiros sem passar pela fatoracao em primos que esta presente em Os elementos de Euclides e e conhecido como algoritmo de Euclides Primeiramente vamos ver um exemplo Exemplo 73 Temos 221 2 91 39 ou seja o resto da divisao de 221 por 91 e 39 e notamos tambem que mdc221 91 mdc91 39 13 No exemplo anterior vimos que o maximo divisor comum de a 221 e b 91 e igual ao maximo divisor comum de b e o resto da divisao de a por b Isto ocorre de maneira geral Proposicao 73 Se a bqr onde 0 r b entao mdca b mdcb r Demonstracao Suponhamos que d mdca b Queremos mostrar que d mdcb r Usando a definicao de mdc ja temos que d a e d b Desta forma como r a bq vamos ter d r Logo ja concluımos que d e um divisor comum de b e r precisamos garantir agora que ele seja o maior de todos os divisores fundamentos de álgebra I2012indd 55 26012012 180350 56 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 50 50 50 CAPITULO 7 AULA 7 M AXIMO DIVISOR COMUM Se c e um outro divisor de b e r temos c b e c r Mas entao como a bq r teremos que c a Assim c e um divisor comum de a e b e portanto deve ser menor ou igual a mdca b ou seja c d Exemplo 74 Vamos calcular mdc754 221 com base no resultado ante rior Dividindo sucessivamente temos 1 754 3 221 91 e mdc754 221 mdc221 91 2 221 2 91 39 e mdc221 91 mdc91 39 3 91 2 39 13 e mdc91 39 mdc39 13 4 39 3 13 0 e mdc39 13 13 5 mdc13 0 13 e a partir daqui isto se repete Assim mdc754 221 mdc221 91 mdc91 39 mdc39 13 13 Em geral podemos obter mdca b pelo metodo das divisoes sucessivas Teorema 71 Algoritmo de Eulides Sejam a e b naturais nao nulos com a b Dividindo sucessivamente obtemos a bq1 r1 0 r1 b mdca b mdcb r1 b r1q2 r2 0 r2 r1 mdcb r1 mdcr1 r2 r1 r2q3 r3 0 r3 r2 mdcr1 r2 mdcr2 r3 rn2 rn1qn rn 0 rn rn1 mdcrn2 rn1 mdcrn1 rn rn1 rnqn1 mdcrn1 rn rn Portanto mdca b rn ou seja e o ultimo resto nao nulo encontrado no processo de divisoes sucessivas Claro que se r1 0 entao mdca b b Demonstracao Como a e b sao naturais e claro que se a bq1 entao mdca b b 0 Portanto vamos considerar o caso geral e provar que podemos calcular o MDC usando inducao sobre o numero de passos do algoritmo de Euclides AE Para isto o que queremos provar e que a seguinte afirmacao e verdadeira se ao aplicarmos o AE a dois naturais a e b obtivermos o primeiro resto nulo apos n 1 passos entao mdca b e igual ao ultimo resto nao nulo obtido ou seja o resto obtido no passo n E claro que para n 1 a afirmacao e verdadeira pois se o primeiro resto nulo e obtido no passo 2 entao a bq1 r1 0 r1 b b r1q2 assim de acordo com a Proposicao 73 temos mdca b mdcb r1 r1 e neste caso o MDC e o resto obtido no passo n 1 Agora suponhamos que a afirmativa seja verdadeira para n k ou seja para obter o primeiro resto nulo precisamos de k 1 passos fundam2Cpia 201061 1350 page 51 51 51 Vamos ver que a afirmativa tambem e verdadeira para n k 1 ou seja quando precisarmos de k 2 passos para chegar no primeiro resto nulo a bq1 r1 0 r1 b b r1q2 r2 0 r2 r1 rk2 rk1qk rk 0 rk rk1 rk1 rkqk1 rk1 rk rk1qk2 Queremos mostrar que mdca b rk1 ou seja o resto nao nulo obtido no passo k 1 Mas note que ao aplicarmos o AE aos numeros b e r1 o primeiro resto nulo foi encontrado apos k 1 passos e entao por hipotese de inducao mdcb r1 rk1 Mas novamente usando a Proposicao 73 temos mdca b mdcb r1 rk1 o que garante o resultado Ja vimos que se a 0 entao mdca 0 a Neste caso podemos escrever mdca 0 a 1 x a 0 y b De maneira geral podemos perguntar se isto ocorre quando a e b sao simul taneamente nao nulos ou seja existem inteiros x e y tais que mdca b ax by Isto e verdade e dizemos que o maximo divisor comum e uma combinacao linear inteira de a e b E claro que podemos provar este fato apenas para o caso em que a e b sao inteiros positivos pois ja sabemos que mdca b mdca b Teorema 72 Se a e b forem naturais e d mdca b entao existem in teiros x e y tais que d ax by Demonstracao Inicialmente notamos que se b a entao mdca b b 0 x a 1 y b Portanto vamos considerar o caso em que b nao divide a Neste caso calculamos d mdca b pelo Teorema 71 e vamos mostrar que d e uma combinacao linear inteira de a e b usando inducao sobre o numero de passos do algoritmo de Euclides E claro que se sao necessarios n 2 passos para calcularmos o MDC entao a bq1 r1 0 r1 b b r1q2 fundamentos de álgebra I2012indd 56 26012012 180351 57 aula 7 fundam2Cpia 201061 1350 page 50 50 50 CAPITULO 7 AULA 7 M AXIMO DIVISOR COMUM Se c e um outro divisor de b e r temos c b e c r Mas entao como a bq r teremos que c a Assim c e um divisor comum de a e b e portanto deve ser menor ou igual a mdca b ou seja c d Exemplo 74 Vamos calcular mdc754 221 com base no resultado ante rior Dividindo sucessivamente temos 1 754 3 221 91 e mdc754 221 mdc221 91 2 221 2 91 39 e mdc221 91 mdc91 39 3 91 2 39 13 e mdc91 39 mdc39 13 4 39 3 13 0 e mdc39 13 13 5 mdc13 0 13 e a partir daqui isto se repete Assim mdc754 221 mdc221 91 mdc91 39 mdc39 13 13 Em geral podemos obter mdca b pelo metodo das divisoes sucessivas Teorema 71 Algoritmo de Eulides Sejam a e b naturais nao nulos com a b Dividindo sucessivamente obtemos a bq1 r1 0 r1 b mdca b mdcb r1 b r1q2 r2 0 r2 r1 mdcb r1 mdcr1 r2 r1 r2q3 r3 0 r3 r2 mdcr1 r2 mdcr2 r3 rn2 rn1qn rn 0 rn rn1 mdcrn2 rn1 mdcrn1 rn rn1 rnqn1 mdcrn1 rn rn Portanto mdca b rn ou seja e o ultimo resto nao nulo encontrado no processo de divisoes sucessivas Claro que se r1 0 entao mdca b b Demonstracao Como a e b sao naturais e claro que se a bq1 entao mdca b b 0 Portanto vamos considerar o caso geral e provar que podemos calcular o MDC usando inducao sobre o numero de passos do algoritmo de Euclides AE Para isto o que queremos provar e que a seguinte afirmacao e verdadeira se ao aplicarmos o AE a dois naturais a e b obtivermos o primeiro resto nulo apos n 1 passos entao mdca b e igual ao ultimo resto nao nulo obtido ou seja o resto obtido no passo n E claro que para n 1 a afirmacao e verdadeira pois se o primeiro resto nulo e obtido no passo 2 entao a bq1 r1 0 r1 b b r1q2 assim de acordo com a Proposicao 73 temos mdca b mdcb r1 r1 e neste caso o MDC e o resto obtido no passo n 1 Agora suponhamos que a afirmativa seja verdadeira para n k ou seja para obter o primeiro resto nulo precisamos de k 1 passos fundam2Cpia 201061 1350 page 51 51 51 Vamos ver que a afirmativa tambem e verdadeira para n k 1 ou seja quando precisarmos de k 2 passos para chegar no primeiro resto nulo a bq1 r1 0 r1 b b r1q2 r2 0 r2 r1 rk2 rk1qk rk 0 rk rk1 rk1 rkqk1 rk1 rk rk1qk2 Queremos mostrar que mdca b rk1 ou seja o resto nao nulo obtido no passo k 1 Mas note que ao aplicarmos o AE aos numeros b e r1 o primeiro resto nulo foi encontrado apos k 1 passos e entao por hipotese de inducao mdcb r1 rk1 Mas novamente usando a Proposicao 73 temos mdca b mdcb r1 rk1 o que garante o resultado Ja vimos que se a 0 entao mdca 0 a Neste caso podemos escrever mdca 0 a 1 x a 0 y b De maneira geral podemos perguntar se isto ocorre quando a e b sao simul taneamente nao nulos ou seja existem inteiros x e y tais que mdca b ax by Isto e verdade e dizemos que o maximo divisor comum e uma combinacao linear inteira de a e b E claro que podemos provar este fato apenas para o caso em que a e b sao inteiros positivos pois ja sabemos que mdca b mdca b Teorema 72 Se a e b forem naturais e d mdca b entao existem in teiros x e y tais que d ax by Demonstracao Inicialmente notamos que se b a entao mdca b b 0 x a 1 y b Portanto vamos considerar o caso em que b nao divide a Neste caso calculamos d mdca b pelo Teorema 71 e vamos mostrar que d e uma combinacao linear inteira de a e b usando inducao sobre o numero de passos do algoritmo de Euclides E claro que se sao necessarios n 2 passos para calcularmos o MDC entao a bq1 r1 0 r1 b b r1q2 fundamentos de álgebra I2012indd 57 26012012 180352 58 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 52 52 52 CAPITULO 7 AULA 7 M AXIMO DIVISOR COMUM ou seja temos mdca b mdcb r1 r1 a bq1 e neste caso x 1 e y q1 Agora suponhamos que a afirmativa seja verdadeira sempre que necessitar mos de n k passos para o calculo do MDC ou seja para obter o primeiro resto nulo no processo de divisoes sucessivas Vamos ver que tambem e verdadeira quando precisarmos de n k 1 passos a bq1 r1 0 r1 b b r1q2 r2 0 r2 r1 r1 r2q3 r3 0 r3 r2 rk2 rk1qk rk 0 rk rk1 rk1 rkqk1 ou seja o que temos aqui e que mdca b rk obtido apos k 1 passos Mas note que mdcb r1 rk e necessitamos de k passos para obtˆelo Logo por hipotese de inducao existem inteiros x e y tais que rk bx r1y Mas como a bq1 r1 temos r1 a bq1 e portanto mdca b rk bx a bq1y a y x b x q1y y e isto finaliza a demonstracao Problema 74 Como determinar os inteiros x e y Solucao Considerando o calculo que fizemos no Exemplo 74 temos o seguinte De 3 13 91 2 39 De 2 91 2 221 2 91 5 91 2 221 De 1 5 754 3 221 2 221 5 754 17 221 Concluımos que 13 5 754 17 221 isto e os inteiros x 5 e y 17 sao tais que 13 754x 221y A partir do proximo resultado temos uma maneira de verificar quando dois inteiros sao relativamente primos Proposicao 74 Sejam a b Z Temos mdca b 1 se e somente se existem inteiros x e y tais que 1 ax by fundam2Cpia 201061 1350 page 53 53 53 Demonstracao Pelo Teorema 72 esta claro que se mdca b 1 entao existem inteiros x e y tais que 1 ax by Por outro lado se existem tais inteiros e d mdca b entao d a e d b mas assim d ax by ou seja d 1 Deste modo d 1 e a demonstracao esta feita Problema 75 Se a b e d sao inteiros tais que d ax by com x y Z entao e verdade que d mdca b Solucao Isto nao e sempre verdadeiro Por exemplo para a 3 b 2 e d 9 temos 9 3x 2y onde x 1 e y 3 e claramente mdc3 2 9 Portanto devemos tomar cuidado com a recıproca do Teorema 72 Ela vale quando d 1 como visto na proposicao anterior Proposicao 75 Sejam a b c d Z Valem as seguintes propriedades do maximo divisor comum 1 se mdca b d entao mdc a d b d 1 2 se a bc e mdca b 1 entao a c Demonstracao Para provar 1 usamos o Teorema 72 e escrevemos d ax by Entao como d a e d b temos que os numeros a d e b d sao naturais e alem disso 1 a d x b d y Assim pela proposicao anterior concluımos que mdc a d b d 1 Agora se a bc e mdca b 1 entao existem inteiros q x e y tais que aq bc e 1 ax by 71 Para garantir que a c devemos mostrar que existe k Z tal que c ak Para obter esta informacao multiplicamos a segunda equacao em 71 por c c axc bc aq y ou seja c a xc qy k com k Z o que prova a proposicao fundamentos de álgebra I2012indd 58 26012012 180353 59 aula 7 fundam2Cpia 201061 1350 page 52 52 52 CAPITULO 7 AULA 7 M AXIMO DIVISOR COMUM ou seja temos mdca b mdcb r1 r1 a bq1 e neste caso x 1 e y q1 Agora suponhamos que a afirmativa seja verdadeira sempre que necessitar mos de n k passos para o calculo do MDC ou seja para obter o primeiro resto nulo no processo de divisoes sucessivas Vamos ver que tambem e verdadeira quando precisarmos de n k 1 passos a bq1 r1 0 r1 b b r1q2 r2 0 r2 r1 r1 r2q3 r3 0 r3 r2 rk2 rk1qk rk 0 rk rk1 rk1 rkqk1 ou seja o que temos aqui e que mdca b rk obtido apos k 1 passos Mas note que mdcb r1 rk e necessitamos de k passos para obtˆelo Logo por hipotese de inducao existem inteiros x e y tais que rk bx r1y Mas como a bq1 r1 temos r1 a bq1 e portanto mdca b rk bx a bq1y a y x b x q1y y e isto finaliza a demonstracao Problema 74 Como determinar os inteiros x e y Solucao Considerando o calculo que fizemos no Exemplo 74 temos o seguinte De 3 13 91 2 39 De 2 91 2 221 2 91 5 91 2 221 De 1 5 754 3 221 2 221 5 754 17 221 Concluımos que 13 5 754 17 221 isto e os inteiros x 5 e y 17 sao tais que 13 754x 221y A partir do proximo resultado temos uma maneira de verificar quando dois inteiros sao relativamente primos Proposicao 74 Sejam a b Z Temos mdca b 1 se e somente se existem inteiros x e y tais que 1 ax by fundam2Cpia 201061 1350 page 53 53 53 Demonstracao Pelo Teorema 72 esta claro que se mdca b 1 entao existem inteiros x e y tais que 1 ax by Por outro lado se existem tais inteiros e d mdca b entao d a e d b mas assim d ax by ou seja d 1 Deste modo d 1 e a demonstracao esta feita Problema 75 Se a b e d sao inteiros tais que d ax by com x y Z entao e verdade que d mdca b Solucao Isto nao e sempre verdadeiro Por exemplo para a 3 b 2 e d 9 temos 9 3x 2y onde x 1 e y 3 e claramente mdc3 2 9 Portanto devemos tomar cuidado com a recıproca do Teorema 72 Ela vale quando d 1 como visto na proposicao anterior Proposicao 75 Sejam a b c d Z Valem as seguintes propriedades do maximo divisor comum 1 se mdca b d entao mdc a d b d 1 2 se a bc e mdca b 1 entao a c Demonstracao Para provar 1 usamos o Teorema 72 e escrevemos d ax by Entao como d a e d b temos que os numeros a d e b d sao naturais e alem disso 1 a d x b d y Assim pela proposicao anterior concluımos que mdc a d b d 1 Agora se a bc e mdca b 1 entao existem inteiros q x e y tais que aq bc e 1 ax by 71 Para garantir que a c devemos mostrar que existe k Z tal que c ak Para obter esta informacao multiplicamos a segunda equacao em 71 por c c axc bc aq y ou seja c a xc qy k com k Z o que prova a proposicao fundamentos de álgebra I2012indd 59 26012012 180354 60 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 54 54 54 CAPITULO 7 AULA 7 M AXIMO DIVISOR COMUM Problema 76 E verdade que se a c e b c entao temos ab c Solucao Devemos tomar cuidado pois temos exemplos onde a e b dividem c e o produto ab nao divide c Isto acontece com a 3 b 6 e c 24 A resposta da questao anterior e positiva e quando mdca b 1 como abaixo Proposicao 76 Se a b c d Z entao vale o seguinte 1 se a c b c e mdca b d entao ab d c 2 se a c b c e a e b sao relativamente primos entao ab c Demonstracao Basta provar o item 1 pois o segundo e um consequˆencia imediata deste Temos a c q Z tal que c aq b c k Z tal que c bk mdca b d x y Z tais que d ax by Assim ao multiplicar a ultima equacao por c obtemos dc ax c bk by c aq ou seja dc ab xk yq m com m Z Mas como ab d Z logo c ab d m isto e ab d c Quando enunciamos a Definicao 71 do maximo divisor comum de a e b nos preocupamos apenas em dizer que ele e o maior divisor dos dois numeros Na verdade existe uma outra maneira de dizer que um inteiro d e o maximo divisor comum de a e b garantindo que este e um divisor comum positivo que e multiplo de todos os outros divisores comuns de a e b conforme provaremos agora Proposicao 77 Sejam a e b dois inteiros nao simultaneamente nulos O inteiro d e o maximo divisor comum de a e b se e somente se d satisfaz as propriedades abaixo i d 0 ii d a e d b iii se c e um inteiro tal que c a e c b entao c d fundam2Cpia 201061 1350 page 55 55 55 Demonstracao Se d mdca b entao claramente d satisfaz as proprieda des i e ii do enunciado Agora temos que mostrar que tambem satisfaz iii Para isto considere c um inteiro tal que c a e c b Usando o Teorema 72 escrevemos d ax by com x y Z e portanto basta usar o item 4 da Proposicao 41 para concluir que c d Para mostrar a recıproca consideramos d um inteiro satisfazendo os itens i ii e iii acima Vamos mostrar que de fato d e o maximo divsor comum de a e b Para isto temos que garantir que d tambem satisfaz os itens da Definicao 71 Claro que so temos que mostrar o ultimo item e para fazer isto tomamos um inteiro c tal que c a e c b Pelo item iii acima temos c d e assim existe c Z tal que d cq cq pois d 0 Logo c c d como querıamos mostrar Problema 77 Mostre que mdca b mdca b b Solucao Para provar a igualdade acima consideramos d mdca b e vamos mostrar que tambem temos d mdca b b usando a proposicao anterior E claro que o item i e verdadeiro e como ja temos que d mdca b entao d a e d b o que implica que d a b Logo d e divisor de a b e de b Falta apenas mostrar que se c e um inteiro tal que c a b e c b entao c d Mas isto tambem ja e verdade pois c a b e c b c a b b isto e c a e como c b usamos novamente a proposicao anterior e con cluımos que c d fundamentos de álgebra I2012indd 60 26012012 180355 61 aula 7 fundam2Cpia 201061 1350 page 54 54 54 CAPITULO 7 AULA 7 M AXIMO DIVISOR COMUM Problema 76 E verdade que se a c e b c entao temos ab c Solucao Devemos tomar cuidado pois temos exemplos onde a e b dividem c e o produto ab nao divide c Isto acontece com a 3 b 6 e c 24 A resposta da questao anterior e positiva e quando mdca b 1 como abaixo Proposicao 76 Se a b c d Z entao vale o seguinte 1 se a c b c e mdca b d entao ab d c 2 se a c b c e a e b sao relativamente primos entao ab c Demonstracao Basta provar o item 1 pois o segundo e um consequˆencia imediata deste Temos a c q Z tal que c aq b c k Z tal que c bk mdca b d x y Z tais que d ax by Assim ao multiplicar a ultima equacao por c obtemos dc ax c bk by c aq ou seja dc ab xk yq m com m Z Mas como ab d Z logo c ab d m isto e ab d c Quando enunciamos a Definicao 71 do maximo divisor comum de a e b nos preocupamos apenas em dizer que ele e o maior divisor dos dois numeros Na verdade existe uma outra maneira de dizer que um inteiro d e o maximo divisor comum de a e b garantindo que este e um divisor comum positivo que e multiplo de todos os outros divisores comuns de a e b conforme provaremos agora Proposicao 77 Sejam a e b dois inteiros nao simultaneamente nulos O inteiro d e o maximo divisor comum de a e b se e somente se d satisfaz as propriedades abaixo i d 0 ii d a e d b iii se c e um inteiro tal que c a e c b entao c d fundam2Cpia 201061 1350 page 55 55 55 Demonstracao Se d mdca b entao claramente d satisfaz as proprieda des i e ii do enunciado Agora temos que mostrar que tambem satisfaz iii Para isto considere c um inteiro tal que c a e c b Usando o Teorema 72 escrevemos d ax by com x y Z e portanto basta usar o item 4 da Proposicao 41 para concluir que c d Para mostrar a recıproca consideramos d um inteiro satisfazendo os itens i ii e iii acima Vamos mostrar que de fato d e o maximo divsor comum de a e b Para isto temos que garantir que d tambem satisfaz os itens da Definicao 71 Claro que so temos que mostrar o ultimo item e para fazer isto tomamos um inteiro c tal que c a e c b Pelo item iii acima temos c d e assim existe c Z tal que d cq cq pois d 0 Logo c c d como querıamos mostrar Problema 77 Mostre que mdca b mdca b b Solucao Para provar a igualdade acima consideramos d mdca b e vamos mostrar que tambem temos d mdca b b usando a proposicao anterior E claro que o item i e verdadeiro e como ja temos que d mdca b entao d a e d b o que implica que d a b Logo d e divisor de a b e de b Falta apenas mostrar que se c e um inteiro tal que c a b e c b entao c d Mas isto tambem ja e verdade pois c a b e c b c a b b isto e c a e como c b usamos novamente a proposicao anterior e con cluımos que c d fundamentos de álgebra I2012indd 61 26012012 180356 62 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 56 56 56 CAPITULO 7 AULA 7 M AXIMO DIVISOR COMUM Exercıcios da Aula 7 1 Encontre os possıveis valores de a Z tal que mdc20 a a 4 2 Se p e um primo e mdca b p quais sao os possıveis valores de mdca2 b E de mdca2 b2 3 Seja n um numero natural tal que mdcn 6 1 Mostre que n2 1 e multiplo de 12 4 Determine o mmca b de dois numeros positivos a e b cujo produto e 25 33 e sendo mdca b 22 3 5 Considere a b c inteiros tais que a bc Mostre que se mdca b d entao a dc 6 Sejam a b c Z nao nulos Prove que a Se mdca c 1 e b c entao mostre que mdca b 1 b Se mdca c 1 entao mdca bc mdca b c Se mdca b 1 entao mdca b a b 1 ou 2 d mdca b 1 mdca b a2 ab b2 1 7 Considerando a b Z e p um numero primo nas afirmativas abaixo verifique se estas sao verdadeiras ou falsas Justifique convenientemente a Se a mdca b e par entao a b e par b Se a mdca b e ımpar entao a b e ımpar c Se d mdca a2 b2 entao d a b2 8 Sejam a e b inteiros nao nulos primos entre si Mostre que mdcan bn 1 n 1 fundam2Cpia 201061 1350 page 57 57 Capıtulo 8 Equacoes Diofantinas Lineares e MMC Objetivos Introduziremos as chamadas equacoes diofantinas lineares que sao utiliza das na solucao de problemas envolvendo numeros inteiros Vamos ver que suas solucoes dependem fortemente de uma condicao envolvendo o MDC Alem disso vamos tratar dos multiplos comuns de dois inteiros destacando o principal deles o mınimo multiplo comum O matematico grego Diofanto de Alexandria viveu no seculo 3 da era crista Ele expˆos uma serie de problemas a respeito de numeros inteiros que desper taram interesse entre os arabes Um deles passou a historia da matematica gracas a Pierre de Fermat no seculo 17 E o problema expresso pela equacao xn yn zn e a pergunta e se existem numeros inteiros x y e z que sejam solucoes desta equacao Diofanto demonstrou que para n 2 existem inumeras solucoes De fato vocˆe ja conhece solucoes classicas dadas por numeros pitagoricos tais como 32 42 52 Fermat ao retomar o problema estabeleceu o famoso Ultimo Teorema de Fermat que diz que a equacao nao tem solucao em numeros inteiros quando n e maior que 2 Na verdade Fermat nao deixou registros sobre a prova deste teorema e a primeira demonstracao publica para ele foi dada em 1993 por Andrew Wiles De modo geral Diofanto se interessava por problemas que envolvessem equacoes cujas solucoes se restringiam aos numeros inteiros e se preocu pou particularmente com as chamadas equacoes diofantinas lineares com duas incognitas que sao equacoes nas incognitas x e y que tˆem a forma ax by c onde a b c Z com a e b nao simultaneamente nulos 57 exercícios fundamentos de álgebra I2012indd 62 26012012 180356 AULA 8 equações diofantinas lineares e mmC objetIvos Introduziremos as chamadas equações diofantinas lineares que são utilizadas na solução de problemas envolvendo números inteiros Vamos ver que suas soluções dependem fortemente de uma condição envolvendo o MDC Além disso vamos tratar dos múltiplos comuns de dois inteiros destacando o principal deles o mínimo múltiplo comum fundam2Cpia 201061 1350 page 56 56 56 CAPITULO 7 AULA 7 M AXIMO DIVISOR COMUM Exercıcios da Aula 7 1 Encontre os possıveis valores de a Z tal que mdc20 a a 4 2 Se p e um primo e mdca b p quais sao os possıveis valores de mdca2 b E de mdca2 b2 3 Seja n um numero natural tal que mdcn 6 1 Mostre que n2 1 e multiplo de 12 4 Determine o mmca b de dois numeros positivos a e b cujo produto e 25 33 e sendo mdca b 22 3 5 Considere a b c inteiros tais que a bc Mostre que se mdca b d entao a dc 6 Sejam a b c Z nao nulos Prove que a Se mdca c 1 e b c entao mostre que mdca b 1 b Se mdca c 1 entao mdca bc mdca b c Se mdca b 1 entao mdca b a b 1 ou 2 d mdca b 1 mdca b a2 ab b2 1 7 Considerando a b Z e p um numero primo nas afirmativas abaixo verifique se estas sao verdadeiras ou falsas Justifique convenientemente a Se a mdca b e par entao a b e par b Se a mdca b e ımpar entao a b e ımpar c Se d mdca a2 b2 entao d a b2 8 Sejam a e b inteiros nao nulos primos entre si Mostre que mdcan bn 1 n 1 fundam2Cpia 201061 1350 page 57 57 Capıtulo 8 Equacoes Diofantinas Lineares e MMC Objetivos Introduziremos as chamadas equacoes diofantinas lineares que sao utiliza das na solucao de problemas envolvendo numeros inteiros Vamos ver que suas solucoes dependem fortemente de uma condicao envolvendo o MDC Alem disso vamos tratar dos multiplos comuns de dois inteiros destacando o principal deles o mınimo multiplo comum O matematico grego Diofanto de Alexandria viveu no seculo 3 da era crista Ele expˆos uma serie de problemas a respeito de numeros inteiros que desper taram interesse entre os arabes Um deles passou a historia da matematica gracas a Pierre de Fermat no seculo 17 E o problema expresso pela equacao xn yn zn e a pergunta e se existem numeros inteiros x y e z que sejam solucoes desta equacao Diofanto demonstrou que para n 2 existem inumeras solucoes De fato vocˆe ja conhece solucoes classicas dadas por numeros pitagoricos tais como 32 42 52 Fermat ao retomar o problema estabeleceu o famoso Ultimo Teorema de Fermat que diz que a equacao nao tem solucao em numeros inteiros quando n e maior que 2 Na verdade Fermat nao deixou registros sobre a prova deste teorema e a primeira demonstracao publica para ele foi dada em 1993 por Andrew Wiles De modo geral Diofanto se interessava por problemas que envolvessem equacoes cujas solucoes se restringiam aos numeros inteiros e se preocu pou particularmente com as chamadas equacoes diofantinas lineares com duas incognitas que sao equacoes nas incognitas x e y que tˆem a forma ax by c onde a b c Z com a e b nao simultaneamente nulos 57 fundamentos de álgebra I2012indd 63 26012012 180357 64 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 58 58 58 CAPITULO 8 EQUAC OES DIOFANTINAS LINEARES E MMC As equacoes diofantinas lineares surgem naturalmente em problemas coti dianos como no exemplo abaixo Exemplo 81 Um feirante vende macas e uvas por quilo Cada quilo de maca custa R3 00 e cada quilo de uva custa R6 00 Determine a equacao que fornece a quantidade de quilos de macas e quilos de uvas vendidos apos o feirante faturar R21 00 Considerando que o feirante vendeu x quilos de macas e y quilos de uvas a equacao que estabelece os quilos vendidos e 3x 6y 21 Definicao 81 Um par de inteiros x0 y0 tais que ax0 by0 c e uma solucao inteira ou simplesmente uma solucao da equacao diofantina linear ax by c Exemplo 82 Considerando a equacao diofantina linear 3x 6y 21 te mos 37 60 21 39 61 21 31 64 21 Logo os pares de inteiros 7 0 9 1 e 1 4 sao exemplos de solucoes Problema 81 Toda equacao diofantina linear possui solucao Solucao Nao existem equacoes diofantinas lineares com duas incognitas que nao tˆem solucao Por exemplo a equacao diofantina linear 2x 4y 7 81 nao tem solucao porque 2x 4y e um inteiro par quaisquer que sejam os valores inteiros de x e y enquanto que 7 e um inteiro ımpar Observe que na equacao 81 temos mdc2 4 2 nao divide 7 De modo geral a equacao diofantina linear axby c nao tem solucao todas as vezes que d mdca b nao divide c conforme provaremos no proximo teorema Teorema 81 A equacao diofantina linear ax by c tem solucao se e somente se d divide c onde d mdca b Demonstracao Suponha que a equacao ax by c tem uma solucao isto e que existe um par de inteiros x0 y0 tais que ax0 by0 c Considerando d mdca b existem inteiros k e q tais que a dk e b dq e assim temos c ax0 by0 dkx0 dqy0 dkx0 qy0 E como kx0 qy0 e um inteiro seguese que d divide c Reciprocamente suponhamos que d divide c isto e que c dt onde t e um inteiro fundam2Cpia 201061 1350 page 59 59 59 Pelo Teorema 72 existem inteiros x e y tais que d ax by Entao c dt ax byt atx bty isto e o par de inteiros tx ty e uma solucao da equacao ax by c Problema 82 Se ja sabemos que existem solucoes como sao estas solucoes Solucao Se d mdca b divide c ja sabemos que existe um par de inteiros x0 y0 que e uma solucao particular da equacao diofantina linear ax by c As outras solucoes desta equacao serao dadas por formulas envolvendo o par x0 y0 e o maximo divisor comum d conforme mostra o resultado seguinte Teorema 82 Seja x0 y0 uma solucao particular da equacao diofantina linear ax by c onde d mdca b divide c Entao todas as demais solucoes sao dadas por x x0 bdk e y y0 adk onde k e um inteiro arbitrario Demonstracao Suponhamos que o par de inteiros x0 y0 e uma solucao particular da equacao ax by c 82 Claro que para qualquer intero k o par x0 bdk y0 adk tambem e solucao de 82 pois ax0 bdk by0 adk ax0 by0 c abdk badk 0 c Agora considere x1 y1 uma outra solucao qualquer desta equacao Entao temos ax0 by0 c ax1 by1 e portanto ax1 x0 by0 y1 Como d mdca b existem inteiros r e s tais que a dr e b ds com r e s primos entre si veja item 1 da Proposicao 75 Substituindo estes valores de a e b na igualdade anterior e cancelando o fator d obtemos rx1 x0 sy0 y1 Assim r sy0 y1 e como mdcr s 1 segue do item 2 da Proposicao 75 que r y0 y1 isto e y0 y1 rk e x1 x0 sk onde k e um inteiro fundamentos de álgebra I2012indd 64 26012012 180358 65 aula 8 fundam2Cpia 201061 1350 page 58 58 58 CAPITULO 8 EQUAC OES DIOFANTINAS LINEARES E MMC As equacoes diofantinas lineares surgem naturalmente em problemas coti dianos como no exemplo abaixo Exemplo 81 Um feirante vende macas e uvas por quilo Cada quilo de maca custa R3 00 e cada quilo de uva custa R6 00 Determine a equacao que fornece a quantidade de quilos de macas e quilos de uvas vendidos apos o feirante faturar R21 00 Considerando que o feirante vendeu x quilos de macas e y quilos de uvas a equacao que estabelece os quilos vendidos e 3x 6y 21 Definicao 81 Um par de inteiros x0 y0 tais que ax0 by0 c e uma solucao inteira ou simplesmente uma solucao da equacao diofantina linear ax by c Exemplo 82 Considerando a equacao diofantina linear 3x 6y 21 te mos 37 60 21 39 61 21 31 64 21 Logo os pares de inteiros 7 0 9 1 e 1 4 sao exemplos de solucoes Problema 81 Toda equacao diofantina linear possui solucao Solucao Nao existem equacoes diofantinas lineares com duas incognitas que nao tˆem solucao Por exemplo a equacao diofantina linear 2x 4y 7 81 nao tem solucao porque 2x 4y e um inteiro par quaisquer que sejam os valores inteiros de x e y enquanto que 7 e um inteiro ımpar Observe que na equacao 81 temos mdc2 4 2 nao divide 7 De modo geral a equacao diofantina linear axby c nao tem solucao todas as vezes que d mdca b nao divide c conforme provaremos no proximo teorema Teorema 81 A equacao diofantina linear ax by c tem solucao se e somente se d divide c onde d mdca b Demonstracao Suponha que a equacao ax by c tem uma solucao isto e que existe um par de inteiros x0 y0 tais que ax0 by0 c Considerando d mdca b existem inteiros k e q tais que a dk e b dq e assim temos c ax0 by0 dkx0 dqy0 dkx0 qy0 E como kx0 qy0 e um inteiro seguese que d divide c Reciprocamente suponhamos que d divide c isto e que c dt onde t e um inteiro fundam2Cpia 201061 1350 page 59 59 59 Pelo Teorema 72 existem inteiros x e y tais que d ax by Entao c dt ax byt atx bty isto e o par de inteiros tx ty e uma solucao da equacao ax by c Problema 82 Se ja sabemos que existem solucoes como sao estas solucoes Solucao Se d mdca b divide c ja sabemos que existe um par de inteiros x0 y0 que e uma solucao particular da equacao diofantina linear ax by c As outras solucoes desta equacao serao dadas por formulas envolvendo o par x0 y0 e o maximo divisor comum d conforme mostra o resultado seguinte Teorema 82 Seja x0 y0 uma solucao particular da equacao diofantina linear ax by c onde d mdca b divide c Entao todas as demais solucoes sao dadas por x x0 bdk e y y0 adk onde k e um inteiro arbitrario Demonstracao Suponhamos que o par de inteiros x0 y0 e uma solucao particular da equacao ax by c 82 Claro que para qualquer intero k o par x0 bdk y0 adk tambem e solucao de 82 pois ax0 bdk by0 adk ax0 by0 c abdk badk 0 c Agora considere x1 y1 uma outra solucao qualquer desta equacao Entao temos ax0 by0 c ax1 by1 e portanto ax1 x0 by0 y1 Como d mdca b existem inteiros r e s tais que a dr e b ds com r e s primos entre si veja item 1 da Proposicao 75 Substituindo estes valores de a e b na igualdade anterior e cancelando o fator d obtemos rx1 x0 sy0 y1 Assim r sy0 y1 e como mdcr s 1 segue do item 2 da Proposicao 75 que r y0 y1 isto e y0 y1 rk e x1 x0 sk onde k e um inteiro fundamentos de álgebra I2012indd 65 26012012 180359 66 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 60 60 60 CAPITULO 8 EQUAC OES DIOFANTINAS LINEARES E MMC Portanto temos as formulas x1 x0 sk x0 bdk e y1 y0 rk y0 adk Como podemos ver se d mdca b divide c entao a equacao diofantina linear ax by c admite um numero infinito de solucoes uma para cada valor do inteiro arbitrario k Problema 83 Como encontrar uma solucao inicial para uma equacao diofantina linear Solucao Uma solucao da equacao diofantina linear ax by c se obtem por tentativa ou pelo Algoritmo de Euclides pois atraves dele podemos escrever d mdca b como combinacao linear de a e b d ax by Mas como d c temos c dm com m um inteiro e assim c axm bym fornecendo assim a solucao inicial xm ym Problema 84 Mostre que a equacao 16x 15y 17 nao possui solucoes positivas x y isto e com x 0 e y 0 Solucao Uma solucao inicial e dada atraves do MDC Temos a 16 b 15 e d mdca b 1 e tal que 16 1 15 1 1 Assim uma solucao inicial e dada por 16 17 15 17 17 ou seja x0 17 e y0 17 Portanto solucoes gerais sao dadas por x 17 15k e y 17 16k Assim solucoes positivas sao tais que 17 15k 0 e 17 16k 0 isto e devemos ter um inteiro k tal que 17 15 k 17 16 o que nao e possıvel Exemplo 83 Considerando o Exemplo 81 quantos quilos de macas e quantos quilos de uvas o feirante vendeu ao faturar R21 00 Note que queremos encontrar solucoes x y da equacao 3x 6y 21 Uma solucao inicial ja foi dada no Exemplo 82 x0 7 e y0 0 Como mdc3 6 3 as demais solucoes sao dadas por x 7 2k e y 0 k Como queremos valores nao negativos pois representam quantidades entao devemos ter 7 2k 0 e k 0 fundam2Cpia 201061 1350 page 61 61 61 ou seja k 7 2 e k 0 devemos encontrar os valores para um inteiro k tal que 3 k 0 que sao k x y 3 1 3 2 3 2 1 5 1 0 7 0 Ou seja o feirante pode ter vendido 1 quilo de macas e 3 quilos de uvas ou 3 quilos de macas e 2 quilos de uvas ou 5 quilos de macas e 1 quilo de uva ou 7 quilos de macas e nenhum quilo de uva Problema 85 Ate agora nos preocupamos com divisores comuns O que dizer sobre os multiplos comuns de dois inteiros nao nulos a e b Solucao A partir de agora vamos trabalhar com esta questao e definir o mınimo multiplo comum MMC de a e b como o menor multiplo positivo dos dois numeros como temos abaixo Definicao 82 Um numero inteiro m e o mınimo multiplo comum dos numeros nao nulos a e b se i m 0 ii a m e b m iii se existe um inteiro c 0 tal que a c e b c entao m c Denotaremos o mınimo multiplo comum de a e b por mmca b e observamos que na definicao acima exigimos que mmca b seja um inteiro estritamente positivo Como ja sabemos no calculo do MDC sempre trabalhamos com inteiros positivos O que dizer do MMC Vejamos no exemplo Exemplo 84 Devemos nos preocupar com numeros negativos Vamos ver que nao atraves deste exemplo Multiplos de 12 Multiplos de 12 0 12 24 36 Multiplos de 18 Multiplos de 18 0 18 36 54 Com isso temos mmc12 18 mmc12 18 mmc12 18 mmc12 18 36 O exemplo anterior pode ser generalizado com o resultado abaixo cuja demonstracao e deixada como exercıcio fundamentos de álgebra I2012indd 66 26012012 180400 67 aula 8 fundam2Cpia 201061 1350 page 60 60 60 CAPITULO 8 EQUAC OES DIOFANTINAS LINEARES E MMC Portanto temos as formulas x1 x0 sk x0 bdk e y1 y0 rk y0 adk Como podemos ver se d mdca b divide c entao a equacao diofantina linear ax by c admite um numero infinito de solucoes uma para cada valor do inteiro arbitrario k Problema 83 Como encontrar uma solucao inicial para uma equacao diofantina linear Solucao Uma solucao da equacao diofantina linear ax by c se obtem por tentativa ou pelo Algoritmo de Euclides pois atraves dele podemos escrever d mdca b como combinacao linear de a e b d ax by Mas como d c temos c dm com m um inteiro e assim c axm bym fornecendo assim a solucao inicial xm ym Problema 84 Mostre que a equacao 16x 15y 17 nao possui solucoes positivas x y isto e com x 0 e y 0 Solucao Uma solucao inicial e dada atraves do MDC Temos a 16 b 15 e d mdca b 1 e tal que 16 1 15 1 1 Assim uma solucao inicial e dada por 16 17 15 17 17 ou seja x0 17 e y0 17 Portanto solucoes gerais sao dadas por x 17 15k e y 17 16k Assim solucoes positivas sao tais que 17 15k 0 e 17 16k 0 isto e devemos ter um inteiro k tal que 17 15 k 17 16 o que nao e possıvel Exemplo 83 Considerando o Exemplo 81 quantos quilos de macas e quantos quilos de uvas o feirante vendeu ao faturar R21 00 Note que queremos encontrar solucoes x y da equacao 3x 6y 21 Uma solucao inicial ja foi dada no Exemplo 82 x0 7 e y0 0 Como mdc3 6 3 as demais solucoes sao dadas por x 7 2k e y 0 k Como queremos valores nao negativos pois representam quantidades entao devemos ter 7 2k 0 e k 0 fundam2Cpia 201061 1350 page 61 61 61 ou seja k 7 2 e k 0 devemos encontrar os valores para um inteiro k tal que 3 k 0 que sao k x y 3 1 3 2 3 2 1 5 1 0 7 0 Ou seja o feirante pode ter vendido 1 quilo de macas e 3 quilos de uvas ou 3 quilos de macas e 2 quilos de uvas ou 5 quilos de macas e 1 quilo de uva ou 7 quilos de macas e nenhum quilo de uva Problema 85 Ate agora nos preocupamos com divisores comuns O que dizer sobre os multiplos comuns de dois inteiros nao nulos a e b Solucao A partir de agora vamos trabalhar com esta questao e definir o mınimo multiplo comum MMC de a e b como o menor multiplo positivo dos dois numeros como temos abaixo Definicao 82 Um numero inteiro m e o mınimo multiplo comum dos numeros nao nulos a e b se i m 0 ii a m e b m iii se existe um inteiro c 0 tal que a c e b c entao m c Denotaremos o mınimo multiplo comum de a e b por mmca b e observamos que na definicao acima exigimos que mmca b seja um inteiro estritamente positivo Como ja sabemos no calculo do MDC sempre trabalhamos com inteiros positivos O que dizer do MMC Vejamos no exemplo Exemplo 84 Devemos nos preocupar com numeros negativos Vamos ver que nao atraves deste exemplo Multiplos de 12 Multiplos de 12 0 12 24 36 Multiplos de 18 Multiplos de 18 0 18 36 54 Com isso temos mmc12 18 mmc12 18 mmc12 18 mmc12 18 36 O exemplo anterior pode ser generalizado com o resultado abaixo cuja demonstracao e deixada como exercıcio k x y 3 1 3 2 3 2 1 5 1 0 7 0 fundamentos de álgebra I2012indd 67 26012012 180400 68 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 62 62 62 CAPITULO 8 EQUAC OES DIOFANTINAS LINEARES E MMC Proposicao 81 Se a e b sao inteiros nao nulos entao 1 mmca b mmca b 2 mmca b maxa b Assim como fizemos com o maximo divisor comum o mınimo multiplo co mum tambem pode ser calculado atraves da fatoracao em primos Proposicao 82 Se a pα1 1 pαk k rγ1 1 rγt t e b pβ1 1 pβk k sλ1 1 sλl l onde p1 pk r1 rt s1 sl sao primos distintos e os expoentes αi γj βi λv sao naturais 1 i k 1 j t 1 v l entao mmca b p1 1 pk k rγ1 1 rγt t sλ1 1 sλl l 83 onde i maxαi βi Demonstracao Considere m mmca b Vamos mostrar que m tem de fato a fatoracao dada em 83 Para isto vamos mostrar como e a fatoracao de um multiplo comum c qualquer de a e b Temos c av v N e entao todos os primos na fatoracao de a aparecem na fatoracao de c com expoentes maiores ou iguais aos respectivos expoentes O mesmo acontece em relacao aos primos na fatoracao de b pois c bw w N Portanto c hp1 1 p2 2 pk k onde i maxαi βi Por outro lado r1 r2 rt aparecem em a e nao em b e s1 s2 sl aparecem em b e nao em a mas todos devem aparecer em c ou seja c rµ1 1 rµ2 2 rµt t sυ1 1 sυ2 2 sυl l p1 1 p2 2 pk k onde i maxαi βi µj γj e υn λn Como m e o menor multiplo comum necessariamente teremos m p1 1 p2 2 pk k rγ1 1 rγ2 2 rγt t sλ1 1 sλ2 2 sλl l onde i maxαi βi e isto finaliza a prova do resultado Exemplo 85 Temos 754 2 13 29 e 221 13 17 Neste caso mmc754 221 2 13 17 29 pois o mınimo multiplo comum e dado pelos primos comuns e nao comuns com maior expoente Na Proposicao 77 demos uma alternativa para a definicao do maximo divisor comum que era equivalente a Definicao 71 Vamos ver que o mesmo ocorre com o MDC Proposicao 83 Sejam a e b dois inteiros nao simultaneamente nulos O inteiro m e o mınimo multiplo comum de a e b se e somente se m satisfaz as propriedades abaixo i m 0 ii a m e b m iii se c e um inteiro tal que a c e b c entao m c fundam2Cpia 201061 1350 page 63 63 63 Demonstracao Se m mmca b entao claramente m satisfaz as pro priedades i e ii do enunciado Agora temos que mostrar que tambem satisfaz iii Para isto considere c um inteiro tal que a c e b c Usando o Lema de Euclides dividimos c por m encontrando c mq r onde 0 r m Portanto r c mq e como c e m sao ambos multiplos de a e de b entao r e multiplo de a e de b Deste modo nao podemos ter r 0 pois se isto acontecesse r seria um multiplo comum positivo de a e b que e m um absurdo Logo r 0 e c mq ou seja m c Reciprocamente se m um inteiro satisfazendo os itens i ii e iii acima para garantir que m e o mınimo multiplo comum de a e b basta mostrar que se c 0 e um inteiro tal que a c e b c entao temos m c Mas isto e claro pois pela condicao iii ja temos m c e assim c mk Mas como m 0 e c 0 temos k 0 isto e k 1 o que implica c m conforme desejavamos Por fim vamos ver que existe uma relacao estreita entre o MDC e o MMC de dois naturais a e b como abaixo Teorema 83 Se a e b sao numeros naturais entao mmca b ab mdca b Demonstracao Para demonstrar este resultado vamos considerar d mdca b Inicialmente observamos que como d a e d b os numeros a d e b d sao inteiros e tambem o numero m ab d e inteiro Precisamos ver que m satisfaz as condicoes que definem o MMC de a e b Para isto ele deve ser positivo o que e claro deve ser um multiplo comum de a e b e deve ser o menor de todos De fato temos que m e multiplo de a e de b pois m a b d inteiro e m b a d inteiro Agora se tomamos um outro multiplo positivo de a e b ou seja c 0 tal que a c e b c entao vamos ter que existem k q N tais que c ak e c bq Mas d mdca b portanto existem x y Z tais que d ax by Assim multiplicando esta igualdade por c temos cd c ax c by bq ax ak by abqx ky 84 Agora ja que ab d e inteiro podemos considerar o numero inteiro c m ab d qx ky fundamentos de álgebra I2012indd 68 26012012 180402 69 aula 8 fundam2Cpia 201061 1350 page 62 62 62 CAPITULO 8 EQUAC OES DIOFANTINAS LINEARES E MMC Proposicao 81 Se a e b sao inteiros nao nulos entao 1 mmca b mmca b 2 mmca b maxa b Assim como fizemos com o maximo divisor comum o mınimo multiplo co mum tambem pode ser calculado atraves da fatoracao em primos Proposicao 82 Se a pα1 1 pαk k rγ1 1 rγt t e b pβ1 1 pβk k sλ1 1 sλl l onde p1 pk r1 rt s1 sl sao primos distintos e os expoentes αi γj βi λv sao naturais 1 i k 1 j t 1 v l entao mmca b p1 1 pk k rγ1 1 rγt t sλ1 1 sλl l 83 onde i maxαi βi Demonstracao Considere m mmca b Vamos mostrar que m tem de fato a fatoracao dada em 83 Para isto vamos mostrar como e a fatoracao de um multiplo comum c qualquer de a e b Temos c av v N e entao todos os primos na fatoracao de a aparecem na fatoracao de c com expoentes maiores ou iguais aos respectivos expoentes O mesmo acontece em relacao aos primos na fatoracao de b pois c bw w N Portanto c hp1 1 p2 2 pk k onde i maxαi βi Por outro lado r1 r2 rt aparecem em a e nao em b e s1 s2 sl aparecem em b e nao em a mas todos devem aparecer em c ou seja c rµ1 1 rµ2 2 rµt t sυ1 1 sυ2 2 sυl l p1 1 p2 2 pk k onde i maxαi βi µj γj e υn λn Como m e o menor multiplo comum necessariamente teremos m p1 1 p2 2 pk k rγ1 1 rγ2 2 rγt t sλ1 1 sλ2 2 sλl l onde i maxαi βi e isto finaliza a prova do resultado Exemplo 85 Temos 754 2 13 29 e 221 13 17 Neste caso mmc754 221 2 13 17 29 pois o mınimo multiplo comum e dado pelos primos comuns e nao comuns com maior expoente Na Proposicao 77 demos uma alternativa para a definicao do maximo divisor comum que era equivalente a Definicao 71 Vamos ver que o mesmo ocorre com o MDC Proposicao 83 Sejam a e b dois inteiros nao simultaneamente nulos O inteiro m e o mınimo multiplo comum de a e b se e somente se m satisfaz as propriedades abaixo i m 0 ii a m e b m iii se c e um inteiro tal que a c e b c entao m c fundam2Cpia 201061 1350 page 63 63 63 Demonstracao Se m mmca b entao claramente m satisfaz as pro priedades i e ii do enunciado Agora temos que mostrar que tambem satisfaz iii Para isto considere c um inteiro tal que a c e b c Usando o Lema de Euclides dividimos c por m encontrando c mq r onde 0 r m Portanto r c mq e como c e m sao ambos multiplos de a e de b entao r e multiplo de a e de b Deste modo nao podemos ter r 0 pois se isto acontecesse r seria um multiplo comum positivo de a e b que e m um absurdo Logo r 0 e c mq ou seja m c Reciprocamente se m um inteiro satisfazendo os itens i ii e iii acima para garantir que m e o mınimo multiplo comum de a e b basta mostrar que se c 0 e um inteiro tal que a c e b c entao temos m c Mas isto e claro pois pela condicao iii ja temos m c e assim c mk Mas como m 0 e c 0 temos k 0 isto e k 1 o que implica c m conforme desejavamos Por fim vamos ver que existe uma relacao estreita entre o MDC e o MMC de dois naturais a e b como abaixo Teorema 83 Se a e b sao numeros naturais entao mmca b ab mdca b Demonstracao Para demonstrar este resultado vamos considerar d mdca b Inicialmente observamos que como d a e d b os numeros a d e b d sao inteiros e tambem o numero m ab d e inteiro Precisamos ver que m satisfaz as condicoes que definem o MMC de a e b Para isto ele deve ser positivo o que e claro deve ser um multiplo comum de a e b e deve ser o menor de todos De fato temos que m e multiplo de a e de b pois m a b d inteiro e m b a d inteiro Agora se tomamos um outro multiplo positivo de a e b ou seja c 0 tal que a c e b c entao vamos ter que existem k q N tais que c ak e c bq Mas d mdca b portanto existem x y Z tais que d ax by Assim multiplicando esta igualdade por c temos cd c ax c by bq ax ak by abqx ky 84 Agora ja que ab d e inteiro podemos considerar o numero inteiro c m ab d qx ky fundamentos de álgebra I2012indd 69 26012012 180403 70 Fundamentos de Álgebra I fundam2Cpia 201061 1350 page 64 64 64 CAPITULO 8 EQUAC OES DIOFANTINAS LINEARES E MMC Com isso c e multiplo de m ab d e o lema anterior garante que m mmca b Exemplo 86 O produto de dois naturais a e b e igual a 100 Sabendo que mmca b 50 determine os possıveis valores de a e b Pelo teorema acima temos ab mmca bmdca b e assim 22 52 mmca bmdca b 2 52 mdca b Entao mdca b 2 Assim a e b tˆem fator comum 2 e como ab 22 52 as possiblidades sao a 2 5 e b 2 5 ou a 5 e b 22 5 fundam2Cpia 201061 1350 page 65 65 65 Exercıcios da Aula 8 1 A soma de dois naturais a b e 120 e mmca b 144 Determine os possıveis valores de a e b 2 Determine todos os possıveis valores para os naturais a e b tais que mdca b 10 e mmca b 100 3 Considerando a b Z e p um numero primo nas afirmativas abaixo verifique se estas sao verdadeiras ou falsas Justifique convenientemente a Se mdca b e par entao mmca b e par b Se mmca b e par entao mdca b e par c Se mmca b p2 entao p3 nao divide a 4 Determine todos os multiplos positivos de 3 e todos os multiplos positivos de 5 cuja soma e igual a 60 5 Uma certa quantidade de macas e dividida em 37 montes de igual numero Apos serem retiradas 17 frutas as restantes sao colocadas em 79 caixas cada uma com uma mesma quantidade de macas Quantas frutas foram colocadas em cada caixa Quantas tinha cada monte 6 Um lojista vende cada par de tˆenis a R5000 e cada par de sapatos a R3000 Qual o mınimo de pares de calcados vendidos para que o total arrecadado ao fim de um dia de venda seja R70000 7 Um certo numero de seis e de noves sao adicionados e a soma resultante e 126 Se o numero de seis e o numero de noves fossem permutados a soma seria 114 Quantos seis e quantos noves foram somados 8 Sejam a b Z e n um numero natural nao nulo Prove que a mdcna nb n mdca b b mmcna nb n mmca b 9 Sejam a b Z nao nulos Mostre que mdca b mmca b se e somente se a b 10 Sejam a b Z nao nulos Se m mmca b entao mostre que mdca b m mdca b fundamentos de álgebra I2012indd 70 26012012 180403 71 aula 8 fundam2Cpia 201061 1350 page 64 64 64 CAPITULO 8 EQUAC OES DIOFANTINAS LINEARES E MMC Com isso c e multiplo de m ab d e o lema anterior garante que m mmca b Exemplo 86 O produto de dois naturais a e b e igual a 100 Sabendo que mmca b 50 determine os possıveis valores de a e b Pelo teorema acima temos ab mmca bmdca b e assim 22 52 mmca bmdca b 2 52 mdca b Entao mdca b 2 Assim a e b tˆem fator comum 2 e como ab 22 52 as possiblidades sao a 2 5 e b 2 5 ou a 5 e b 22 5 fundam2Cpia 201061 1350 page 65 65 65 Exercıcios da Aula 8 1 A soma de dois naturais a b e 120 e mmca b 144 Determine os possıveis valores de a e b 2 Determine todos os possıveis valores para os naturais a e b tais que mdca b 10 e mmca b 100 3 Considerando a b Z e p um numero primo nas afirmativas abaixo verifique se estas sao verdadeiras ou falsas Justifique convenientemente a Se mdca b e par entao mmca b e par b Se mmca b e par entao mdca b e par c Se mmca b p2 entao p3 nao divide a 4 Determine todos os multiplos positivos de 3 e todos os multiplos positivos de 5 cuja soma e igual a 60 5 Uma certa quantidade de macas e dividida em 37 montes de igual numero Apos serem retiradas 17 frutas as restantes sao colocadas em 79 caixas cada uma com uma mesma quantidade de macas Quantas frutas foram colocadas em cada caixa Quantas tinha cada monte 6 Um lojista vende cada par de tˆenis a R5000 e cada par de sapatos a R3000 Qual o mınimo de pares de calcados vendidos para que o total arrecadado ao fim de um dia de venda seja R70000 7 Um certo numero de seis e de noves sao adicionados e a soma resultante e 126 Se o numero de seis e o numero de noves fossem permutados a soma seria 114 Quantos seis e quantos noves foram somados 8 Sejam a b Z e n um numero natural nao nulo Prove que a mdcna nb n mdca b b mmcna nb n mmca b 9 Sejam a b Z nao nulos Mostre que mdca b mmca b se e somente se a b 10 Sejam a b Z nao nulos Se m mmca b entao mostre que mdca b m mdca b exercícios fundamentos de álgebra I2012indd 71 26012012 180404 fundamentos de álgebra I2012indd 72 26012012 180404 referências COUTINHO S C Números inteiros e criptografia RSA Rio de Janeiro IMPA 2005 HEFEz A Curso de álgebra 3 ed Rio de Janeiro IMPA 2002 MILIES F C P COELHO S P Números uma introdução à matemá tica 3 ed São Paulo Editora da Universidade de São Paulo 2003 MOREIRA G C T de A SALDANHA N Primos de Mersenne e outros primos muito grandes Rio de Janeiro IMPA 1999 RIBENBOIM P Números primos mistérios e recordes Rio de Janeiro IMPA 2001 SANTOS J P de O Introdução à Teoria dos Números Rio de Janeiro IMPA 2007 VIDIGAL A et al Fundamentos de álgebra Editora UFMG 2005 WIkIPÉDIA Disponível em httpptwikipediaorgwiki Acesso em 21 fev 2010 fundamentos de álgebra I2012indd 73 26012012 180405 fundamentos de álgebra I2012indd 74 26012012 180405 sobre a autora Ana Cristina Vieira possui graduação em Matemática pela Univer sidade Federal Fluminense 1988 mestrado em Matemática pela Universidade de Brasília 1991 e doutorado em Matemática também pela Universidade de Brasília 1997 Atualmente é professora associada da Universidade Federal de Minas Gerais Tem experiência na área de Matemática com ênfase em Teoria de Grupos e Teoria de Anéis atuando principalmente nos seguintes temas álgebras de grupos grupos de automorfismos de árvores representações de grupos e álgebras com identidades polinomiais fundamentos de álgebra I2012indd 75 26012012 180405 A presente edição foi composta pela Editora UFMG em caracteres Chaparral Pro e Optima Std e impressa pela Imprensa Universitária da UFMG em sistema offset 90g miolo e cartão supremo 250g capa em 2012 fundamentos de álgebra I2012indd 76 26012012 180405