Question

Determine o resto da divisão de 2^101 + 898^6 por 7.

Answer 1

$898 = 2\cdot(449)$

$2^{101} +898^6 = 2^6\cdot\left(2^{95}+449^6\right)$

$2^3 \equiv 1 \mod(7) \\~\\2^{93} \equiv 1 \mod(7) \\~\\2^{95} \equiv 4 \mod(7)$

Pelo pequeno teorema de Fermat:

$449^{7-1} \equiv 1 \mod(7) \\~\\449^{6} \equiv 1 \mod(7)$

Temos que:

$2^6\cdot\left(2^{95}+449^6\right) \equiv \left( 2^3\right)^2 \cdot\left(2^{95}+449^6\right) \mod(7) \\~\\2^6\cdot\left(2^{95}+449^6\right) \equiv 1^2 \cdot\left(2^{95}+449^6\right) \mod(7) \\~\\2^6\cdot\left(2^{95}+449^6\right) \equiv 2^{95}+449^6\right \mod(7) \\~\\2^6\cdot\left(2^{95}+449^6\right) \equiv 4+1\right \mod(7) \\~\\2^6\cdot\left(2^{95}+449^6\right) \equiv 5\right \mod(7)$

A divisão dá resto 5.