Question

Tìm số dư của phép chia sau: 1991¹⁹⁹¹ chia cho 31

Answer 1

Lời giải:
Áp dụng định lý Fermat nhỏ:

$1991^{30}\equiv 1\pmod {31}$

$\Rightarrow 1991^{1991}=(1991^{30})^{66}.1991^{11}\equiv 1^{66}.1991^{11}\equiv 1991^{11}\pmod {31}$

$1991^2\equiv 18\pmod {31}$

$\Rightarrow 1991^{11}=(1991^2)^5.1991\equiv 18^5.1991\pmod {31}$

$18^3\equiv 4\pmod {31}$
$\Rightarrow 18^5.1991\equiv 4.18^2.1991\equiv 20\pmod {31}$

$\Rightarrow 1991^{1991}\equiv 20\pmod {31}$

Hay $1991^{1991}$ chia 31 dư 20.