Question

qual resto da divisão 5^63 por 29

Answer 1

Resposta:

28

Explicação passo-a-passo:

O Pequeno Teorema de Fermat nos garante que:

Se $p$ é primo e $a$ é um inteiro não divisível por $p$ então $a^{p-1}\equiv1\pmod{p}$

Como $29$ é primo e $5$ não é divisível por $29$, temos que $5^{28}\equiv1\pmod{29}$

Logo, $5^{63}=(5^{28})^{2}\cdot5^{7}\equiv1^{28}\cdot5^7\equiv1\cdot5^7\equiv5^7\pmod{29}$

Veja que $5^2\equiv25\equiv(-4)\pmod{29}$, então:

$5^7\equiv(5^2)^3\cdot5\equiv(-4)^3\cdot5\equiv(-64)\cdot5\equiv(-6)\cdot5\equiv(-30)\pmod{29}$

$5^7\equiv(-1)\equiv(29-1)\equiv28\pmod{29}$

Portanto, $5^{63}\equiv28\pmod{29}$

O resto é $28$