Arquivos de Impressão: Tamanho A4 (pdf), Tamanho A5 (pdf), Texto (txt).
Definição 1. Dados dois inteiros a e b, com a ≠ 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.
(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:
|
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 A2 + 1. Prove que se B − A > 0, então B − A > √A.
Seja B − A = q. Assim, A + q | A2 + 1. Como (A − q)(A + q) = A2 − q2 é divisível por A + q, podemos concluir que A + q | [(A2 + 1) − (A2 − q2)] = q2 + 1. Pela propriedade de limitação, A + q ≤ q2 + 1. Nessa desigualdade, não podemos ter q = 1 pois A > 1. Usando então que q > 1, temos A ≤ q2 − q + 1 < q2, ou seja, √A < q.
Problema 8. (AIME 1986) Qual é o maior inteiro n para o qual n3 + 100 é divisível por n + 10?
Para achar explicitamente o quociente de n3 + 100 por n + 10 podemos fazer uso de alguma fatoração. Utilizaremos a soma dos cubos n3 + 103 = (n + 10)(n2 − 10n + 100). Como,
|
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 n3 + 100 por n + 10 é n2 − 10n + 100 − 1 = 8902 − 10 ·890 + 99.
Exemplo 9. (Extraído de [1]) Encontre todos os inteiros positivos n tais que 2n2 + 1 | n3 + 9n − 17.
Utilizando o "2n2 + 1 divide" para reduzir o grau de n3 + 9n − 17, temos que
|
|
Como o grau de 17n − 34 é menor do que o de 2n2 + 1, podemos utilizar a "limitação" para obter uma lista finita de candidatos a n. Temos 17n − 34 = 0 ⇔ n = 2 ou | 2n2 + 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 b2 + ba + 1 divide a2 + ab + 1. Prove que a = b.
Pela propriedade de limitação, b2 + ba + 1 ≤ a2 + ab + 1 e daí b ≤ a. Além disso, b2 + ab + 1 > a − b. A igualdade b(a2 + ab + 1) − a(b2 + ba + 1) = b − a implica que a − b é divisível por b2 + ba + 1. Se a − b ≠ 0, então b2 + ab + 1 ≤ a − b. Mas isso é um absurdo, logo a − b = 0.
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 n2 + 2009 e n + 2010 divide n2 + 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
|
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 a3 é divisível por b, b3 é divisível por c e c3 é 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 xy2 + y + 7 divide x2y + x + y.
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).
|
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 = 103 ·[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:
|
Assim, m + n é o quadrado de um inteiro. Se m − n = t, então m + n = t2 e (m, n) = ([( t2 + t)/ 2], [( t2 − 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(x2y + x + y) − x(xy2 + y + 7) = y2 − 7x implica que y2 − 7x é divisível por xy2 + y + 7. Se y2 − 7x ≥ 0, como y2 − 7x < xy2 + y + 7, segue que y2 − 7x = 0. Assim, (x, y) = (7t2, 7t) para algum t ∈ N. É fácil checar que esses pares são realmente soluções. Se y2 − 7x < 0, então 7x − y2 > 0 é divisível por xy2 + y + 7. Daí, xy2 + y + 7 ≤ 7x − y2 < 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: (7t2, 7t)(t ∈ N), (11, 1) e (49, 1).