O número 15 possui inverso módulo 72 ? Se sim, determine esse inverso. Justifique sua resposta.
Passo 1
O enunciado pergunta se o número
tem inverso multiplicativo módulo
e, se sim, pede que esse inverso seja determinado.
Informações dadas:
Informações dadas:
- O inteiro cujo inverso queremos é
. - O módulo é
.
A pergunta específica é: existetal que ? Se sim, encontrar um tal .
Passo 2
Regra importante (explicada de forma simples): um inteiro
tem inverso multiplicativo módulo
se, e somente se,
.
Por quê? Porque se existe com
Por quê? Porque se existe
então existem inteiros
tais que
Isto é uma combinação linear de
e
que dá
; a existência dessa combinação implica que o maior divisor comum de
e
divide
, logo deve ser
. Inversamente, se
, o algoritmo euclidiano estendido fornece inteiros
com
, de onde
e
é o inverso.
Passo 3
Vamos calcular
pelo algoritmo de Euclides, passo a passo.
Quando o resto vira
, o último resto não nulo é o
. Portanto
Passo 4
Interpretação do resultado:
. Pelo argumento do Passo 2, isso impede a existência de um inteiro
tal que
. Outra forma de ver isso é observar que qualquer combinação linear
é múltipla de
(porque
divide tanto
quanto
), então não pode ser igual a
(que não é múltiplo de
). Logo é impossível obter
como combinação linear de
e
.
Para completar a intuição, da substituição inversa do algoritmo de Euclides obtemos também a representação do
como combinação linear:
e como
,
Isto mostra
. Se houvesse inverso de
, multiplicando essa congruência por ele obteríamos
, o que é impossível porque
não divide
.
Passo 5
Conclusão e justificativa clara: como
, o número
não possui inverso módulo
. (Se
fosse
, aplicaríamos o algoritmo euclidiano estendido para achar o inverso.)
Resposta
Não,
não possui inverso módulo
, pois
.