Ensino SuperiorAlgoritmo estendido de Euclides Tópico resolvido

Poste aqui problemas sobre assuntos estudados no Ensino Superior (exceto os cobrados em concursos públicos e escolas militares).

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
ChunLi
iniciante
Mensagens: 9
Registrado em: Sex 01 Jun, 2018 00:00
Última visita: 09-11-21
Out 2018 04 14:32

Algoritmo estendido de Euclides

Mensagem não lida por ChunLi »

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




Avatar do usuário
Cardoso1979
6 - Doutor
Mensagens: 4008
Registrado em: Sex 05 Jan, 2018 19:45
Última visita: 04-04-23
Localização: Teresina- PI
Out 2018 11 23:14

Re: Algoritmo estendido de Euclides

Mensagem não lida por 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!




Responder

Voltar para “Ensino Superior”