Polos Olímpicos de Treinamento Intensivo (POTI) Curso de Teoria dos Números - Nível 2 Aula 2 - Divisibilidade II Prof. Samuel Feitosa "Arquivo Original"{1} ****** Sumário ****** 1 Divisibilidade II 1.1 Problemas Propostos 1.2 Dicas e Soluções 1.3 Referências ***** 1 Divisibilidade II ***** Definição 1. Dados dois inteiros a e b, com a não= 0, dizemos que a divide b ou que a é um divisor de b ou ainda que b é um múltiplo de a, e escrevemos a | b se o r obtido pelo algoritmo de divisão aplicado à a e b é 0, ou seja, se b = aq para algum inteiro q. Lema 2. Sejam a, b, c, d inteiros. Temos i) ("d divide") Se d | a e d | b, então d | ax + by para quaisquer x e y inteiros. ii) ("Limitação") Se d | a, então a = 0 ou | d | <= | a | . iii) (Transitividade) Se a | b e b | c, então a | c. Em particular, segue da propriedade i) que d | a + b e d | a - b. Exemplo 3. (Olimpíada de Maio 2006) Encontre todos os naturais a e b tais que a | b + 1 e b | a + 1. Pela propriedade da Limitação, temos a <= b + 1 e b <= a + 1. Daí, a - 1 <= b <= a + 1. Vejamos os casos: (i) a = b. Como a | b + 1 e a | b (pois b = a) temos que a | [(b + 1) - b] = 1. Assim, a = 1. Nesse caso, só temos a solução (a, b) = (1, 1) (ii) a = b + 1. Como b | a + 1 e b | a - 1 (pois b = a - 1) temos que b | [(a + 1) - (a - 1)] = 2. Assim, b = 1 ou b = 2 e nesse caso, só temos as soluções (3, 2) e (2, 1). (iii) a = b - 1. Esse caso é análogo ao anterior e as soluções para (a, b) são (1, 2) e (2, 3). Exemplo 4. (Critério de Divisibilidade por 7) Existem alguns métodos práticos para decidirmos se um número é múltiplo de outro. Certamente o leitor já deve ter se deparado com algum critério de divisibilidade. Existe um critério por 7 bastante popular: Para saber se um inteiro é múltiplo de 7, basta apagar seu último dígito, multiplicá-lo por 2 e o subtrair do número que restou. Se o resultado é múltiplo de 7, então o número original também é múltiplo de 7. Podemos aplicar esse algoritmo sucessivas vezes até que o resultado obtido seja facilmente verificável como um múltiplo de 7. Por exemplo, para o número 561421 podemos escrever: 56142 - 2 = 56140 5614 - 0 = 5614 561 - 8 = 553 55 - 6 = 49 Como 49 é múltiplo de 7, nosso número original também é. Por que esse processo funciona? Se o nosso número original está escrito na forma 10a + b, então o número obtido após a operação descrita é a - 2b. Basta mostrarmos que se 7 | a - 2b, então 7 | 10a + b. Se 7 | a - 2b, pela propriedade (i) do lema, concluímos que 7 | 10a - 20b. Como 7 | 21b, também temos que 7 | [(10a - 20b) + 21b] = 10a + b. Exemplo 5. Mostre que se 7 | 3a + 2b então 7 | 4a - 2b. Veja que 7 | 7a e 7 | 3a + 2b, então 7 | [7a - (3a + 2b)] = 4a - 2b. Na prática, o que fizemos foi multiplicar o número 3a + 2b por algum inteiro para posteriormente subtraímos um múltiplo de 7 conveniente e obtermos o número 4a - 2b. Existem outras formas de fazermos isso. Observe os números 3 ·0, 3 ·1, 3 ·2, 3 ·3, 3 ·4, 3 ·5, 3 ·6. O número 3 ·6 deixa o mesmo resto que 4 por 7, pois 3 ·6 = 7 ·2 + 4. Como 7 | 3a + 2b podemos concluir que 7 | (18a + 12b) e consequentemente 7 | [18a + (12b - 14a)] = 4a + 12b. Mas 7 | 14b, então 7 | [4a + 12b - 14b] = 4a - 2b. Para o próximo exemplo, o leitor precisará lembrar dos critérios de divisibilidade por 9 e 3 vistos na aula passada. Exemplo 6. Usando os dígitos 1, 2, 3, 4, 5, 6, 7, construímos vários números de sete dígitos distintos. Existem dois deles, distintos, tais que um divide o outro? Não. Suponha, por absurdo, que m < n sejam dois desses números, com m | n. Claramente m | n - m e 9 | n - m, pois n e m possuem a mesma soma dos dígitos e consequentemente possuem o mesmo resto na divisão por 9. Por outro lado, sabemos a soma dos dígitos de m: 1 + 2 + ... + 7 = 3 ·9 + 1. Daí, m não possui fator 9 e podemos garantir que 9m | n - m. Mas então 9m <= n - m - > 10m <= n -> n tem pelo menos oito dígitos, uma contradição. Exemplo 7. (Leningrado 1989) Seja A um número natural maior que 1, e seja B um número natural que é um divisor de A^(2) + 1. Prove que se B - A > 0, então B - A > \/A. Seja B - A = q. Assim, A + q | A^(2) + 1. Como (A - q)(A + q) = A^(2) - q^ (2) é divisível por A + q, podemos concluir que A + q | [(A^(2) + 1) - (A^ (2) - q^(2))] = q^(2) + 1. Pela propriedade de limitação, A + q <= q^(2) + 1. Nessa desigualdade, não podemos ter q = 1 pois A > 1. Usando então que q > 1, temos A <= q^(2) - q + 1 < q^(2), ou seja, \/A < q. Problema 8. (AIME 1986) Qual é o maior inteiro n para o qual n^(3) + 100 é divisível por n + 10? Para achar explicitamente o quociente de n^(3) + 100 por n + 10 podemos fazer uso de alguma fatoração. Utilizaremos a soma dos cubos n^(3) + 10^(3) = (n + 10)(n^(2) - 10n + 100). Como, n^(3) + 100 = (n + 10)(n^(2) - 10n + 100) - 900, podemos concluir que o número 900 deve ser múltiplo de n + 10. O maior inteiro n para o qual n + 10 divide 900 é 890. Veja que se n = 890, o quociente da divisão de n^(3) + 100 por n + 10 é n^(2) - 10n + 100 - 1 = 890^(2) - 10 ·890 + 99. Exemplo 9. (Extraído de [1]) Encontre todos os inteiros positivos n tais que 2n^(2) + 1 | n^(3) + 9n - 17. Utilizando o "2n^(2) + 1 divide" para reduzir o grau de n^(3) + 9n - 17, temos que / | 2n^(2) + 1 | n^(3) + 9n - 17 { 2n^(2) + 1 | 2n^(2) + 1 | \ -> 2n^(2) + 1 | (n^(3) + 9n - 17) ·2 + (2n^(2) + 1) ·(-n) <--> 2n^(2) + 1 | 17n - 34 Como o grau de 17n - 34 é menor do que o de 2n^(2) + 1, podemos utilizar a "limitação" para obter uma lista finita de candidatos a n. Temos 17n - 34 = 0 <--> n = 2 ou | 2n^(2) + 1 | <= | 17n - 34 | <--> n = 1, 4 ou 5. Destes candidatos, apenas n = 2 e n = 5 são soluções. Exemplo 10. (Leningrado 1990) Sejam a e b números naturais tais que b^(2) + ba + 1 divide a^(2) + ab + 1. Prove que a = b. Pela propriedade de limitação, b^(2) + ba + 1 <= a^(2) + ab + 1 e daí b <= a. Além disso, b^(2) + ab + 1 > a - b. A igualdade b(a^(2) + ab + 1) - a(b^ (2) + ba + 1) = b - a implica que a - b é divisível por b^(2) + ba + 1. Se a - b não= 0, então b^(2) + ab + 1 <= a - b. Mas isso é um absurdo, logo a - b = 0. **** 1.1 Problemas Propostos **** Problema 11. Mostre que se 3 | a + 7b então 3 | a + b. Problema 12. Mostre que se 7 | a + 3b então 7 | 13a + 11b Problema 13. Mostre que se 19 | 3x + 7y então 19 | 43x + 75y Problema 14. Mostre que se 17 | 3a + 2b então 17 | 10a + b Problema 15. Encontre todos os inteiros positivos n tais que n + 2009 divide n^(2) + 2009 e n + 2010 divide n^(2) + 2010. Problema 16. Seja n > 1 e k um inteiro positivo qualquer. Prove que (n - 1)^(2) | (nk - 1) se, e somente se , (n - 1) | k. Problema 17. (OBM 2005) Prove que a soma 1k + 2k + ... + nk, onde n é um inteiro e k é ímpar, é divisível por 1 + 2 + ... + n. Problema 18. O número de seis dígitos X = ^-[abcdef] satisfaz a propriedade de que ^-[abc] - ^-[def] é divisível por 7. Prove que X também é divisível por 7. Problema 19. (Bielorússia 1996) Inteiros m e n, satisfazem a igualdade 4mn (m - n)^(2) = =============================================================== m + n - 1 a) Prove que m + n é um quadrado perfeito. b) Encontre todos os pares (m, n) satisfazendo a equação acima. Problema 20. (Olimpíada de Leningrado) Os números naturais a, b e c têm a propriedade que a^(3) é divisível por b, b^(3) é divisível por c e c^ (3) é divisível por a. Prove que (a + b + c)^(13) é divisível por abc. Problema 21. (OBM 2000) É possível encontrar duas potências de 2, distintas e com o mesmo número de algarismos, tais que uma possa ser obtida através de uma reordenação dos dígitos da outra? (Dica: Lembre-se do critério de divisibilidade por 9) Problema 22. (IMO 1998) Determine todos os pares de inteiros positivos (x, y) tais que xy^(2) + y + 7 divide x^(2)y + x + y. **** 1.2 Dicas e Soluções **** 11. Como 3 | 6b, segue que 3 | [(a + 7b) - 6b] = a + b. 12. Como 7 | a + 3b, segue que 7 | 13a + 39b = (13a + 11b) + 28b. Mas 7 | 28b, portanto 7 | [(13a + 11b) + 28b - 28b] = 13a + 11b. 13. Como 19 | 3x + 7y, segue que 19 | 27(3x + 7y) = (43x + 75y) + (38x + 114y). Mas 19 | 19 (2x + 6y), portanto 19 | [(43x + 75y) + (38x + 114y) - 19 (2x + 6y)] = 43x + 75y. 14. Como 17 | 3a + 2b, segue que 17 | 27a + 18b = (10a + b) + 17(a + b). 16. Veja que nk - 1 nk-1 - 1 nk-2 - 1 n-1 k ========== = / ========== + ========== + ... + =========== + =========== \ (n - 1)^ \ n - 1 n - 1 n-1 n-1 / (2) Como os números [(nl - 1)/(n - 1)] sempre são inteiros, o número do lado esquerdo da equação será inteiro se, e somente se, o número [k/(n - 1)] for inteiro. 17. Comece dividindo o problema quando em dois casos: n é par ou n é ímpar. Sabemos que 1 + 2 + ... + n = [(n(n+1))/2]. Para n ímpar, basta mostrar que o número em questão é divisível por n e [(n+1)/2]. O próximo passo é lembrar do problema 33 da aula 1. Pela fatoração de xn + yn, temos que ik + (n - i)k é divisível por n. Faça outros tipos de pares para mostrar a divisibilidade por [n/2]. O caso quando n é par é análogo. 18. Veja que X = 10^(3) · ^-[abc] + ^-[def] = 1001 ^-[abc] - ( ^-[abc] - ^- [def]). Como 1001 é múltiplo de 7, concluímos que X é a soma de dois múltiplos de 7. 19. Somando 4mn em ambos os lados, obtemos: 4mn (m + n)^(2) = ======================================================= + 4mn m + n - 1 4mn (m + n) = ========================================================== -> m + n - 1 4mn (m + n) = ============================================================ m + n - 1 = (m - n)^(2) Assim, m + n é o quadrado de um inteiro. Se m - n = t, então m + n = t^ (2) e (m, n) = ([( t^(2) + t)/ 2], [( t^(2) - t)/ 2]). É fácil verificar que para qualquer t inteiro esse par é solução do problema. 20. Analise a expansão pelo binômio de Newton. 21. Não. Suponha, por absurdo, que existam duas potências de 2, 2m < 2n, satisfazendo o enunciado. Como 2n é um múltiplo de 2m, podemos ter: 2n = 2 ·2m, 4 ·2m, 8 ·2m, ... . Além disso, como ambos possuem a mesma quantidade de dígitos, temos 1 < [(2n)/(2m)] < 10. Assim, as únicas possibilidade são 2n = 2 ·2m, 4 ·2m, 8 ·2m. Pelo critério de divisibilidade por 9, como 2m e 2n possuem os mesmos dígitos, podemos concluir que 2n - 2m é um múltiplo de 9. Entretanto, nenhuma das possibilidade anteriores satisfaz essa condição e chegamos em um absurdo. 22. Começaremos usando a idéia do exemplo 10. A igualdade y(x^(2)y + x + y) - x(xy^(2) + y + 7) = y^(2) - 7x implica que y^(2) - 7x é divisível por xy^ (2) + y + 7. Se y^(2) - 7x >= 0, como y^(2) - 7x < xy^(2) + y + 7, segue que y^(2) - 7x = 0. Assim, (x, y) = (7t^(2), 7t) para algum t pertence N. É fácil checar que esses pares são realmente soluções. Se y^(2) - 7x < 0, então 7x - y^(2) > 0 é divisível por xy^(2) + y + 7. Daí, xy^(2) + y + 7 <= 7x - y^(2) < 7x, que nos permite concluir que y <= 2. Para y = 1, temos x + 8 | 7x - 1 e consequentemente x + 8 | 7(x + 8) - (7x - 1) = 57. Então as únicas possibilidades são x = 11 e x = 49, cujos pares correspondentes são (11, 1), (49, 1). Para y = 2, temos 4x + 9 | 7x - 4 e consequentemente 7(4x + 9) - 4 (7x - 4) = 79 é divisível por 4x + 9. Nesse caso, não obtemos nenhuma solução nova. Todas as soluções para (x, y) são: (7t^(2), 7t)(t pertence N), (11, 1) e (49, 1). **** 1.3 Referências **** ***** Referências Bibliográficas ***** [1] F. E. Brochero Martinez, C. G. Moreira, N. C. Saldanha, E. Tengan - Teoria dos Números um passeio com primos e outros números familiares pelo mundo inteiro, Projeto Euclides, IMPA, 2010. [2] E. Carneiro, O. Campos and F. Paiva, Olimpíadas Cearenses de Matemática 1981-2005 (Níveis Júnior e Senior), Ed. Realce, 2005. [3] S. B. Feitosa, B. Holanda, Y. Lima and C. T. Magalhães, Treinamento Cone Sul 2008. Fortaleza, Ed. Realce, 2010. [4] D. Fomin, A. Kirichenko, Leningrad Mathematical Olympiads 1987-1991, MathPro Press, Westford, MA, 1994. [5] D. Fomin, S. Genkin and I. Itenberg, Mathematical Circles, Mathematical Words, Vol. 7, American Mathematical Society, Boston, MA, 1966. [6] I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers. =============================================================================== **** Notas de Rodapé: **** {1} Documento: "... gaia/educacional/matematica/pot2tn02/Aula02-DivisibilidadeII.pdf".