Resolva os itens a seguir utilizando o Algoritmo de Euclides ou propriedades de inversos:
(a) Encontre o inverso multiplicativo de [17] módulo 64.
(b) Resolva a congruência linear: 17 x \equiv 12(\bmod 64).

Passo 1

O enunciado pede duas coisas:
  • (a) Encontrar o inverso multiplicativo de [17] no anel \mathbb{Z}_{64}, ou seja, encontrar uma classe [y] tal que
[17]\cdot[y]=[1]\\ (\bmod\\\ 64).
  • (b) Resolver a congruência linear
17x\equiv 12\pmod{64},
isto é, encontrar todas as classes de x módulo 64 que satisfazem a congruência.
Informações relevantes dadas pelo enunciado:
  • O módulo é 64.
  • O coeficiente multiplicador é 17.
  • O termo do lado direito da congruência no item (b) é 12.

Passo 2

Conceitos úteis e plano (explicação didática):
  • Um número a tem inverso multiplicativo módulo m se e só se \gcd(a,m)=1. Se a \gcd for 1, existe u,v\in\mathbb{Z} tais que
u a + v m = 1,
pela identidade de Bézout. Reduzindo essa igualdade módulo m obtemos u a \equiv 1\pmod{m}, ou seja, [u] é o inverso de [a] em \mathbb{Z}_m.
  • O Algoritmo de Euclides estendido permite calcular esses u e v encontrando a \gcd e, no processo de retro-substituição, os coeficientes de Bézout.
  • Se o inverso de 17 existir, a solução da congruência 17x\equiv 12\pmod{64} é única modulo 64 e dada por
x \equiv 17^{-1}\cdot 12 \pmod{64}.
Vou aplicar o Algoritmo de Euclides para \gcd(17,64) e depois obter os coeficientes de Bézout.

Passo 3

Aplicando o Algoritmo de Euclides (mostrando cada divisão com resto):
64 = 17\cdot 3 + 13.
17 = 13\cdot 1 + 4.
13 = 4\cdot 3 + 1.
4 = 1\cdot 4 + 0.
Como o último resto não nulo é 1, temos \gcd(17,64)=1. Portanto o inverso de [17] módulo 64 existe.

Passo 4

Agora encontramos os coeficientes de Bézout por retro-substituição (mostrar passo a passo):
Partimos de
1 = 13 - 4\cdot 3.
Substituímos 4 pela expressão obtida na segunda linha:
4 = 17 - 13\cdot 1,
então
1 = 13 - (17-13)\cdot 3 = 13 -3\cdot 17 +3\cdot 13 = 4\cdot 13 - 3\cdot 17.
Agora substituímos 13 pela expressão da primeira linha:
13 = 64 - 17\cdot 3,
portanto
1 = 4\cdot(64 - 17\cdot 3) - 3\cdot 17.
Desenvolvendo:
1 = 4\cdot 64 - 12\cdot 17 - 3\cdot 17 = 4\cdot 64 - 15\cdot 17.
Assim obtemos a identidade de Bézout
(-15)\cdot 17 + 4\cdot 64 = 1.
Reduzindo módulo 64
(-15)\cdot 17 \equiv 1 \pmod{64},
logo -15 é um inverso de 17 módulo 64.

Passo 5

Passamos para representante positivo do inverso: -15 \equiv 64-15 = 49\pmod{64}. Portanto
17\cdot 49 \equiv 1 \pmod{64}.
Fazendo a checagem rápida: 17\cdot 49 = 833 e 833 = 64\cdot 13 + 1, confirmando o resto 1.
Logo o inverso multiplicativo de [17] em \mathbb{Z}_{64} é [49].

Passo 6

Resolver a congruência 17x\equiv 12\pmod{64}.
Como já temos 17^{-1}\equiv 49\pmod{64}, multiplicamos ambos os lados da congruência por 49:
x \equiv 49\cdot 12 \pmod{64}.
Calculamos 49\cdot 12 = 588. Agora reduzimos módulo 64:
588 = 64\cdot 9 + 12,
portanto 588 \equiv 12\pmod{64}. Assim
x \equiv 12 \pmod{64}.
Observação didática: como \gcd(17,64)=1, a solução é única na classe dos resíduos módulo 64; todas as soluções inteiras são x = 12 + 64k com k\in\mathbb{Z}.

Resposta

(a) [17]^{-1}\equiv [49]\pmod{64}
(b) x\equiv 12\pmod{64}

Exercícios relacionados