Prévia do material em texto
Indaial – 2020 AritméticA e teoriA dos Números Prof. Leonardo Garcia dos Santos Prof. Luiz Carlos Pitzer 1a Edição Copyright © UNIASSELVI 2020 Elaboração: Prof. Leonardo Garcia dos Santos Prof. Luiz Carlos Pitzer Revisão, Diagramação e Produção: Centro Universitário Leonardo da Vinci – UNIASSELVI Ficha catalográfica elaborada na fonte pela Biblioteca Dante Alighieri UNIASSELVI – Indaial. Impresso por: S237a Santos, Leonardo Garcia dos Aritmética e teoria dos números. / Leonardo Garcia dos Santos; Luiz Carlos Pitzer. – Indaial: UNIASSELVI, 2020. 181 p.; il. ISBN 978-65-5663-024-3 1. Aritmética. - Brasil. 2. Teoria dos números. - Brasil. I. Pitzer, Luiz Carlos. II. Centro Universitário Leonardo Da Vinci. CDD 510.7 III ApreseNtAção A Aritmética e a Teoria dos Números são áreas da matemática que procura estudar, principalmente, os números inteiros. Destes, abordam-se temas como a divisibilidade, os números primos, de onde surge o famoso Teorema Fundamental da Aritmética. Nesta abordagem, ainda, discorrem aplicações importantes para a matemática, por exemplo, as equações diofantinas e as congruências. A teoria dos números pode ser considerada com a geometria euclidiana, como um dos estudos mais antigos da matemática, haja visto que Euclides em Os elementos dedicou alguns capítulos a este tema. Outro matemático historicamente importante que se dedicou bastante a este estudo foi Carl Friedrich Gauss (1777–1855), onde dizia que a teoria dos números é a rainha da matemática. Acerca da teoria dos números ainda existem problemas importantes não solucionados (quem sabe você consegue!?). São eles: • (Conjectura de Goldbach) Todo número natural n > 2 é soma de dois números primos. • Será que existem infinitos números primos da forma n2 + 1? • Será que existem infinitos números primos da forma 2n – 1? Estes números primos são chamados de Mersenne. • Será que existem infinitos números primos da forma 22n+1? Estes números primos são chamados de Fermat. Neste livro, mostraremos as teorias que permitem a continuidade dos estudos acerca da Aritmética e Teoria dos Números. Ele se divide em três importantes unidades. Na Unidade 1, estudaremos os números inteiros e suas propriedades. Além disso, daremos foco em métodos importantes de demonstração e o conceito fundamental de divisibilidade. Na Unidade 2, apresentaremos as principais ferramentas deste estudo: O Algoritmo de Euclides (mmc e mdc) e os Números Primos. O primeiro, o alicerce da aritmética, o segundo, os principais atores do processo (você entenderá por quê!). Por fim, na Unidade 3, teremos foco nas aplicações, com as congruências, sistemas de congruências, aritmética dos restos e a criptografia. Para finalizar, destaca-se que o estudo não será simples. Você deverá ler e reler trechos algumas vezes, resolver os exemplos com a leitura, pesquisar bastante. Essa é uma disciplina bastante técnica e exigirá dedicação e empenho. Realize as autoatividades com atenção e busque apoio sempre que precisar! IV Você já me conhece das outras disciplinas? Não? É calouro? Enfim, tanto para você que está chegando agora à UNIASSELVI quanto para você que já é veterano, há novidades em nosso material. Na Educação a Distância, o livro impresso, entregue a todos os acadêmicos desde 2005, é o material base da disciplina. A partir de 2017, nossos livros estão de visual novo, com um formato mais prático, que cabe na bolsa e facilita a leitura. O conteúdo continua na íntegra, mas a estrutura interna foi aperfeiçoada com nova diagramação no texto, aproveitando ao máximo o espaço da página, o que também contribui para diminuir a extração de árvores para produção de folhas de papel, por exemplo. Assim, a UNIASSELVI, preocupando-se com o impacto de nossas ações sobre o ambiente, apresenta também este livro no formato digital. Assim, você, acadêmico, tem a possibilidade de estudá-lo com versatilidade nas telas do celular, tablet ou computador. Eu mesmo, UNI, ganhei um novo layout, você me verá frequentemente e surgirei para apresentar dicas de vídeos e outras fontes de conhecimento que complementam o assunto em questão. Todos esses ajustes foram pensados a partir de relatos que recebemos nas pesquisas institucionais sobre os materiais impressos, para que você, nossa maior prioridade, possa continuar seus estudos com um material de qualidade. Aproveito o momento para convidá-lo para um bate-papo sobre o Exame Nacional de Desempenho de Estudantes – ENADE. Bons estudos! Bons estudos. Prof. Leonardo Garcia dos Santos Prof. Luiz Carlos Pitzer NOTA V Olá acadêmico! Para melhorar a qualidade dos materiais ofertados a você e dinamizar ainda mais os seus estudos, a Uniasselvi disponibiliza materiais que possuem o código QR Code, que é um código que permite que você acesse um conteúdo interativo relacionado ao tema que você está estudando. Para utilizar essa ferramenta, acesse as lojas de aplicativos e baixe um leitor de QR Code. Depois, é só aproveitar mais essa facilidade para aprimorar seus estudos! UNI VI VII Olá, acadêmico! Iniciamos agora mais uma disciplina e com ela um novo conhecimento. Com o objetivo de enriquecer teu conhecimento, construímos, além do livro que está em tuas mãos, uma rica trilha de aprendizagem, por meio dela terás contato com o vídeo da disciplina, o objeto de aprendizagem, materiais complementares, entre outros, todos pensados e construídos na intenção de auxiliar teu crescimento. Acesse o QR Code, que te levará ao AVA, e veja as novidades que preparamos para teu estudo. Conte conosco, estaremos juntos nessa caminhada! LEMBRETE VIII IX UNIDADE 1 – NÚMEROS INTEIROS E DIVISIBILIDADE ...........................................................1 TÓPICO 1 – NÚMEROS INTEIROS ......................................................................................................3 1 INTRODUÇÃO .......................................................................................................................................3 2 ADIÇÃO E MULTIPLICAÇÃO ............................................................................................................4 3 ORDENAÇÃO DOS INTEIROS ..........................................................................................................6 4 PRINCÍPIO DA BOA ORDENAÇÃO ................................................................................................9 RESUMO DO TÓPICO 1........................................................................................................................12 AUTOATIVIDADE .................................................................................................................................14 TÓPICO 2 – INDUÇÃO MATEMÁTICA ...........................................................................................15 1 INTRODUÇÃO .....................................................................................................................................15 2 PRINCÍPIO DA INDUÇÃO MATEMÁTICA .................................................................................15 3 DEFINIÇÃO POR RECORRÊNCIA ..................................................................................................22 RESUMO DO TÓPICO 2........................................................................................................................29 AUTOATIVIDADE .................................................................................................................................30 TÓPICO 3 – DIVISIBILIDADE ............................................................................................................33 1 INTRODUÇÃO .....................................................................................................................................33 2 DIVISIBILIDADE .................................................................................................................................332.1 PROPRIEDADES DA DIVISIBILIDADE ......................................................................................35 3 DIVISÃO EUCLIDIANA ....................................................................................................................39 RESUMO DO TÓPICO 3........................................................................................................................42 AUTOATIVIDADE .................................................................................................................................43 TÓPICO 4 – SISTEMAS DE NUMERAÇÃO .....................................................................................45 1 INTRODUÇÃO .....................................................................................................................................45 2 SISTEMA DE NUMERAÇÃO DECIMAL .......................................................................................45 3 SISTEMA DE NUMERAÇÃO EM UMA BASE QUALQUER .....................................................46 4 EXPANSÃO DE UM NÚMERO EM BASE B ..................................................................................47 LEITURA COMPLEMENTAR ...............................................................................................................50 RESUMO DO TÓPICO 4........................................................................................................................56 AUTOATIVIDADE .................................................................................................................................57 UNIDADE 2 – ALGORÍTMO DE EUCLIDES E NÚMEROS PRIMOS ........................................59 TÓPICO 1 – MDC E MMC .....................................................................................................................61 1 INTRODUÇÃO .....................................................................................................................................61 2 MÁXIMO DIVISOR COMUM ..........................................................................................................61 2.1 CÁLCULO DO MDC .......................................................................................................................65 2.2 FATORAÇÃO MÚLTIPLA .............................................................................................................65 2.3 ALGORITMO DE EUCLIDES ........................................................................................................68 3 MÍNIMO MÚLTIPLO COMUM ........................................................................................................75 3.1 CÁLCULO DO MMC ......................................................................................................................77 sumário X RESUMO DO TÓPICO 1........................................................................................................................79 AUTOATIVIDADE .................................................................................................................................80 TÓPICO 2 – APLICAÇÃO DE MDC ....................................................................................................81 1 INTRODUÇÃO .....................................................................................................................................81 2 EQUAÇÕES DIOFANTINAS LINEARES .......................................................................................81 RESUMO DO TÓPICO 2........................................................................................................................93 AUTOATIVIDADE .................................................................................................................................94 TÓPICO 3 – NÚMEROS PRIMOS .......................................................................................................97 1 INTRODUÇÃO .....................................................................................................................................97 2 NÚMEROS PRIMOS ...........................................................................................................................97 RESUMO DO TÓPICO 3......................................................................................................................103 AUTOATIVIDADE ...............................................................................................................................104 TÓPICO 4 – NÚMEROS ESPECIAIS.................................................................................................105 1 INTRODUÇÃO ...................................................................................................................................105 2 PRIMOS DE FERMAT .......................................................................................................................105 3 NÚMEROS PERFEITOS ....................................................................................................................106 4 PRIMOS DE MERSENNE .................................................................................................................109 5 FATORAÇÃO DO FATORIAL EM PRIMOS ................................................................................110 LEITURA COMPLEMENTAR .............................................................................................................115 RESUMO DO TÓPICO 4......................................................................................................................119 AUTOATIVIDADE ...............................................................................................................................120 UNIDADE 3 – CONGRUÊNCIA ........................................................................................................121 TÓPICO 1 – CONCRUÊNCIAS ..........................................................................................................123 1 INTRODUÇÃO ...................................................................................................................................123 2 ARITMÉTICA DOS RESTOS ...........................................................................................................123 RESUMO DO TÓPICO 1......................................................................................................................133 AUTOATIVIDADE ...............................................................................................................................134 TÓPICO 2 – APLICAÇÃO DE CONGRUÊNCIA ............................................................................137 1 INTRODUÇÃO ...................................................................................................................................137 2 PROVA DOS NOVE ...........................................................................................................................137 3 PEQUENO TEOREMA DE FERMAT ..............................................................................................139 4 TEOREMA DE EULER .......................................................................................................................142 5 TEOREMA DE WILSON ...................................................................................................................148 RESUMO DO TÓPICO 2......................................................................................................................150 AUTOATIVIDADE ...............................................................................................................................151 TÓPICO 3 – CONGRUÊNCIAS LINEARES E CLASSES RESIDUAIS ......................................153 1 INTRODUÇÃO ...................................................................................................................................153 2 CONGRUÊNCIAS LINEARES ........................................................................................................153 3 TEOREMA CHINÊSDOS RESTOS ...............................................................................................155 4 ARITMÉTICA DAS CLASSES RESISUAIS ..................................................................................158 RESUMO DO TÓPICO 3......................................................................................................................163 AUTOATIVIDADE ...............................................................................................................................164 XI TÓPICO 4 – NOÇÕES DE CRIPTOGRAFIA RSA .........................................................................165 1 INTRODUÇÃO ...................................................................................................................................165 2 CRIPTOGRAFIA RSA .......................................................................................................................165 RESUMO DO TÓPICO 4......................................................................................................................178 AUTOATIVIDADE ...............................................................................................................................179 REFERÊNCIAS .......................................................................................................................................181 XII 1 UNIDADE 1 NÚMEROS INTEIROS E DIVISIBILIDADE OBJETIVOS DE APRENDIZAGEM PLANO DE ESTUDOS A partir do estudo desta unidade, você deverá ser capaz de: • conhecer as propriedades e as estrutura dos números inteiros; • reconhecer as operações de adição e de multiplicação e as propriedades construídas a partir delas; • desenvolver a capacidade para demonstração de propriedades; • aplicar o conceito de adição e multiplicação em questões relacionadas com a divisibilidade; • compreender o sistema de numeração e como é possível representá-los em outras bases numéricas. Esta unidade está dividida em quatro tópicos. No decorrer da unidade você encontrará autoatividades com o objetivo de reforçar o conteúdo apresentado. TÓPICO 1 – NÚMEROS INTEIROS TÓPICO 2 – INDUÇÃO MATEMÁTICA TÓPICO 3 – DIVISIBILIDADE TÓPICO 4 – SISTEMAS DE NUMERAÇÃO Preparado para ampliar teus conhecimentos? Respire e vamos em frente! Procure um ambiente que facilite a concentração, assim absorverás melhor as informações. CHAMADA 2 3 TÓPICO 1 UNIDADE 1 NÚMEROS INTEIROS 1 INTRODUÇÃO É extremamente curioso e intrigante como a matemática, ao longo dos anos, vem se desenvolvendo e contribuindo para o surgimento de novas tecnologias e descobertas. Apesar das inúmeras aplicações, existe uma matemática esperando ser utilizada, a qual chamamos de matemática pura. Porém, apesar de termos grandes avanços em vários momentos ao analisar a história da humanidade, tudo referente à fundamentação da matemática passou por grandes questionamentos no final do Século XIX. Neste primeiro momento, daremos fundamentos axiomáticos, para a construção desta disciplina, que foi desenvolvido pelo matemático italiano Giuseppe Peano (1858-1932), no final do Século XIX. Ele foi quem contribui para a menor lista de axiomas, para obter os números naturais e, consequentemente, os inteiros. Os números naturais possuem como ideia simples e primordial a noção intuitiva de contagem. Porém, houve a necessidade de criar outros números, entre eles, os números negativos. Estes possuem, como uma de suas aplicações, as atividades comerciais. Suas regras operatórias foram publicadas em 1572 pelo matemático Rafael Bombelli. O conjunto dos números inteiros, { }, 2, 1, 0, 1, 2,= … − − …Z , é munido das operações de adição e de multiplicação. Neste conjunto, há um subconjunto muito importante que utilizaremos bastante, o dos números naturais, que trataremos sem a utilização do zero, { }1, 2, 3, .= …N Acadêmico, você sabe o que são axiomas? São sentenças que não necessitam ser provados ou demonstrados, simplesmente são consideradas evidentes dentro da matemática. NOTA UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE 4 2 ADIÇÃO E MULTIPLICAÇÃO Para fins de simplificação, a lista de axiomas que utilizaremos para construir as propriedades será bastante sucinta. Porém, como o intuito é estudar outras partes da teoria, selecionamos as seguintes propriedades: A1 – A adição e multiplicação são Bem Definidas. Para todos , , ’, ’ ,se ’ ’, então ’ ’ e ’ ’a b a b a a e b b a b a b a b a b∈ = = + = + ⋅ = ⋅Z A2 – A adição e a multiplicação são Comutativas. Para todos , , , e a b a b b a a b b a∈ + = + ⋅ = ⋅ Z A3 – A adição e a multiplicação são Associativas. ( ) ( ) ( ) ( )Para todos , , , , e a b c a b c a b c a b c a b c∈ + + = + + ⋅ ⋅ = ⋅ ⋅ Z A4 – A adição e a multiplicação possuem Elementos Neutros. Para todo , , 0 e 1a a a a a∈ + = ⋅ = Z Assim, 0 é o Elemento Neutro da adição e 1 é o Elemento Neutro da multiplicação. A5 – Adição possui elemento simétrico. ( )Para todo , ,existe tal que 0a b a a b∈ = − + = Z A6 – A multiplicação é distributiva com relação à adição. Para todos , , , ,a b c ∈ Z tem-se ( )a b c a b a c⋅ + = ⋅ + ⋅ Esse conjunto de propriedades que estão representados pela letra A e mais um número serão nossas ferramentas para mostrar a validade de algumas propriedades do conjunto dos números inteiros e que se estenderam a toda estrutura algébrica de um anel. Caro acadêmico, você sabe o que é um anel? Um anel A é um conjunto munido com as operações de adição (+) e de multiplicação (·), obedecendo as seguintes propriedades na adição: associatividade, comutatividade, elemento neutro e simétrico; na multiplicação: associatividade; na adição combinado com a multiplicação: distributiva. NOTA TÓPICO 1 | NÚMEROS INTEIROS 5 Exemplo 1: realize a demonstração da proposição 0 0a ⋅ = para todo a∈Z . Resolução: para realizar a demonstração, utilizaremos das terminologias adotadas nos axiomas anteriores. Utilizando A4 (elemento neutro) ( )0 0 0a a⋅ = ⋅ + Utilizando A6 (distributiva) ( )0 0 0 0 0a a a a⋅ = ⋅ + = ⋅ + ⋅ Logo, 0 0 0a a a⋅ = ⋅ + ⋅ Somando ( )0a− ⋅ a ambos os membros da igualdade A1 (adição bem definida): ( )( ) ( ) ( )( )0 0 0 0 0a a a a a⋅ + − ⋅ = ⋅ + ⋅ + − ⋅ Aplicando A5 (simétrico) no lado esquerdo e A3 (associatividade) no lado direito, obtemos: ( )( )( )0 0 0 0a a a= ⋅ + ⋅ + − ⋅ Aplicando A5 no lado direito 0 0 0a= ⋅ + . Por fim, aplicando A2 (comutativo) e A6 no lado direito 0 0a= ⋅ . Como queríamos demonstrar. Perceba que nesse primeiro exemplo, apresentamos, de forma detalhada, a cronologia dos eventos. Isso teve um motivo bem lógico, que é familiarizar o leitor com esse tipo de demonstração. É importante comentar que não há a necessidade de ser tão meticuloso na demonstração, você pode realizá-la de forma mais rápida, como fizemos na última etapa da demonstração. A adição nos fornece condições suficientes para definir uma outra operação, que chamaremos de subtração. D1 – Seja dado dois números inteiros a e b, define-se o número b menos a, denotando essa operação por b – a, como sendo ( )b a b a− = + − e dizemos que b – a é o resultado da subtração de a de b. UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE 6 Exemplo 2: mostre que se 0a b+ = , então b a= − e a b= − . Resolução: primeiramente, demonstraremos que vale a igualdade b a= − . Partindo de 0a b+ = , somaremos (–a) em ambos os membros A1 ( ) ( ) ( )0a b a a+ + − = + − . Aplicando A3 na esquerda e A2 na direita ( )( ) ( ) 0a b a a+ + − = − + . Aplicando A3 e A2 na esquerda, primeiramente dentro dos parênteses, obtemos ( )( ) ( ) 0a a b a+ − + = − + . Aplicando A5 na esquerda e A4 na direita 0 b a+ = − . Aplicando A2 e A4 na esquerda .b a= − Como queríamos demonstrar. Demonstraremos, agora, que vale a igualdade a b= − . Partindo de 0a b+ = , somaremos (–b) em ambos os membros A1 ( ) ( ) ( )0a b b b+ + − = + − . Aplicando A3 na esquerda e A2 na direita ( )( ) ( ) 0a b b b+ + − = − + . Aplicando A5 na esquerda ( )0 0a b+= − + . Por fim, aplicando A4 em ambos os membros .a b= − Como queríamos demonstrar. 3 ORDENAÇÃO DOS INTEIROS Vimos, anteriormente, algumas propriedades que são válidas para os inteiros. Desta forma, dando continuidade, veremos mais duas importantes propriedades que contribuirão para a demonstração de algumas proposições. Para facilitar, usaremos a mesma forma de denotar tais propriedades. A7 – Fechamento nos N : O conjunto dos N é fechada para a adição e multiplicação, ou seja, para todo , ,a b c∈N , tem-se que a b+ ∈N e a b⋅ ∈N. A8 – Tricotomia: Dados ,a b∈Z , uma, e apenas uma, das seguintes possibilidades é verificada: TÓPICO 1 | NÚMEROS INTEIROS 7 I. a = b II. b a− ∈N III. ( )b a a b− − = − ∈N A propriedade (ii) nos diz que se a é menor que b, o qual denotaremos por a < b, seu resultado será um número natural. (caso tenha dúvida, teste algumas possibilidades). No caso da propriedade (iii), temos o caso contrário, caso b seja menor que a, ou seja, b < a, temos um número natural. Desta forma, podemos entender que a tricotomia nos fornece que, para ,a b∈Z , apenas uma, e somente uma, das seguintes condições será verificada: I. a = b II. a < b III. b < a Perceba que outra importante definição é ao utilizarmos a notação b > a, ou seja, b é maior que a, estamos representando a < b. NOTA Apresentaremos algumas propriedades que podem ser demonstradas pelos axiomas vistos até o momento, e, em alguns casos, realizaremos sua demonstração. Proposição 1: a relação “menor do que” é transitiva: , , , e . .a b c a b b c a c∀ ∈ < < <Z Demonstração: supomos que e a b b c< < , então usando A8 temos, b a− ∈N e c b− ∈N . Por A1 que diz que a adição é fechada, temos que: ( ) ( ) ,c a b a c b− = − + − ∈N logo a c< . Proposição 2: a adição e a lei do cancelamento são compatíveis com respeito à relação “menor do que”: , , , .a b c a b a c b c∀ ∈ < ⋅ + < +Z Demonstração: ⇒ supondo que a b< , então b a− ∈N . Desta forma, ( ) ( ) ,b c a c b a+ − + = − ∈N o que implica que .a c b c+ < + ⇐ supunha que a c b c+ < + , então ( ) ( )b c a c+ − + ∈N . Desta forma, ao somar (–a) em ambos os lados da desigualdade, obtemos a recíproca desejada. Proposição 3: a multiplicação por elementos de N é compatível e passível de cancelamento com respeito à relação “menor do que”: , , , .a b c a b ac bc∀ ∈ ∀ ∈ < ⋅ <Z N UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE 8 Demonstração: ⇒ supondo que a b< , então b a− ∈N . Desta forma, escolhendo um c∈N e sabendo por A7 que a multiplicação é fechada nos naturais, temos: ( ) ,b c a c b a c⋅ − ⋅ = − ⋅ ∈N o que implica que .ac bc< ⇐ supunha que ac bc< , com c∈N . Por A8 tricotomia, temos três casos para analisar. (I) – a b= Está é falsa, pois isso tornaria .ac bc= (II) b a< – Pela primeira parte da demonstração, podemos notar que acarretaria b c a c⋅ < ⋅ , o que também é falso. (III) – a b< Logo, está é a única possibilidade. Proposição 4: a multiplicação é compatível e passível de cancelamento com respeito à igualdade: { } , , \ 0 , , .a b c a b ac bc∀ ∈ ∀ ∈ = =Z N Tente demonstrar está propriedade. Além de citar que a notação { }\ 0N significa o conjunto dos números naturais, exceto o zero, uma dica que deixamos para você, acadêmico, que pode te ajudar na demonstração, é seguir a ideia da proposição anterior e também utilizá-la com argumentos para provar a volta. DICAS Essa proposição é bem objetiva quanto ao cancelamento na multiplicação, não sendo possível cancelar se o número for o zero. Isso já é bem natural em várias situações da matemática. Veja este exemplo: Exemplo 3: resolva a equação 2 4x x= com x∈R . Resolução: por descuido, é possível simplificar o x em ambos os lados, obtendo, x = 4 como solução. Você pode estar se perguntando: mas o problema não está resolvido? A resposta é não, pois, não foi levado em consideração que o x poderia ser zero, é pela definição que vimos anteriormente, isso não pode ser feito. Porém, veremos o porquê! 2 4x x= Somando (–4x) em ambos os lados: 2 4 0x x− = TÓPICO 1 | NÚMEROS INTEIROS 9 Aplicando a distributiva: ( )4 0x x − = Logo, é intuitivo perceber que x = 0 e x = 4 são duas possibilidades para a resolução da equação. Um outro exemplo mais simples seria pensar na igualdade 2 0 3 0⋅ = ⋅ , que é verdade. Porém, ao cancelar o zero em ambos os lados, não obtemos uma igualdade com 2 = 3. Neste último momento, definiremos uma importante proposição. Nos falta, porém, definir, por completo, a relação de ordem. Sendo assim, diremos que a é menor ou igual do que b, ou que b é maior ou igual do que a, denotando por a b≤ ou b a≥ , se a < b, ou a = b. Desta forma, a relação de ordem é satisfeita, pois possui as seguintes propriedades: (I) É reflexiva: ,a a a∀ ∈ ≤Z . (II) É antissimétrica: , , , e .a b a b b a a b∀ ∈ ≤ ≤ ⇒ =Z (III) É transitiva: , , , , e a b c a b b c a c∀ ∈ ≤ ≤ ⇒ ≤Z . Com essa definição, podemos definir a importante noção de valor absoluto ou módulo. Seja a∈Z , definimos: , 0 , 0. a se a a a se a ≥ = − < O módulo ou valor absoluto de um número inteiro, representado por |a|, possui as seguintes propriedades básicas: Proposição 5: para ,a b∈Z e r∈ N , temos: I. ;a b a b⋅ = ⋅ II. a r≤ se, e somente se, ;r a r− ≤ ≤ III. ;a a a− ≤ ≤ IV. a desigualdade triangular: .a b a b a b− ≤ ± ≤ + Exemplo 4: para , ,a b c∀ ∈Z , mostre que vale: a < b e b c a c≤ ⇒ < . Demonstração: se a < b e b c≤ , então é como se tivéssemos: a < b e (b < c ou b = c). Desta forma, uma das duas possibilidades a < b e b < c ou a < b e b = c. Perceba que ambas implicam em a < c (na primeira, por transitividade e, na segunda, apenas pela troca). Portanto, se a < b e b c a c≤ ⇒ < . UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE 10 4 PRINCÍPIO DA BOA ORDENAÇÃO Veremos, agora, o nono e último axioma, que nos darão condições suficientes para deduzir todas as propriedades que estão ligadas aos números inteiros, e que fornecerão uma propriedade que diferenciará os inteiros dos demais conjuntos. Com esse nono axioma será possível, então, caracterizar o conjunto dos números inteiros. Vamos, primeiramente, recordar a definição do que seria um conjunto limitado inferiormente. Dizemos que um subconjunto S de Z é limitado inferiormente, se existir c∈Z tal que c x≤ para todo x S∈ . Dizemos que a S∈ é um menor elemento de S se a x≤ para todo x S∈ , denotando por min(S) = a. Um exemplo de conjunto limitado inferiormente é o próprio conjunto dos naturais, que possui o 1 como menor elemento. IMPORTANT E A9 – Princípio da Boa Ordenação: se S é um subconjunto não vazio de � e limitado inferiormente, então S possui um menor elemento. Vejamos como esse axioma pode diferenciar os inteiros dos racionais e dos reais. Se escolhermos um intervalo aberto qualquer (2, 4), perceba que tanto os racionais como os reais estão limitados inferiormente, porém, ambos não possuem um menor elemento. Pois, é sempre possível conseguir encontrar um valor cada vez mais próximo do 2. Veremos, agora, algumas propriedades dos inteiros, possíveis de serem demonstradas com este axioma, porém realizaremos a demonstração apenas de algumas, ficando a cargo do leitor as demais. Proposição 6: não existe nenhum número inteiro n tal que 0 < n < 1. Demonstração: vamos supor por absurdo que exista um valor n com esta propriedade. Sendo assim, o conjunto { }, 0 1 S a a= ∈ < <Z não é vazio. Logo, S possui um menor elemento x, com 0 < x < 1. Porém, multiplicando a desigualdade por x, obtemos 0 < x2 < x, ou seja, atribuindo o que já supomos 0 < x2 < x < 1. Portanto, 2x S∈ . Contradição! Corolário 1: dado um número inteiro n qualquer, não existe nenhum número inteiro m tal que n < m < n + 1. TÓPICO 1 | NÚMEROS INTEIROS 11 Demonstração: vamos supor por absurdo que exista um valor m com esta propriedade. Somando (–n) a cada termo da desigualdade, obtemos: ( ) ( ) ( )1n n m n n n+ − < + − < + + − 0 < m – n < 1 Porém, pelaproposição anterior, temos que, entre zero e um, não há número inteiro, logo uma contradição. Corolário 2: sejam ,a b∈Z . Se 1a b⋅ = , então 1.a b= = ± Corolário 3: sejam ,a b∈Z com 0b ≠ , então .a b a⋅ ≥ Demonstração: pela proposição anterior, temos que, não existe valor entre zero e um, logo, com 0b ≠ , então 1b ≥ . Sendo assim, .a b a b a⋅ = ⋅ ≥ Corolário 4: (Propriedade Arquimediana) sejam ,a b∈Z com 0b ≠ , então existe n∈Z tal que .n b a⋅ > Esse corolário quer nos dizer algo bem importante da matemática: que um conjunto (como os inteiros) não possui números infinitamente grandes ou infinitamente pequenos, pois sempre é possível obtermos números cada vez maiores ou menores. Já havíamos definido conjunto limitado inferiormente, agora, completaremos o Princípio da Boa Ordenação com a definição de conjunto limitado superiormente. Proposição 7: se T é um subconjunto de � não vazio e limitado superiormente, então T possui um maior elemento. Denotaremos, caso exista, o maior elemento do conjunto T, por max(T ) e por convenção, que o conjunto vazio é limitado superiormente por qualquer cota superior. Agora que todas as proposições já foram esclarecidas e que Princípio da Boa Ordenação está bem definido, podemos apresentar no próximo tópico, sua principal consequência: Princípio da Indução Matemática. Este princípio consta também nos axiomas de Peano, que falam sobre o sucessor de um número natural. Você pode aprofundar seus conhecimento acessando o link: https://www.ime.unicamp.br/~ftorres/ENSINO/MONOGRAFIAS/Afonso_TN18.pdf. DICAS 12 Neste tópico, você aprendeu que: • A adição e multiplicação são Bem Definidas: para todos , , ’, ’ ,se ’ ’, então ’ ’ e ’ ’.a b a b a a e b b a b a b a b a b∈ = = + = + ⋅ = ⋅Z • A adição e a multiplicação são Comutativas: para todos , , , e a b a b b a a b b a∈ + = + ⋅ = ⋅ Z . • A adição e a multiplicação são Associativas: ( ) ( ) ( ) ( )para todos , , , , e a b c a b c a b c a b c a b c∈ + + = + + ⋅ ⋅ = ⋅ ⋅ Z . • A adição e a multiplicação possuem Elementos Neutros para todos , , 0 e 1 .a a a a a∈ + = ⋅ = Z • A Adição possui elemento simétrico: ( )para todos , ,existe tal que 0a b a a b∈ = − + = Z . • A multiplicação é distributiva com relação à adição: para todos , , , ,a b c ∈ Z tem-se ( )a b c a b a c⋅ + = ⋅ + ⋅ • Existe Fechamento nos � : O conjunto dos � é fechada para a adição e multiplicação, ou seja, para todo , ,a b c∈N , tem-se que a b+ ∈N e a b⋅ ∈N. • A propriedade da Tricotomia: Dados ,a b∈Z , uma, e apenas uma, das seguintes possibilidades é verificada: RESUMO DO TÓPICO 1 ( ) (I) ; = (I) ; (II) ; = (II) ; (III) . = (III) . a b a b b a a b b a a b b a = = − ∈ < − − = − ∈ < N N • O Princípio da Boa Ordenação: Se S é um subconjunto não vazio de � e limitado inferiormente, então S possui um menor elemento. • A relação de ordem é satisfeita com as seguintes propriedades: (i) É reflexiva: ,a a a∀ ∈ ≤Z . (ii) É antissimétrica: , , , e .a b a b b a a b∀ ∈ ≤ ≤ ⇒ =Z (iii) É transitiva: , , , , e a b c a b b c a c∀ ∈ ≤ ≤ ⇒ ≤Z 13 • Para ,a b∈Z e r∈ N , temos: (i) ;a b a b⋅ = ⋅ (ii) a r≤ se, e somente se, ;r a r− ≤ ≤ (iii) ;a a a− ≤ ≤ (iv) a desigualdade triangular .a b a b a b− ≤ ± ≤ + 14 1 Para , ∈Za b , mostre que: AUTOATIVIDADE 2 Mostre que para todo , ∈Za b , vale a propriedade: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 2 2 3 3 a) b) 1 c) d) e) g 1 1 1 f ) ) a a a a a b a b a b a b a a b b − − = ⋅ = − − ⋅ = − ⋅ − ⋅ − = − ⋅ − = ⋅ − − = − − = ( ) ( ) ( ) ( ) ( ) ( ) a) b) c) d 0 ) e) a a a b a a b a a b a b c a c b a b c a b c − = − + = − − − − = − − − = + − − + = − − 15 TÓPICO 2 INDUÇÃO MATEMÁTICA UNIDADE 1 1 INTRODUÇÃO Neste tópico, veremos a forma de demonstrar pelo Princípio da Indução Matemática, “essa expressão designa o princípio que serve para o estabelecer a verdade de um teorema matemático em um número indefinido de casos” (ABBAGNANO, 2012, p. 645). Além de aprender a formalidade da demonstração, traremos várias aplicações, tanto para situações acadêmicas do estudo da matemática, quanto para as atividades com os estudantes das escolas. 2 PRINCÍPIO DA INDUÇÃO MATEMÁTICA Para entender um pouco o funcionamento do teorema antes de apresentá- lo, vamos supor algo bem intuitivo, acredito que você já tenha se divertido com este tipo de brincadeira que envolve dominós. Imagine uma quantidade de dominós colocados em sequência, de modo que ao derrubar um deles, o procedimento se estenderá até o último deles. Na prática, o método da brincadeira com dominós possui um funcionamento bem simples. Garanta que todos estejam alinhados, que o primeiro funcione e que este influencie no próximo e assim por diante. Assim, mesmo que a fila seja indefinidamente extensa, podemos garantir que todos os dominós cairão. Teorema 1: (Princípio da Indução Matemática) sejam S um subconjunto de � e a∈Z tais que: (I) a S∈ (II) S é fechado em relação à operação de “somar 1” a seus elementos, ou seja, , 1n n S n S∀ ∈ ⇒ + ∈ . Então, { };x x a S∈ ≥ ⊂Z . Parece simples o teorema, porém, apesar da simplicidade de imaginar que o sucessor de um número pertence a um subconjunto dos inteiros, este serve como base para um importante método de demonstração, que chamaremos de Prova por Indução Matemática. UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE 16 As ciências naturais utilizam o método chamado indução empírica para formular leis que devem reger determinados fenômenos a partir de um grande número de observações particulares, selecionadas adequadamente. Esse tipo de procedimento, embora não seja uma demonstração de que um dado fato é logicamente verdadeiro, é frequentemente satisfatório (FONSECA, 2011, p. 30). Apesar do comentário de Fonseca ser “satisfatório”, pode não ser relevante para várias situações da matemática, em que o intuito é que uma proposição seja válida para um certo conjunto de números. Bertrand Russel (1872-1970), matemático inglês, batizou a indução empírica de forma irônica, chamando de indução galinácea, que apresentava a seguinte história: Havia uma galinha nova no quintal de uma velha senhora. Diariamente, ao entardecer, a boa senhora levava milho às galinhas. No primeiro dia, a galinha, desconfiada, esperou que a senhora se retirasse para se alimentar. No segundo dia, a galinha, prudentemente, foi se alimentando enquanto a senhora se retirava. No nonagésimo dia, a galinha, cheia de intimidade, já não fazia caso da velha senhora. No centésimo dia, ao se aproximar a senhora, a galinha, por indução, foi ao encontro dela para reclamar o seu milho. Qual não foi a sua surpresa quando a senhora a pegou pelo pescoço com a intenção de pô-la na panela (HEFEZ, 2009, p. 10). Admitir que algo funcione para uma certa quantidade de valores não significa que funcione para qualquer uma delas. Esse foi o caso da galinha da estória do matemático Russel. Achou que funcionaria novamente no caso 100, porém, a prova não foi muito bem o esperado, pelo menos para a galinha. Veremos exemplos extremamente curiosos sobre a raciocínio indutivo que darão ênfase ao motivo de “demonstrar para validar”. Exemplo 5: encontramos um polinômio ( ) 2 – 41P n n n= + , que fornece apenas números primos. Veja na tabela a seguir, os 40 primeiros números obtidos através dele: TÓPICO 2 | INDUÇÃO MATEMÁTICA 17 n P(n) n P(n) n P(n) n P(n) 1 41 11 151 21 461 31 971 2 43 12 173 22 503 32 1033 3 47 13 197 23 547 33 1097 4 53 14 223 24 593 34 1163 5 61 15 251 25 641 35 1231 6 71 16 281 26 691 36 1301 7 83 17 313 27 743 37 1373 8 97 18 347 28 797 38 1447 9 113 19 383 29 853 39 1523 10 131 20 421 30 911 40 1601 TABELA 1 – VALORES APLICADOS EM P(n) FONTE: Os autores Será que conhecemos, então, um polinômio que fornece apenas números primos? Apesar de todos os números obtidosaté o momento serem realmente primos, o polinômio não funciona para ( )41 1681 41 41P = = ⋅ . Notem como é importante na matemática a demonstração. Apesar de refutarmos a ideia do polinómio com um contraexemplo, é fundamental trabalhar com verdades. Caso você tenha ficado surpreso com este polinômio, vamos lhe apresentar outro caso: ( ) 2 79 1601T n n n= − + . Este polinômio fornece primos do 1 até o 79, falhando em: ( ) 280 80 79 80 1601 1681 41 41T = − ⋅ + = = ⋅ . Sendo assim, aceite apenas afirmações que forem demonstradas para todos os números. DICAS UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE 18 Teorema 2: (Prova por Indução Matemática) sejam a∈Z e seja p(n) uma sentença aberta em n. Suponha que: (I) p(a) é verdadeiro, e que (II) é verdadeiro. Então, p(n) é verdadeiro para todo n a≥ . O teorema nos diz que, se um certo valor a goza da sentença definida nos números inteiros, e que, além disso, o sucessor de a também goza desta sentença, então todos os números deste conjunto gozam desta sentença. Diferente da indução empírica já comentada, a indução matemática não deixa pontos abertos quanto à validade de uma proposição. Mesmo que uma sentença seja verdade para uma finidade de valores, isso não significa que funcionará para todos. Segundo Hefez (2016, p. 15), o primeiro registro da utilização do Princípio da Indução Matemática foi feita por Francesco Maurolycus, em 1575, na tentativa de encontrar uma fórmula exata, para a soma dos n primeiros números naturais ímpares: ( )1 3 2 1 .nS n= + +…+ − Acompanhe o resultado obtido, quando realizamos a soma dos seis primeiros casos: ( ) ( ) , 1n a p n p n∀ ≥ ⇒ + 1 2 3 4 5 6 • 1 • 1 3 4 • 1 3 5 9 • 1 3 5 7 16 • 1 3 5 7 9 25 • 1 3 5 7 9 11 36 S S S S S S = = + = = + + = = + + + = = + + + + = = + + + + + = É intuitivo perceber que a fórmula ( )1 3 2 1 ,nS n= + +…+ − é o resultado da soma dos n números naturais ímpares. Ela nos fornece uma conjectura, para um raciocínio indutivo em que 2nS n= . Porém, já vimos anteriormente que nada está provado ainda. Vamos, então, utilizar do Princípio da Indução Matemática para realizar a demonstração. Os passos para realizar tal demonstração são simples: TÓPICO 2 | INDUÇÃO MATEMÁTICA 19 (I) Queremos provar que a propriedade ( ) 2: nP n S n= vale para todo n∈N. Verificaremos inicialmente que P(1) é válida. De fato: 21 1 1 S = = o que é verdade. (II) Agora, vamos supor que P(n) é verdadeira para certo valor de n, somamos ambos os membros da igualdade por (2n + 1), obtemos: Logo ( ) ( )1P n P n⇒ + . Assim, pelo Princípio da Indução, a proposição P(n) vale para todo n∈N . Colocaremos duas explicações da demonstração que não foram colocadas no exemplo, pois, “poluiriam” a escrita: • Somar (2n + 1) em ambos os lados da igualdade está ligado ao sucessor do próximo termo da sequência, ou seja, qual é o próximo número depois do (2n – 1). Para saber quem deve ser acrescido, devemos trocar no último termo da sequência (2n – 1), o n por n + 1. Perceba: ( ) ( ) ( ) ( )2 1 2 1 1 2 2 1 2 1n n n n − ⇒ + − = + − = + . • Após somarmos em ambos os lados da igualdade por (2n + 1), devemos conseguir realizar a implicação para o sucessor da nossa conjectura, ou seja, que o ( )22 1n n⇒ + . Para que você possa familiarizar com o método da indução, faremos alguns exemplos variados que lhe contribuirão com artifícios lógicos e manipulações matemática elementares importantíssimas para formular a ideia da utilização desta ferramenta. Exemplo 6: mostre que para n∈N, vale: ( ) ( ) 1 1 1 1 2 2 3 11 n hipótese de indução nn n + + + = ⋅ ⋅ ++ Demonstração: usaremos o Princípio da Indução Finita. Queremos provar que a propriedade: ( ) ( ) 1 1 1: 1 2 2 3 11 nP n nn n + + + = ⋅ ⋅ ++ ( ) ( ) ( ) ( ) ( ) ( ) 2 2 1 3 2 1 2 1 2 1 1 3 2 1 2 1 1 n n n n n n n + +…+ − + + = + + + +…+ − + + = + UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE 20 Vale para todo n∈N. Verificaremos inicialmente que P(1) é válida. De fato: ( ) 1 1 1 1 1 21 1 1 = ⇒ ++ O que é verdade. Supondo que P(n) é verdadeira para certo valor de n, somamos ambos os membros da igualdade por ( )( ) 1 , obtendo: 1 2n n+ + ( ) ( )( ) ( )( ) ( ) ( )( ) ( )( ) 2 1 1 1 1 1 1 2 2 3 11 1 2 1 2 2 1 1 2 2 1 1 2 n nn n n n n n n n n n n n n n + + + + = + ⋅ ⋅ ++ + + + + + + = + + + + = + + ( ) ( )( ) 1 ² 1 2 1 2 n n n n n + = + + + = + Logo, ( ) ( )1P n P n⇒ + . Assim pelo Princípio da Indução, a proposição P(n) vale para todo n∈N. Exemplo 7: encontre uma fórmula para n∈N , que determina a soma da sequência: 2 4 8 2 .n+ + + + Resolução: queremos encontrar uma fórmula para a seguinte soma: ( )2 4 8 2 InnS = + + + + (que é o sucessor da expressão mostrada como hipótese de indução) TÓPICO 2 | INDUÇÃO MATEMÁTICA 21 Note que ela é uma progressão geométrica, então multiplicaremos ambos os lados por 2, obtemos: ( )12 4 8 16 2 2 IIn nnS +⋅ = + + + + + Subtraímos (II) de (I), temos: 1 2 4 8 16 2 2 2 4 8 2 n n n n n S S +⋅ = + + + + + − = + + + + ( )12 2 2 2 1n nn nS S+= − + ⇒ = − Note que vários valores se cancelam: 4 e 4, 8 e 8, ..., 2n e 2n, sobrando apenas dois elementos. Desta forma, montamos nossa fórmula, ( )2 4 8 2 2 2 1 .n n+ + + + = − Tente realizar a demonstração! Exemplo 8: encontre uma fórmula para n∈N , que determina a soma da sequência: ( ) ( )1 4 7 3 5 3 2 .n n+ + + + − + − Resolução: queremos encontrar uma fórmula para a seguinte soma: ( ) ( ) ( )1 4 7 3 5 3 2 InS n n= + + + + − + − Note que ela é uma progressão aritmética, então vamos reordenar a soma, obtendo: ( ) ( ) ( )3 2 3 5 7 4 1 IInS n n= − + − + + + + Somando (I) de (II), temos: ( ) ( ) ( ) ( ) 1 4 3 5 3 2 3 2 3 5 4 1 n n S n n S n n = + + + − + − = − + − + + + 1 2 4 8 16 2 2 2 4 8 2 n n n n n S S +⋅ = + + + + + − = + + + + ( ) ( ) ( ) ( )2 3 1 3 1 3 1 3 1nS n n n n= − + − +…+ − + − n vezes + UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE 22 ( ) ( ) 2 3 1 3 1 2 n n S n n n n S ⇒ = − − ⇒ = Portanto, a fórmula procurada é ( ) ( ) ( )3 11 4 7 3 5 3 2 2 n n n n − + + + + − + − = . Novamente, tente realizar está demonstração! Já vimos uma quantidade significativa da aplicação do Princípio da Indução Matemática, porém, existe uma variação chamada Princípio da Indução Completa que abrange outros casos muito importantes. Teorema 3: (Prova por Indução Completa) seja p(n) uma sentença aberta tal que (i) p(a) é verdadeiro, e que (ii) ( ) , n p a∀ e p(a + 1) e ••• e ( )p n ⇒ p(n + 1) é verdadeiro Então, p(n) é verdadeiro para todo n a≥ . A diferença entre o Princípio de Indução Matemática com este, é que enquanto no primeiro tínhamos um número natural n qualquer e tentamos provar que P(n + 1) é verdadeira baseado apenas, na hipótese de que P(n) é verdadeira. Na indução completa, prova-se que P(n + 1) é verdadeira fundamentado no fato de que as proposições P(1), P(2), P(3), ..., P(n) são todas verdadeiras, ou seja, em vez de admitir que apenas P(n) é verdadeira, pode-se admitir que P(1), P(2), ..., P(n) são verdadeiros, desta forma, temos mais base e consistência na demonstração. 3 DEFINIÇÃO POR RECORRÊNCIA Para dar continuidade ao desenvolvimento das aplicações do método da indução, veremos o conceito de recorrência, que trará mais rigor no tratamento de algumas situações matemáticas. Muitas sequências, como as aritméticas e geométricas, podem ser definidas recursivamente, ou seja, mediado de uma regra que possibilita calcular qualquer termo, em função do antecessor imediato. TÓPICO 2 | INDUÇÃOMATEMÁTICA 23 Exemplo 9: seja a sequência ( )1 5 9 4 3n+ + +…+ − com n∈N. Essa é uma sequência bem conhecida, uma progressão aritmética de razão 4. Logo, uma forma de definir o próximo termo da sequência an+1, por recorrência, resumir-se-ia na expressão: 1 4.n na a+ = + Ou, ainda, a soma de todos Sn os termos, seria definida por 1 1.n n nS S a+ += + Perceba que neste exemplo elementar conseguimos notar a aplicação do conceito de recorrência por duas vezes, uma definindo o próximo termo da sequência e, no outro caso, a soma até determinado ponto. É importante ressaltar que podemos denotar somas como a dos exemplos anteriores, pela notação de somatório: 1 . n n i i S a = =∑ IMPORTANT E FIGURA – EXPLICAÇÃO DA NOTAÇÃO DE SOMATÓRIO FONTE: Os autores Existem algumas propriedades que apenas apresentaremos sobre o somatório. Sejam ai e bi duas sequências de elementos de um conjunto A munida de duas operações sujeitas às leis da aritmética e seja .c A∈ Vale as seguintes propriedades: UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE 24 ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 1 1 1 1 1 I II III IV n n n i i i i i i i n n i i i i n i i n i n i a b a b c a c a a a a a c nc = = = = = + + = = + = + ⋅ = ⋅ − = − = ∑ ∑ ∑ ∑ ∑ ∑ ∑ Exemplo 10: encontre uma expressão fechada para a soma ( )1 2 2 3 3 4 1 .n n⋅ + ⋅ + ⋅ +…+ ⋅ + Resolução: perceba que podemos escrever este somatório por: ( ) 1 1 . n i i i = ⋅ +∑ Utilizando da distributiva e da propriedade (i), temos: ( ) ( )2 2 1 1 1 1 1 n n n n i i i i i i i i i i = = = = ⋅ + = + = +∑ ∑ ∑ ∑ Usando os resultados do exercício 1 itens a) e b), que são: ( ) ( )( )2 2 21 1 2 11 2 e 1 2 2 6 n n n n n n n + + + + +…+ = + +…+ = TÓPICO 2 | INDUÇÃO MATEMÁTICA 25 ( )( ) ( ) ( )( ) ( ) ( )( ) ( )( ) ( )( ) 2 1 1 1 2 1 1 6 2 1 2 1 3 1 6 1 2 1 3 6 1 2 4 6 1 2 . 3 n n i i n n n n n i i n n n n n n n n n n n n n n = = + + + + = + + + + + = + + + = + + = + + = ∑ ∑ Podemos escrever então, Por recorrência, é possível definir o fatorial de um número inteiro, com 0n ≥ , denotado por n!, como sendo 0! = 1! = 1 e ( ) ( )1 ! ! 1 ,n n n+ = ⋅ + se 1n ≥ . Outra importante aplicação da recorrência está na definição da operação de potenciação. Seja a um elemento de um conjunto A munido de duas operações sujeitas às leis básicas da aritmética. As potências an com n inteiro, 0n ≥ , são definidas por recorrência, como: a1 = a e a0 = 1, se 0,a ≠ então 1n na a a+ = ⋅ . Com está definição, podemos apresentar e provar as propriedades da potenciação. Proposição 8: sejam ,a b A∈ e , m n∈N . Então: ( ) ( ) . (I) . (II) . (III) m n m n nm m n n n n a a a a a a b a b + ⋅ ⋅ = = ⋅ = ⋅ Demonstração: demonstraremos os itens (i) e (ii) apenas. Item (i): Fixando a e m arbitrariamente, realizaremos a prova por indução sobre n. Verificamos inicialmente que para n = 1 a propriedade é verdadeira, 1 1.m m ma a a a a +⋅ = ⋅ = UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE 26 Supondo que m n m na a a +⋅ = , temos que: ( ) ( )1 1 1 1m n m n m n m n m na a a a a a a a a a a+ + + +⋅ = ⋅ ⋅ = ⋅ ⋅ = ⋅ = Logo, por indução, a propriedade é válida. Note que as duas partes da demonstração obedecem a definição de potenciação e utiliza como artifício a associatividade da multiplicação. NOTA Item (ii): fixando a e m arbitrariamente realizaremos a prova por indução sobre n. Verificamos inicialmente que para n = 1 a propriedade é verdadeira, ( )1 1.m m ma a a ⋅= = Supondo que ( )nm m na a ⋅= , temos que: ( ) ( ) ( ) ( )1 1 1 .n n m nm m m m n m m n ma a a a a a a a+ ⋅ +⋅ ⋅ += ⋅ = ⋅ = ⋅ = Logo, por indução, a propriedade é válida. Neste caso, utilizamos para a demonstração, definição de potenciação, propriedade (i) e da distributiva da multiplicação. INTERESSA NTE Com essas definições, podemos realizar mais alguns exemplos de aplicação da prova por indução. Exemplo 11: mostre que para cada n∈N , é válida a propriedade ( )2 4 8 2 2 2 1 .n n+ + + + = − TÓPICO 2 | INDUÇÃO MATEMÁTICA 27 Demonstração: usaremos o Princípio da Indução Finita para provar então que a propriedade: ( ) ( ): 2 4 8 2 2 2 1n nP n + + + + = − Vale para todo n∈N. Verificaremos inicialmente que P(1) é válida. De fato: ( )12 2 2 1 2 2= − ⇒ = , o que é verdade. Supondo que P(n) é verdadeira para certo valor de n, somamos ambos os membros da igualdade por 2n+1, obtendo: ( )1 12 4 8 2 2 2 2 1 2n n n n+ ++ + + + + = − + ( ) 1 1 1 2 2 2 2 2 1 n n n + + + = − + = − Logo ( ) ( )1P n P n⇒ + . Assim, pelo Princípio da Indução, P(n) vale para todo n∈N . Exemplo 12: seja a∈Z , mostre que para cada n∈N, existe um m∈Z , tal que: 2 1( 1) 1.na ma+− = − Demonstração: usaremos o Princípio da Indução Finita. Queremos provar que a propriedade ( ) 2 1: ( 1) 1nP n a ma+− = − Vale para todo n∈N e para todo m∈Z . Verificaremos inicialmente que P(1) é válida. De fato: ( )2 1 3 3 2 2( 1) ( 1) 3 3 1 3 3 1a a a a a a a a+− = − = − + − = − + − Substituindo a2 – 3a + 3 por m, temos: am –1. O que mostra que é válida para 1. Supondo que P(n) é verdadeira para certo valor de n, multiplicando ambos os membros da igualdade por (a – 1)2, obtendo: ( ) ( ) ( )( ) ( ) 2 22 1 2 3 2 3 2 2 2 ( 1) 1 ( 1) 1 ( 1) 1 2 1 2 2 1 2 2 1 n n a a ma a a ma a a a m a m a am a a a m am a m + + − − = − − − = − − + = − − + + − = − − + + − UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE 28 Substituindo 2 2 2a m am a m− − + + por t = at – 1 Logo ( ) ( )1P n P n⇒ + . Assim pelo Princípio da Indução, P(n) vale para todo n∈N . Exemplo 13: mostre que para cada n > 4 com n∈N , vale n! > 2n. Demonstração: usaremos o Princípio da Indução Finita. Queremos provar que a propriedade P(n): n! > 2n vale para todo n∈N com 4n ≥ . Verificaremos inicialmente que P(4) é válida. De fato: 44! 2 24 16,> ⇒ > o que é verdade. Supondo que P(n) é verdadeira para certo valor de n, multiplicamos ambos os membros da igualdade por (n + 1), obtendo: n! (n + 1) > 2n(n + 1) Como mencionado n deve ser maior ou igual a 4, portanto: 4n ≥ Somando 1 a ambos os lados 1 5n+ ≥ com 5 é menor que 2, podemos escrever 1 5 2,n+ ≥ > ou seja, n + 1 > 2 multiplicando ambos os lados por 2n: Substituindo II e I, temos Logo, ( ) ( )1P n P n⇒ + . Assim pelo Princípio da Indução, a propriedade P(n) vale para todo n∈N . Neste ponto de nosso estudo, vimos uma forma de demonstração muito importante. Ela será bastante útil para entender e mostrar vários resultados posteriores em nosso material. Você poderá ler mais sobre aplicações especiais acerca da indução matemática, na Leitura Complementar desta unidade. ( ) 12 1 2 (II)n nn ++ > ( ) ( )1 ! 2 1 (I)nn n+ > ( ) ( ) ( ) 1 1 1 ! 2 1 2 1 ! 2 n n n n n n + + + > + > + > 29 RESUMO DO TÓPICO 2 Neste tópico, você aprendeu que: • A Prova por Indução Matemática: sejam a∈Z e seja p(n) uma sentença aberta em n. Suponha que: (i) p(a) é verdadeiro, e que (ii) n a∀ ≥ , ( ) ( )1p n p n⇒ + é verdadeiro. Então, p(n) é verdadeiro para todo n a≥ . • A Prova por Indução Completa: seja p(n) uma sentença aberta tal que (i) p(a) é verdadeiro, e que (ii) ( ) , n p a∀ e p(a + 1) e ... e ( ) ( )1p n p n⇒ + é verdadeiro Então, p(n) é verdadeiro para todo n a≥ . • As Propriedades do somatório são: ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 1 1 1 1 1 I II III IV n n n n i i i i i i n i i i i n n n i i i i i a b a b a a a a c a c a c nc + + = = = = = = = + = + − = − ⋅ = ⋅ = ∑ ∑ ∑ ∑ ∑ ∑ ∑ • A definição do fatorial de um número inteiro, com 0n ≥ , denotado por n!, como sendo: ( ) ( )0! 1! 1 e 1 !! 1 , se 1.n n n n= = + = ⋅ + ≥ • A definição da operação de potenciação. Seja a um elemento de um conjunto A munido de duas operações sujeitas às leis básicas da aritmética. As potências an com n inteiro, 0n ≥ , são definidas por recorrência, como: a1 = a e a0 = 1, se 0,a ≠ então 1n na a a+ = ⋅ . • Sejam , e , a b A m n∈ ∈N . Então, ( ) ( ) (I) (II) (III) m n m n nm m n n n n a a a a a a b a b + ⋅ ⋅ = = ⋅ = ⋅ 30 AUTOATIVIDADE 1 Mostre as seguintes fórmulas por indução: 2 Ache uma fórmula para cada uma das seguintes somas: ( ) ( )( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( )( ) 2 2 2 2 3 3 3 2 22 2 22 2 1 a) 1 2 2 1 2 1 b) 1 2 6 1 c) 1 2 2 4 1 d) 1 3 2 1 3 2 1 2 1 e) 2 4 2 3 1 1 1f) 1 2 2 3 11 31 1 1g) 1 2 3 2 3 4 1 2 4 1 2 1 1 1h) 1 3 3 5 2 n n n n n n n n n n n n n n n n n n nn n n n n n n n n + + +…+ = + + + +…+ = + + +…+ = − + +…+ − = + + + +…+ = + +…+ = ⋅ ⋅ +⋅ + + + +…+ = ⋅ ⋅ ⋅ ⋅ ⋅ + ⋅ + + + + +…+ ⋅ ⋅ ( ) ( ) ( ) ( ) ( ) ( ) 2 11 2 1 1 1 1i) 1 4 4 7 3 13 2 3 1 1 1 1j) 1 5 5 9 4 14 3 4 1 n nn n n nn n n nn n = +− ⋅ + + +…+ = ⋅ ⋅ +− ⋅ + + +…+ = ⋅ ⋅ +− ⋅ + ( ) ( ) ( ) a) 1 3 2 1 b) 1 4 3 2 c) 2 6 4 2 d) 3 9 3 1 1 1 1e) 3 9 27 3 n n n n n + +…+ − + +…+ − + +…+ − + +…+ + + …+ 31 ( ) ( ) ( ) a) 1 3 2 1 b) 1 4 3 2 c) 2 6 4 2 d) 3 9 3 1 1 1 1e) 3 9 27 3 n n n n n + +…+ − + +…+ − + +…+ − + +…+ + + …+ 3 Calcule fórmulas fechadas para as seguintes somas: 5 Mostre por indução as seguintes observações. 4 Seja a∈Z . Mostre que ( ) ( ) ( ) ( )( ) ( )( ) ( ) ( ) ( )2 2 2 2 2 2 a) 1 1 2 1 2 3 ··· 1 2 ··· . b) 1·2·3 2·3·4 3·4·5 ··· 1 2 . c) 1·3 3·5 5·7 ··· 2 1 2 1 . d) 1 1 2 1 2 3 ··· 1 2 3 ··· . n n n n n n n + + + + + + + + + + + + + + + + + + + + − + + + + + + + + + + + + ( ) ( )2 . ) b a para cada , existe tal que 1 1. para cada , existe tal que ) 1 1 n n n m a ma n m a ma ∈ ∈ + = + ∈ ∈ − = + N Z N Z 2 2 , para todo . ! , para todo com 4. ! 3 , para todo com 7. ! , para todo com 2. a) b) c) d) n n n n n n n n n n n n n n n n > ∈ > ∈ ≥ > ∈ ≥ < ∈ ≥ N N N N 32 33 TÓPICO 3 DIVISIBILIDADE UNIDADE 1 1 INTRODUÇÃO Neste tópico, apresentaremos o conceito de divisibilidade, retomaremos e aprofundaremos os conceitos acerca dos números inteiros. Além disso, utilizaremos uma linguagem um pouco mais formal do que normalmente utilizamos para apresentar o conceito de divisibilidade. Reforçando, divisibilidade não é nenhuma novidade e podemos tratá-la como uma continuação do conceito de múltiplos e divisores, porém com uma abordagem diferente. Veja a divisão de um número inteiro a por um número inteiro não nulo b. Note que se r = 0, resulta que a q b= × e seguem as seguintes relações: • a divisão de a por b tem resto 0; • a divisão de a por b é exata; • a é divisível por b; • a é um múltiplo de b; • b é um divisor de a; Ou seja, lembrando que são 5 afirmações verdadeiras desde que r = 0, para designar o mesmo fato. 2 DIVISIBILIDADE Neste subtópico, dando sequência a ideia explorada na introdução, teremos que desenvolver uma sexta afirmação, pois será interessante colocar o zero em algumas oportunidades. Desse modo, poderemos falar também de “pares” de números inteiros a e b, tais que exista um número inteiro t, de modo que .a t b= × 34 UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE Esta sexta forma de tratar a divisão é a nomenclatura clássica da aritmética e teoria dos números. ATENCAO Definição 1: dados a e b, números inteiros. Afirmaremos que b divide a, se existir .t∈Z de modo que .a t b= × De mesmo modo, diremos que b não divide a, quando não puder ser escrita a forma .a t b= × , com .t∈Z Notações: • b | a indica que b divide a; • b aŒ indica que b não divide a. Essa relação aqui definida é a de divisibilidade de números inteiros. Não pode ser confundida a relação de divisibilidade b | a com a de fração b | a. IMPORTANT E Exemplos: 1) 5|15, pois 15 3 5 e 3 .= × ∈Z 2) Mas 15 5Œ , pois não existe t inteiro tal que 5 15t= × . Note ainda: • Para o caso de t = 0, teremos 15 0 5t× = ≠ ; • Para o caso de t = 1, teremos 15 15 5t× = ≠ ; • Caso t > 1, teremos 15 15 5, e assim 15 5t t× > > × ≠ ; 3) 1 | k, para todo k∈Z , uma vez que 1 ,k k= × para todo k; 4) Este aqui é um tanto polêmico e por este motivo iremos reforçar esta análise mais tarde em nosso material: 0 | 0, pois, por exemplo, 0 7 0= × e ainda 7 .∈Z Proposição 8: 0 | a, se e somente se, a = 0. TÓPICO 3 | DIVISIBILIDADE 35 Mostraremos este caso para destituir a polêmica criada pelo exemplo 4 anterior. Como pode ser notado, estamos lidando com um caso de “se e somete se”, e assim sendo temos que mostrar: 0 0 0 0 a a e a a⇒ = = ⇒ (I) Mostraremos incialmente o primeiro caso. Seja a um número inteiro tal que 0 | a. Deste modo, utilizando a definição de divisibilidade, existe k∈Z , tal que 0a k= × . Mas, sabe-se que 0 0k× = , logo, a = 0. (II) Suponhamos agora que a é um número inteiro qualquer, é fácil notar que a | a, sendo que 1a a= × , para todo a inteiro e ainda 1 .∈Z Particularmente, se a = 0, chegamos a mesma conclusão. Logo, 0 | a. Por (i) e (ii), concluímos que 0 | 0.a a⇔ = Observações importantes: 1. Denotaremos por m • n, ou mn o produto do número m pelo número n. 2. Se b | a, e 0b ≠ , então o número inteiro t, em que a = tb é único. Se considerarmos que existe um k (outro inteiro) onde a = kb, teríamos que kb = tb, sendo que supondo 0b ≠ , podemos cancelar b e obter k = t. 3. Já justificamos que 0 | 0. Porém, é interessante perceber que 0 1 0, 0 5 0, 0 12 0, 0 147 0,= × = × = × = × ou seja, o número t não é único. Assim, dizemos que o quociente de 0 por 0 é indeterminado. Por isso, é verdade que 0 | 0, porém, 0 0 não está definido. 4. Pelo fato da não unicidade citada na observação anterior, é comum não utilizar zero como divisor. Assim, daqui em diante iremos supor os divisores diferentes de zero, apesar de não ser dito de modo explícito. 5. Poderemos utilizar as seguintes expressões, mesmo se b = 0: • b é um divisor de a. • a é múltiplo de b. 6. Se b = 0 não poderemos utilizar: • a divisão de a por b tem resto 0; • a divisão de a por b é exata; • a é divisível por b. 2.1 PROPRIEDADES DA DIVISIBILIDADE Neste momento, apresentaremos as propriedades iniciais da divisibilidade de números inteiros. Essas propriedades são fundamentais, pois serão utilizadas na demonstração de outros resultados e ainda para resolver problemas propostos. 36 UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE Propriedade 1: se a | b e b | a, então a = b. Para se compreender o que esta propriedade trata, devemos imaginar que para cada número inteiro diferente de zero a, o único número b (inteiro) que é concomitantemente múltiplo e divisor de a, é o próprio a. Demonstração: se a | b e b | a, então, por definição, existem números inteiros t e k tais que b = ta e a = kb. Dessa forma, a = k(ta) = (kt)a. Mas 0a ≠ ; logo, de a = (kt)a, segue que kt = 1. No entanto, t e k são números inteiros; portanto, kt = 1 só é possível se k = t = 1 e, assim, b = ta (ou a = kb) segue que a = b. Propriedade 2: se a | b e b | m, então a | m. Essa propriedade é conhecida como a propriedade de transitividade da divisibilidade. Ou seja, informalmente: divisor do divisor é divisor! Demonstração: se a | b e b | m, então, por definição, existem números inteiros t e k de modo que b = ta e m = kb. Assim, temos que: m = k(ta) = (kt)a (i) mas como t e k são números inteiros, então x = kt também será um número inteiro, já que o produto de dois números inteiros é um número inteiro. Dessa forma, por (i), temos que m = xa, com x∈Z . Portanto, por definição, a | m. Propriedade 3: se a | m e a | n, então a | m + n. Essa propriedade nos informa que se a é divisor de dois números m e n, teremos que a também será divisor da soma m + n. Demonstração:se a | m e a | n, então, por definição, existem números inteiros t e k de modo que m = ta e n = ka. Assim, temos que: m + n = ta + ka = (t + k)a (i), mas como t e k são números inteiros, então z = t + k também será um número inteiro, já que a soma de dois números inteiros é um número inteiro. Dessa forma, por (i), temos que m + n = za, com z∈Z . Portanto, por definição, a | m + n. Propriedade 4: se a | m, então a | mn. Essa propriedade nos mostra que se a divide m, a também divide qualquer múltiplo de m. Demonstração: se a | m, então, por definição, existe um número inteiro k tal que m = ka. Então, para qualquer número inteiro n, temos que mn = (ka)n = (kn)a. Dessa forma, se fizermos kn = t, então teremos que mn = ta, com t∈Z , e isso é suficiente para garantir que a | mn. Propriedade 5: se a | m e a | n, então a | xm + yn, para quaisquer números inteiros x e y. TÓPICO 3 | DIVISIBILIDADE 37 Informalmente, podemos definir essa propriedade sendo que se a é divisor de m e n, então a também será divisor da soma dos produtos xm e yn, com xe y∈Z . Demonstração: utilizaremos as propriedades 3 e 4. Desta forma, suponhamos que a seja um divisor de m e de n. Portanto, se x e y são números inteiros, então, pela propriedade 4, temos que a | xm e a | yn. Como temos que, a | xm e a | yn, utilizamos a propriedade 3 para concluir que a é divisor da soma entre xm e yn. Assim, podemos afirmar que a | xm + yn, para ,x y∈Z . Além de demonstrar essas propriedades importantes e, obviamente, já munidos delas, resolveremos alguns problemas que tratam de divisibilidade. Exemplo 14: 1008 é divisível por 21? Resolução: sim, uma vez que ( )41008 3 7 2 3= ⋅ ⋅ ⋅ . E, ainda, realizando 42 3 k⋅ = , temos que 1008 3 7 21k k= ⋅ ⋅ = , com k∈Z . Exemplo 15: o número 42 5⋅ é divisível por 3? Resolução: não, basta notar que a decomposição deste número não contém o número 3. Exemplo 16: encontre o menor número natural n tal que n! é divisível por 990. Resolução: como 990 2 3² 5 11= ⋅ ⋅ ⋅ , para que n! seja divisível por 990, é necessário que em sua decomposição haja todos esses fatores. 11 é primo, logo, ele mesmo tem que estar contido no produto. Observe que 11! é divisível por 2, por 32 e por 5. Assim, n = 11 é o menor valor possível, pois o fatorial de qualquer outro número menor que este não terá o fator 11 em sua decomposição. Tentaremos notar que a divisibilidade em Z é uma relação de ordem, uma vez que: (I) É reflexiva: para todo a, temos que a | a. (II) É transitiva: se a |b e b | c, temos que a | c. (III) É antissimétrica: se a | b, e b | a, então a = b. Tente voltar no texto e determinar quais as propriedades que justificam tais afirmações. ATENCAO 38 UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE A partir disso, mostraremos alguns resultados relevantes: Proposição 9: sejam , e a b n∈ ∈Z N , então a – b | an – bn. Demonstração: usaremos indução em n. É elementar que a propriedade é válida para n = 1. Pois, a – b | a1 – b1 = a – b. Supondo agora a propriedade válida para n, ou seja, a – b | an – bn, escreveremos percebendo que podemos somar e subtrair um valor de uma expressão, sem alterar o seu valor: ( ) ( )1 1 .n n n n n n na b aa bb a b a b a b+ +− = − + − = − + −n nba ba Como a – b | a – b, e por hipótese a – b | an – bn, decorre da propriedade 5, que a – b | an+1 – bn+1. Verificando o resultado para todo n. Proposição 10: sejam , e a b n∈ ∈Z N , então a + b | a2n+1 – b2n+1. Demonstração: utilizaremos novamente indução em n. Note que a propriedade é válida para n = 0. Utilizaremos zero para fins de simplificação dos raciocínios, veja que a + b | a1 + b1. Supondo válida a propriedade para n, ou seja, a + b | a2n+1 – b2n+1, escreveremos: ( ) ( ) ( ) ( ) 2 1 1 2 1 1 2 1 2 1 2 2 1 2 1 2 2 2 1 2 1 2 1 ² ² ² ² . n n n n n n n n n a b a a b a b a b b a b a b a b + + + + + + + + + + + − = − + + = − + + Como a + b | a2 – b2 = (a – b)(a + b), e, por hipótese, a + b | a2n+1 – b2n+1, decorre das propriedades anterior que a + b | a2(n+1)+1 – b2(n+1)+1, verificando o resultado para todo n. Proposição 11: sejam , e a b n∈ ∈Z N , então a + b | a2n – b2n. Demonstração: novamente, utilizaremos indução em n. Notamos que a afirmação é válida para n = 1, pois é elementar notar que a + b | a2 – b2 = (a – b)(a + b). Supondo agora válida a propriedade para n, temos que a + b | a2n – b2n. Então, escreveremos: ( ) ( ) ( ) ( )2 1 2 1 2 2 2 2 2 2 2 2 2 2² ² ² ² .n n n n n n n n na b a a b a b a b b a b a b a b+ +− = − + − = − + − Como a + b | a2 + b2, e, por hipótese, a + b | a2n – b2n, decorre das propriedades anteriores que a + b | a2(n+1) – b2(n+1), verificando o resultado para todo n. TÓPICO 3 | DIVISIBILIDADE 39 Exemplo 17: para quais valores de ,a∈N temos que 4 3 22 | 2 1a a a a+ + + + . Resolução: teremos como hipótese que 4 3 22 | 2 1a a a a+ + + + , logo, podemos reescrever utilizando as proposições anteriores, sendo: ( )4 4 3 3 3 3 2 22 | 2 2 2 2 1 16 8 8 4a a a a a+ − + + + + + − + + + − − + Sabemos, então que: Logo, basta verificar os valores para os quais: a + 2 | 5. Como 5 é divisível por 1 e 5, teremos que: ( )2 1 1 , a a nãoconsideraremos poisaé natural+ = ⇒ = − (não consideraremos, pois a é natural) ou 2 5 3.a a+ = ⇒ = Exemplo 18: mostre que 53 | 74n – 24n Resolução: temos que, ( )24 2 2 47 49 53 4 53 4 53 2nn n n nk k k= = − = − = + Logo: 74n – 24n = 53k Portanto, 53 | 74n – 24n. 3 DIVISÃO EUCLIDIANA Neste ponto de nosso material, introduziremos um conceito baseado nos estudos de Euclides, nos seus Elementos, em que é tratado que mesmo que quando um número inteiro a não divide outro inteiro b, é citado que sempre é possível efetuar a divisão, porém, neste caso, com um resto (lembrando que Euclides só tratava de números positivos). Teorema 4 (Divisão Euclidiana): sejam a e b, dois números inteiros quaisquer, com 0a ≠ . Existem dois números (únicos) q e r, tais que: , 0b a q r com r a= ⋅ + < ≤ . Demonstração: vamos considerar o seguinte conjunto (incluindo o zero): { } { }( ); 0 .S x b ay y= = − ∈ ∩ ∪Z N 4 4 2 2 3 3 2 1 2 1 2 2 2 2 pois pois . , pois . • 2 | 2 , | . • 2 | 2 , | • 2| 2 | n n n n n n a a a b a b a a a b a b a a a b a b + + + − + − + + + − + − + − 40 UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE Demonstraremos dois fatos, a existência dos valores q e r e fato de serem únicos. Existência: utilizando a Propriedade Arquimediana, dizemos que existe n∈Z , tal que n (–a) > b, e, assim, temos que b – na > 0. Esse resultado mostra que S não é vazio. Percebendo que S é limitado inferiormente por zero, podemos utilizar o princípio da boa ordenação e aferir que S possui um menor elemento r. A partir disso, vamos supor que r = b – aq. Sabendo que 0r ≥ , devemos mostrar agora que .r a< Supomos, então, por absurdo que r a≥ . Desta forma existe { }0s∈ ∪N , em que r a s= + , e assim, 0 .s r≤ < Contudo, isso contradiz o fato que r é o menor elemento de S. Unicidade: suponhamos que 'b aq r aq r= + ′= + , onde , , , 'q q r r′ são inteiros. Ainda temos que perceber que: 0 0r a e r a≤ < ≤ ′ < . Assim, vem: .a r r r a′− < − ≤ − < O que resulta que: . r r a′ − < Por outro lado, ( )' , a q q r r− = −′ o que gera: ' . a q q r r a− −′= < O que só é possível, quando e 'q q r r′= = . Esse resultado nos mostra os números q e r, que são respectivamente nomeados de quociente e resto da divisão de b por a. Nesta divisão (euclidiana) o resto só será zero, caso a | b. ATENCAO Exemplo 19: como exemplo do resultado visto, podemos afirmar que para a divisão de 19 por 5, temos q = 3 e r = 4. Pois, sabemos que b a q r= ⋅ + , assim 19 5 3 4= ⋅ + . Já se tivéssemos –19 por 5, seriam q = – 4 e r = 1. Pois, ( )19 5 4 1− = ⋅ − + . Exemplo 20: mostrar que o resultado da divisão de 10n por 9 é sempre 1, para todo n. Resolução: para garantir a veracidade do resultado, utilizaremos indução em n. De fato, para n = 1, é elementar, pois, 110 9 1 1= ⋅ + . Agora,supondo válido o resultado para n, ou seja, 10 9 1n q= ⋅ + , iremos escrever: ( ) ( )110 10 10 9 1 10 9 10 10 9 10 9 1 9 10 1n n n n n n nq q+ = ⋅ = + ⋅ = ⋅ + = ⋅ + ⋅ + = ⋅ + + TÓPICO 3 | DIVISIBILIDADE 41 O que mostra o resultado válido para todo n natural. Proposição 12: dados dois naturais a e b, com a > 0, existe um inteiro n, tal que: ( )1na b n a≤ < + . Demonstração: esta proposição procura mostrar que um sempre existe um número b entre dois múltiplos de um número natural a. Estes múltiplos são representados por na e (n + 1)a, ou seja, a multiplicação de a por n e por seu sucessor. Utilizando o conceito visto de divisão euclidiana, temos ,q r∈Z , com 0 r a≤ < , determinados univocamente, em que b a q r= ⋅ + . Basta usar agora, n = q. Prezado acadêmico, os próximos dois exemplos serão citados sem sua devida demonstração, porém, fica como sugestão você procurar mostrar ou criar situações em sua mente que permitam comprovar sua veracidade. DICAS Exemplo 21: dado um número inteiro n, temos duas possibilidades: (I) A divisão de n por 2, tem resto 0, ou seja, existe ,q∈Z onde n = 2q, ou ainda, (II) A divisão de n por 2, tem resto 1, ou seja, existe ,q∈Z onde n = 2q + 1. A partir disso, classificamos os números inteiros em dois tipos, os números pares e os números ímpares. Exemplo 22: Todo número inteiro pode ser escrito na forma n = mk + r, com 0 r m≤ < . Ilustrando: • Todo número n, pode ser escrito como 3k, ou 3k+1 ou 3k+2 • Todo número n, pode ser escrito como 4k, ou 4k+1, ou 4k+2 ou 4k+3, e assim por diante. Exemplo 23: determinaremos a quantidade de múltiplos de 5, entre 1 e 253. Resolução: sabemos que pela divisão euclidiana, podemos escrever: 253 5 50 3= ⋅ + . Deste modo, o maior deles é 5 50⋅ , e, assim sendo, podemos escrever os múltiplos de 5 entre 5 e 253: 1 5, 2 5, 3 5,..., 5 50⋅ ⋅ ⋅ ⋅ . Que obviamente resultam em 50 valores. Os estudos que seguem abordarão vários conceitos, e todos eles estão fortemente ligados com o conceito de divisibilidade. Desta forma, é importante que você esteja bastante apropriado deste embasamento teórico para a sequência de seus estudos. 42 RESUMO DO TÓPICO 3 Neste tópico, você aprendeu que: • Dados a e b, números inteiros. Afirmaremos que b divide a, se existir t∈Z de modo que . a t b= × De mesmo modo, diremos que b não divide a, quando não puder ser escrita a forma . a t b= × , com t∈Z . • b | a indica que b divide a; • b aŒ indica que b não divide a. • Se a | b e b | a, então a = b. • Se a | b e b | m, então a | m. • Se a | m e a | n, então a | m + n. • Se a | m, então a | mn. • Se a | m e a | n, então a | xm + yn, para quaisquer números inteiros x e y. • Sejam , e a b n∈ ∈Z N , então a – b | an – bn. • Sejam , e a b n∈ ∈Z N , então a + b | a2n+1 – b2n+1. • Sejam , e a b n∈ ∈Z N , então a + b | a2n – b2n. • Sejam a e b, dois números inteiros quaisquer, com 0a ≠ . Existem dois números (únicos) q e r, tais que: , com 0b a q r r a= ⋅ + < ≤ • Dados dois naturais a e b, com a > 0, existe um inteiro n, tal que: ( )1na b n a≤ < + • Dado um número inteiro n, temos duas possibilidades: (I) A divisão de n por 2, tem resto 0, ou seja, existe ,q∈Z onde n = 2q, ou ainda, (II) A divisão de n por 2, tem resto 1, ou seja, existe ,q∈Z onde n = 2q + 1. • Todo número inteiro pode ser escrito na forma n = mk + r, com 0 r m≤ < . 43 1 Mostre que dados a, b e c inteiros, com 0c ≠ , temos: .ac bc a b⇔ 2 Determinar a soma de todos os múltiplos de 6 que podem ser escritos com 2 dígitos. 3 Com quantos zeros termina 1000! 4 Mostre utilizando indução: a) 8 | 32n + 7 b) 169 | 33n+3 – 26n – 27 5 Mostre que 70 7013 | 2 3 .+ 6 Mostre que para todo n: a) 9 | 10n + 7 b) 8 | 32n + 7 7 Para quais valores de a, temos que a + 2 | a4 + 2. 8 Determine o quociente e o resto da: a) Divisão de 36 por 7. b) Divisão de 147 por 32. 9 Verifique a paridade: a) Da soma de dois números inteiros. b) Da diferença de dois números inteiros. c) Do produto de dois números inteiros. d) Da soma de n ímpares. 10 Mostre que a é par, se e somente se, an é par. 11 Seja a terna de números n, n + 1 e n + 2, mostre que apenas um deles é divisível por 3. AUTOATIVIDADE 44 12 (ENC, 2002) O resto da divisão do inteiro N por 20 é 8. Qual é o resto da divisão de N por 5? FONTE: Exame Nacional de Cursos – INEP (2002) 13 Ache o menor múltiplo de 5 que deixa resto 2 quando dividido por 3 e por 4. 14 (ENC, 2000) Mostre que, se um número a não é divisível por 3, então a2 deixa resto 1 na divisão por 3. FONTE: Exame Nacional de Cursos – INEP (2000) 45 TÓPICO 4 SISTEMAS DE NUMERAÇÃO UNIDADE 1 1 INTRODUÇÃO O sistema de numeração que estamos habituados a utilizar é o sistema posicional de base 10. Porém, existem outros sistemas de numeração que são bastante usuais e que tem sua base de análise fortemente ligadas à Aritmética. Por exemplo, o sistema sexagesimal que, de acordo com Roque (2012, p. 50), datam registros em fontes históricas por volta de 1700 a.C. na civilização dos babilônicos. Era usado, frequentemente, por matemáticos e astrônomos. Eles faziam uma combinação de base 60 e de base 10, pois os sinais até 59 mudam de 10 em 10. Por exemplo, para representarmos o valor decimal de 1h4min23s, temos que calcular ( )1 3600 4 60 23 6023 . s⋅ + ⋅ + = Portanto, o sistema que usamos para representar as horas é um sistema sexagesimal. Neste tópico, dedicaremos algumas linhas para discutir a base formal desse sistema de numeração e ampliar nosso horizonte para outras formas de representações numéricas. 2 SISTEMA DE NUMERAÇÃO DECIMAL O sistema que utilizamos é o sistema de base 10, ele está organizado através de agrupamentos de 10 em 10, conforme podemos visualizar: FIGURA 1 – CLASSES E ORDENS DE BASE 10 FONTE: Os autores 46 UNIDADE 1 | NÚMEROS INTEIROS E DIVISIBILIDADE Por exemplo, no nosso sistema decimal, no número 325, o 3 representa 100; o 2 representa 20 e o 5 representa 5 mesmo. Assim, 2 1 0325 3 10 2 10 5 10= ⋅ + ⋅ + ⋅ . Mais genericamente, podemos escrever um número n, em base 10, como sendo: 𝑛 = 𝑎0 + 𝑎110 + 𝑎2102 + ⋯ + 𝑎𝑟 10𝑟, em que 𝑟 ≥ 0 e 𝑎𝑖 ∈ 0, 1, … , 9 ; para 𝑖 = 0, 1, 2, … , 𝑟 e o representamos por 𝑎𝑟𝑎𝑟−1 … 𝑎1𝑎0 com 𝑎𝑖 sendo um dígito de 𝑛. Exemplo 24: 11547 = 7 + 4 × 10 + 5 × 102 + 1 × 103 + 1 × 104 Este sistema de numeração supracitado já está no nosso íntimo emprocessos matemáticos que já vivenciamos, agora, generalizaremos os sistemas de numeração para uma base qualquer. 3 SISTEMA DE NUMERAÇÃO EM UMA BASE QUALQUER Ao utilizar uma base qualquer (chamaremos 𝑏), devemos supor um conjunto de 𝑏 símbolos 0, 1, 2, … , 𝑏 − 1 que representará quaisquer números. utilizaremos o Teorema a seguir para garantir a existência destes números nesta base 𝑏. Teorema 5: seja 𝑏 um número natural e 𝑀 = 0, 1, 2, … , 𝑏 − 1 com 𝑏 > 1. Todo número natural 𝑛 pode ser representado, de modo único, da seguinte maneira: 𝑛 = 𝑎0 + 𝑎1𝑏 + 𝑎2𝑏2 + ⋯ + 𝑎𝑟 𝑏𝑟, em que 𝑟 ≥ 0, 𝑎𝑖 ∈ 𝑀, com 𝑖 = 0, 1, 2, … , 𝑟 e 𝑎𝑟 ≠ 0. Demonstração: mostraremos a existência da representação por indução em 𝑛. Se 𝑛 < 𝑏, neste caso, basta tomar 𝑛 = 𝑎0 e a representação está definida. Suponha agora, 𝑛 ≥ 𝑏 e que para todo 𝑞 𝜖 ℕ entre 1 ≤ 𝑞 < 𝑛 a representação esteja definida. Pelo algoritmo de Euclides temos 𝑛 = 𝑏𝑞 + 𝑎0, com 𝑎0 ∈ 𝑀. Observe que de 𝑞 < 𝑛, pois, caso contrário teríamos: 𝑛 = 𝑏𝑞 + 𝑎0 ≥ 𝑏𝑞 > 𝑞 ≥ 𝑛 absurdo. Pela hipótese de indução podemos escrever 𝑞 na base 𝑏, ou seja, 𝑞 = 𝑎0 + 𝑎1𝑏 + 𝑎2𝑏2 + ⋯ + 𝑎𝑟 𝑏𝑟−1 com 𝑎0 ∈ 𝑀 e 𝑎0 ≠ 0. Logo, 𝑛 = 𝑏 𝑎0 + 𝑎1𝑏 + 𝑎2𝑏2 + ⋯ + 𝑎𝑟 𝑏𝑟−1 = 𝑎0 + 𝑎1𝑏 + 𝑎2𝑏2 + ⋯ + 𝑎𝑟 𝑏𝑟, o que conclui a existência da representação. Devemos garantir a unicidade da escrita e também faremos por meio do segundo princípio de indução. É fácil ver que para 𝑛 ≤ 𝑏 a unicidade é óbvia. Suponhamos que 𝑛 > 𝑏, e que a unicidade é válida para todo 𝑞, com 1 ≤ 𝑞 < 𝑛. Suponhamos