Ache os inversos de 1951 em Z2431

Passo 1

O enunciado pede para encontrar o elemento xinZ2431 tal que
1951cdot x equiv 1 pmod2431
ou seja, o inverso de 1951 em Z2431. Para isso, vamos usar o algoritmo de Euclides estendido.

Passo 2

Aplicamos o algoritmo de Euclides para 2431 e 1951:
2431 = 1cdot1951 + 480
1951 = 4cdot480 + 31
480 = 15cdot31 + 15
31 = 2cdot15 + 1
15 = 15cdot1 + 0
Como o último resto não nulo é 1, temos gcd(1951,2431)=1 e o inverso existe.

Passo 3

Agora expressamos 1 como combinação linear de 1951 e 2431.
Da penúltima linha,
1 = 31 - 2cdot15
Como 15 = 480 - 15cdot31,
1 = 31 - 2l(480 - 15cdot31r) = 31cdot31 - 2cdot480
Como 31 = 1951 - 4cdot480,
1 = (1951 - 4cdot480)cdot31 - 2cdot480 = 1951cdot31 - (4cdot31 + 2)cdot480 = 1951cdot31 - 126cdot480
Como 480 = 2431 - 1cdot1951,
1 = 1951cdot31 -126l(2431 - 1951r) = 1951cdot(31+126) -126cdot2431 = 1951cdot157 -126cdot2431
Daí segue
1951cdot157 equiv 1 pmod2431

Passo 4

Concluímos que o inverso de 1951 em Z2431 é 157.

Resposta

O inverso de 1951 em Z2431 é 157.

Exercícios relacionados