Arquivos de Impressão: Tamanho A4 (pdf), Tamanho A5 (pdf), Texto (txt).
Exemplo 1. Seja S um conjunto infinito de inteiros não negativos com a seguinte propriedade: dados dois quaisquer de seus elementos, o valor absoluto da diferença entre eles também pertence a S. Se d é o menor elemento positivo de S, prove que S consiste de todos os múltiplos de d.
Considere um elemento m qualquer de S. Pelo algoritmo da divisão, m = qd + r com 0 ≤ r < d. Como todos os números m − d, m − 2d, m − 3d, ... , m − qd = r pertencem a S, e d é o menor elemento positivo de tal conjunto, devemos ter obrigatoriamente que r = 0. Sendo assim, podemos concluir que todos os elementos de S são múltiplos de d. Resta mostrarmos que todos os múltiplos de d estão em S. Seja kd um múltiplo positivo qualquer de d. Como S é infinito, existe um inteiro m ∈ S tal que m = qd > kd. Assim todos os números m − d, m − 2d, ... , m − (q − k)d = kd estão em S.
Definição 2. Um inteiro a é um divisor comum de b e c se a | b e a | c. Se b e c são ambos não nulos, denotaremos por mdc(b, c) o máximo divisor comum de b e c.
Como um inteiro não nulo possui apenas um número finito de divisores, se b e c são ambos não nulos, o número mdc(b, c) sempre existe, isto é, sempre está bem definido.
Lema 3. (Euclides) Se x ≠ 0, mdc(x, y) = mdc(x, x + y)
Demonstração. Seja d um divisor comum de x e y. Então d | x + y e consequentemente d também á um divisor comum de x e x + y. Reciprocamente, se f é um divisor comum de x + y e x, f também divide (x + y) − y = x e assim f é um divisor comum de x e y. Como os conjuntos de divisores comuns dos dois pares de números mencionados são os mesmos, o maior divisor comum também é o mesmo.
|
Exemplo 4. Três máquinas I, R, S imprimem pares de inteiros positivos em tickets. Para a entrada (x, y), as máquinas I, R, S imprimem respectivamente (x − y, y), (x + y, y), (y, x). Iniciando com o par (1, 2) podemos alcançar
Para o item a), calculemos inicialmente mdc(819, 357):
|
Pelo Lema de Euclides, o mdc entre os dois números em um ticket nunca muda. Como mdc(1, 2) = 1 ≠ 21 = mdc(819, 357), não podemos alcançar o par do item a).
Para o item b), indiquemos com → uma operação de alguma das máquinas. Veja que:
(2, 1) [R || (→)] (3, 1) [S || (→)] (1, 3) [R || (→)] (4, 3) [R || (→)] ... [R || (→)] (19, 3) [S || (→)] (3, 19) [R || (→)] (22, 19) [R || (→)] (41, 19) [R || (→)] (60, 19) [R || (→)] (79, 19).
Observação 5. Procurar invariantes sempre é uma boa estratégia para comparar configurações diferentes envolvidas no problema. Confira o problema proposto 31.
Definição 6. Dizemos que dois inteiros p e q são primos entre si ou relativamente primos se mdc(p, q) = 1. Dizemos ainda que a fração [p/q] é irredutível se p e q são relativamente primos.
Exemplo 7. (IMO 1959) Prove que [(21n + 4)/(14n + 3)] é irredutível para todo número natural n.
Pelo lema de Euclides, mdc(21n+4, 14n+3) = mdc(7n+4, 14n+3) = mdc(7n+1, 7n+2) = mdc(7n + 1, 1) = 1.
O seguinte lema será provado na próxima aula.
Lema 8. (Propriedades do MDC) Seja mdc(a, b) = d, então:
i) Se k ≠ 0, mdc(ka, kb) = kd.
iii) Se mdc(a, c) = 1, então mdc(a, bc) = d.
Exemplo 9. (Olimpíada Inglesa) Se x e y são inteiros tais que 2xy divide x2 + y2 − x, prove que x é um quadrado perfeito
Se d = mdc(x, y), então x = da e y = db, com mdc(a, b) = 1. Do enunciado, temos:
|
Logo, a = dc, para algum c. Como x | y2, obtemos d2c | d2b2, ou seja, c | b2 e mdc(c, b2) = c. Usando que mdc(a, b) = 1 e que todo divisor comum de b e c também é um divisor comum de a e b, podemos concluir que mdc(c, b) = 1. Usando o item iii) do lema anterior, mdc(c, b2) = 1. Assim, c = 1 e x = d2c = d2.
Exemplo 10. No planeta X, existem apenas dois tipos de notas de dinheiro: $5 e $78. É possível pagarmos exatamente $7 por alguma mercadoria? E se as notas fossem de $3 e $78?
Veja que 2×78 − 31×5 = 1 e consequentemente 14×78 − 217×5 = 7. Basta darmos 14 notas de $78 para recebermos 217 notas de $5 como troco na compra de nossa mercadoria. Usando as notas de $3 e $78 não é possível pois o dinheiro pago e recebido como troco por algo sempre é múltiplo de 3 e 7 não é múltiplo de 3.
Queremos estudar a versão mais geral desse exemplo. Quais são os valores que podemos pagar usando notas de $a e $b? Em particular, estaremos interessados em conhecer qual o menor valor que pode ser pago. Para responder essa pergunta, precisaremos do algoritmo de Euclides:
Teorema 11. (O Algoritmo de Euclides) Para os inteiros b e c > 0, aplique sucessivamente o algoritmo da divisão para obter a série de equações:
|
A sequência de restos não pode diminuir indefinidamente pois 0 ≤ ri < ri−1 e existe apenas um número finito de naturais menores que c. Assim, para algum j, obteremos rj+1 = 0. O maior divisor comum de b e c será rj, ou seja, o último resto não nulo da sequência de divisões acima.
Demonstração. Pelo Lema de Euclides,
|
|
Exemplo 12. Calcule mdc(42823, 6409).
|
Portanto, mdc(42823, 6409) = 17.
Podemos extrair mais informações do Algoritmo de Euclides. Para isso, iremos organizar as equações do exemplo acima de outra forma.
Essencialmente, a equação mdc(x+qy, y) = mdc(x, y) nos diz que podemos subtrair q vezes um número de outro sem alterar o máximo divisor comum do par em questão. Realizando esse procedimento sucessivas vezes, subtraindo o número menor do maior, podemos obter pares com números cada vez menores até que chegarmos em um par do tipo (d, d). Como o máximo divisor comum foi preservado ao longo dessas operações, d será o máximo divisor comum procurado. Iremos repetir o exemplo anterior registrando em cada operação quantas vezes um número é subtraido do outro. Isso será feito através de dois pares de números auxiliares:
|
Da primeira linha para a segunda, como subtraímos 6 vezes o número 6409 de 42823, subtraímos 6 vezes o par (0,1) de (1,0), obtendo: (1,0) − 6(0,1) = (1,−6). Se em uma dada linha, temos:
|
então, a próxima linha deverá ser:
|
porque representará a operação de subtrairmos q vezes o primeiro número do segundo. Veja que o par (a, b) foi subtraido de (c, d) exatamente q vezes. Os números escritos nos últimos dois pares representam os coeficientes dos números originais para cada número do primeiro par. Por exemplo, analisando a linha:
|
|
Em cada linha, essa propriedade é mantida pois a mesma subtração que é realizada no primeiro par também é realizada entre os dois últimos pares. Analisando o último par, podemos escrever 17 como combinação de 42823 e 6409 de duas formas diferentes:
|
Assim, se no planeta X tivéssemos apenas notas de $42823 e $6409, poderíamos comprar algo que custasse exatamente $17.
Como conclusão da discussão anterior e do algoritmo de Euclides, podemos concluir que:
Teorema 13. (Bachet-Bèzout) Se d = mdc(a, b), então existem inteiros x e y tais que ax + by = d.
De fato, a discussão anterior também nos mostra um algoritmo para encontrarmos x e y. Voltando à discussão sobre o planeta X, podemos concluir em virtude do teorema anterior que qualquer valor múltiplo de d poderá ser pago usando apenas as notas de $a e $b. Como todo valor pago, necessariamente é um múltiplo do máximo divisor comum de a e b, descobrimos que o conjunto que procurávamos consiste precisamente do conjunto dos múltiplos de d.
Observação 14. (Para professores) A prova mais comum apresentada para o teorema anterior baseia-se na análise do conjunto de todas as combinações lineares entre a e b e quase sempre se preocupa apenas com mostrar a existência de x e y. Acreditamos que o algoritmo para encontrar x e y facilite o entendimento do teorema para os alunos mais jovens. Entretanto, frequentemente utilizemos apenas a parte da existência descrita no enunciado. Além disso, preferimos discutir um exemplo numérico ao invés de formalizarmos uma prova e sugerimos que o professor faça o mesmo com mais exemplos em aula.
Exemplo 15. (Olimíada Russa 1995) A sequência a1, a2, ... de naturais satisfaz mdc(ai, aj) = mdc(i, j) para todo i ≠ j. Prove que ai = i para todo i.
Para qualquer inteiro n, mdc(a2n, an) = mdc(2n, n) = n, consequentemente n | an. Seja d um divisor qualquer de an diferente de n, então d | mdc(ad, an). De mdc(ad, an) = mdc(d, n), podemos concluir que d | n. Sendo assim, todos os divisores de an que são diferentes de n são divisores de n. Como já sabemos que an = nk, para algum k, não podemos ter k > 1 pois nk não divide n e assim concluímos que an = n.
Exemplo 16. Mostre que mdc(2120 − 1, 2100 − 1) = 220 − 1.
|
Exemplo 17. (Olimpíada Russa 1964) Sejam x, y inteiros para os quais a fração
|
é inteira. Ache todos os possíveis valores de a.
A primeira estratégia é cancelar os fatores comuns com o objetivo de reduzir o problema ao caso em que x e y são primos entre si. Seja d = mdc(x, y), com
|
|
Nessa condição, como x0 divide y02 e y0 divide x02, cada um deles é igual a 1, donde
|
Definição 18. Os inteiros a1, a2, ... , an, todos diferentes de zero, possuem múltiplo comum b se ai | b para i = 1, 2, …, n (note que a1a2 …an é um múltiplo comum). O menor múltiplo comum positivo para tal conjunto de inteiros é chamado de mínimo múltiplo comum e será denotado por mmc(a1, a2, …, an).
Proposição 19. Se a e b são não nulos, então: mmc(a, b) ·mdc(a, b) = |ab|.
(A prova desta proposição também será deixada para a próxima seção)
Exemplo 20. (Olimpíada Russa 1995) Sejam m e n inteiros positivos tais que:
|
Prove que um deles é divisível pelo o outro.
Se d = mdc(m, n), então podemos escrever m = da e n = db. Pela proposição anterior,
|
|
Portanto, ou a = 1 e m | n ou então b = 1 e n | m.
Exemplo 21. (Torneio das Cidades 1998) Prove que, para quaisquer inteiros positivos a e b, a equação mmc(a, a + 5) = mmc(b, b + 5) implica que a = b.
Para o item a), como (a + 5) − a = 5, temos mdc(a, a + 5) é igual a 1 ou 5. O mesmo vale para mdc(b, b + 5). Pela proposição anterior, temos:
|
Suponha que mdc(a, a + 5) = 5 e mdc(b, b + 5) = 1, então a(a + 5) = 5b(b + 5). Consequentemente, a é múltiplo de 5 e a(a + 5) é múltiplo de 25. Isso implica que b(b + 5) também é múltiplo de 5 e que mdc(b, b + 5) > 1. Uma contradição. Analogamente, não podemos ter mdc(a, a + 5) = 1 e mdc(b, b + 5) = 5. Sendo assim, mdc(a, a + 5) = mdc(b, b + 5) e:
|
Como a + b + 5 > 0, concluímos que a = b.
Exemplo 22. Uma máquina f executa operações sobre o conjunto de todos os pares de inteiros positivos. Para cada par de inteiros positivos, ela fornece um inteiro dado pelas regras:
|
Claramente mmc(x, x) = x e mmc(x, y) = mmc(y, x). Usando a proposição anterior e o lema de Euclides temos:
|
Temos então uma forte suspeita de que f = mmc. Seja S o conjunto de todos os pares de inteiros positivos (x, y) tais que f(x, y) ≠ mmc(x, y), e seja (m, n) o par em S com a soma m + n mínima. Note que todo par da forma (n, n) não está em S pois f(n, n) = n = mmc(n, n). Assim, devemos ter m ≠ n. Suponha sem perda de generalidade que n > m. Portanto:
|
Como o par (m, m − n) não está em S, dado que a soma de seus elementos é menor que m + n, temos:
|
Uma contradição. Desse modo, S deve ser um conjunto vazio e f(x, y) = mmc(x, y) para todos os pares de inteiros positivos. Como 2012 | 2012!, mdc(2012, 2012! + 1) = 1 e consequentemente mmc(2012, 2012! + 1) = 2012(2012! + 1).
c) mdc ( [(240 + 1)/(28 + 1)], 28 + 1 ).
Problema 24. Encontre mdc(2n + 13, n + 7)
Problema 25. Prove que a fração [(12n+1)/(30n+2)] é irredutível.
Problema 26. Sejam a, b, c, d inteiros não nulos tais que ad − bc = 1. Prove que [(a+b)/(c+d)] é uma fração irredutível.
Problema 27. Mostre que mdc(am − 1, an − 1) = amdc(m, n) − 1.
Problema 28. Mostre que se mdc(a, b) = 1, então:
|
Problema 29. Dado que mdc(a, 4) = 2, mdc(b, 4) = 2, prove que:
|
Problema 30. Prove que, para todo natural n,
|
Problema 31. No exemplo 4, determine todos os pares que podem ser obtidos começando-se com o par (1, 2).
Problema 32. Qual o máximo divisor comum do conjunto de números:
|
Problema 33. A sequência Fn de Farey é a sequência de todos as frações irredutíveis [a/b] com 0 ≤ a ≤ b ≤ n arranjados em ordem crescente.
|
Claramente, toda fração [a/b] < 1 com mdc(a, b) = 1, está em algum Fn. Mostre que se m/n e m ′/n ′ são frações consecutivas em Fn temos |mn ′− nm ′| = 1.
Problema 34. (Resvista Quantum - Jornal Kvant) Todas as frações irredutíveis cujos denominadores não excedem 99 são escritas em ordem crescente da esquerda para a direita:
|
Quais são as frações [a/b] e [c/d] em cada lado de [5/8]?
Problema 35. (OBM) Para cada inteiro positivo n > 1, prove que 1 + [1/2] + [1/3] + …+ [1/n] não é inteiro.
Problema 36. Determine todas as soluções em inteiros positivos para [1/a] + [1/b] = [1/c].
Problema 37. Inteiros positivos a e b, relativamente primos, são escolhidos de modo que [(a + b)/(a − b)] seja também um inteiro positivo. Prove que pelo menos um dos números ab + 1 e 4ab + 1 é um quadrado perfeito.
Problema 38. (IMO 1979) Sejam p, q números naturais primos entre si tais que:
|
Prove que p é divisível por 1979.
|
|
Outra opção seria observar que o mdc procurado deve dividir o número 3(2×2012 + 1) − 2(3×2012) = 3 e que 2×2012 + 1 não é múltiplo de 3.
(c)
|
|
|
26. Seja f = mdc(a + b, c + d). Então f | d(a + b) − b(c + d) = 1 e consequentemente f = 1.
|
O resultado segue aplicando o Algoritmo de Euclides aos expoentes.
28. Seja f = mdc(a + b, a2 − ab + b2). Então f | (a + b)2 − (a2 − ab + b2) = 3ab. Se mdc(f, a) > 0, devemos ter mdc(f, b) > 0 pois f | a + b. O mesmo argumento vale para mdc(f, b) > 0. Assim, mdc(f, a) = mdc(f, b) = 1. Portanto, f | 3.
|
34. Sejam l = mmc{1, 2, …, n} e ai = l/i. A soma considerada é
|
Queremos analisar o expoente do fator 2 no numerador e no denominador. Seja k tal que 2k ≤ n < 2k+1. Então 2k | l e ai é par para todo i ≠ 2k. Como a2k é ímpar, segue que o numerador é ímpar enquanto que o denominador é par. Consequentemente a fração anterior não representa um inteiro.
36. Sejam d = mdc(a, b), a = dx, b = dy. Consequentemente mdc(x, y) = 1 e podemos escrever a equação como:
|
Como mdc(xy, x + y) = 1 pois mdc(x, y) = 1, devemos ter xy | c e consequentemente c = xyk. Assim, d = k(x + y). O conjunto solução é formado pelas triplas (a, b, c) onde (a, b, c) = (kx(x + y), ky(x + y), xyk) com mdc(x, y) = 1 e x, y e k inteiros positivos.
38. Use a identidade de Catalão:
|
Em seguida, agrupe os termos da forma [1/(n + i)] + [1/(2n − i + 1)] e analise o numerador da fração obtida.