Question

Determine o resto na divisão de 37¹³ por 17.

Answer 1

Resposta:  O resto da divisão é 12.

Explicação passo a passo:

Determinar o resto da divisão de 37¹³ por 17.

Efetuando a divisão euclidiana de 37 por 17, temos

     $37=34+3=17\cdot 2+3\\\\ \Longrightarrow\quad 37\equiv 3\quad\mathrm{(mod~}17)\\\\ \Longrightarrow\quad 37^n\equiv 3^n\quad\mathrm{(mod~}17)\qquad\mathrm{(i)}$

para todo n ∈ ℕ.

Como mdc(3, 17) = 1, é possível encontrar um representante x da classe inversa de 3, módulo 17, ou seja

     $3x\equiv 1\quad\mathrm{(mod~}17)\\\\ \Longrightarrow\quad 3x=17y+1$

para algum y ∈ ℕ.

Podemos resolver essa equação usando o algoritmo de Euclides, mas como 3 é um número primo pequeno, conseguimos encontrar uma solução substituindo alguns valores para y.

Perceba que $17\cdot 1+1=18$ é múltiplo de 3. Então, obtemos uma solução para y = 1:

     $\Longrightarrow\quad 3x=18\\\\ \Longleftrightarrow\quad x=6$

Logo, 6 é um representante da classe inversa de 3, módulo 17, pois

     $3\cdot 6\equiv 1\quad\mathrm{(mod~}17)\qquad\mathrm{(ii)}$

Como 17 é primo, e 17 não divide 3, podemos usar o Pequeno Teorema de Fermat:

     $3^{17-1}\equiv 1\quad\mathrm{(mod~}17)\\\\ \Longleftrightarrow\quad 3^{16}\equiv 1\quad\mathrm{(mod~}17)\\\\ \Longleftrightarrow\quad 3^{13}\cdot 3^3\equiv 1\quad\mathrm{(mod~}17)$

Multiplicando os dois lados por $6^3,$ temos

     $\Longrightarrow\quad 3^{13}\cdot 3^3\cdot 6^3\equiv 1\cdot 6^3\quad\mathrm{(mod~}17)\\\\ \Longleftrightarrow\quad 3^{13}\cdot (3\cdot 6)^3\equiv 6^3\quad\mathrm{(mod~}17)\\\\ \Longleftrightarrow\quad 3^{13}\cdot (18)^3\equiv 6^3\quad\mathrm{(mod~}17)\\\\ \overset{\mathrm{(ii)}}{\Longleftrightarrow}\quad 3^{13}\cdot 1^3\equiv 6^3\quad\mathrm{(mod~}17)\\\\ \Longleftrightarrow\quad 3^{13}\equiv 6^3\quad\mathrm{(mod~}17)\\\\ \Longleftrightarrow\quad 3^{13}\equiv 6^2\cdot 6\quad\mathrm{(mod~}17)\qquad\mathrm{(iii)}$

Mas

    $6^2=36=34+2=17\cdot 2+2\\\\ \Longrightarrow\quad 6^2\equiv 2\quad\mathrm{(mod~}17)\qquad\mathrm{(iv)}$

Logo, a congruência (iii) fica

     $\overset{\mathrm{(iv)}}{\Longleftrightarrow}\quad 3^{13}\equiv 2\cdot 6\quad\mathrm{(mod~}17)\\\\ \Longleftrightarrow\quad 3^{13}\equiv 12\quad\mathrm{(mod~}17)\\\\ \overset{\mathrm{(i)}}{\Longleftrightarrow}\quad 37^{13}\equiv 12\quad\mathrm{(mod~}17)\qquad\checkmark$

O resto da divisão é 12.

Dúvidas? Comente.

Bons estudos! :-)