Question

Записать вместо точек наименьшее возможное положительное число
3^30 = ... (mod 31)

Answer 1

Числа равны по модулю, когда одно из них получено путем однократного или многократного прибавления или отнимания этого модуля из другого числа.

$a\equiv b\pmod k\Leftrightarrow a=b+nk,\ n\in\mathbb{Z}$

Выполним преобразования:

$3^{30}=(3^3)^{10}=27^{10}\equiv(27-31)^{10}=(-4)^{10}=4^{10}=4\cdot4^9=4\cdot(4^3)^3=$

$=4\cdot64^3\equiv4\cdot(64-2\cdot31)^3=4\cdot2^3=4\cdot8=32\equiv32-31=1\pmod{31}$

Ответ: 1