[obm-l] Re: [obm-l] Congruência modulo n

[Carlos Victor]

Olá  Kleber ,

Usando o teorema de Euler temos que  12^20 é congruo a 1 mod (25). Elevando
a 657 , temos que  12^13140 é congruo 1 mod(25).Logo , basta ver a divisão
de 12^5 por 25 , ok ?.

Teorema de Euler :Sejam a,m naturais com m  1 e mdc(a,m) =1. Então  a^(fi
de m) é congruo a 1 modm .

Abraços

Carlos  Victor

Em 16 de dezembro de 2011 13:49, Kleber Bastos klebe...@gmail.comescreveu:


 Queria saber qual o método para calcular:
 Dado que 12^13145(mod 25), calcular o resto da divisão de 12^13145 por 25.

 Desde já agradeço a ajuda.
 Abraços, Kleber.

[obm-l] Re: [obm-l] Congruência modulo n

[Bernardo Freitas Paulo da Costa]

2011/12/16 Kleber Bastos klebe...@gmail.com:

 Queria saber qual o método para calcular:
 Dado que 12^13145(mod 25), calcular o resto da divisão de 12^13145 por 25.
Como os números são pequenos, é mais fácil ir na força bruta. Ou seja:
12^2 = 144 = -6 mod 25
12^4 = (-6)^2 = 36 = 11 mod 25
12^8 = 11^2 = 121 = -4 mod 25
12^10 = 12^2 * 12^8 = (-6)*(-4) = 24 = -1 mod 25
Logo 12^20 = 1 mod 25

Assim, 12^13145 = 12^a mod 25 se a = 13145 mod 25, ou seja, a = 5.
12^5 = 12*11 = 132 = 7 mod 25

Obs: sabemos que 12 é primo com 25, portanto 12^phi(25) = 1 mod 25.
Aqui, phi é a função de Euler, e vale 5*4 = 20, o que é coerente com o
que a gente fez. Poderíamos ter usado direto phi(25) = 20, e ter
continuado a partir do Assim,  do segundo parágrafo, mas o fato é
que (como eu disse) não precisa disso nesse caso.

Abraços,
-- 
Bernardo Freitas Paulo da Costa

=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=