Para cada par a e b de números inteiros abaixo, calcule o máximo divisor comum e determine alpha e beta de modo que mdc(a, b)=alpha cdot a+beta cdot b.
(1) 14 e 35

Passo 1

Beleza, o enunciado quer que a gente calcule o máximo divisor comum (mdc) de dois inteiros gcd(a,b) ;=;alpha,a;+;beta,b e e ainda ache dois coeficientes e tais que
Isso faz parte de Teoria dos Números, em especial do Algoritmo de Euclides e da Identidade de Bézout. Para resolver vamos precisar:
  1. aplicar o Algoritmo de Euclides (divisões sucessivas);
  2. usar a Identidade de Bézout (voltar nas divisões pra achar e ).

Passo 2

Vamos executar o Algoritmo de Euclides em 35 = 14 times 2 + 7 e 14 = 7 times 2 + 0 :
  1. Dividimos o maior pelo menor:
  2. Agora dividimos o último divisor (14) pelo resto (7):
Como o resto ficou zero, o último resto não-nulo, que é , é o nosso .

Passo 3

Agora, para achar 35 = 14 times 2 + 7 Longrightarrow 7 = 35 - 14 times 2 e , usamos a Identidade de Bézout e voltamos na primeira divisão:
Isso já é uma combinação linear de em função de e .

Resposta

7 = (-2)times 14 + 1 times 35 , com e , pois

Exercícios relacionados