Ensino Superior ⇒ Algoritmo estendido de Euclides Tópico resolvido

[ChunLi]

Como posso achar a inversa de a (mod b) pelo algoritmo estendido de Euclides??
por exemplo: qual a inversa de 15 (mod 4) ?

[Cardoso1979]

Observe

Uma solução:

Temos que mdc ( 15 , 4 ) = 1, ou seja , 15x ≡ 1 ( mod 4 ).Vamos usar o algoritmo de Euclides para escrever 1 em termos de 15 e 4.

15|__4 → 15 = 3.4 + 3
3......3


4|__3 → 4 = 1.3 + 1
1....1


3|__1 → 3 = 1.3 + 0
0....3


Então;

1 = 1.4 - 1.3
1 = 1.4 - 1.( 15 - 3.4 )
1 = 4.4 - 1.15

A conclusão é que 1 = 4.4 - 1.15. Obtemos, então, a congruência : - 1.15 ≡ 1 ( mod 4 ). Isso mostra que - 1 é um inverso de 15 ( mod 4 )

Portanto, a inversa de 15 ( mod 4 ) é - 1.


Bons estudos!