Veja o exemplo abaixo: Encontrar interios x e y tais que 93 x+81 y=3. Solução:
93 x+81 y=3 dividindo por 3 é equivalente a 31 x+27 y=1,
Teremos que resolver o problema na equação 31 x+27 y=1, para isso utilizaremos o algoritimo de euclides de divisão:
note que:
31=27 * 1+4 Rightarrow 4=31-27 (4 é o resto da divisão de 31 por 27)
27=4 * 6+3 Rightarrow 3=27-4 * 6 ( 3 é o resto da divisão de 27 por 4)
4=3 * 1+1 Rightarrow 1=4-3 (1 é o resto da divisão de 4 por 3 )
Daí, 1=4-3
=(31 & -27)-(27-4 * 6 & =31-27-27+(31-27) * 6 & =31-27-27+31 * 6-27 * 6 & =7 * 31-8 * 27
ou seja,
37 * 7+27 *(-8)=1
Logo uma solução inteira seriam x=7 e y=-8
Utilize a mesma ideia para encontrar inteiros x e y que satisfaçam as equações:
b) 71 x-50 y=1

Passo 1

O enunciado pede para encontrar inteiros x e y tais que 71 x − 50 y = 1 usando o algoritmo de Euclides estendido, que nos dá a combinação linear de 71 e 50.

Passo 2

Reescrevemos a equação na forma padrão de combinação linear: 71 x + (−50) y = 1, e constatamos que gcd(71,50)=1, ou seja, há solução.

Passo 3

Aplicamos o algoritmo de Euclides de divisão para 71 e 50:
71 = 50 cdot 1 + 21
50 = 21 cdot 2 + 8
21 = 8 cdot 2 + 5
8 = 5 cdot 1 + 3
5 = 3 cdot 1 + 2
3 = 2 cdot 1 + 1

Passo 4

Agora fazemos a retro-substituição para escrever 1 como combinação de 71 e 50. Começamos com 1 = 3 − 2 e usamos as definições:
2 = 5 − 3 ⇒ 1 = 3 − (5 − 3) = 2·3 − 5
3 = 8 − 5 ⇒ 1 = 2·(8 − 5) − 5 = 2·8 − 3·5
5 = 21 − 2·8 ⇒ 1 = 2·8 − 3·(21 − 2·8) = 8·8 − 3·21
8 = 50 − 2·21 ⇒ 1 = 8·(50 − 2·21) − 3·21 = 8·50 − 19·21
21 = 71 − 50 ⇒ 1 = 8·50 − 19·(71 − 50) = (8+19)·50 − 19·71 = 27·50 − 19·71

Resposta

x = -19, y = -27

Exercícios relacionados