Veja o exemplo abaixo: Encontrar interios
e
tais que
. Solução:
dividindo por 3 é equivalente a
,
Teremos que resolver o problema na equação
, para isso utilizaremos o algoritimo de euclides de divisão:
note que:
(4 é o resto da divisão de 31 por 27)
( 3 é o resto da divisão de 27 por 4)
(1 é o resto da divisão de 4 por 3 )
Daí,
ou seja,
Logo uma solução inteira seriam
e
Utilize a mesma ideia para encontrar inteiros
e
que satisfaçam as equações:
b)
Teremos que resolver o problema na equação
note que:
Daí,
Utilize a mesma ideia para encontrar inteiros
b)
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:
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
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