Índice Superior

Arquivos de Impressão: Tamanho A4 (pdf), Tamanho A5 (pdf), Texto (txt).

Sumário

1  O Algoritmo de Euclides

     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.

     Então podemos calcular:

     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

     a) (819, 357)?

     b) (19, 79)?

     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.

     ii) mdc([a/d], [b/d]) = 1.

     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  x² + y² − 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 | y², obtemos  d²c | d²b², ou seja, c | b² e  mdc(c, b²) = 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, b²) = 1. Assim, c = 1 e  x = d²c = d².

     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 ≤ r_i < r_i−1 e existe apenas um número finito de naturais menores que  c. Assim, para algum  j, obteremos  r_j+1 = 0. O maior divisor comum de  b  e  c  será r_j, ou seja, o último resto não nulo da sequência de divisões acima.

     Demonstração. Pelo Lema de Euclides,

     Então,

     Exemplo 12. Calcule  mdc(42823, 6409).

     Pelo Algoritmo de Euclides,

     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:

obtemos que:

     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  a₁, a₂, ... de naturais satisfaz  mdc(a_i, a_j) = mdc(i, j) para todo  i ≠ j. Prove que  a_i = i  para todo  i.

     Para qualquer inteiro  n, mdc(a_2n, a_n) = mdc(2n, n) = n, consequentemente  n | a_n. Seja  d  um divisor qualquer de  a_n  diferente de  n, então  d | mdc(a_d, a_n). De  mdc(a_d, a_n) = mdc(d, n), podemos concluir que  d | n. Sendo assim, todos os divisores de  a_n  que são diferentes de  n  são divisores de  n. Como já sabemos que  a_n = nk, para algum  k, não podemos ter  k > 1 pois  nk  não divide  n  e assim concluímos que  a_n = n.

     Exemplo 16. Mostre que  mdc(2¹²⁰ − 1, 2¹⁰⁰ − 1) = 2²⁰ − 1.

     Pelo lema de Euclides,

     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

então

     Nessa condição, como  x₀ divide  y₀² e  y₀ divide  x₀², cada um deles é igual a 1, donde

     Definição 18. Os inteiros  a₁, a₂, ... , a_n, todos diferentes de zero, possuem múltiplo comum  b  se  a_i | b  para  i = 1, 2, …, n (note que  a₁a₂ …a_n é 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(a₁, a₂, …, a_n).

     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,

     Temos:

     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:

     Determine  f(2012, 2012! + 1).

     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).

1.1  Problemas Propostos

     Problema 23. Calcule:

     a) mdc(n, n² + n + 1).

     b) mdc(3×2012, 2×2012 + 1).

     c) mdc ( [(2⁴⁰ + 1)/(2⁸ + 1)], 2⁸ + 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(a^m − 1, aⁿ − 1) = a^mdc(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 F_n  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 F_n. Mostre que se  m/n  e  m ′/n ′  são frações consecutivas em F_n  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.

1.2  Respostas, Dicas e Soluções

     23. (a)

     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.

     24.

     25.

     26. Seja  f = mdc(a + b, c + d). Então  f | d(a + b) − b(c + d) = 1  e consequentemente  f = 1.

     27. Veja que

     O resultado segue aplicando o Algoritmo de Euclides aos expoentes.

     28. Seja  f = mdc(a + b, a² − ab + b²). Então  f | (a + b)² − (a² − ab + b²) = 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.

     30. Pelo lema de Euclides,

     34. Sejam  l = mmc{1, 2, …, n} e  a_i = l/i. A soma considerada é

     Queremos analisar o expoente do fator 2 no numerador e no denominador. Seja  k  tal que 2^k ≤ n < 2^k+1. Então 2^k | l  e  a_i é par para todo  i ≠ 2^k. Como  a_2^k é í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.

1.3  Referências

Referências Bibliográficas

[1]

S. B. Feitosa, B. Holanda, Y. Lima and C. T. Magalhães, Treinamento Cone Sul 2008. Fortaleza, Ed. Realce, 2010.

[2]

D. Fomin, A. Kirichenko, Leningrad Mathematical Olympiads 1987-1991, MathPro Press, Westford, MA, 1994.

[3]

D. Fomin, S. Genkin and I. Itenberg, Mathematical Circles, Mathematical Words, Vol. 7, American Mathematical Society, Boston, MA, 1966.

[4]

I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers.