Para cada par de inteiros a e b, determine m d c(a, b) e encontre inteiros r e s, tais que m d c(a, b)=r a+s b onde a=312, b=42.

Passo 1

Beleza, vamos resolver esse exercício juntos! A gente precisa encontrar o máximo divisor comum (mdc) entre os números 312 e 42. Além disso, temos que encontrar dois números inteiros, chamados de e , que satisfaçam a equação . Para isso, vamos usar o algoritmo de Euclides para encontrar o mdc e depois o algoritmo estendido de Euclides para achar os valores de e .

Passo 2

Primeiro, vamos encontrar o mdc de 312 e 42 usando o algoritmo de Euclides. Esse método se baseia na ideia de que o mdc de dois números também divide a diferença deles. A gente divide o número maior pelo menor e continua o processo com o divisor e o resto até o resto ser zero. O último resto diferente de zero será o mdc.

Passo 3

Vamos começar dividindo 312 por 42:
312 div 42 = 7 com resto 18
Aqui, mdc(312, 42) = mdc(42, 18) . Agora, substituímos:

Passo 4

Agora, vamos dividir 42 por 18:
42 div 18 = 2 com resto 6
Ou seja, mdc(42, 18) = mdc(18, 6) . Agora, temos:

Passo 5

Em seguida, dividimos 18 por 6:
18 div 6 = 3 com resto 0
Como o resto é zero, o último divisor não nulo é o mdc. Portanto:
mdc(312, 42) = 6

Passo 6

Agora que temos o mdc, vamos encontrar e tais que . Para isso, usamos o algoritmo estendido de Euclides, que além de encontrar o mdc, também nos dá os coeficientes e .

Passo 7

Vamos reverter os passos que fizemos no algoritmo de Euclides para expressar o mdc como combinação linear de 312 e 42.
Começamos com:
6 = 18 - 6 times 2
Mas sabemos que:
6 = 42 - 18 times 2
E substituímos 18 = 312 - 42 times 7 pela expressão encontrada anteriormente:

Passo 8

Substituindo 6 = 42 - (312 - 42 times 7) times 2 na equação de 6 = 42 - 312 times 2 + 42 times 14 :
6 = (-2) times 312 + 15 times 42
Simplificando:

Passo 9

Portanto, encontramos os valores de r = -2 e s = 15 e :

Resposta

O máximo divisor comum de 312 e 42 é 6, e os inteiros que satisfazem são e .

Exercícios relacionados