Calcular mdc ( 5 a+7 b, 2 a+3 b ), sabendo que mdc(a, b)=3.

Passo 1

O enunciado pede para calcular gcd(5a+7b,,2a+3b) dado que gcd(a,b)=3. O conteúdo necessário é o Algoritmo de Euclides, que diz que para inteiros x,y vale
gcd(x,y)=gcd(x - k,y,;y)
para qualquer inteiro k.

Passo 2

Aplicamos o passo do Euclides a
gcd(5a+7b,,2a+3b) usando k=2:
gcd(5a+7b,,2a+3b) =gcdl((5a+7b)-2(2a+3b),;2a+3br) =gcd(a+b,;2a+3b)

Passo 3

Agora calculamos
gcd(2a+3b,;a+b) de modo semelhante, subtraindo 2(a+b) de 2a+3b:
gcd(2a+3b,;a+b) =gcdl((2a+3b)-2(a+b),;a+br) =gcd(b,;a+b)

Passo 4

Usamos a propriedade gcd(x+y,y)=gcd(x,y), com x=a e y=b:
gcd(b,;a+b)=gcd(a,b)

Passo 5

Como gcd(a,b)=3 (dado no enunciado), concluímos que
gcd(5a+7b,,2a+3b)=3

Resposta

3

Exercícios de Livros Relacionados