Polos Olímpicos de Treinamento Intensivo (POTI) Curso de Teoria dos Números - Nível 2 Aula 3 - O Algoritmo de Euclides Prof. Samuel Feitosa "Arquivo Original"{1} ****** Sumário ****** 1 O Algoritmo de Euclides 1.1 Problemas Propostos 1.2 Respostas, Dicas e Soluções 1.3 Referências ***** 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 pertence 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 não= 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: mdc(123, 164) = mdc(123, 41) = mdc(41, 123) = mdc(41, 82) = mdc(41, 41) = 41. 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): mdc(819, 357) = mdc(462, 357) = mdc(105, 357) = mdc(105, 252) = ... = mdc(21, 21) = 21. Pelo Lema de Euclides, o mdc entre os dois números em um ticket nunca muda. Como mdc(1, 2) = 1 não= 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 não= 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^(2) + y^(2) - 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: 2abd^(2) | d^(2)a^(2) + d^(2)b^(2) - da -> d^(2) | d^(2)a^(2) + d^(2)b^(2) - da -> d^(2) | -da -> d | a. Logo, a = dc, para algum c. Como x | y^(2), obtemos d^(2)c | d^(2)b^(2), ou seja, c | b^(2) e mdc(c, b^(2)) = 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^(2)) = 1. Assim, c = 1 e x = d^(2)c = d^(2). 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: b = cq1 + r1, 0 < r1 < c, c = r1q2 + r2, 0 < r2 < r1, r1 = r2q3 + r3, 0 < r3 < r2, : rj-2 = rj-1qj + rj, 0 < rj < rj-1, rj-1 = rjqj+1 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, mdc(x + qy, y) = mdc(x + (q - 1)y, y) = mdc(x + (q - 2)y, y) = ... = mdc(x, y). Então, mdc(b, c) = mdc(c, r1) = mdc(r1, r2) = ... = mdc(rj-1, rj) = rj. Exemplo 12. Calcule mdc(42823, 6409). Pelo Algoritmo de Euclides, 42823 = 6×6409 + 4369 6409 = 1×4369 + 2040 4369 = 2×2040 + 289 2040 = 7×289 + 17 289 = 17×17. 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: (42823, 6409) | (1, 0)(0, 1) (4369, 6409) | (1, -6)(0, 1) (4369, 2040) | (1, -6)(-1, 7) (289, 2040) | (3, -20)(-1, 7) (289, 17) | (3, -20)(-22, 147) (17, 17) | (355, -2372)(-22, 147) 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: (x, x + qy) | (a, b)(c, d); então, a próxima linha deverá ser: (x, y) | (a, b)(c - aq, d - bq); 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: (289, 2040) | (3, -20)(-1, 7); obtemos que: 289 = 3×42823 - 20×6409, 2040 = -1×42823 + 7×6409. 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: 17 = -22×42823 + 147×6409, 17 = 355×42823 - 2372×6409, 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 não= 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(2^(120) - 1, 2^(100) - 1) = 2^(20) - 1. Pelo lema de Euclides, mdc(2^(120) - 1, 2^(100) - 1) = mdc(2^(120) - 1 - 2^(20)(2^(100) - 1), 2^ (100) - 1), = mdc(2^(20) - 1, 2^(100) - 1), = mdc(2^(20) - 1, 2^(100) - 1 - 2^(80)(2^(20) - 1)), = mdc(2^(20) - 1, 2^(80) - 1), = mdc(2^(20) - 1, 2^(80) - 1 - 2^(60)(2^(20) - 1)), = mdc(2^(20) - 1, 2^(60) - 1), = mdc(2^(20) - 1, 2^(60) - 1 - 2^(40)(2^(20) - 1)), = mdc(2^(20) - 1, 2^(40) - 1), = mdc(2^(20) - 1, 2^(40) - 1 - 2^(20)(2^(20) - 1)), = mdc(2^(20) - 1, 2^(20) - 1) = 2^(20) - 1. Exemplo 17. (Olimpíada Russa 1964) Sejam x, y inteiros para os quais a fração x^(2) + y^(2) a = ========================================================================= xy é 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 / | x = d ·x0, mdc(x0, y0) = 1, { y = d ·y0 | \ então x^(2) + y^(2) x02 + y02 a = =================================== = =================================== . xy x0y0 Nessa condição, como x0 divide y02 e y0 divide x02, cada um deles é igual a 1, donde 1^(2) + 1^(2) a = ====================================================================== = 2. 1 ·1 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: mmc(m, n) + mdc(m, n) = m + n. 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, d^(2)ab mmc(m, n) = ============================================================ = dab. d Temos: mmc(m, n) + mdc(m, n) - m - n = 0 -> dab + d - da - db = 0 -> ab + 1 - a - b = 0 -> (a - 1)(b - 1) = 0. 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: a(a + 5) mmc(a, a + 5) = ========================================================== , mdc(a, a + 5) b(b + 5) mmc(b, b + 5) = ========================================================== . mdc(b, b + 5) 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: a(a + 5) - b(b + 5) = 0 -> (a - b)(a + b + 5) = 0. 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: f(x, x) = x, f(x, y) = f(y, x), (x + y)f(x, y) = yf(x, x + y). 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: xy (x + y)mmc(x, y) = (x + y) ============================================ mdc(x, y) x(x + y) = y · ================================================ mdc(x, x + y) = y ·mmc(x, x + y) 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) não= 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ão= n. Suponha sem perda de generalidade que n > m. Portanto: nf(m, n - m) = [m + (n - m)] f(m, n - m) -> = (n - m) f(m, m + (n - m)) -> n - m f(m, n - m) = ================================================= ·f(m, n) n Como o par (m, m - n) não está em S, dado que a soma de seus elementos é menor que m + n, temos: f(m, n - m) = mmc(m, n - m) -> n - m ================================== ·f(m, n) = (n - m)mmc(m, m + (n - m)) -> n f(m, n) = mmc(m, n) 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^(2) + n + 1). b) mdc(3×2012, 2×2012 + 1). c) mdc ( [(2^(40) + 1)/(2^(8) + 1)], 2^(8) + 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: mdc(a + b, a^(2) - ab + b^(2)) = 1 ou 3 Problema 29. Dado que mdc(a, 4) = 2, mdc(b, 4) = 2, prove que: mdc(a + b, 4) = 4. Problema 30. Prove que, para todo natural n, mdc(n! + 1, (n + 1)! + 1) = 1. 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: {16n + 10n - 1, n = 1, 2, 3 ... }? 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. F1 = {0/1, 1/1} F2 = {0/1, 1/2, 1/1} F3 = {0/1, 1/3, 1/2, 2/3, 1/1} F4 = {0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1} F5 = {0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1} F6 = {0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1} Claramente, toda fração [a/b] < 1 com mdc(a, b) = 1, está em algum Fn. Mostre que se m/n e m 2/n 2 são frações consecutivas em Fn temos |mn 2- nm 2| = 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: 1 1 a 5 c =========== , ============ , ... , ======= , ======== , ======== , ... 99 98 b 8 d 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: p 1 1 1 1 ========== = 1 - =========== + =========== - ... - =========== + =========== . q 2 3 1318 1319 Prove que p é divisível por 1979. **** 1.2 Respostas, Dicas e Soluções **** 23. (a) mdc(n, n^(2) + n + 1) = mdc(n, n^(2) + n + 1 - n(n + 1)), = mdc(n, 1), = 1. (b) mdc(3×2012, 2×2012 + 1) = mdc(3×2012 - (2×2012 + 1), 2×2012 + 1), = mdc(2012 - 1, 2×2012 + 1), = mdc(2012 - 1, 2×2012 + 1 - 2(2012 - 1)), = mdc(2012 - 1, 3), = mdc(2012 - 1 - 3×670, 3), = mdc(2, 3) = 1. 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) / 2^(40) + 1 \ = mdc(2^(32) + 2^(24) + 2^(16) + 2^(8) mdc \ =============== , 2^(8) + 1 / + 1, 2^(8) + 1), 2^(8) + 1 = mdc((2^(32) - 1) + (2^(24) + 1) + (2^(16) - 1) + (2^(8) + 1) + 1, 2^(8) + 1), = mdc(1, 2^(8) + 1) = 1. 24. mdc(2n + 13, n + 7) = mdc(2n + 13 - 2(n + 7), n + 7), = mdc(2n + 13 - 2(n + 7), n + 7), = mdc(-1, n + 7) = 1 25. mdc(12n + 1, 30n + 2) = mdc(12n + 1, 30n + 2 - 2(12n + 1)), = mdc(12n + 1, 6n), = mdc(12n + 1 - 2(6n), 6n), = mdc(1, 6n) = 1 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 mdc(am - 1, an - 1) = mdc(am-n - 1 + (an - 1)am-n, an - 1) = mdc(am-n - 1, an - 1) O resultado segue aplicando o Algoritmo de Euclides aos expoentes. 28. Seja f = mdc(a + b, a^(2) - ab + b^(2)). Então f | (a + b)^(2) - (a^(2) - ab + b^(2)) = 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, mdc(n! + 1, (n + 1)! + 1) = mdc(n! + 1, (n + 1)! + 1 - (n + 1)(n! + 1)) = mdc(n! + 1, -n) = mdc(n! + 1 - n[(n - 1)!], -n) = 1 34. Sejam l = mmc{1, 2, ... , n} e ai = l/i. A soma considerada é a1 + a2 + ... + an ============================================================================ . l 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 não= 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: 1 1 1 ================ + ================ = ================================= -> a b c bc + ac = ab dyc + dxc = d^(2)xy c(x + y) = dxy 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: 1 1 1 + ... 1 1 1 1 1 - ====== + ====== - ====== - ====== = ======= + ======= + ... + ======= 2 3 4 2n n + 1 n + 2 2n 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. =============================================================================== **** Notas de Rodapé: **** {1} Documento: "... gaia/educacional/matematica/pot2tn03/Aula03-Algoritmo_de_Euclides.pdf".