Faça o que se pede
Calcule o inverso multiplicativo de 13 em Z29

Passo 1

Vamos calcular o inverso de 13 em Z29, ou seja, achar um x tal que 13 cdot x equiv 1 pmod29. Para isso a gente vai usar aritmética modular e o algoritmo de Euclides estendido.

Passo 2

Começamos aplicando o algoritmo de Euclides em 29 e 13 para encontrar o mdc. As divisões sucessivas são:
29 = 2 cdot 13 + 3
13 = 4 cdot 3 + 1
3 = 3 cdot 1 + 0
Logo gcd(29,13) = 1.

Passo 3

Agora fazemos a retro-substituição para expressar 1 como combinação linear de 29 e 13. Da segunda divisão vem 1 = 13 - 4 cdot 3. E da primeira divisão vem 3 = 29 - 2 cdot 13. Substituindo em 1 = 13 - 4 cdot 3 obtemos:
1 = 13 - 4 cdot (29 - 2 cdot 13) = 13 - 4 cdot 29 + 8 cdot 13 = 9 cdot 13 - 4 cdot 29

Passo 4

O coeficiente que multiplica 13 nessa combinação é 9, o que significa que em Z29 temos 13 cdot 9 equiv 1 pmod29. Portanto, o inverso multiplicativo de 13 em Z29 é 9.

Resposta

9

Exercícios relacionados