Teorema Chinês do Resto
3 participantes
PiR2 :: Matemática :: Álgebra
Página 1 de 1
Teorema Chinês do Resto
por brasileiro312 Qui 28 Dez 2017, 19:20
Como eu faço para calcular o inverso multiplicativo modular de um número?
brasileiro312- Jedi
- Mensagens : 304
Data de inscrição : 28/02/2017
Idade : 21
Localização : Rio de Janeiro, Rio de Janeiro, Brasil
biologiaéchato- Mestre Jedi
- Mensagens : 664
Data de inscrição : 19/09/2017
Idade : 23
Localização : São Bonifácio - SC
Re: Teorema Chinês do Resto
por brasileiro312 Qui 28 Dez 2017, 19:31
É um valor que você multiplica por um certo número para que ele seja congruente a 1 módulo m
brasileiro312- Jedi
- Mensagens : 304
Data de inscrição : 28/02/2017
Idade : 21
Localização : Rio de Janeiro, Rio de Janeiro, Brasil
Re: Teorema Chinês do Resto
por superaks Qui 28 Dez 2017, 21:33
Isso você acha na força bruta. Porém você pode achar mais rápido fazendo:
A classe inversa de a mod m existe se, e somente se, mdc(m, a) = 1.
Se a' é classe inversa de a mod m, temos que
a . a' Ξ 1 (mod m)
Ao invés de verificar todas as classes mod m, poderia usar outra congruência para achar mais rápido
Pegue um k tal que
a | mk + 1
E faça
a' = (mk + 1)/a
Sai mais rápido você testar valores para k do que para a'. E talvez a solução da congruência:
mk + 1 Ξ 0 (mod a)
Seja mais trivial
A classe inversa de a mod m existe se, e somente se, mdc(m, a) = 1.
Se a' é classe inversa de a mod m, temos que
a . a' Ξ 1 (mod m)
Ao invés de verificar todas as classes mod m, poderia usar outra congruência para achar mais rápido
Pegue um k tal que
a | mk + 1
E faça
a' = (mk + 1)/a
Sai mais rápido você testar valores para k do que para a'. E talvez a solução da congruência:
mk + 1 Ξ 0 (mod a)
Seja mais trivial
superaks- Mestre Jedi
- Mensagens : 525
Data de inscrição : 27/06/2016
Idade : 22
Localização : São Paulo, Guarulhos, Brasil
Tópicos semelhantes» Teorema do Resto Chinês
» Teorema chinês do resto, congruência
» Teorema do resto
» Teorema do resto
» (EEAr) Raízes de Polinômios + Teorema de D'Alembert ( Teorema do Resto )
» Teorema chinês do resto, congruência
» Teorema do resto
» Teorema do resto
» (EEAr) Raízes de Polinômios + Teorema de D'Alembert ( Teorema do Resto )
PiR2 :: Matemática :: Álgebra
Página 1 de 1
Permissões neste sub-fórum
Não podes responder a tópicos|
|
|
