Question

Qual o resto da divisão de 3^1000 por 101?

Answer 1

O Pequeno Teorema de Fermat diz o seguinte:

$\bullet\;\;$ Se $p$ é um número primo, e $a$ é um inteiro qualquer, tal que $\mathrm{mdc}\left(a,\,p \right )=1$ (isto é, $a$ não é múltiplo de $p$), então

$a^{p-1}$ deixa resto $1$ na divisão por $p$.

ou seja,

$a^{p-1}\equiv 1\left(\mathrm{mod\;}p \right )$


Sabendo que $101$ é primo e $\mathrm{mdc}\left(3,\,101 \right )=1$, podemos aplicar o teorema acima para

$a=3,\;\;p=101$

ou seja

$3^{101-1}$ deixa resto $1$ na divisão por $101$:

$3^{100}\equiv 1\left(\mathrm{mod\;}101 \right )$


Podemos aplicar agora esta propriedade válida para congruências modulares:

Se $a \equiv b\left(\mathrm{mod\;}m \right )$, então

$a^{k} \equiv b^{k}\left(\mathrm{mod\;}m \right )$

onde $k$ é um número natural.


Sendo assim

$3^{100}\equiv 1\left(\mathrm{mod\;}101 \right )\\ \\ \left(3^{100} \right )^{10}\equiv 1^{10}\left(\mathrm{mod\;}101 \right )\\ \\ 3^{100\cdot 10}\equiv 1\left(\mathrm{mod\;}101 \right )\\ \\ \boxed{ \begin{array}{c} 3^{1\,000}\equiv 1\left(\mathrm{mod\;}101 \right ) \end{array} }$


Logo, a divisão de $3^{1\,000}$ por $101$ deixa resto $1$.