Document 2

Prévia do material em texto

No nosso caso, temos: 
𝑎=133 
P= 13 
 
Como 13 é um número primo e 133 não é divisível por 13 (pois 133 = 13x10+3 , ou seja, 
133≡3(mod13), podemos aplicar o teorema. 
Pelo PTF, sabemos que 𝑎𝑝−1= 1 (mod p) Substituindo 𝑎 por 133 e 𝑝 por 13, temos: 
𝑎𝑝−1 = 13313−1 = 13312 (mod 13) 
objetivo é encontrar o resto da divisão de 13367por 13. Podemos reescrever o expoente 
67 em termos de 12 para usar a congruência encontrada no passo anterior. 
Dividimos o expoente 67 por 12 teremos que: 
67= 5x12+7. 
Utilizando este resultado e reescrevendo a expressão original teremos: 
13367 = 133(5×12+7) = (13312)5  × 1337 
Após aplicarmos a propriedade de congruência á expressão reescrita teremos o então 
sabendo que 13312 = 1 (mod 13) e 133=3 (mod 13) Calculado no início do exercício, 
substituímos na expressão modular: 
13367 =  (13312)5 × 1337   (mod 13) 
13367 =  (1)5 × 1337   (mod 13) 
13367 =  1 × 1337    
13367 = 1337    
 
Calculando 1337   (mod 13), lembrando que utilizaremos a potência menor e 
lembrando que 133=3 (mod 13) teremos: 1337  = 37   
Agora calculando a potência de 3 módulo 13 teremos: 
31 =  3 (mod 13) 
32 =  9 (mod 13) 
33 =  27 (mod 13) ( 27= 2x13+1) 
Reescrevendo a potência de 37 = 3
(2×3+1)= (33)
2
×31 
Aplicando mais uma vez a congruência temos: 
37 = (3
3)
2
×31 (mod 13) 
37 = (1)
2×3 (mod 13) 
37  = 1 × 3 (mod 13) 
37  = 3 (mod 13) 
 
Concluindo que 13367 =  3.