Prévia do material em texto
Mestrado Profissional em Matemática em Rede Nacional Iniciação à Matemática Autores: Krerley Oliveira Adán J. Corcho Unidade II: Capítulos III e IV 3 Divisibilidade Os números governam o mundo. Platão A teoria dos números é o ramo da Matemática que estuda os mis- térios dos números e teve sua origem na antiga Grécia. Os belíssimos problemas ligados a esta área constituem, até hoje, uma das princi- pais fontes inspiradoras dos amantes da Matemática. Além disso, essa área possui várias aplicações úteis a humanidade, como por exemplo, o processo de criptogra�a usado em transações pela Internet. Alguns problemas em teoria dos números demoram séculos para serem resolvidos, como por exemplo o último teorema de Fermat, que a�rma que não existe nenhum conjunto de inteiros positivos x, y, z e n com n maior que 2 que satisfaça xn + yn = zn. Esse problema foi ob- jeto de fervorosas pesquisas durante mais de 300 anos e foi �nalmente demonstrado em 1995 pelo matemático Andrew Wiles. Ainda hoje persistem muitas questões naturais e simples sem res- posta. Por exemplo, ninguém sabe mostrar (apesar de todo mundo 89 90 3 Divisibilidade acreditar que é verdade!) que todo natural par é soma de dois pri- mos. Essa é a famosa conjectura de Goldbach. Essa simplicidade de se anunciar problemas e a extrema di�culdade em resolvê-los faz desta área um grande atrativo para os matemáticos do mundo todo. Este capítulo será dedicado ao estudo de algumas propriedades básicas relativas aos números inteiros. 3.1 Conceitos Fundamentais e Divisão Eu- clidiana Denotamos por Z o conjunto dos números inteiros formado pelo con- junto dos números naturais N = {1, 2, 3, . . .} munido do zero e dos números negativos. Ou seja, Z = {. . . ,−3,−2,−1, 0, 1, 2, 3, . . .}. Começamos observando que a soma, diferença e produto de núme- ros inteiros também serão números inteiros. Entretanto, o quociente de dois inteiros pode ser um inteiro ou não. Uma das propriedades fundamentais dos números naturais que uti- lizaremos ao longo do texto é o conhecido princípio da boa ordenação, que a�rma o seguinte: Princípio da Boa Ordenação: todo subconjunto não vazio A ⊆ N possui um elemento menor que todos os outros elementos deste, ou seja, existe a ∈ A tal que a ≤ n para todo n ∈ A. Por exemplo, se A é o conjunto dos números pares, o menor ele- mento de A é o número 2. Por outro lado, observamos que o conjunto dos números inteiros não goza da boa ordenação. Apesar do princípio da boa ordenação parecer inocente e natural, muitos resultados importantes a respeito dos números naturais decor- 3.1 Conceitos Fundamentais e Divisão Euclidiana 91 rem do mesmo, como veremos ao longo de todo este capítulo. De�nição 3.1. Sejam a e b inteiros. Dizemos que a divide b se existe um inteiro q tal que b = aq. Também usaremos as frases a é divisor de b ou b é múltiplo de a para signi�car esta situação. Usaremos a notação a | b para representar todas as frases equi- valentes ditas anteriormente. Se a não for divisor de b, então escre- veremos a - b. Exemplo 3.2. 7 | 21 pois 21 = 7 · 3. Por outro lado 3 - 8 pois considerando o conjunto M = {3m, m ∈ N} = {3, 6, 9, 12, . . .} dos múltiplos positivos de 3 vemos que 8 não pertence ao mesmo. A seguinte proposição é um bom exercício para entender os con- ceitos enunciados acima. Proposição 3.3. Sejam a, b e c números inteiros. Então, (a) se a | b e b | c então a | c; (b) se a | b e a | c então a | (b+ c) e a | (b− c); (c) se a e b são positivos e a | b então 0 < a ≤ b; (d) se a | b e b | a então a = b ou a = −b. Demonstração. Se a | b e b | c então existem inteiros q1 e q2 tais que b = aq1 (3.1) e c = bq2. (3.2) 92 3 Divisibilidade Substituindo (3.1) em (3.2) temos que c = aq1q2 = aq, onde q = q1q2 ∈ Z, (3.3) provando isto a a�rmação feita em (a). Agora provaremos (b). Com efeito, se a | b e a | c valem as igualdades b = aq1, q1 ∈ Z (3.4) e c = aq2, q2 ∈ Z. (3.5) Operando com os ambos lados das igualdades (3.4) e (3.5) temos que b+ c = a(q1 + q2︸ ︷︷ ︸ r∈Z ) e b− c = a(q1 − q2︸ ︷︷ ︸ s∈Z ), obtendo assim o resultado desejado. Continuamos agora com a prova de (c). De fato, se a | b, sendo ambos positivos, então b = aq com q ≥ 1. (3.6) Logo, multiplicando por a ambos lados de (3.6) temos (como a é posi- tivo) que b = aq ≥ a > 0, como esperávamos. Finalmente, provaremos (d). Com este propósito observamos que se a | b e b | a então |a| divide |b| e |b| divide |a|. Portanto, pelo item (c) temos que |a| ≤ |b| e |b| ≤ |a|, ou seja, |a| ≤ |b| ≤ |a|. Logo, |a| = |b| e consequentemente a = b ou a = −b. 3.1 Conceitos Fundamentais e Divisão Euclidiana 93 Exemplo 3.4. Prove que o número N = 545362−7 não é divisível por 5. Solução. Vamos mostrar isso utilizando o método do absurdo. Se este número fosse divisível por 5, então 545362 − 7 = 5q. Logo, 7 = 545362 − 5q, ou seja, 7 seria divisível por 5, o que é um absurdo. O próximo passo de nossa discussão é ver o que acontece quando um número não é divisível por outro. Por exemplo, analisemos se 31 é divisível por 7 e para isto listaremos a diferença entre 31 e os múltiplos positivos de 7, isto é: r1 = 31− 7 · 1 = 24, r2 = 31− 7 · 2 = 17, r3 = 31− 7 · 3 = 10, r4 = 31− 7 · 4 = 3, r5 = 31− 7 · 5 = −4, r6 = 31− 7 · 6 = −11, ... Claramente 31 não é divisível por 7, pois caso contrário teríamos que alguma das diferenças acima seria igual a zero, o que é impossível pois as diferenças rq = 31 − 7q com 1 ≤ q ≤ 4 são todas positivas e com q ≥ 5 são todas negativas. Entretanto, notamos que entre as diferenças positivas a única que é menor que 7 corresponde ao caso q = 4. O resultado seguinte nos diz o que acontece no caso geral da divisão de um inteiro b por um inteiro positivo a. 94 3 Divisibilidade Teorema 3.5 (Divisão Euclidiana). Dados dois inteiros a e b, sendo a positivo, existem únicos inteiros q e r tais que b = aq + r, 0 ≤ r < a. Se a - b, então r satisfaz a desigualdade estrita 0 < r < a. Demonstração. Por simplicidade, suporemos que b é positivo. Se b < a, basta tomar q = 0 e r = b. Se b = a, então tomamos q = 1 e r = 0. Assim, assumiremos também que b > a > 0. Consideremos o conjunto R = {b− aq ∈ Z; b− aq ≥ 0} ⊆ N ∪ {0} (3.7) Notemos que o conjunto R é não vazio, pois b − a ∈ R, já que b − a > 0. Deste modo, pelo princípio da boa ordenação temos que R admite um menor elemento, que denotaremos por r. Claramente r = b − aq ≥ 0, para algum q ≥ 0. Além disso, r < a pois caso contrário r = b− aq ≥ a⇒ b− a(q + 1) ≥ 0. (3.8) Por outro lado, a > 0⇒ b− a(q + 1) < b− aq. (3.9) Das desigualdades (3.8) e (3.9) segue que 0 ≤ b− a(q + 1) < b− aq, contradizendo o fato de que r = b−aq é o menor elemento não negativo de R. Agora provaremos que de fato r e q, escolhidos desta forma, são únicos. Com efeito, suponhamos que existem outros inteiros r1 e q1 tais que b = aq1 + r1, 0 ≤ r1 < a. 3.1 Conceitos Fundamentais e Divisão Euclidiana 95 Então resulta que aq + r = aq1 + r1. Logo, (r − r1) = (q1 − q)a; (3.10) sendo assim, r−r1 é múltiplo de a. Mas, em virtude de−a < r−r1 < a, o único valor que r − r1 pode tomar, sendo este múltiplo de a, é r − r1 = 0. Portanto, r = r1, de onde se deduz diretamente de (3.10) que q = q1. Os números q e r no enunciado do teorema acima são chamados, respectivamente, de quociente e resto da divisão de b por a. Um resultado imediato da divisão euclidiana é o seguinte. Corolário 3.6. Dados dois números naturais a e b com 1 < a ≤ b, existe um número natural n tal que na ≤ b < (n+ 1)a. Demonstração. Pela divisão euclidiana, existem únicos q, r ∈ N com 0 ≤ r < a tais que b = aq + r. Assim aq ≤ b = aq + r < aq + a = a(q + 1). Basta agora tomar q = n para obtermos o resultado. Os exemplos a seguir apresentam a utilidade do Teorema 3.5. Exemplo 3.7. Se a é um natural com a ≥ 3, então a2 deixa resto 1 na divisão por a− 1. Consequentemente, a− 1 divide a2 − 1. Solução. Usando a identidade a2 − 1 = (a − 1)(a + 1) temos que a2 = (a− 1)(a+ 1) + 1 com 1 < a−1, de onde segue o resultado. 96 3 Divisibilidade O próximo exemplo, como veremos, motiva a procura de cami- nhos e�cientes para encontrar o resto que deixa um número quando é dividido por outro. Exemplo 3.8. Um turista brasileiro chega a Cuba e troca parte de seu dinheiro na casa de câmbio, recebendo 175 notas de 50 pesos e 213 notas de 20 pesos. Ele decide trocar este dinheiro pela maior quantidade possível das famosas moedas de 3 pesos cubanos, porque elas têm gravada a imagem do guerrilheiro Che Guevara. Quanto sobrou do dinheiro depois de fazer a troca pelas moedas? Solução. Para resolver este problema basta achar o resto que deixa o número n = 175 · 50 + 213 · 20 quando é dividido por 3. Entretanto, queremos destacar que não é preciso fazer os produtos e a soma envol- vidos no número n. Em lugar de fazer isto substituímos cada número que aparece em n pelo resto que este deixa na divisão por 3, formando assim um novo número n1, ou seja, n1 = 1 · 2 + 0 · 2 = 2. Agora procuramos o resto que n1 deixa na divisão por 3, que obvi- amente é 2. A surpresa é que este resto é o mesmo que deixa n na divisão por 3. Logo, sobraram 2 pesos depois de fazer a troca. A solução do exemplo anterior é uma aplicação particular do se- guinte lema que é de muita utilidade na resolução de problemas. Lema 3.9 (Lema dos Restos). A soma e o produto de quaisquer dois números naturais deixa o mesmo resto que a soma e o produto dos seus restos, na divisão por um inteiro positivo a. 3.1 Conceitos Fundamentais e Divisão Euclidiana 97 Demonstração. Sejam n1, n2 ∈ Z. Fazendo a divisão com resto de ambos os números por a temos que n1 = aq1 + r1 e n2 = aq2 + r2, com 0 ≤ r1, r2 < a. Então, n1n2 = (aq1 + r1)(aq2 + r2) = a2q1q2 + aq1r2 + aq2r1 + r1r2 = a(aq1q2 + q1r2 + q2r1) + r1r2 = aq + r1r2, (3.11) onde q = aq1q2+q1r2+q2r1. Agora dividimos r1r2 por a para obtermos r1r2 = ap+ r, p ∈ Z, 0 ≤ r < a. (3.12) Das igualdades (3.11) e (3.12) segue que n1n2 = aq + ap+ r = a(p+ q) + r, 0 ≤ r < a. (3.13) Portanto, de (3.12) e (3.13) concluímos que os restos que deixam n1n2 e r1r2 na divisão por a são iguais, �cando provado o resultado para o produto. A prova para a soma é análoga. Observação 3.10. A vantagem do lema é que em certos problemas que envolvem números muito grandes podemos substituir estes por nú- meros muito menores e mais confortáveis para trabalhar. Vejamos como aplicar o lema dos restos nos seguintes exemplos a seguir. Exemplo 3.11. Prove que o produto de dois números naturais con- secutivos é sempre divisível por 2. 98 3 Divisibilidade Solução. Se n ∈ N temos que provar que an = n(n+1) é divisível por 2. Quando fazemos a divisão de n por 2 temos duas possibilidades para o resto: r = 0 ou r = 1. Analisemos os dois casos por separado. • [r = 0] Neste caso o resto que deixa an na divisão por 2 é o mesmo que o resto que deixa 0(0+1)=0, logo an é divisível por 2. • [r = 1] Neste caso podemos substituir an por 1(1+1)=2 e o resto que este último deixa quando é dividido por 2 é 0, logo an também é divisível por 2. Mostraremos agora como utilizar o exemplo anterior pra resolver um dos problemas da 1a Olimpíada Brasileira de Matemática. Exemplo 3.12. Prove que se n é ímpar, então n2 − 1 é múltiplo de 8. Solução. Como n é ímpar, podemos escrever n = 2m+ 1, para algum k ∈ Z. Logo n2 − 1 = (2m+ 1)2 − 1 = 4m2 + 4m+ 1− 1 = 4m2 + 4m. Assim, n2 − 1 = 4m(m+ 1). Observe que de acordo com o exemplo 3.11, m(m + 1) é múltiplo de 2. Portanto, m(m+ 1) = 2q para algum q ∈ Z, de aonde n2 − 1 = 4m(m+ 1) = 4 · 2q = 8q, como queríamos demonstrar. 3.2 Bases Numéricas 99 Exemplo 3.13. Prove que em qualquer triângulo retângulo com lados inteiros, pelo menos um deles é múltiplo de 3. Solução. Comecemos analisando quais são os restos possíveis para a divisão por 3 de um número que é quadrado. De acordo com o lema dos restos temos a seguinte tabela para os restos de n e n2, na divisão por 3: n n2 0 0 1 1 2 1 Resumindo, se um número não é múltiplo de 3 então o resto da divisão de seu quadrado por 3 deve ser igual a 1. Agora denotemos por a e b os catetos e por c a hipotenusa. Supo- nhamos que nenhum deles é divisível por 3. Então a2 e b2 deixam resto 1 na divisão por 3. Logo, a2 + b2 deixa resto 12 + 12 = 2 na divisão por 3; mas isto é uma contradição pois, pelo Teorema de Pitágoras, a2 + b2 = c2 e c2 deixa resto 1 quando é dividido por 3. 3.2 Bases Numéricas Começamos esta seção com uma brincadeira interessante. João, ao sair da aula de matemática do professor Peitágoras, en- controu Pedro e lhe propôs a seguinte brincadeira: � Pense numa peça de dominó, Pedro. Vou adivinhar que peça é essa usando uma fórmula mágica. � Ok, João. Pode começar, já pensei. 100 3 Divisibilidade x y Figura 3.1: Peça de Dominó - Escolha um dos números na peça e multiplique por 5. Depois disso some três a esse resultado. Multiplique agora o número que você obteve por dois. Some isto com o outro número da peça. Qual foi o resultado? � Foi 40. � Então a peça que você escolheu foi a 3 com 4! � Como você acertou? Me ensina! Claro que de mágico João não tinha nada e decidiu contar seu segredo a Pedro. O jogo funciona assim: cada parte da peça de dominó pode ser considerada como um dos dígitos de um número de 2 algarismos, o qual denotamos por n = xy = 10x+ y (veja a Figura 3.1). Acompanhando os passos de João, temos que: (5x+ 3)2 + y = 40⇔ 10x+ y = 34, (3.14) que claramente, tem por soluções: x = 3 e y = 4, usando a represen- tação de 34 na base decimal. No sistema de numeração decimal, também conhecido como sis- tema numérico na base 10, todo número pode ser representado como uma sequência de 10 símbolos, constituídos pelo 0 (zero) e os alga- rismos 1, 2, 3, . . . , 9. Por exemplo, 345 escreve-se na base decimal da 3.2 Bases Numéricas 101 seguinte forma 345 = 300 + 40 + 5 = 3 · 102 + 4 · 10 + 5, assim como 2768 se escreve da forma 2768 = 2000 + 700 + 60 + 8 = 2 · 103 + 7 · 102 + 6 · 10 + 8. De modo geral, se denotamos por a = anan−1 . . . a1a0 o número inteiro positivo formado pelos algarismos an, an−1, . . . , a1 e a0, nessa ordem, então a se escreve na base decimal da forma a = an10 n + an−110 n−1 + . . .+ a110 + a0 (3.15) Antes de provar alguns dos critérios de divisibilidade mais po- pulares do sistema de numeração decimal, provamos uma identidade muito útil. Lema 3.14. Sejam a, b, n ∈ N. Temos que an − bn = (a− b)(an−1 + an−2b+ · · ·+ abn−2 + bn−1). Consequentemente, se 0 < b < a, então a− b divide an − bn. Demonstração. Primeiro provaremos que a propriedade vale para b = 1. Com efeito, considerando a soma geométrica s = 1 + a+ a2 + · · ·+ an−1 e multiplicando s por a temos que as = (a+ a2 + · · ·+ an−1) + an = s− 1 + an. 102 3 Divisibilidade Assim, (a− 1)s = as− s = an − 1, de onde se segue que an − 1 = (a− 1)(an−1 + an−2 + · · ·+ a+ 1). (3.16) Daí temos a validade para b = 1. Para b ∈ N qualquer, observe que an− bn = bn [ (a b )n − 1 ] . Usando esta expressão e (3.16) tem-se an − bn = bn(a b − 1) [ (a b )n−1 + (a b )n−2 + · · ·+ (a b ) + 1 ] = (a− b)bn−1 [ (a b )n−1 + (a b )n−2 + · · ·+ (a b ) + 1 ] = (a− b)(an−1 + an−2b+ · · ·+ abn−2 + bn−1), (3.17) obtendo-se a igualdade clamada. Proposição 3.15 (Critérios de Divisibilidade). Seja a = an . . . a1a0 um inteiro positivo, então (a) a é divisível por 10 se, e somente se, a0 for igual a 0; (b) a é divisível por 3 ou por 9 se, e somente se, a soma dos seus dígitos é divisível por 3 ou por 9, respectivamente; (c) a é divisível por 5 se, e somente se, a0 for igual a 0 ou 5. Demonstração. Utilizando a representação decimal (3.15) temos que a = 10(an10 n−1 + an−110 n−2 + · · ·+ a1) + a0. Então, pela Proposição 3.3-(b) tem-se que 10 | a se, e somente se, 10 | a0, prondose-se assim o critério (a). Para provar (b) observemos que a = an10 n + an−110 n−1 + · · ·+ 10a1 + a0 = an(10 n − 1) + an−1(10n−1 − 1) + · · ·+ (10− 1)a1 + an + an−1 + · · ·+ a1 + a0. (3.18)3.2 Bases Numéricas 103 Pelo Lema 3.14 temos que 10j − 1 = 9qj para todo 1 ≤ j ≤ n, daí segue-se a = 9(anqn + an−1qn−1 + · · ·+ a1) + an + an−1 + · · ·+ a1 + a0. Então, aplicando novamente o item (b) da Proposição 3.3 temos que 9 | a se, e somente se, 9 | (an + an−1 + · · ·+ a1 + a0). A prova para o caso da divisibilidade por 3 segue de maneira idêntica, logo �ca provado o item (b). A prova do item (c) segue de maneira muito semelhante e deixamos a mesma a cargo do leitor. Exemplo 3.16. Prove sem fazer muitas contas que o número N = 13424136 + 1234567890 é divisível por 3. Solução. Note que não precisamos fazer a soma dos números ante- riores. Para mostrar isso, basta aplicar o item (b) da Proposição 3.3 e o item (b) da Proposição 3.15, observando que cada um dos números acima é divisível por 3, pois a soma de seus dígitos é um múltiplo de 3. Finalizamos esta seção com uma aplicação da divisão euclidiana que nos mostra que, analogamente à representação decimal, qualquer número admite uma representação única em qualquer outra base nu- mérica. 104 3 Divisibilidade Teorema 3.17 (Bases Numéricas). Dados a, b ∈ N, com b > 1, exis- tem únicos números naturais r0, r1, . . . , rn tais que 0 ≤ ri ≤ b− 1, 0 ≤ i ≤ n, e satisfazendo a = rnb n + rn−1b n−1 + · · ·+ r1b+ r0. A representação acima é dita representação de a na base b e usaremos a notação a = (rncn−1 . . . r1r0)b, para fazer referência a esta. Demonstração. Apliquemos sucessivamente a divisão euclidiana como segue: a = bq0 + r0, r0 < b, q0 = bq1 + r1, r1 < b, q1 = bq2 + r2, r2 < b, ... ... ... ... qj−1 = bqj + rj, rj < b, e assim por diante. Como a > q0 > q1 > q2 > · · · > qj−1, para algum j = n deveremos ter que qn−1 < b. Logo, qj = 0 para todo j ≥ n, assim como rj = 0 para todo j ≥ n + 1. Das igualdades acima, para 3.2 Bases Numéricas 105 1 ≤ j ≤ n, tem-se a = bq0 + r0, bq0 = b 2q1 + br1, b2q1 = b 3q2 + b 2r2, ... ... ... bn−1qn−2 = b nqn + b n−1rn−1 bnqn−1 = b n+10 + bnrn. (3.19) Efetuando a soma de todas as igualdades em (3.19) obtemos a = rnb n + rn−1b n−1 + · · ·+ r1b+ r0. A unicidade dos números ri vem da unicidade dos restos na divisão euclidiana. Observação 3.18. O sistema de numeração na base 2 é também co- nhecido como sistema binário e é o sistema habitualmente utilizado no funcionamento dos computadores. Exemplo 3.19. Se deseja pesar qualquer número inteiro de gramas de ouro, entre 1g e 100g, numa balança de dois pratos, onde os pesos só podem ser usados no prato esquerdo da balança. Mostre que a escolha adequada de 7 pesos diferentes é su�ciente para realizar esta tarefa. Demonstração. Usando o sistema de numeração em base 2 temos que qualquer número a tal que 1 ≤ a ≤ 100 pode ser expressado de forma única como a = r62 6 + r52 5 + r42 4 + r32 3 + r22 2 + r12 + r01, 106 3 Divisibilidade com ri ∈ {0, 1}, 0 ≤ i ≤ 1. Observe que 2n ≥ 128, com n ≥ 7, logo estas potências não são consideradas. notemos também que o fato de cada ri ser 0 ou 1 nos diz que não precisamos repetir nenhum dos pesos na realização de qualquer pesada. Logo, os pesos 1, 22, 23, 24, 25, 26 são su�cientes para realizar as pesadas de gramas de ouro entre 1g e 100g. 3.3 Máximo Divisor Comum eMínimoMúl- tiplo Comum Nesta seção estudaremos dois conceitos fundamentais, que aparecem naturalmente em vários problemas de divisibilidade, assim como a relação existente entre eles. 3.3.1 Máximo Divisor Comum O primeiro destes conceitos está relacionado com os inteiros positivos que dividem simultaneamente a dois inteiros pre�xados e é denomi- nado máximo divisor comum. Daqui por diante só consideraremos os divisores positivos dos nú- meros. De�nição 3.20 (Máximo Divisor Comum). Sejam a e b inteiros dife- rentes de zero. O máximo divisor comum, resumidamente mdc, entre a e b é o número d que satisfaz as seguintes condições: (a) d é um divisor comum de a e b, isto é, d | a e d | b; 3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 107 (b) d é o maior inteiro positivo com a propriedade (a). Neste caso, denotamos o mdc entre a e b por d = mdc(a, b) ou por d = (a, b). Se (a, b) = 1, então dizemos que a e b são primos entre si. Exemplo 3.21. Observando que 12 = 6 · 2, 18 = 6 · 3 temos que mdc.(12, 18) = 6. Por outro lado, mdc.(4, 15) = 1, logo os números 4 e 15 são primos entre si. Vejamos agora algumas das propriedades mais importantes dos divisores comuns de dois inteiros. Proposição 3.22. Sejam a e b dois inteiros. Então valem as seguintes a�rmações. (a) Se a é múltiplo de b, então (a, b) = b. (b) Se a = bq+ c, c 6= 0, então o conjunto dos divisores comuns dos números a e b coincide com o conjunto dos divisores comuns dos números b e c. Particularmente, (a, b) = (b, c). Demonstração. Começamos com a prova de (a). Com efeito, todo divisor comum dos números a e b é um divisor de b. Reciprocamente, usando que a é múltiplo de b, todo divisor de b é também um divisor de a, ou seja, um divisor comum dos números a e b. Portanto, o conjunto dos divisores comuns dos números a e b é igual ao conjunto dos divisores de b. Como o maior divisor de b é ele mesmo, resulta que (a, b) = b. Vejamos (b). Usando o item (b) da Proposição 3.3 temos que todo divisor comum de a e b também divide c e, consequentemente, é um divisor de b e c. Pela mesma razão todo divisor comum de b e c também divide a e, consequentemente, é um divisor de a e b. Portanto 108 3 Divisibilidade os divisores comuns de a e b são os mesmos que os divisores comuns de b e c. Particularmente, também coincidem os maiores divisores comuns, ou seja, (a, b) = (b, c). O teorema a seguir é uma das ferramentas básicas na resolução de problemas que envolvem o mdc entre dois números. O resultado foi provado pela primeira vez por Claude-Gaspard Bachet de Méziriac (1581-1638) e mais tarde generalizado para polinômios por Étienne Bézout (1730-1783). Frequentemente, na literatura se enuncia este resultado como teorema (ou identidade) de Bézout, esquecendo-se o nome de Bachet. Teorema 3.23 (Teorema de Bachet-Bézout). Se d é o mdc de a e b, então existem números inteiros x0 e y0 tais que d = (a, b) = ax0+ by0. Demonstração. Considere a combinação linear ax + by, onde x e y percorrem todos os inteiros. Este conjunto de inteiros, denotado por Ca,b = {ax+ by; x, y ∈ Z}, inclui valores positivos e negativos. Além disso, escolhendo x = y = 0, vemos que Ca,b também contém o zero. Pelo princípio da boa ordenação, podemos escolher x0 e y0 tais que λ = ax0+by0 seja o menor número inteiro positivo contido no conjunto Ca,b. Agora mostraremos que λ | a e λ | b. Provaremos que λ | a e o outro segue analogamente. Usaremos para este propósito o método de redução ao absurdo, ou seja, vamos supor que λ - a e obteremos uma contradição. 3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 109 Usando a divisão euclidiana, de λ - a segue que existem inteiros q e r tais que a = λq + r com 0 < r < λ. Portanto, r = a− λq = a− q(ax0 + by0) = a(1− qx0) + b(−qy0) e assim r está no conjunto Ca,b, o que contradiz a hipótese de λ ser o menor elemento positivo contido em Ca,b. Uma vez que λ divide a e b só resta provar que λ = d. Com efeito, desde que d = (a, b), podemos escrever a = da1, b = db1 e λ = ax0 + by0 = d(a1x0 + b1y0). Assim d | λ. Logo pela parte (c) da Proposição 3.3, concluímos que d ≤ λ. Agora d < λ é impossível pois d = mdc(a, b), e portanto d = λ = ax0 + by0. A seguinte proposição resume algumas consequências importantes da demonstração dada ao teorema de Bézout. Proposição 3.24. Sejam d, λ ∈ N e a, b, c ∈ Z. Então valem as seguintes a�rmações: (a) Se d | a e d | b, então d | (a, b). (b) O mdc.(a, b) é o menor valor positivo de ax + by, onde x e y percorrem todos os números inteiros. (c) (λa, λb) = λ(a, b). (d) Se d | a e d | b, então (a d , b d ) = 1 d (a, b). Consequentemente,( a (a, b) , b (a, b) ) = 1. 110 3 Divisibilidade (e) Se (a, c) = (b, c) = 1, então (ab, c) = 1. (f) Se c | ab e (b, c)= 1, então c | a. Demonstração. A prova de (a) é consequência imediata da igualdade (a, b) = ax0 + by0 anunciada no teorema de Bézout; assim como (b) segue diretamente da demonstração dada a este teorema. Para provar (c), primeiro observamos que (λa)x+ (λb)y = λ(ax+ by) onde x, y ∈ Z. Usando o item (a) e o fato de λ ser positivo, da igualdade acima segue que (λa, λb) = min { (λa)x+ (λb)y > 0; x, y ∈ Z } = λmin { ax+ by ; x, y ∈ Z } = λ(a, b). A a�rmação feita em (d) segue diretamente de (c), observando que (a, b) = ( d a d , d b d ) = d ( a d , b d ) . Continuamos com a prova de (e). De (a, c) = (b, c) = 1, temos que existem inteiros xj e yj, j = 1, 2, tais que ax1 + cy1 = 1, bx2 + cy2 = 1. Multiplicando lado a lado as igualdades obtemos (x1x2︸︷︷︸ x )ab+ (ax1y2 + y1bx2 + cy1y2︸ ︷︷ ︸ y )c = 1. 3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 111 Então, usando o item (b) e a igualdade acima resulta que (ab, c) = 1. Finalmente, provaremos (f). Das hipóteses temos que existem in- teiros x0 e y0 tais que bx0 + cy0 = 1. Multiplicamos a igualdade acima por a em ambos lados para obtermos abx0 + acy0 = a. Por outro lado, ab = cq para algum inteiro q. Usando esta condição na última igualdade temos que cqx0 + acy0 = c(qx0 + ay0) = a, logo c | a. 3.3.2 Algoritmo de Euclides Apesar de conhecermos propriedades teóricas do mdc entre dois intei- ros, encontrá-lo de fato pode ser uma tarefa complicada, sem auxílio das ferramentas corretas. Lembrando o seu signi�cado, o leitor talvez pudesse pensar que devemos calcular todos os divisores de a, todos os divisores de b e descobrir qual é o maior elemento comum aos dois conjuntos. Para achar o mdc se faz uso de um importante método denominado algoritmo de Euclides . Teorema 3.25 (Algoritmo de Euclides). Dados dois inteiros positivos, a e b, aplicamos sucessivamente a divisão euclidiana para obter a se- 112 3 Divisibilidade guinte sequência de igualdades b = aq1 + r1, 0 ≤ r1 < a, a = r1q2 + r2, 0 ≤ r2 < r1, r1 = r2q3 + r3, 0 ≤ r3 < r2, · · · · · · · · · · · · · · · rn−2 = rn−1qn + rn, 0 ≤ rn < rn−1, rn−1 = rnqn+1, (3.20) até algum rn dividir rn−1. Assim, o mdc.(a, b) = rn, ou seja, é o último resto não-nulo no processo de divisão anterior. Observação 3.26. Quando lidamos com números pequenos achar o mdc é uma tarefa fácil pois podemos calcular o mdc valendo-nos das fatorações dos números envolvidos. No entanto, quando estamos tra- balhando com números grandes o algoritmo de Euclides, em geral, é mais fácil que a fatoração, podendo ser esta última bem difícil. Demonstração do algoritmo de Euclides. Começamos observando que o processo de divisão (3.20) é �nito. Com efeito, a sequência de núme- ros inteiros rk é estritamente decrescente e está contida no conjunto {r ∈ Z, 0 ≤ r < a}, portanto não pode conter mais do que a intei- ros positivos. Examinando as igualdades (3.20) de cima para baixo e usando a Proposição 3.22 temos que (a, b) = (a, r1) = (r1, r2) = · · · = (rn−1, rn) = rn. 3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 113 Observação 3.27. Notemos que o teorema de Bézout também pode ser obtido como consequência do processo de divisão (3.20). Com efeito, podemos escrever rn = rn−2 − rn−1qn rn−1 = rn−3 − rn−2qn−1 } ⇒ rn = rn−2 − (rn−3 − rn−2qn−1)qn. Logo, conseguimos escrever rn em termos de rn−2 e rn−3. Utilizando a expressão rn−2 = rn−4− rn−3qn−2 podemos escrever rn como combina- ção de rn−3 e rn−4. Repetindo este processo várias vezes, concluímos que existem x, y ∈ Z tais que d = rn = xr1 + yr2. Ora, como r1 = b − aq1 e r2 = a − r1q2 = a(1 + q1q2) − bq2, então, substituindo estes valores na última igualdade obtemos o Teorema de Bézout. Exemplo 3.28. Achar o máximo divisor comum dos números 471 e 1.176. Solução. Aplicando o algoritmo de Euclides obtemos a seguinte sequên- cia de divisões com resto: 1176 = 471 · 2 + 234, 471 = 234 · 2 + 3, 234 = 78 · 3, então o mdc(471, 1176) = 3. Exemplo 3.29. Provar que a fração 2n+ 8 4n+ 15 é irredutível para todo número natural n. 114 3 Divisibilidade Solução. Usando o algoritmo de Euclides temos que 4n+ 15 = (2n+ 8) · 1 + 2n+ 7, 2n+ 8 = (2n+ 7) · 1 + 1, 2n+ 7 = (2n+ 7) · 1. Então o mdc.(4n + 15, 2n + 8) = 1 e portanto 4n + 15 e 2n + 8 são primos entre si para qualquer valor de n. Exemplo 3.30. Achar o mdc.(111 . . . 111︸ ︷︷ ︸ 100 vezes , 11 . . . 11︸ ︷︷ ︸ 60 vezes ) Solução. Primeiro escrevemos os números na base decimal, isto é, 111 . . . 111︸ ︷︷ ︸ 100 vezes = 1099 + 1098 + · · ·+ 1, 11 . . . 11︸ ︷︷ ︸ 60 vezes = 1059 + 1058 + · · ·+ 1. Aplicamos agora o algoritmo de Euclides para obter as seguintes igual- dades 111 . . . 111︸ ︷︷ ︸ 100 vezes = (1059 + 1058 + · · ·+ 1)1040 + 1039 + 1038 + · · ·+ 1, 1059 + 1058 + · · ·+ 1 = (1039 + 1038 + · · ·+ 1)1020+ + 1019 + 1018 + · · ·+ 1, 1039 + 1038 + · · ·+ 1 = (1019 + 1018 + · · ·+ 1)1020+ + 1019 + 1018 + · · ·+ 1. Disso resulta que mdc.(111 . . . 111︸ ︷︷ ︸ 100 vezes , 11 . . . 11︸ ︷︷ ︸ 60 vezes ) = 1019 + 1018 + · · ·+ 1 = 11 . . . 11︸ ︷︷ ︸ 20 vezes . 3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 115 3.3.3 Mínimo Múltiplo Comum Agora passamos ao segundo conceito importante desta seção. O mesmo está relacionado com os inteiros positivos que são simultaneamente múltiplos de dois inteiros pre�xados e é denominado mínimo múltiplo comum. De�nição 3.31 (Mínimo Múltiplo Comum). Sejam a e b inteiros diferentes de zero. O mínimo múltiplo comum, resumidamente mmc, entre a e b é o inteiro positivo m que satisfaz as seguintes condições: (a) m é um múltiplo comum de a e b, isto é, a | m e b | m; (b) m é o menor inteiro positivo com a propriedade (a). Neste caso, denotamos o mmc entre a e b por m = mmc(a, b) ou por m = [a, b]. Resumimos a seguir algumas das propriedades fundamentais do mmc de dois inteiros. Proposição 3.32. Sejam a, b, c ∈ Z e λ ∈ Z. Então valem as se- guintes a�rmações: (a) se c é múltiplo comum de a e b, então [a, b] | c; (b) [λa, λb] = λ[a, b]; (c) |ab| = [a, b] · (a, b). Demonstração. Começamos com a prova de (a). A divisão com resto de c por [a, b] nos dá c = [a, b]q + r, 0 ≤ r < [a, b]. (3.21) 116 3 Divisibilidade Da igualdade anterior, basta provar que r = 0 para obter o resultado desejado. Suponhamos, pelo contrário, que 0 < r < [a, b]. Notemos que tanto a como b dividem c e [a, b]. Logo, pelo item (b) da Pro- posição 3.3 e a igualdade (3.21), temos que a e b também dividem r, ou seja, r é múltiplo comum de a e b e não pode ser menor que [a, b], contradizendo nossa suposição. Prosseguimos com a prova de (b). Observemos que λ[a, b] é múlti- plo comum de λa e λb, logo pelo item (i) vale que [λa, λb] ≤ λ[a, b]. (3.22) Por outro lado, [λa, λb] = q1λa = q2λb, para alguns inteiros q1 e q2; logo, [λa,λb] λ é um múltiplo comum de a e b. Portanto, [a, b] ≤ [λa, λb] λ ⇔ λ[a, b] ≤ [λa, λb]. (3.23) Das igualdades (3.22) e (3.23) segue que λ[a, b] ≤ [λa, λb] ≤ λ[a, b], de onde vem diretamente o resultado. Para provar (c) podemos supor sem perda de generalidade que a e b são positivos devido às igualdades [a, b] = [a,−b] = [−a, b] = [−a,−b]. Dividiremos a prova em dois casos: Caso 1: (a, b) = 1. Sabemos que b | [a, b] e [a, b] = qa, para algum q ∈ N. Então b | qa e além disso (a, b) = 1. Logo, pelo item (v) da Proposição 3.24 temos que b | q. Portanto, b ≤ q e consequentemente ab ≤ aq = [a, b]. (3.24) 3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 117 Entretanto, da de�nição de [a, b] vale que [a, b] ≤ ab. (3.25) Das desigualdades (3.24) e (3.25) segue que ab ≤ [a, b] ≤ ab. Assim, ab = [a, b] = [a, b] · 1 = [a, b] · (a, b). Caso 2: (a, b) > 1. Da parte (c) da Proposição 3.24 sabemos que ( a (a,b) , b (a,b) ) = 1. Aplicando o caso anterior vale que a (a, b) · b (a, b) = [ a (a, b) , b (a, b) ] · ( a (a, b) , b (a, b) ) . Multiplicamos esta última igualdade por (a, b)2 e usamos o item (b) provado anteriormente, assim como a parte (d) da Proposição 3.24 paraobter ab = (a, b) [ a (a, b) , b (a, b) ] (a, b) ( a (a, b) , b (a, b) ) = [a, b] · (a, b). Exemplo 3.33. Dois amigos passeiam de bicicleta, na mesma dire- ção, em torno a uma pista circular. Para dar uma volta completa um deles demora 15 minutos e o outro demora 18 minutos. Eles partem juntos e combinam interromper o passeio quando os dois se encontra- rem pela primeira vez no ponto de partida. Quantas voltas deu cada um? Solução. Denotemos por n1 e n2, respectivamente, o número de voltas que dá cada um dos amigos. Notemos que o tempo total da corrida é o menor valor positivo de T que satisfaz as igualdades T = 15n1 = 18n2, 118 3 Divisibilidade ou seja T = [15, 18] = 15 · 18 3 = 90. Portanto, n1 = 6 e n2 = 5. Finalizamos esta seção com um exemplo que nos fornece uma bela interpretação geométrica do mínimo múltiplo comum. O mesmo foi proposto na Olimpíada Brasileira de Matemática. Exemplo 3.34. Um retângulo de lados inteiros AB = m e CD = n, é dividido em quadrados de lado 1. Em cada um dos vértices ele possui um pequeno orifício. Um raio de luz entra no retângulo por um dos vértices, na direção da bissetriz do ângulo reto, e é re�etido sucessi- vamente nos lados do retângulo. Quantos quadrados são atravessados pelo raio de luz? A B CD Figura 3.2: Interpretação geométrica do mmc Solução. Se �zermos alguns testes preliminares dando valores a m e n, veremos que em cada caso a resposta coincidirá com o mmc(m,n). Provemos que isto de fato vale para m e n quaisquer. Para realizar a prova nos auxiliaremos da Figura 3.2. 3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 119 Primeiramente, notemos que cada vez que o raio de luz atravessa um quadrado ele avança uma unidade tanto na direção horizontal como na direção vertical. Usando este fato fazemos as observações a seguir. • Se o raio entra pelo vértice A, terá que atravessar m quadrados até chegar ao lado BC, imediatamente mais m para chegar ao lado AD, depois mais m para chegar novamente ao lado BC, e assim sucessivamente. Além disso, depois do raio percorrer pm quadrados, com p ∈ N, estará batendo no lado BC ou no lado AD. • Analogamente o raio baterá no lado AB ou no lado DC se, e somente se, atravessar qn quadrados, com q ∈ N. • Somente nos vértices B, C e D do retângulo pode acontecer que o raio incidente saia do retângulo, terminando assim o processo de re�exão. Usando as observações acima é fácil ver que o raio chegará a um vértice quando chegar simultaneamente a dois lados perpendiculares do retângulo. Portanto, deve ter atravessado um número x de quadra- dos tal que x = pm = qn, ou seja, x deverá ser um múltiplo comum de m e n. É claro que a primeira vez que o raio chega a um vértice o número x é o menor múltiplo comum de m e n, isto é, x = [m,n]. Finalmente, observamos que nenhum dos quadrados é atravessado duas vezes no percurso do raio de A até bater no primeiro vértice, pois como vemos na �gura numa das direções os quadrados atravessados serão todos cinzas e na outra direção, serão todos brancos. 120 3 Divisibilidade 3.3.4 Equações Diofantinas Lineares Consideremos a equação ax+ by = c, (3.26) onde a, b, c ∈ Z, com a 6= 0 e b 6= 0. A equação (3.26) é chamada de equação diofantina linear e uma solução desta é qualquer par de inteiros (x, y) que satisfaçam (3.26). É conhecido que todos os pontos do plano, com coordenadas (x, y), que satisfazem a igualdade (3.26) representam, geometricamente, uma reta. Logo, as soluções de uma equação diofantina linear são os pontos de coordenadas inteiras do plano cartesiano, que estão dispostos sobre a reta que esta representa. Por exemplo, os pontos (−1,−2) e (1, 1) são soluções da equação diofantina 3x− 2y = 1, veja a Figura 3.3. -3 -2 -1 0 1 2 -3 -2 -1 0 1 2 3 x y • • ℓ Figura 3.3: A equação da reta ` é 3x− 2y = 1. Naturalmente nos perguntamos: É sempre possível achar soluções para uma equação diofantina linear? A resposta é não; o próximo resultado nos diz quando isto é possível. Além disso, se uma equação diofantina linear tem uma solução na verdade ela tem uma in�nidade de soluções. 3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 121 Proposição 3.35. A equação diofantina linear ax+ by = c, a, b, c ∈ Z, com a 6= 0 e b 6= 0, (3.27) tem solução se, e somente se, d | c, onde d = (a, b). Além disso, se (x0, y0) é uma solução, então o conjunto de soluções de (3.27) é constituído por todos os pares de inteiros (x, y) da forma: x = x0 + t b d e y = y0 − tad , t ∈ Z. (3.28) Demonstração. Primeiramente suponhamos que (x0, y0) é uma solução de (3.27), logo ax0 + by0 = c. Usando que d = (a, b) sabemos que existem inteiros q1 e q2, tais que dq1 = a e dq2 = b. Portanto, se veri�ca a igualdade dq1x0 + dq2y0 = d(q1x0 + q2y0) = c, de onde segue obviamente que d | c. Reciprocamente, suponhamos que d | c e portanto c = qd com q inteiro. O teorema de Bézout nos garante a existência de dois inteiros, x0 e y0, tais que ax0 + by0 = d. Multiplicando ambos os lados desta última igualdade por q temos que ax0q + by0q = c, logo o par (x1, y1), com x1 = x0q e y1 = y0q, é solução da equação diofantina. Resta provar agora que temos in�nitas soluções da forma (3.28). Com efeito, sendo (x, y) uma outra solução qualquer além de (x0, y0), vale que ax0 + by0 = c = ax+ by, de onde ax0 + by0 = ax+ by. Desta igualdade obtemos a(x− x0) = b(y0 − y) e dividimos esta última por d para obtermos a d (x− x0) = b d (y0 − y). 122 3 Divisibilidade Como (a d , b d ) = 1, então temos que a d | (y0 − y) e bd | (x − x0). Logo, existe inteiro t tal que x = x0 + t b d e y = y0 − tad . Por outro lado, é fácil veri�car que para qualquer inteiro t as expressões achadas acima para x e y resolvem a equação diofantina. A seguir damos um exemplo de como proceder para resolver equa- ções diofantinas. Exemplo 3.36. Achar todas as soluções inteiras da equação 12x+ 33y = 27. Solução. Observemos que (12, 33) = 3 e que 3 | 27, logo a equa- ção tem in�nitas soluções. Como sabemos, basta achar uma delas e teremos as restantes. Para achar esta solução particular podemos trabalhar de duas maneiras, que descrevemos a seguir: Alternativa 1: reduzimos a equação à forma equivalente 4x+ 11y = 9, e por tentativa e erro vemos que x0 = 5 e y0 = −1 solucionam a mesma. Então pela Proposição 3.35 temos que x = 5 + 11t e y = 4t− 1, t ∈ Z, esgotam todas as soluções que procuramos. Alternativa 2: aplicamos o algoritmo de Euclides para achar o mdc (12, 33), obtendo os seguintes resultados: 33 = 12 · 2 + 9, 12 = 9 · 1 + 3, 9 = 3 · 3 + 0. 3.4 Números Primos e Compostos 123 Da segunda e primeira igualdades temos, respectivamente, que 3 = 12− 9 · 1 e 9 = 33− 12 · 2. Usando estas duas obtemos 3 = 12− (33− 12 · 2) · 1 = 12− 33 + 12 · 2 = 3 · 12− 1 · 33, ou seja, achamos x0 = 3 e y0 = −1, garantidos pelo teorema de Bézout, que validam 3 = 12x0+33y0. Multiplicamos por 9 esta última igualdade para obter 27 = 12(9x0) + 33(9y0). Portanto, x̃0 = 9x0 = 27 e ỹ0 = 9y0 = −9 resolvem, particularmente, a equação diofantina. Analogamente, como na alternativa anterior, podemos escrever a solução geral da forma: x = 27 + 11s e y = 4s− 9, s ∈ Z. 3.4 Números Primos e Compostos Ao longo da história da Matemática, os números primos foram pro- tagonistas de célebres problemas que motivaram o desenvolvimento de teorias e técnicas pelas mentes mais férteis, como Fermat, Euler e Gauss. Até hoje muitos desses problemas, simples de enunciar, que envolvem números primos são desa�os intelectuais para toda a huma- nidade. 124 3 Divisibilidade Esta seção será dedicada ao estudo de propriedades básicas dos números primos. Todo número natural n maior do que 1 tem pelo menos 2 divisores, claramente 1 e n. Isto motiva a seguinte de�nição. De�nição 3.37 (Números Primos e Compostos). Um inteiro positivo n ≥ 2 é dito primo se os únicos divisores que ele tem são 1 e ele próprio; caso contrário, é dito composto. Observação 3.38. De modo geral o número1 não é considerado nem primo nem composto. Exemplo 3.39. Os números 2, 3, 5, 7, e 11 são primos e os números 10, 15, 35 e 348 são compostos. Exemplo 3.40. O número n = 220 − 254 é composto. Solução. Escrevemos n de outra forma, com o objetivo de facilitar nosso trabalho. Com efeito, observemos que n = (210)2 − (252)2 = 10242 − 6252, logo é composto por ser diferença de quadrados. Além disso, n = 10242 − 6252, = (1024− 625)(1024 + 625), = 399 · 1649, = 3 · 133 · 1649. (3.29) Portanto, podemos concluir que 3 | n. Proposição 3.41. Seja n > 1 um número inteiro. Então (a) o menor divisor de n diferente de 1 é um número primo; 3.4 Números Primos e Compostos 125 (b) se n é composto, o seu menor divisor diferente de 1 não é maior que √ n. Em outras palavras, se n não possui divisores diferentes de 1, menores ou igual que √ n, então n é primo. Demonstração. Começamos provando (a). Seja p o menor divisor de n, diferente de 1. Se p fosse composto teria algum divisor q tal que 1 < q < p; mas q | p e p | n, o que nos diz que q | n, e isto contradiz a hipótese levantada sobre p. Para provar (b) denotamos por p o menor divisor de n, diferente de 1. Portanto, n = pq com q ≥ p. Multiplicando ambos lados da desigualdade por p obtemos n = pq ≥ p2, e consequentemente vale √ n ≥ p. Agora vamos enunciar um dos resultados mais clássicos da Mate- mática, que garante a existência de in�nitos números primos. Até onde se conhece, a demonstração a seguir foi a primeira demonstração escrita utilizando o método de redução ao absurdo e é devida a Eu- clides cerca de 300 a.C. Para outras seis provas, incluindo a moderna prova de Fustenberg, recomendamos os livros [1] e [10]. Teorema 3.42 (Teorema de Euclides). A quantidade de números pri- mos é in�nita. Demonstração. Faremos a prova por redução ao absurdo. Suponha que existe uma quantidade �nita de números primos e denotemos estes por p1, p2, p3, . . . , pk. 126 3 Divisibilidade Consideremos o número n = p1p2p3 · · · pk + 1 e chamemos de q o seu menor divisor primo. Obviamente q não coin- cide com nenhum dos números pi, 1 ≤ i ≤ k, pois caso contrário, como ele divide n, teria que dividir 1, o que é impossível. Logo, te- mos uma contradição à hipótese de termos uma quantidade �nita de primos. Os números primos também podem ser caracterizados da seguinte maneira: Proposição 3.43. Um inteiro positivo p é primo se, e somente se, satisfaz a seguinte propriedade: p | ab =⇒ p | a ou p | b (3.30) onde a, b ∈ Z. Demonstração. Primeiramente, suponhamos que p é primo e que p - b, logo (p, b) = 1. Então, pelo item (f) da Proposição 3.24 temos que p | a. Reciprocamente, suponhamos que, a propriedade 3.30 é válida e além disso vamos supor, pelo absurdo, que p não é primo. Então, p = d1d2, com 1 < d1 < p, 1 < d2 < p. (3.31) De (3.30) segue que p | d1 ou p | d2; consequentemente p ≤ d1, ou p ≤ d2, (3.32) contradizendo isto o a�rmado em (3.31). 3.5 Procurando Primos 127 3.5 Procurando Primos Os números primos além de belos e desa�adores do ponto de vista matemático, são extremamente importantes para as atividades usuais de nosso dia a dia. Por exemplo, nenhuma transação bancária ou pela internet estaria segura sem o uso de números primos muito grandes. Assim, surge naturalmente a pergunta de como podemos produzi-los em grandes quantidades. Essa pergunta sempre intrigou os matemá- ticos e continua sem solução até os dias atuais. Apesar deles serem abundantes, em quantidade in�nita de acordo com o Teorema 3.42, não existe nenhum método razoável de produção de números primos, mesmo tendo em mãos a alta tecnologia de hoje em dia. Porém, ao longo do tempo algumas fórmulas e algoritmos se mostraram úteis para a descoberta de números primos. 3.5.1 O Crivo de Eratóstenes O crivo de Eratóstenes é um algoritmo que nos permite achar todos os números primos que são menores ou iguais que um natural N dado. Segundo a tradição, este método foi criado pelo matemático grego Eratóstenes (285-194 a.C.). O método consiste nos seguintes passos: escrevemos os números de forma ordenada a partir de 2, isto é, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, . . . , n (3.33) • Observamos que o primeiro primo que aparece em (3.33) é 2 e imediatamente apagamos da lista (3.33) todos os múltiplos de 2 maiores que ele, por serem compostos; resta assim a seguinte 128 3 Divisibilidade lista 2, 3, 5, 7, 9, 11, 13, 15, 17 . . . • O primeiro número não apagado que aparece na lista restante é 3, que também é primo. Imediatamente apagamos da lista todos os múltiplos de 3 maiores que ele, por serem compostos; resta agora a lista 2, 3, 5, 7, 11, 13, 17, . . . • O primeiro número não apagado que aparece na lista que restou do passo anterior é 5, que também é primo. Imediatamente apagamos da lista todos os múltiplos de 5 maiores que ele, por serem compostos. • Repetimos este processo até que o primeiro número não apagado da lista em questão seja maior que √ n, pois graças à Proposição 3.41-(b) a partir desse momento todos os números restantes são os primos menores ou iguais que n.. Por exemplo, se n = 40, temos que √ 40 = 6, 324555. Então, aplicando o método: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 Passo 1: ordenamos os números 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 3.5 Procurando Primos 129 Passo 2: tiramos os múltiplos de 2 2 3 5 7 11 13 17 19 23 25 29 31 35 37 Passo 3: tiramos os múltiplos de 3 2 3 5 7 11 13 17 19 23 29 31 37 Passo 4: tiramos os múltiplos de 5 Como 72 = 49 > 40, paramos agora. Observação 3.44. Note que ao começar a apagar os múltiplos de um número primo p podemos começar a apagar a partir de p2, pois se supomos que existe um número composto m não apagado menor que p2, temos que m = p1q1, sendo p1 seu menor divisor primo. Então, pelo item (b) da Proposição 3.41, p1 < √ m < p, logo m deveria ter sido apagado pois é múltiplo de um primo menor que p. 3.5.2 Primos de Mersenne Marin Mersenne (1588-1648) foi um monge francês que nasceu na ci- dade de Maine e foi um dos grandes in�uenciadores da Matemática 130 3 Divisibilidade 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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 Tabela 3.1: Os primeiros 100 números primos francesa nos séculos XVI e XVII. Apaixonado pelos números, teve en- tre seus correspondentes Descartes, Fermat, Pascal e Galileu. Entre suas várias descobertas, ele estudou os números da forma: Mn = 2 n − 1. Observe que vale o seguinte fato a respeito desses números: Proposição 3.45. Se Mn é primo, então n é primo. Demonstração. Provar essa proposição equivale a mostrar que a sua forma contrarrecíproca vale. Ou seja, que se n é composto, digamos n = a.b, com a ≥ b > 1, então Mn também é composto. De fato, usando o Lema 3.14, podemos decompô-lo do seguinte modo: Ma.b = 2 ab − 1 = ( 2a(b−1) − 2a(b−2) + · · ·+ 2a + 1 )( 2b − 1 ) . 3.5 Procurando Primos 131 Porém, não é verdade a recíproca da a�rmação acima. Por exem- plo, Hudalricus Regius mostrou em 1536 que M11 = 211 − 1 = 2.047 não é primo, já que 2.047 = 23 · 89. Em 1643, Mersenne a�rmou que para n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 e 257, os valores de Mn são todos primos e para todos os outros valores de n menores que 257, Mn é composto. Hoje sabemos que Mersenne errou na sua a�rmação, esquecendo três valores de n ondeMn é primo: 61, 89 e 107 e incluindoM67 eM257 como números primos. Para mais informações, sugerimos a página web http://primes.utm.edu/mersenne/index.html. Finalizamos esta seção, com um critério interessante, devido à ma- temática francesa Sophie Germain(1776-1831), que nos permite saber quando um número não é primo. Proposição 3.46 (Identidade de Sophie Germain). Dados a, b ∈ R, vale a igualdade a4 + 4b4 = (a2 + 2b2 + 2ab)(a2 + 2b2 − 2ab). Demonstração. A prova segue das seguintes igualdades: a4 + 4b4 = a4 + 4a2b2 + 4b4 − 4a2b2 = (a2 + 2b2)2 − 4a2b2 = (a2 + 2b2 + 2ab)(a2 + 2b2 − 2ab). Como aplicação desta identidade vejamos os seguintes exemplos. 132 3 Divisibilidade Exemplo 3.47. qn = n 4 + 4n é composto, para todo n ∈ N. Solução. O conjunto dos números naturais é particionado em duas classes disjuntas:o conjunto dos números pares e o conjunto dos nú- meros ímpares. Estudaremos cada classe por separado. Assim, • se n é um número par, então n = 2m para algum inteiro positivo m ≥ 1. Deste modo, n4 + 4n = (2m)4 + 42m = 16m4 + 24m, = 2 ( 8m4 + 24m−1 ) . Portanto, neste caso, n4 + 4n ≥ 2. Logo, se n > 1 é qualquer número inteiro positivo par temos que n4+4n não é um número primo; • se n é um número ímpar, então n = 2m + 1 para algum inteiro positivo m ≥ 1. Assim, n4 + 4n = (2m+ 1)4 + 42m+1 = (2m+ 1)4 + 4 · 42m = (2m+ 1)4 + 4 · 24m = (2m+ 1)4 + 4 · (2m)4. Logo, tomando a = 2m + 1 e b = 2m, o resultado é uma con- sequência direta da identidade de Sophie Germain. Exemplo 3.48. 520 + 230 é um número composto. Solução. Escrevemos 520 + 230 = 55·4 + 22 · 228 = ( 55 )4 + 4 · ( 27 )4 , de onde podemos usar a Identidade de Sophie Germain com a = 55 e b = 27 para comprovar que o número 520 + 230 é composto. 3.5 Procurando Primos 133 3.5.3 O Teorema Fundamental da Aritmética Os números primos são as células dos números naturais, no sentido de que qualquer número natural é produto de números primos. Por exemplo, 560 = 56 · 10 = 7 · 8 · 5 · 2 = 7 · 2 · 2 · 2 · 5 · 2, onde cada um dos fatores que aparecem no produto são números pri- mos. Perguntamo-nos, o que acontece se começamos com uma outra fatoração inicial de 560, por exemplo, 560 = 28 · 20. Vejamos: 560 = 28 · 20 = 14 · 2 · 10 · 2 = 7 · 2 · 2 · 5 · 2 · 2. Surpreendentemente chegamos à mesma representação anterior, salvo a ordem dos fatores. 222 2 75 Figura 3.4: O número 560 é composto de 4 células do tipo 2, uma célula do tipo 7 e uma célula do tipo 5. O fato observado acima vale para qualquer número natural maior que 1. Especi�camente, temos o seguinte resultado conhecido como teorema fundamental da aritmética. 134 3 Divisibilidade Teorema 3.49 (Teorema Fundamental da Aritmética). Todo número natural n maior que 1 pode ser escrito como um produto n = pα11 p α2 2 p α3 3 · · · pαmm , (3.34) onde m ≥ 1 é um número natural, αi ∈ N e pi é primo para todo 1 ≤ i ≤ m . Além disso, a fatoração em (3.34) é única se exigirmos que p1 < p2 < · · · < pm. Demonstração. Seja n um inteiro maior que 1. Denotando por p1 seu menor divisor primo tem-se que n = p1β1, 1 ≤ β1 < n. Se β1 = 1, então N1 = p1 e a fatoração desejada é obtida. Caso contrário, denotando por p2 o menor divisor primo de β1 tem-se que n = p1p2β2, 1 ≤ β2 < β1. Se β2 = 1, então n = p1p2 e novamente chegamos à fatoração desejada. Caso contrário, denotando por p3 o menor divisor primo de β2 tem-se que n = p1p2p3β3, 1 ≤ β3 < β2. Continuando este processo sucessivamente obtemos então uma sequên- cia estritamente decrescente de números naturais αn, ou seja, n > β1 > β2 > β2 > · · · > βn > βn+1 > · · · ≥ 1, Então, pelo princípio da boa ordem, só pode existir uma quantidade �nita de índices n tais que βn > 1 e consequentemente βn+1 = 1, de onde segue que n = p1p2 · · · pn. 3.5 Procurando Primos 135 Notemos que na representação acima os pi podem-se repetir, resul- tando �nalmente a representação desejada em (3.34). Provaremos agora a unicidade de tal fatoração. Com efeito, supo- nha que existem duas fatorações: pα11 p α2 2 p α3 3 · · · pαmm = n = qβ11 qβ22 qβ33 · · · qβss Pela Proposição 3.43 temos que cada pi divide algum qj, logo pi = qj, por serem primos. Portanto, cada pi aparece no lado direito da igualdade acima, e, um argumento análogo nos dá que cada qj também aparece no lado esquerdo da igualdade. Então, como os pis e os qjs são diferentes dois a dois e organizados crescentemente, temos m = s e a igualdade se reduz a pα11 p α2 2 p α3 3 · · · pαmm = pβ11 pβ22 pβ33 · · · pβmm . Suponhamos agora que α1 seja diferente de β1; sem perda de ge- neralidade vamos supor que α1 < β1. Portanto, pα22 · pα33 · · · pαmm = pβ1−α11 pβ22 pβ33 · · · pβmm , e como β1 − α1 > 0 então, pela Proposição 3.43 temos que p1 di- vide algum pj, com j > 1, o que é impossível. Portanto, α1 = β1. Similarmente provamos que αi = βi, com i = 1, . . . , n. Observação 3.50. O teorema fundamental da aritmética foi enun- ciado precisamente por Gauss (1777-1855). Seus antecessores, Fer- mat, Euler, Lagrange e Legendre, utilizavam este teorema sem a preo- cupação de tê-lo enunciado ou demonstrado com precisão. Uma prova alternativa deste teorema será apresentada no Capítulo 6, usando o método de indução. 136 3 Divisibilidade Exemplo 3.51. Prove que um número n é par se, e somente se, o número 2 aparece na fatoração de n em fatores primos. Solução. Obviamente, se 2 aparece na fatoração em primos de N , então N é par. Ora, se n é par temos que n = 2q. Por outro lado q e n se fatoram, respectivamente, como q = qα11 q α2 2 · · · qαmm e n = pβ11 pβ22 · · · pβss . Logo, 2 · qα11 qα22 · · · qαmm = pβ11 pβ22 · · · pβss . Pela unicidade da fatoração, para algum i, com 1 ≤ i ≤ s, o cor- respondente pi deve ser igual a 2. Portanto, 2 aparece na fatoração de n. Exemplo 3.52. Seja A = {1, 2, 3, 4, 5, 6, 7}. É possível decompor o conjunto A em dois subconjuntos disjuntos tais que o produto dos elementos de um seja igual ao produto dos elementos do outro? Solução. Mostraremos que é impossível fazer esta decomposição. Com efeito, suponha que existem tais conjuntos, A1 = {p1, p2, . . . , pr} e A2 = {q1, q2, . . . , qs}. Então p1p2 · · · pr︸ ︷︷ ︸ α = q1q2 · · · qs︸ ︷︷ ︸ β e além disso, como os conjuntos A1 e A2 são disjuntos, temos que o número 5 aparece no produto α ou no produto β, mas não em ambos simultaneamente. Por outro lado, o Teorema 3.49 nos diz que a fatora- ção em primos de α é igual à fatoração em primos de β, logo o número 5 deveria aparecer tanto no produto α como no produto β, contra- dizendo isto o fato anterior. Portanto não existe uma decomposição com as condições exigidas. 3.5 Procurando Primos 137 Exemplo 3.53. Encontre todos os números inteiros e positivos n com a propriedade de que o conjunto A = {n, n+ 1, n+ 2, n+ 3, n+ 4, n+ 5} pode ser particionado em dois subconjuntos tais que o produto dos elementos de um dos subconjuntos seja igual ao produto dos elementos do outro. Demonstração. Digamos que seja possível essa decomposição para al- gum n e vamos denotar os conjuntos que obtemos com a decomposição por A1 e A2. Observando a decomposição dos elementos dos subcon- juntos em fatores primos, temos que todo fator primo de A1 também deverá pertencer a A2. No conjunto dos seis números só podemos ter um múltiplo de 7, por isso não podemos tomar n como múltiplo deste primo. Analogamente para primos maiores que 7. Analisando o primo 5, concluímos que n e n+ 5 são múltiplos de 5, pois se não, cairíamos na análise anterior. Assim, os números n+ 1, n+ 2, n+ 3 e n+ 4 são da forma 2α3β. Como entre eles existem dois ímpares, logo teremos duas potências de 3 cuja diferença é 2, um absurdo. Assim, não existe n que satisfaz as condições do enunciado. Finalizamos esta seção com um exemplo que mostra como podemos combinar os fatos estudados para resolver problemas mais difíceis Exemplo 3.54. Encontre todos os números que são formados por 4 algarismos da forma aabb e que sejam quadrados perfeitos. 138 3 Divisibilidade Solução. Como o número aabb é um quadrado perfeito, signi�ca que: n2 =aabb n2 =103a+ 102a+ 10b+ b = ( 103 + 102 ) · a+ (10 + 1) · b n2 =1100 · a+ 11 · b n2 =11 ( 100a+ b ) = 11 ( 99a+ a+ b ) . Como 11 é primo é fácil ver, usando aProposição 3.43, que 112 | N2. Segue-se então que 11 | (99a+a+b). Portanto, 11 | (a+b). Como aabb tem 4 algarismos, segue-se que a 6= 0; portanto a ∈ {1, 2, 3, . . . , 9} e b ∈ {0, 1, 2, . . . , 9}. De onde a + b ≤ 18. Logo, necessariamente devemos ter a + b = 11. Podemos observar que a 6= 1, pois se a = 1 então b = 10. Analogamente, b 6= 0, 1. Portanto, a ∈ {2, 3, 4, . . . , 9} e b ∈ {2, 3, 4, . . . , 9}. Como em todo número quadrado perfeito o algarismo das unidades somente pode acabar em 0, 1, 4, 5, 6 e 9. Segue-se que b ∈ {4, 5, 6, 9}. Certamente b 6= 5, pois todo número que acaba em 5 quando é elevado ao quadrado sempre acaba em 25. Assim, b ∈ {4, 6, 9}. • Se b = 4, então a = 7. Neste caso o número seria 7.744 que é um quadrado perfeito; • Se b = 6, então a = 5. Neste caso o número seria 5.566 que não é um quadrado perfeito; 3.6 Exercícios 139 • Se b = 9, então a = 2. Neste caso o número seria 2.299 que não é um quadrado perfeito. Finalmente, a única solução possível é aabb = 7.744 = 882. 3.6 Exercícios 1. Encontre o resto que deixa (a) 2001 · 2002 · 2003 · 2004 + 20052 quando é dividido por 7; (b) 2100 quando é dividido por 3; (c) (1237156 + 34)28 quando é dividido por 111. 2. Provar que o número n5 + 4n é divisível por 5 para qualquer número natural n. 3. Prove que se n é ímpar (a) n3 − n é divisível por 24; (b) n2 − 1 é divisível por 8; (c) n2 + (n+ 2)2 + (n+ 4)2 + 1 é divisível por 12. 4. O número 21093 − 2 é divisível por 10932 ? 5. Prove que (999994)1234567890 − 1 é divisível por 333331. 6. O número N = 42005 + 20054 é primo? 7. Demonstre que o número 1 000 . . . 00︸ ︷︷ ︸ 2006 zeros 1 é composto. 140 3 Divisibilidade 8. Utilizando o fato de que o resto de um quadrado quando dividido por 4 só pode ser 0 ou 1, dê uma outra solução para o problema do Exemplo 3.54. 9. Dados três inteiros, x, y, z, tais que x2 + y2 = z2, mostre que x e y não são ambos ímpares e que xy é múltiplo de 6. 10. Demonstre que o quadrado de um inteiro é da forma 8n ou 8n+1 ou 8n+ 4. 11. Três números primos p, q e r, maiores que 3, formam uma pro- gressão aritmética, ou seja, q = p+ d e r = p+ 2d. Prove que d é divisível por 6. 12. Demonstrar que existem in�nitos números primos da forma 4m+ 3 e da forma 6m+ 5, onde m ∈ Z. 13. Encontrar o último dígito dos números (a) 19892005; (b) 777777 + 250; (c) 1 + 22 + 32 + · · ·+ 20052. 14. Prove que a soma dos quadrados de cinco números consecutivos não é um quadrado perfeito. 15. Prove que 1 00 · · · 00︸ ︷︷ ︸ 100−zeros 5 00 · · · 00︸ ︷︷ ︸ 100−zeros 1 não é um cubo perfeito. 16. Seja b um inteiro positivo. Enuncie e prove o critério de divisi- bilidade por b no sistema de numeração de base b. 17. Prove que os números 3.6 Exercícios 141 (a) αn = 1 + 1 2 + 1 3 + · · ·+ 1 n , com n > 1, (b) βn = 1 3 + 1 5 + · · ·+ 1 2n+ 1 , com n > 0, não são inteiros. 18. Considere o polinômio p(n) = amnm + am−1nm−1 + · · · + a0 de grau m ≥ 1 com coe�cientes inteiros e n ∈ N. Prove que p(n) é um número composto para in�nitos valores de n. Sugestão: Use o fato de que existe a ∈ N tal que α = |p(a)| > 1 e mostre que α divide a p(αk + a), para todo k ∈ Z. 19. Dizemos que um conjunto An formado por n inteiros positivos escritos no sistema binário (base 2) é regular se, para qualquer s inteiro não negativo a quantidade de números de An que con- templam 2s na representação binária é par. Dizemos que An é irregular se, pelo menos para algum s, este número é ímpar. De- monstre que um sistema irregular pode se converter em regular excluindo-se apenas um único elemento do mesmo, e, um sistema regular pode se converter em irregular excluindo-se qualquer um dos seus elementos. 20. Seja n um inteiro positivo. Demonstrar que todos os coe�cientes do desenvolvimento do binômio de Newton (a+ b)n são ímpares se, e somente se, n é da forma 2s − 1. 21. Prove que se (x0, y0) é uma solução da equação diofantina linear ax − by = 1, então a área do triângulo cujos vértices são (0, 0), (b, a) e (x0, y0) é 1/2. 142 3 Divisibilidade 22. Qual é a menor distância possível entre dois pontos (x1, y1) e (x2, y2), com coordenadas inteiras, situados sobre a reta de�nida pela equação diofantina ax+ by = c? 4 O Princípio da Casa dos Pombos Uma vez um matemáti o me falou que o verdadeiro prazer não estáem a har a verdade, mas em pro urar por ela. Leo Tolstoy Um interessante instrumento elementar para tratar problemas mate- máticos relacionados à existência de elementos de conjuntos validando certas exigências é o chamado princípio de Dirichlet , também conhe- cido como princípio da casa dos pombos (PCP). Este princípio foi usado por Dirichlet (1805-1859) para resolver problemas na Teoria dos Números, entretanto ele possui um grande número de aplicações em diversos ramos da Matemática como Combinatória e Geometria. A seguir enunciamos a versão mais simples do PCP. Proposição 4.1 (PCP � Versão Simples). Se distribuímos N + 1 pombos em N casas, então alguma das casas contém dois ou mais pombos. 143 144 4 O Princípio da Casa dos Pombos · · · · · · · · ·P1 P2 PN C1 C2 CN PN+1 Figura 4.1: Em cada casa Cj , 1 ≤ j ≤ N , coloca-se um único pombo, denotado por Pj . O pombo restante, denotado por PN+1, deve ir para alguma das casas, juntando-se ao que já se encontrava contido nela Demonstração. A prova deste princípio é muito fácil e decorre de fa- zer uma simples contagem dos pombos contidos em todas as casas de- pois de distribuídos. Com efeito, suponhamos pelo contrário que em cada casa não existe mais do que um pombo, então contando todos os pombos contidos nas N casas não teremos mais do que N pombos, contradizendo isto a hipóteses de termos N + 1 pombos distribuídos nas N casas (ver Figura 4.1). Não é difícil detectar quando o princípio pode ser usado, mas a principal di�culdade para aplicá-lo reside em identi�car, em cada pro- blema, quem faz papel de pombos e quem faz papel de casas. Nas seguintes seções discutiremos vários exemplos de diferentes naturezas onde o princípio da casa dos pombos é aplicado com sucesso. 4.1 Primeiros Exemplos 145 4.1 Primeiros Exemplos Exemplo 4.2. Numa �oresta crescem 1.000 jaqueiras. É conhecido que uma jaqueira não contém mais do que 600 frutos. Prove que existem 2 jaqueiras na �oresta que têm a mesma quantidade de frutos. Solução. Temos 1.000 jaqueiras, representando os pombos, e 601 casas identi�cadas pelos números 0, 1, 2, 3, . . . , 600. O número k associado a cada casa signi�ca que nela serão colocadas jaqueiras que têm exa- tamente k frutos. Como 1000 > 602 = 601 + 1, o PCP nos garante que existem duas jaqueiras com a mesma quantidade de frutos. Exemplo 4.3. Em uma reunião há n pessoas. Mostre que existem duas pessoas que conhecem exatamente o mesmo número de pessoas. Solução. Os pombos neste caso são as n pessoas. As casas são enume- radas com os números 0, 1, 2, . . . , n−1, indicando estes que na mesma serão colocadas pessoas que têm essa quantidade de conhecidos. No- temos que uma das casas enumeradas com 0 ou n − 1 permanece desocupada, pois a possibilidade de conhecer 0 e n − 1 pessoas não acontece simultaneamente. Logo, nas n − 1 casas restantes haverá uma ocupada por dois ou mais pombos, depois de serem distribuídos. Portanto, existem no mínimo duas pessoas com o mesmo número de conhecidos. Exemplo 4.4. Dados 8 números inteiros mostre que existem dois deles cuja diferença é divisível por 7. Solução. Consideramos os 8 números como sendo os pombos e as casas como sendo os 7 possíveis restos na divisão por 7. Como temos 8 = 7 + 1 números o PCP nos diz que existem dois números dentro dos 146 4 O Princípio da Casa dos Pombos 8 dados que têm o mesmo resto quando divididos por 7. Finalmente, observamos que se dois números deixam o mesmo resto na divisão por 7 então a diferença entre eles é divisível por 7. Uma forma alternativa e muito útil na qual pode-se apresentar o princípio da casa dos pombos é a seguinte: Proposição 4.5 (PCP � VersãoAlternativa). Se a soma de n nú- meros naturais é igual S, então existe pelo menos um deles que não é maior que S/n, assim como existe pelo menos um deles que não é menor que S/n. Exemplo 4.6. Numa família formada por 5 pessoas a soma das idades é de 245 anos. Prove que podem ser selecionados 3 membros da família cuja soma das idades não é menor que 147. Solução. Temos um total de ( 5 3 ) = 5! 3!2! = 10 trios diferentes formados por membros da família. Além disso, cada pessoa aparece exatamente em ( 4 2 ) = 4! 2!2! = 6 trios. Então, denotando por Ej a soma das idades dos membros de cada trio Tj, j = 1, 2 . . . 10, temos que E1 + E2 + · · ·+ E10 = 6 · 245 = 1470; consequentemente existe algum trio Tj∗ tal que Ej∗ ≥ 147010 = 147. 4.2 Uma Versão mais Geral A seguinte versão mais geral do PCP é bastante útil na resolução de alguns problemas. Proposição 4.7 (PCP � Versão Geral). Se distribuímos Nk+1 pom- bos em N casas, então alguma das casas contém pelo menos k + 1 pombos. 4.2 Uma Versão mais Geral 147 A prova deste enunciado mais geral é similar à anterior. Com efeito, suponhamos pelo contrário que em cada casa não existe mais do que k pombos, então contando todos os pombos contidos nas N casas não teremos mais do que Nk pombos, contradizendo isto a hipóteses de termos Nk + 1 pombos distribuídos nas N casas. Notemos que se k = 1, esta versão mais geral coincide com a versão mais simples. Exemplo 4.8. Num colégio com 16 salas são distribuídas canetas nas cores preta, azul e vermelha para realizar uma prova de concurso. Se cada sala recebe canetas da mesma cor então prove que existem pelo menos 6 salas que receberam canetas da mesma cor. Solução. Fazendo a divisão com resto de 16 por 3 temos que 16 = 3 · 5 + 1. Consideramos as 16 salas como sendo os pombos e as três cores, preto, azul e vermelho como sendo as casas. Logo, podemos �colocar� cada sala em uma das três cores. Assim, o PCP com N = 3 e k = 5 nos dá que existe uma casa com pelo menos 6 pombos, ou seja, existem no mínimo 6 salas que receberam canetas da mesma cor. Exemplo 4.9. Uma equipe formada por seis alunos de Matemática é selecionada para representar o Brasil numa olimpíada internacional. Mostre que necessariamente existem três deles que se conhecem mu- tuamente, ou três deles que não se conhecem mutuamente. Solução. Resolveremos o problema com o auxílio da Figura 4.2. Cada aluno Aj, com j = 1, 2, . . . , 6, é representado por um dos vértices de um hexágono regular. Quando dois alunos se conhecem traçamos o segmento de reta que liga os vértices correspondentes com uma linha contínua; caso contrário traçamos este segmento com uma linha pon- tilhada. Logo, usando este esquema, o problema equivale a provar 148 4 O Princípio da Casa dos Pombos que sempre existe um triângulo de lados contínuos ou um triângulo de lados pontilhados com vértices no conjunto A = {A1, A2, . . . , A6}. Temos 5 segmentos (pombos) incidindo no vértice A1, cada um deles contínuo ou pontilhado (estes dois tipos de linhas são conside- radas como as casas). Como 5 = 2 · 2 + 1, pelo PCP temos que 3 dos 5 segmentos são contínuos ou pontilhados. Suponhamos que 3 são contínuos (caso contrário o argumento é similar) e denotemos estes por A1A3, A1A4 e A1A6 (ver Figura 4.2). Se algum dos segmentos A3A4, A3A6 ou A4A6 for contínuo então este segmento junto aos que se ligam com A1 formam um triângulo de lados contínuos. Por outro lado, se nenhum deles for contínuo, então eles formam um triângulo de lados pontilhados, completando isto a demonstração. A1 A2A3 A4 A5 A6 Figura 4.2: O triângulo A1A2A5 indica que os alunos A1, A2 e A5 não se conhecem mutuamente e o triângulo A1A4A6 indica que os alunos A1, A4 e A6 se conhecem mutuamente 4.3 Aplicações na Teoria dos Números 149 4.3 Aplicações na Teoria dos Números Nesta seção apresentamos alguns exemplos de aplicações do PCP na Teoria dos Números. A primeira delas é: Exemplo 4.10. Se n e m são números naturais, então o conjunto A = {m+ 1,m+ 2, . . . ,m+ n} possui algum divisor de n. Solução. Temos n números diferentes no conjunto acima. Vamos utili- zar o método de redução ao absurdo. Se não existisse nenhum múltiplo de n, quando dividíssemos os números do conjunto A por n, os res- tos pertenceriam ao conjunto B = {1, 2, . . . , n− 1}, que possui n− 1 elementos. Logo, devem existir dois números m + i e m + j, com 1 ≤ i < j ≤ n tais que o resto da divisão de m + i por n é o mesmo que o resto da divisão de m + j por n. Logo, m + j − (m + i) é um múltiplo de n, o que implica que n > j − i ≥ 1 é múltiplo de n menor que n (absurdo!). Logo, deve existir algum múltiplo de n no conjunto A. Como consequência desse exemplo, podemos resolver o próximo problema. Exemplo 4.11. Demonstrar que todo inteiro tem um múltiplo cuja representação decimal começa com o bloco de dígitos 1234567890. Solução. Se m e n são inteiros positivos, pelo exemplo anterior um dos número m + 1,m + 2, . . . ,m + n é múltiplo de n. Assim, dado n um inteiro qualquer, escolhe-se m = 1234567890×10n+1. Deste modo, todos os inteiros m+1,m+2, . . . ,m+ n começam com 1234567890 e algum deles é múltiplo de n. 150 4 O Princípio da Casa dos Pombos Exemplo 4.12. Dado um número inteiro positivo n, mostre que existe um múltiplo de n que se escreve com os algarismos 0 e 1 apenas. (Por exemplo, se n = 3, temos 111 ou 1.101 etc.) Solução. Consideramos os n+ 1 números 1, 11, 111, 1111, . . . , 111 · · · 1︸ ︷︷ ︸ n+1−vezes (4.1) como sendo os pombos e n casas enumeradas com os números 0, 1, 2, 3, . . . , n− 1, ou seja, com os possíveis restos na divisão por n. Similarmente ao exemplo anterior existem dois números na lista (4.1) que deixam o mesmo resto na divisão por n e, portanto, a diferença entre o maior e o menor é múltiplo de n. Obviamente a diferença entre dois números quaisquer da lista (4.1) resulta em um número formado apenas pelos algarismos 0 e 1. Exemplo 4.13. Prove que entre n + 1 elementos escolhidos no con- junto {1,2,3, . . . , 2n} existem dois que são primos relativos. Solução. A escolha das casas e dos pombos neste exemplo não é tão ób- via. Os pombos representam os n + 1 números escolhidos do conjunto {1, 2, . . . , 2n} e as casas são escolhidas como sendo os n conjuntos: Cj = {2j − 1, 2j}, 1 ≤ j ≤ n. Logo, pelo PCP, quando distribuímos os n + 1 números nos n conjun- tos Cj, 1 ≤ j ≤ n, dois deles �carão juntos em algum conjunto Cj, ou seja, estes números serão consecutivos e portanto primos entre si. 4.4 Aplicações Geométricas 151 Finalizaremos esta seção com uma outra prova do teorema de Bachet-Bézout, (veja o Teorema 3.23). Exemplo 4.14. Seja d = (a, b) o mdc entre os números naturais a e b. Então, existem x e y números inteiros tais que ax+ by = d. Solução. Denotando por m = a/d e n = b/d, podemos supor que a e b são primos entre si. Realmente, se podemos escrever mx+ ny = 1 então, substituindo os valores de m e n na equação acima, temos que ax+ by = d. Se (a, b) = 1, considere a sequência A = {a, 2a, . . . , ba}. A�rmamos que existe algum número no conjunto A que deixa resto 1 quando dividido por b. De fato, se isso não ocorresse, teríamos b números em A deixando no máximo b − 1 restos diferentes quando divididos por b. Logo, pelo PCP, dois deles, digamos ia e ja com b > j > i ≥ 1, devem deixar o mesmo resto quando divididos por b. assim, (j − i)a é divisível por b. Como estamos supondo que (a, b) = 1, temos que b deve dividir j − i > 0. Como b > j − i, temos um absurdo. Assim, algum dos números em a deixa resto 1 quando divididos por b. Digamos que esse número seja ax. Logo, ax − 1 é múltiplo de b, onde ax− 1 = by, o que encerra nossa prova. 4.4 Aplicações Geométricas Na geometria também encontramos belas aplicações do PCP. Vejamos os problemas a seguir para constatar isto. 152 4 O Princípio da Casa dos Pombos Exemplo 4.15. Mostre que se tomamos cinco pontos quaisquer sobre um quadrado de lado 1, então pelo menos dois deles nãodistam mais que √ 2/2. Solução. Vamos dividir o quadrado em quatro quadradinhos de lado 1/2, como mostra a �gura. Logo, pelo PCP pelo menos dois deles de- 1 • •• • • vem estar no mesmo quadradinho, uma vez que temos 4 quadradinhos e 5 pontos. Logo, como a maior distância num quadrado é a diagonal, o Teorema de Pitágoras nos garante que a distância desses dois pontos é no máximo √ 2/2, como queríamos mostrar. Exemplo 4.16. Na região delimitada por um triângulo equilátero de lado 4 são marcados 10 pontos no interior deste. Prove que existe ao menos um par destes pontos cuja distância entre eles não é maior que√ 3. Solução. Dividimos o triângulo equilátero de lado 4 em 16 triângulos equiláteros menores de lado 1, conforme a Figura 4.3. Agora pintamos os triângulos nas cores branco e cinza de maneira que dois triângulos vizinhos, isto é, com um lado comum, são pintados de cores diferentes. Se tivéssemos dois pontos no mesmo triângulo a distância máxima possível entre eles seria 1 e o problema estaria resol- vido. Se tivéssemos pontos em triângulos vizinhos, a maior distância possível entre eles seria √ 3 e também isto resolveria o problema. Se não tivéssemos nenhum dos casos anteriores, não seria difícil ver que 4.5 Miscelânea 153 A B C D E • • • • • • • •• • Figura 4.3: O triângulo DBE é equilátero de lado 3 os 10 pontos deveriam estar situados sobre os 10 triângulos brancos, contendo cada triângulo exatamente um ponto. Dividindo o triângulo DBE em 4 triângulos congruentes de lado 3/2 pelo PCP temos que pelo menos dois dos 6 pontos contidos em DBE estão num destes 4 triângulos, logo a distância entre eles não é maior que 3/2 < √ 3. Com isto terminamos nossa prova. 4.5 Miscelânea Os problemas que apresentamos a seguir usam o PCP combinado com outras idéias que são muito empregadas nas suas soluções. Exemplo 4.17. Em cada quadradinho de um tabuleiro 3×3 é colocado um dos números: -1, 0 ou 1. Prove que entre todas as somas das linhas, colunas e diagonais do tabuleiro há duas que são iguais. Por exemplo, no tabuleiro abaixo a soma da segunda linha é 2, que coincide com a soma da terceira coluna. 154 4 O Princípio da Casa dos Pombos -1 -1 1 1 0 1 0 -1 0 Solução. Seja S = a1 + a2 + a3, onde cada a1, a2 e a3 podem tomar valores: −1, 0 e 1. Então, temos 7 valores possíveis para S (casas), que são: −3,−2,−1, 0, 1, 2, 3. O tabuleiro 3×3 tem 3 linhas, 3 colunas e 2 diagonais, portanto, ao somarmos os elementos de cada uma das linhas, colunas e diagonais, obteremos 8 números (pombos). Como existem somente 7 valores possíveis para estes números, pelo PCP pelo menos dois deles devem ser iguais. Exemplo 4.18. Dado qualquer conjunto A formado por 10 números naturais escolhidos entre 1 e 99, inclusos, demonstre que existem dois subconjuntos disjuntos e não vazios de A tal que a soma dos seus res- pectivos elementos é igual. Solução: É conhecido que A tem 210 − 1 = 1.023 subconjuntos não- vazios diferentes. A soma dos elementos de cada um deles dá uma quantidade menor do que 1.000, pois o subconjunto com no máximo 10 elementos de maior soma possível é o formado por 90, 91, . . . , 99, e nesse caso 90+ 91+ · · ·+99 = 945. Agora consideramos os pombos como sendo os 1.023 subconjuntos distintos de A e as casas como sendo as somas possíveis dos elementos de cada um dos conjuntos. Logo, como o número de conjuntos é maior que o número de somas possíveis, devem existir dois conjuntos B e C de A, de tal modo que a soma dos elementos de B é igual à soma dos elementos de C. Se B 4.5 Miscelânea 155 e C são disjuntos, acabou a prova. Se não, considere D = B −B ∩ C e E = C − B ∩ C. Logo, os conjuntos D e E são disjuntos e a soma dos seus elementos é a mesma, pois retiramos de ambos a mesma quantidade. Exemplo 4.19. Qual é o maior número de quadradinhos de um ta- buleiro de 8 × 8 que podem ser pintados de preto, de forma tal que qualquer arranjo de três quadradinhos, como mostra a Figura 4.4, te- nha pelo menos um dos quadradinhos não pintado de preto? Figura 4.4: Tridominós Solução. Primeiramente, pintamos o tabuleiro de 8×8 como um tabu- leiro de jogar xadrez, ou seja, 32 quadradinhos pintados de branco e 32 quadradinhos pintados de preto (ver Figura 4.5). Figura 4.5: Tabuleiro de xadrez 156 4 O Princípio da Casa dos Pombos Notemos que uma vez pintado o tabuleiro desta forma é satisfeita a exigência do problema, pois nunca temos 2 quadradinhos vizinhos (quadradinhos com um lado comum) pintados de preto. Mostraremos agora que se pintamos 33 quadradinhos de preto en- tão a condição exigida no problema falha. De fato, se dividimos o tabuleiro em 16 quadrados de 2 × 2 (casas) e pintamos 33 quadra- dinhos de preto (pombos); então, como 33 = 16 · 2 + 1, pela versão geral do PCP um dos 16 quadrados de 2× 2 contém 3 quadradinhos pintados de preto. Portanto, este último contém um arranjo como na Figura 4.4 completamente pintado de preto. Resumindo, o número máximo de quadradinhos que podemos pin- tar de preto é 32. Exemplo 4.20. Dados sete números reais arbitrários, demonstre que existem dois deles, digamos x e y, tais que 0 ≤ x− y 1+ xy ≤ 1√ 3 Solução. Primeiramente observamos que a expressão x−y 1+xy nos faz pen- sar na fórmula tan(α− β) = tanα− tan β 1 + tanα tan β . (4.2) Sejam x1, x2, · · · , x7 os sete números selecionados arbitrariamente. Lembramos que a função tangente é uma bijeção entre o intervalo (−π 2 , π 2 ) e os números reais R, logo para cada xi, 1 ≤ i ≤ 7, existe um αi ∈ (−π2 , π2 ) tal que tan(αi) = xi. Dividimos o intervalo (−π2 , π2 ) em seis subintervalos de comprimento π 6 , como mostra o desenho a seguir. Pelo PCP dois dos números αi pertencem ao mesmo subintervalo. Denotemos os mesmos por αi1 e αi2 e suponhamos, sem perda de 4.6 Exercícios 157 αi1 αi2 −π 2 π 2π 6 generalidade, que αi1 ≤ αi2 . Então vale 0 ≤ αi2 − αi1 ≤ π 6 . Usando o fato de que a tangente é uma função crescente e a fórmula (4.2) temos que tan(0) ≤ tan(αi2 − αi1) ≤ tan( π 6 ). Equivalentemente, 0 ≤ xi2 − xi1 1 + xi2xi1 ≤ 1√ 3 . 4.6 Exercícios 1. Seja C um conjunto formado por cinco pontos de coordenadas inteiras no plano. Prove que o ponto médio de algum dos seg- mentos com extremos em C tem também coordenadas inteiras. 2. O conjunto dos dígitos 1, 2, ..., 9 é dividido em três grupos. Prove que o produto dos números de algum dos grupos deve ser maior que 71. 3. Prove que se N é ímpar então para qualquer bijeção p : IN → IN 158 4 O Princípio da Casa dos Pombos do conjunto IN = {1, 2, . . . , N} o produto P (p) = (1−p(1))(2− p(2)) · · · (N − p(N)) é necessariamente par. (Dica: O produto de vários fatores é par se, e somente se, um dos fatores é par.) 4. Dado um conjunto de 25 pontos no plano tais que entre quaisquer 3 deles existe um par com distância menor que 1. Prove que existe um círculo de raio 1 que contém pelo menos 13 dos 25 pontos dados. 5. Prove que entre quaisquer 5 pontos escolhidos dentro de um triângulo equilátero de lado 1 sempre existe um par deles cuja distância não é maior que 0,5. 6. Marquemos todos os centros dos 64 quadradinhos de um ta- buleiro de xadrez de 8× 8. É possível cortar o tabuleiro com 13 linhas retas que não passem pelos pontos marcados e de forma tal que cada pedaço de recorte do tabuleiro tenha no máximo um ponto marcado? 7. Prove que existem duas potências de 3 cuja diferença é divisível por 1.997. 8. São escolhidos 6 números quaisquer pertencentes ao conjunto A = {1, 2, 3, . . . , 10}. Prove que existem dois desses seis números cuja soma é ímpar. 9. Seja x um número real arbitrário. Prove que entre os números x, 2x, 3x, . . . , 101x 4.6 Exercícios 159 existe um tal que sua diferença com certo número inteiro é menor 0,011. 10. Mostre que entre nove números que não possuem divisores pri- mos maiores que cinco, existem dois cujo produto é um qua- drado. 11. Um disco fechado de raio um contém sete pontos, cujas distân- cias entre quaisquer dois deles
Compartilhar