POTI - Aula 03 - MDC & MMC

Prévia do material em texto

Polos Olímpicos de Treinamento
Curso de Teoria dos Números - Nível 3
Carlos Gustavo Moreira
Aula 3
MDC, MMC, Algoritmo de Euclides e o Teorema de
Bachet-Be´zout
1 mdc, mmc e Algoritmo de Euclides
Dados dois nu´meros inteiros a e b com a 6= 0 ou b 6= 0, a cada um deles
pode-se associar seu conjunto de divisores positivos, Da e Db respectivamente,
e a intersecc¸a˜o de tais conjuntos Da ∩Db e´ finita (pela “limitac¸a˜o”) e na˜o vazia
(ja´ que 1 pertence a` intersecc¸a˜o). Por ser finito, Da ∩ Db possui elemento
ma´ximo, que e´ chamado de ma´ximo divisor comum (mdc) dos nu´meros a e b.
Denotamos este nu´mero por mdc(a, b) (alguns autores usam a notac¸a˜o (a, b)).
Para a = b = 0 convencionamos mdc(0, 0) = 0. Quando mdc(a, b) = 1 dizemos
que a e b sa˜o primos entre si.
Por outro lado, se denotamos por Mn o conjunto dos mu´ltiplos positivos de
n, dados dois nu´meros inteiros a e b com a 6= 0 e b 6= 0, enta˜o a intersecc¸a˜o
Ma∩Mb e´ na˜o vazia (ja´ que |ab| esta´ na intersecc¸a˜o). Como os naturais sa˜o bem
ordenados, Ma ∩Mb possui elemento mı´nimo. Tal nu´mero e´ chamado mı´nimo
mu´ltiplo comum (mmc) de a e b e o denotaremos por mmc(a, b) (alguns autores
escrevem [a, b]).
Para calcularmos o mdc e o mmc de maneira eficiente, vamos descrever
o chamado algoritmo de Euclides ou algoritmo das diviso˜es sucessivas. Pri-
meiramente, vamos relembrar o conceito de divisa˜o euclidiana, ou divisa˜o com
resto, que e´ uma das quatro operac¸o˜es que toda crianc¸a aprende na escola. Sua
formulac¸a˜o precisa e´: dados a, b ∈ Z com b 6= 0, existem q, r ∈ Z com
a = bq + r e 0 ≤ r < |b|.
Tais q e r esta˜o unicamente determinados pelas duas condic¸o˜es acima (veja o
argumento a seguir) e sa˜o chamados o quociente e resto da divisa˜o de a por b.
O resto r e´ tambe´m denotado por a mod b.
Para x ∈ R, definimos o piso ou parte inteira ⌊x⌋ de x como sendo o u´nico
k ∈ Z tal que k ≤ x < k + 1; definimos o teto ⌈x⌉ de x como o u´nico k ∈ Z tal
que k− 1 < x ≤ k. Por exemplo, temos ⌊√2⌋ = 1, ⌈√2⌉ = 2, ⌊10⌋ = ⌈10⌉ = 10,
POT 2012 - Teoria dos Nu´meros - Nı´vel 3 - Aula 3 - Carlos Gustavo Moreira1 MDC, MMC E ALGORITMO DE EUCLIDES
⌊−pi⌋ = −4 e ⌈−pi⌉ = −3. Podemos agora mostrar a existeˆncia de q e r
satisfazendo as duas condic¸o˜es acima: basta tomar
q =
{
⌊a/b⌋ se b > 0
⌈a/b⌉ se b < 0 e r = a− bq em ambos os casos
e e´ fa´cil verificar que 0 ≤ r < |b| a partir das definic¸o˜es das func¸o˜es piso e teto.
Por outro lado, se a = bq1+ r1 = bq2+ r2 com 0 ≤ r1, r2 < |b|, enta˜o temos que
r2− r1 = b(q1− q2) e´ um mu´ltiplo de b com |r2− r1| < |b|, portanto r2− r1 = 0
e assim q1 = q2 tambe´m, o que prova a unicidade.
Podemos agora descrever o algoritmo de Euclides para calcular o mdc, que
se baseia na seguinte simples observac¸a˜o:
Lema 1 (Euclides). Se a = bq + r, enta˜o mdc(a, b) = mdc(b, r).
Demonstrac¸a˜o. Basta mostrar que Da∩Db = Db∩Dr, ja´ que se estes conjuntos
forem iguais em particular os seus ma´ximos tambe´m sera˜o iguais. Se d ∈ Da∩Db
temos d | a e d | b, logo d | a− bq ⇐⇒ d | r e portanto d ∈ Db∩Dr. Da mesma
forma, se d ∈ Db ∩ Dr temos d | b e d | r, logo d | bq + r ⇐⇒ d | a e assim
d ∈ Da ∩Db.
O algoritmo de Euclides consiste na aplicac¸a˜o reiterada do lema acima onde
q e r sa˜o o quociente e o resto na divisa˜o de a por b (note que o lema vale
mesmo sem a condic¸a˜o 0 ≤ r < |b|). Como os restos formam uma sequeˆncia
estritamente decrescente, o algoritmo eventualmente para quando atingimos o
resto 0.
Exemplo 2. Calcule mdc(1001, 109).
Soluc¸a˜o: Realizando as diviso˜es sucessivas, temos
1001 = 109 · 9 + 20
109 = 20 · 5 + 9
20 = 9 · 2 + 2
9 = 2 · 4 + 1
2 = 1 · 2 + 0
Assim, temos mdc(1001, 109) = mdc(109, 20) = mdc(20, 9) = mdc(9, 2) =
mdc(2, 1) = mdc(1, 0) = 1.
Exemplo 3. Sejam m 6= n dois nu´meros naturais. Demonstrar que
mdc(a2
m
+ 1, a2
n
+ 1) =
{
1 se a e´ par,
2 se a e´ ı´mpar.
Soluc¸a˜o: Suponha sem perda de generalidade que m > n e observe a fato-
rac¸a˜o
a2
m − 1 = (a2m−1 + 1)(a2m−2 + 1)(a2m−3 + 1) . . . (a2n + 1)(a2n − 1)
2
POT 2012 - Teoria dos Nu´meros - Nı´vel 3 - Aula 3 - Carlos Gustavo Moreira1 MDC, MMC E ALGORITMO DE EUCLIDES
Logo a2
m
+ 1 = (a2
n
+ 1) · q + 2 com q ∈ Z e assim
mdc(a2
m
+ 1, a2
n
+ 1) = mdc(a2
n
+ 1, 2)
que e´ igual a 2 se a2
n
+ 1 for par, isto e´, se a for ı´mpar, e e´ igual a 1 caso
contra´rio.
Ale´m de servir de ferramenta computacional para o ca´lculo do mdc, a divisa˜o
euclidiana tem consequeˆncias teo´ricas importantes. O pro´ximo teorema mostra
que e´ sempre poss´ıvel escrever o mdc de dois nu´meros como combinac¸a˜o linear
destes (com coeficientes inteiros).
Teorema 4 (Bachet-Be´zout). Sejam a, b ∈ Z. Enta˜o existem x, y ∈ Z com
ax+ by = mdc(a, b).
Portanto se c ∈ Z e´ tal que c | a e c | b enta˜o c | mdc(a, b).
Demonstrac¸a˜o. O caso a = b = 0 e´ trivial (temos x = y = 0). Nos outros casos,
considere o conjunto de todas as combinac¸o˜es Z-lineares de a e b:
I(a, b)
def
= {ax+ by : x, y ∈ Z}
Seja d = ax0 + by0 o menor elemento positivo de I(a, b) (ha´ pelo menos um
elemento positivo, verifique!). Afirmamos que d divide todos os elementos de
I(a, b). De fato, dado m = ax + by ∈ I(a, b), sejam q, r ∈ Z o quociente e o
resto na divisa˜o euclidiana de m por d, de modo que m = dq + r e 0 ≤ r < d.
Temos
r = m− dq = a(x− qx0) + b(y − qy0) ∈ I(a, b).
Mas como r < d e d e´ o menor elemento positivo de I(a, b), segue que r = 0 e
portanto d | m.
Em particular, como a, b ∈ I(a, b) temos que d | a e d | b, logo d ≤ mdc(a, b).
Note ainda que se c | a e c | b, enta˜o c | ax0 + by0 ⇐⇒ c | d. Tomando
c = mdc(a, b) temos que mdc(a, b) | d o que, juntamente com a desigualdade
d ≤ mdc(a, b), mostra que d = mdc(a, b).
Corola´rio 5. Sejam a, b, c ∈ Z. A equac¸a˜o
ax+ by = c
admite soluc¸a˜o inteira em x e y se, e somente se, mdc(a, b) | c.
Demonstrac¸a˜o. Se a equac¸a˜o admite soluc¸a˜o inteira, enta˜o mdc(a, b) divide o
lado esquerdo, logo deve dividir o direito tambe´m. Reciprocamente, se mdc(a, b) |
c, digamos c = k · mdc(a, b) com k ∈ Z, pelo teorema acima existem inteiros
x0 e y0 tais que ax0 + by0 = mdc(a, b) e multiplicando tudo por k obtemos que
x = kx0 e y = ky0 sa˜o soluc¸o˜es da equac¸a˜o dada.
Temos uma outra importante consequeˆncia do teorema anterior:
3
POT 2012 - Teoria dos Nu´meros - Nı´vel 3 - Aula 3 - Carlos Gustavo Moreira1 MDC, MMC E ALGORITMO DE EUCLIDES
Proposic¸a˜o 6. Se mdc(a, b) = 1 e a | bc, enta˜o a | c.
Demonstrac¸a˜o. Como mdc(a, b) = 1, existem x, y ∈ Z tais que ax+by = 1 =⇒
a · cx + (bc) · y = c. Do fato de a dividir cada termo do lado esquerdo, temos
que a | c.
Lembramos que um natural p > 1 e´ chamado primo se os u´nicos divisores
positivos de p sa˜o 1 e p e um natural n > 1 e´ chamado composto se admite outros
divisores ale´m de 1 e n. Observemos que 1 na˜o e´ nem primo nem composto.
Claramente, se p e´ primo e p ∤ a temos mdc(p, a) = 1. Usando a proposic¸a˜o
anterior e induc¸a˜o temos o seguinte resultado:
Corola´rio 7. Seja p um nu´mero primo e sejam a1, . . . am ∈ Z. Se p | a1 · · · am,
enta˜o p | ai para algum i, 1 ≤ i ≤ m.
O pro´ximo lema resume algumas propriedades u´teis do mdc:
Lema 8. Temos
1. Se p e´ primo, enta˜o mdc(a, p) e´ 1 ou p.
2. Se k e´ um inteiro, enta˜o mdc(a, b) = mdc(a− kb, b).
3. Se a | c, enta˜o mdc(a, b) | mdc(c, b).
4. Se mdc(a, b) = 1, enta˜o mdc(ac, b) = mdc(c, b).
Demonstrac¸a˜o. O primeiro item e´ claro e o segundo e´ apenas uma reformulac¸a˜o
do lema 1. Para provar o terceiro item, observe que mdc(a, b) | a e a | c implicam
que mdc(a, b) | c. Como tambe´m temos mdc(a, b) | b, conclu´ımos que mdc(a, b) |
mdc(b, c) por Bachet-Be´zout. Finalmente, para mostrar o u´ltimo item, note
primeiro que mdc(c, b) | mdc(ac, b) pois mdc(c, b) divide simultaneamente ac e
b. Reciprocamente, para mostrar que mdc(ac, b) | mdc(c, b), podemos escrever
ax+ by = 1 com x, y ∈Z por Bachet-Be´zout. Assim, mdc(ac, b) divide ac · x+
b · cy = c e tambe´m divide b, logo divide mdc(c, b).
Vejamos como podemos usar as propriedades acima para solucionar o se-
guinte
Exemplo 9. Sejam an = 100+n
2 e dn = mdc(an, an+1). Calcular dn para todo
n.
Soluc¸a˜o: Aplicando a propriedade 2 temos que
dn = mdc(100 + n
2, 100 + (n+ 1)2) = mdc(100 + n2, 2n+ 1).
Como 2n+ 1 e´ ı´mpar, mdc(4, 2n+ 1) = 1 e pelas propriedades 4 e 2 temos que
dn = mdc(400 + 4n
2, 2n+ 1)
= mdc(400 + 4n2 − (2n+ 1)(2n− 1), 2n+ 1)
= mdc(401, 2n+ 1).
4
POT 2012 - Teoria dos Nu´meros - Nı´vel 3 - Aula 3 - Carlos Gustavo Moreira1 MDC, MMC E ALGORITMO DE EUCLIDES
Como 401 e´ primo, enta˜o mdc(401, 2n + 1) = 401 se 2n + 1 = 401k (com
k = 2r + 1 inteiro ı´mpar) e mdc(401, 2n+ 1) = 1 caso contra´rio, ou seja,
dn =
{
401 se n = 401r + 200 com r ∈ Z
1 caso contra´rio.
A pro´xima proposic¸a˜o conecta o mdc e o mmc de dois inteiros e pode ser
utilizada, juntamente com o algoritmo de Euclides, para o ca´lculo eficiente do
mmc.
Proposic¸a˜o 10. Sejam a e b dois nu´meros naturais, enta˜o
mdc(a, b) ·mmc(a, b) = a · b.
Demonstrac¸a˜o. Escreva d = mdc(a, b) e a = a1d e b = b1d onde a1, b1 ∈ Z sa˜o
tais que mdc(a1, b1) = 1. Temos mmc(a, b) = al para algum l ∈ Z; ale´m disso,
b | mmc(a, b) ⇐⇒ b1d | a1dl ⇐⇒ b1 | a1l. Como mdc(a1, b1) = 1, isto implica
que b1 | l pela proposic¸a˜o 6. Pela definic¸a˜o de mı´nimo mu´ltiplo comum, temos
que l deve ser o mı´nimo nu´mero divis´ıvel por b1, assim conclu´ımos que l = b1 e
portanto mmc(a, b) = b1a. Logo mdc(a, b) ·mmc(a, b) = d · b1a = a · b.
A demonstrac¸a˜o que demos do teorema de Bachet-Be´zout na˜o mostra como
efetivamente encontrar uma soluc¸a˜o de ax+ by = mdc(a, b). Pore´m, isto pode
ser feito utilizando-se o algoritmo de Euclides, como mostra o exemplo a seguir.
De fato, este exemplo pode servir como ponto de partida para uma segunda
demonstrac¸a˜o do teorema de Bachet-Be´zout (veja os exerc´ıcios).
Exemplo 11. Encontre todos os x, y ∈ Z tais que
1001x+ 109y = mdc(1001, 109).
Soluc¸a˜o: Fazemos as diviso˜es sucessivas para o ca´lculo de
mdc(1001, 109) = 1
utilizando o algoritmo de Euclides (veja o exemplo 2). Em seguida, isolamos os
restos:
20 = 1001 − 109 · 9
9 = 109 − 20 · 5
2 = 20 − 9 · 2
1 = 9 − 2 · 4
Note que a u´ltima divisa˜o permite expressar o mdc 1 como combinac¸a˜o linear
de 9 e 2:
9 · 1− 2 · 4 = 1.
5
POT 2012 - Teoria dos Nu´meros - Nı´vel 3 - Aula 3 - Carlos Gustavo Moreira1 MDC, MMC E ALGORITMO DE EUCLIDES
Mas da penu´ltima divisa˜o, temos que 2 = 20 − 9 · 2, logo substituindo esta
expressa˜o na combinac¸a˜o linear acima, temos
9 − ( 20 − 9 · 2) · 4 = 1 ⇐⇒ 9 · 9− 20 · 4 = 1
e agora expressamos 1 como combinac¸a˜o linear de 20 e 9. Repetindo este
procedimento, eventualmente expressaremos 1 como combinac¸a˜o linear de 1001
e 109. Tomamos o cuidado de lembrar quais sa˜o os “coeficientes” a e b nas
equac¸o˜es ax+ by = mdc(a, b) durante as simplificac¸o˜es. Continuando, obtemos
1 = ( 109 − 20 · 5) · 9− 20 · 4 = 109 · 9− 20 · 49
1 = 109 · 9− ( 1001 − 109 · 9) · 49 = 1001 · (−49) + 109 · 450
Logo uma soluc¸a˜o da equac¸a˜o 1001x + 109y = 1 e´ (x0, y0) = (−49, 450). Para
encontrar as demais, escrevemos o lado direito desta equac¸a˜o utilizando a solu-
c¸a˜o particular que acabamos de encontrar:
1001x+ 109y = 1001x0 + 109y0 ⇐⇒ 1001(x− x0) = −109(y − y0).
Como mdc(1001, 109) = 1 temos pela proposic¸a˜o 6 que 1001 divide y − y0, ou
seja, y − y0 = 1001t para algum t ∈ Z e, portanto, x − x0 = −109t. Assim,
as soluc¸o˜es da equac¸a˜o dada sa˜o todos os pontos da reta 1001x + 109y = 1 da
forma
(x, y) = (x0 − 109t, y0 + 1001t) = (−49, 450) + (−109, 1001) · t
com t ∈ Z.
Em geral, o racioc´ınio do exemplo acima mostra que se mdc(a, b) = 1 e
(x0, y0) e´ uma soluc¸a˜o da equac¸a˜o ax+ by = c, enta˜o todas as soluc¸o˜es inteiras
sa˜o dadas por x = x0 − bk e y = y0 + ak com k ∈ Z.
Exemplo 12. Sejam a, b inteiros positivos com mdc(a, b) = 1. Mostre que para
todo c ∈ Z com c > ab− a− b, a equac¸a˜o ax+ by = c admite soluc¸o˜es inteiras
com x, y ≥ 0.
Soluc¸a˜o: Seja (x0, y0) uma soluc¸a˜o inteira (que existe pelo teorema de Bachet-
Be´zout). Devemos mostrar a existeˆncia de um inteiro k tal que
x = x0 − bk > −1 e y = y0 + ak > −1,
ou seja,
−y0 + 1
a
< k <
x0 + 1
b
.
Mas isto segue do fato de o intervalo (−y0+1
a
, x0+1
b
) ter tamanho maior do que
1:
x0 + 1
b
−
(
−y0 + 1
a
)
=
ax0 + by0 + a+ b
ab
=
c+ a+ b
ab
> 1.
6
POT 2012 - Teoria dos Nu´meros - Nı´vel 3 - Aula 3 - Carlos Gustavo Moreira1 MDC, MMC E ALGORITMO DE EUCLIDES
Problemas Propostos
Problema 13. Mostre que
(a) 215 − 1 e 210 + 1 sa˜o primos entre si.
(b) 232 + 1 e 24 + 1 sa˜o primos entre si.
Problema 14 (IMO1992). Encontrar todos os inteiros a, b, c com 1 < a < b < c
tais que (a− 1)(b− 1)(c− 1) e´ divisor de abc− 1.
Problema 15. Mostre que, se n > 1, enta˜o
n∑
k=1
1
k
= 1 +
1
2
+ · · ·+ 1
n
na˜o e´ um nu´mero inteiro.
Problema 16 (OBM1997). Sejam c ∈ Q, f(x) = x2 + c. Definimos
f0(x) = x, fn+1(x) = f(fn(x)), ∀n ∈ N.
Dizemos que x ∈ R e´ pre´-perio´dico se {fn(x), n ∈ N} e´ finito. Mostre que
{x ∈ Q|x e´ pre´-perio´dico} e´ finito.
Problema 17. Demonstrar que se mdc(a, 2n+1) = 2n e mdc(b, 2n+1) = 2n,
enta˜o mdc(a+ b, 2n+1) = 2n+1.
Problema 18. Demonstrar que se a, b, c, d, m e n sa˜o inteiros tais que ad−bc =
1 e mn 6= 0, enta˜o
mdc(am+ bn, cm+ dn) = mdc(m,n).
Problema 19. Seja Fn o n-e´simo termo da sequeˆncia de Fibonacci.
(a) Encontrar dois nu´meros inteiros a e b tais que 233a + 144b = 1 (observe
que 233 e 144 sa˜o termos consecutivos da sequeˆncia de Fibonacci).
(b) Mostre que mdc(Fn, Fn+1) = 1 para todo n ≥ 0.
(c) Determine xn e yn tais que Fn · xn + Fn+1 · yn = 1.
Problema 20. Sejam a e b dois inteiros positivos e d seu ma´ximo divisor comum.
Demonstrar que existem dois inteiros positivos x e y tais que ax− by = d.
Problema 21. Definimos a sequeˆncia de frac¸o˜es de Farey de ordem n como o
conjunto de frac¸o˜es reduzidas a
b
tais que 0 ≤ a
b
≤ 1, 1 ≤ b ≤ n. Por exemplo a
sequeˆncia de Farey de ordem 3 e´ 01 ,
1
3 ,
1
2 ,
2
3 ,
1
1 .
(a) Demonstrar que se a
b
e c
d
sa˜o dois termos consecutivos de uma sequeˆncia
de Farey, enta˜o cb− ad = 1.
7
POT 2012 - Teoria dos Nu´meros - Nı´vel 3 - Aula 3 - Carlos Gustavo Moreira1 MDC, MMC E ALGORITMO DE EUCLIDES
(b) Demonstrar que se a1
b1
, a2
b2
, a3
b3
sa˜o treˆs termos consecutivos de uma sequeˆncia
de Farey, enta˜o a2
b2
= a1+a3
b1+b3
.
Problema 22. Utilize induc¸a˜o em min{a, b} e o algoritmo de Euclides para
mostrar que ax + by = mdc(a, b) admite soluc¸a˜o com x, y ∈ Z, obtendo uma
nova demonstrac¸a˜o do teorema de Bachet-Be´zout.
Problema 23. Sejam a e b nu´meros inteiros positivos. Considere o conjunto
C = {ax+ by | x, y ∈ N}
Lembre-se de que ja´ mostramos no exemplo 12 que todo nu´mero maior que
ab− a− b pertence a C.
(a) Demonstre que o nu´mero ab− a− b na˜o pertence a C.
(b) Achar a quantidade de nu´meros inteiros positivos que na˜o pertencem a C.
Problema 24 (IMO1984). Dados os inteiros positivos a, b e c, dois a dois primos
entre si, demonstrar que 2abc− ab− bc− ca e´ o maior nu´mero inteiro que na˜o
pode expressar-se na forma xbc+yca+ zab com x, y e z inteiros na˜o negativos.
Problema 25 (IMO1977). Sejam a, b inteiros positivos. Quando dividimos a2+
b2 por a + b, o quociente e´ q e o resto e´ r. Encontrar todos os a, b tais que
q2 + r = 1977.
Problema 26. Demonstrar que mdc(2a − 1, 2b − 1) = 2mdc(a,b) − 1 para todo
a, b ∈ N.
Problema 27. Encontrar todas as func¸o˜es f : N∗ × N∗ −→ Z satisfazendo
simultaneamente as seguintes propriedades
(i) f(a, a) = a.
(ii) f(a, b) = f(b, a).
(iii) Se a > b, enta˜o f(a, b) = a
a−b
f(a− b, b).
Dicas e Soluc¸o˜es
14. Mostrarprimeiro que a ≤ 4 e considerar os poss´ıveis casos.
15. Considere a maior poteˆncia de 2 que e´ menor ou igual a n.
16. Mostre que, dado c racional, existe M > 0 tal que, se |x| > M , enta˜o
|f(x)| > |x|, e existe um inteiro positivo s tal que, se x e´ um racional cujo
denominador, em sua representac¸a˜o reduzida, e´ q > s, enta˜o o denomi-
nador de f(x) (em sua representac¸a˜o reduzida) e´ estritamente maior que
q.
18. Observe que d(am+bn)−b(cm+dn) = m e −c(am+bn)+a(cm+dn) = n.
8
21. Vamos provar que os dois itens valem para todo inteiro positivo n, por
induc¸a˜o. Isto e´ facilmente verifica´vel para n = 1 e n = 2. Considere
agora a sequeˆncia de frac¸o˜es de Farey de ordem n + 1, e seja u
n+1 uma
frac¸a˜o irredut´ıvel em (0, 1). Seus dois vizinhos nessa sequeˆncia de Farey
teˆm denominadores menor que n+1 (as distaˆncias de u
n+1 a`s frac¸o˜es mais
pro´ximas de denominador n sa˜o menores que 1
n
, e sa˜o mu´ltiplos inteiros
de 1
n(n+1) , donde sa˜o menores ou iguais a
1
n+1). Sejam
a
b
e c
d
esses dois
vizinhos, com a
b
< u
n+1 <
c
d
. Temos u
n+1 − ab = vb(n+1) e cd − un+1 = wd(n+1) ,
para certos inteiros positivos v e w, donde v
b(n+1) +
w
d(n+1) =
c
d
− a
b
= 1
bd
(por hipo´tese de induc¸a˜o, pois a
b
e c
d
sa˜o vizinhos na sequeˆncia de Farey
de ordem n), ou seja n+1 = vd+wb ≥ b+d. Como a
b
< a+c
b+d <
c
d
, e a
b
e c
d
sa˜o os vizinhos de u
n+1 , segue que
u
n+1 =
a+c
b+d . Temos (a+ c)b−a(b+d) =
cb − ad = 1 e c(b + d) − (a + c)d = cb − ad = 1, e as duas afirmac¸o˜es
seguem por induc¸a˜o.
24. Se 2abc− ab− bc− ca = xbc+ yca+ zab com x, y e z inteiros positivos,
a divide (x+ 1)bc, donde x ≥ a− 1; analogamente, y ≥ b− 1 e z ≥ c− 1,
donde xbc+ yca+ zab ≥ 3abc− ab− bc− ca > 2abc− ab− bc− ca.
Seja agora k > 2abc− ab− bc− ca inteiro. Enta˜o, como 1 = mdc(bc, a) =
mdc(bc,mdc(ca, ab)), k se escreve como ubc+vca+wab, para certos u, v, w
inteiros. Como ubc+vca+wab = (u− ta)bc+(v−sb)ca+(w+(t+s)c)ab,
para quaisquer t, s inteiros, podemos supor sem perda de generalidade que
0 ≤ u ≤ a− 1 e 0 ≤ v ≤ b− 1. Assim, ubc+ vca ≤ (a− 1)bc+ (b− 1)ac =
2abc− bc− ca, donde wab = k− (ubc+ vca) ≥ k− (2abc− bc− ca) > −ab,
e logo w ≥ 0.
26. Pelo algoritmo de Euclides aplicado aos expoentes, basta mostrar que
mdc(2bq+r − 1, 2b − 1) = mdc(2b − 1, 2r − 1). Mas isto segue novamente
do lema de Euclides, pois 2bq+r − 1 = 2r(2bq − 1) + 2r − 1 e 2bq − 1 =
(2b − 1)(2b(q−1) + 2b(q−2) + · · ·+ 2b + 1) e´ um mu´ltiplo de 2b − 1.
27. Prove por induc¸a˜o em a+ b que f(a, b) = mmc(a, b) para quaisquer a, b ∈
N∗.
Refereˆncias
[1] F. E. Brochero Martinez, C. G. Moreira, N. C. Saldanha, E. Tengan -
Teoria dos Nu´meros - um passeio com primos e outros nu´meros familiares
pelo mundo inteiro, Projeto Euclides, IMPA, 2010.
	mdc, mmc e Algoritmo de Euclides