Para dois inteiros quaisquer a e b, prove que mdc(a, b)=mdc(5 a+3 b, 13 a+8 b).

Passo 1

O enunciado nos pede para mostrar que, para quaisquer inteiros a e b, vale
gcd(a,b) ;=;gcdl(5a+3b,;13a+8br)
O conteúdo aqui é usar propriedades de máximo divisor comum, em particular que
gcd(x,y)=gcd(x,y+kx) e também que, se um número divide dois outros, ele divide qualquer combinação linear desses dois.

Passo 2

Primeiro, vamos ver que qualquer divisor comum de a e b também é divisor de 5a+3b e de 13a+8b. De fato, se dmid a e dmid b, então
dmid 5a, dmid 3b
implica
dmid (5a+3b),
e de modo análogo
dmid 13a, dmid 8b
implica
dmid (13a+8b)
Logo qualquer divisor comum de ,a,b é divisor comum de ,5a+3b,,13a+8b, daí
gcd(a,b);<=;gcd(5a+3b,;13a+8b)

Passo 3

Agora vamos mostrar a desigualdade contrária, ou seja, que qualquer divisor comum de 5a+3b e 13a+8b também divide a e b. Para isso, formamos combinações lineares:
Tomemos
13,(5a+3b);-;5,(13a+8b) ;=; 65a+39b ;-; (65a+40b) ;=;-,b
Logo se um inteiro d divide ambos 5a+3b e 13a+8b, então d divide o lado esquerdo acima e, portanto, dmid b.
De forma semelhante,
8,(5a+3b);-;3,(13a+8b) ;=; 40a+24b ;-;(39a+24b) ;=;a
Logo d também divide a. Assim concluímos que qualquer divisor comum de 5a+3b e 13a+8b divide simultaneamente a e b, o que implica
gcd(5a+3b,;13a+8b);<=;gcd(a,b)

Passo 4

Das desigualdades
gcd(a,b);<=;gcd(5a+3b,;13a+8b) e gcd(5a+3b,;13a+8b);<=;gcd(a,b)
seguimos que
gcd(a,b);=;gcd(5a+3b,;13a+8b)

Resposta

gcd(a,b)=gcd(5a+3b,;13a+8b).

Exercícios de Livros Relacionados