Question

Qual o resto na divisão 2^327 por 1463?

Gabarito: 1338

Answer 1

Pequeno Teorema de Fermat: sejam $p$ um primo e $a$ um número que não é divisível por $p$. Então $a^{p-1}\equiv1\pmod{p}$

Note que $1463=7\times11\times19$. Desse modo, vamos calcular o resto da divisão de $2^{327}$ por $7$, por $11$ e por $19$.

Divisão por 7

Pelo Pequeno Teorema de Fermat, $2^{6}\equiv1\pmod{7}$

Como $327=6\times54+3$, então $2^{327}=(2^6)^{54}\cdot2^3$

Assim, $2^{327}\equiv(2^6)^{54}\cdot2^{3}\equiv1^{54}\cdot8\equiv8\equiv1\pmod{7}$

Logo, $2^{327}$ deixa resto $1$ na divisão por $7$.

Divisão por 11

Analogamente, pelo Pequeno Teorema de Fermat, $2^{10}\equiv1\pmod{11}$

Note que $327=10\times32+7$ e $2^{327}=(2^{10})^{32}\cdot2^7$

Desse modo, $2^{327}\equiv(2^{10})^{32}\cdot2^{7}\equiv1^{32}\cdot128\equiv1\cdot7\equiv7\pmod{11}$

Divisão por 19

Pelo Pequeno Teorema de Fermat, $2^{18}\equiv1\pmod{19}$

Como $327=18\times18+3$, segue que $2^{327}=(2^{18})^{18}\cdot2^{3}$

Assim, $2^{327}\equiv(2^{18})^{18}\cdot2^{3}\equiv1^{18}\cdot8\equiv1\cdot8\equiv8\pmod{19}$

Com isso, temos:

$\begin{cases}2^{327}\equiv1\pmod{7}\\2^{327}\equiv7\pmod{11}\\2^{327}\equiv8\pmod{19}\end{cases}$

Como $2^{327}$ deixa resto $1$ na divisão por $7$, podemos escrever $2^{327}=7a+1~(i)$, com $a\in\mathbb{N}$.

Analogamente, temos que $2^{327}=11b+7~(ii)$ e $2^{327}=19c+8~(iii)$, com $b,c\in\mathbb{N}$.

Igualando $(i)$ e $(ii)$:

$7a+1=11b+7~\longrightarrow~7a-11b=6$

Observe que $7\cdot5-11\cdot3=2$. Multiplicando os dois lados dessa igualdade por $3$:

$7\cdot5\cdot3-11\cdot3\cdot3=2\cdot3~\longrightarrow~7\cdot15-11\cdot9=6$

Assim, uma solução particular é $(a_0,b_0)=(15,9)$. As soluções gerais são da forma:

$a=15-11t$
$b=9-7t$, sendo $t$ um inteiro

Substituindo em $(i)$:

$2^{327}=7a+1~\longrightarrow~2^{327}=7\cdot(15-11t)+1$

$2^{327}=105-77t+1~\longrightarrow~2^{327}=106-77t~~(iv)$

Isso significa que $2^{327}\equiv106\equiv29\pmod{77}$

Igualando $(iii)$ e $(iv)$:

$19c+8=106-77t~\longrightarrow~19c+77t=98$

Observe que $77-19\cdot4=1$. Multiplicando os dois lados dessa igualdade por $98$, obtemos:

$77\cdot98-19\cdot4\cdot98=1\cdot98~\longrightarrow~77\cdot98-19\cdot392=98$

$77\cdot98+19\cdot(-392)=98~\longrightarrow~19\cdot(-392)+77\cdot98=98$

Então, uma solução particular é $(c_0,t_0)=(-392,98)$. As soluções gerais são da forma:

$c=-392+77k$
$t=98-19k$, sendo $k$ um inteiro

Substituindo em $(iv)$:

$2^{327}=106-77t~\longrightarrow~2^{327}=106-77\cdot(98-19k)$

$2^{327}=106-7546+1463k~\longrightarrow~2^{327}=1463k-7440$

Logo, podemos afirmar que:

$2^{327}\equiv-7440\equiv-125\equiv1463-125\equiv1338\pmod{1463}$

Portanto, o resto da divisão de $2^{327}$ por $1463$ é $1338$