Question

Найти остаток от деления 101^88+17×48^101+3 на 31

Answer 1

Если к числу $A$ прибавить (или отнять) некоторое количество раз число $N$, то полученное число будет равно числу $A$ по модулю $N$:

$A=A+kN\pmod{N},\ k\in\mathbb{Z}$

Числа, равные по модулю $N$, дают при делении на $N$ равные остатки.

Преобразуем первое слагаемое:

$101^{88}=(8+3\cdot31)^{88}\equiv8^{88}=(8^2)^{44}=64^{44}=(2+2\cdot31)^{44}\equiv2^{44}=2^4\cdot2^{40}=$

$=16\cdot(2^5)^8=16\cdot32^8=16\cdot(1+31)^8\equiv16\cdot1^8=16\cdot1=16\pmod{31}$

Преобразуем второе слагаемое:

$17\cdot48^{101}=17\cdot(17+31)^{101}\equiv17\cdot17^{101}=17^{102}=(17^2)^{51}=289^{51}=$

$=289^{51}=(10+9\cdot31)^{51}\equiv10^{51}=(10^3)^{17}=1000^{17}=(8+32\cdot31)^{17}\equiv$

$\equiv8^{17}=(2^3)^{17}=2^{51}=2\cdot2^{50}=2\cdot(2^5)^{10}=2\cdot32^{10}=2\cdot(1+31)^{10}\equiv$

$\equiv2\cdot1^{10}=2\cdot1=2\pmod{31}$

Тогда, исходная сумма перепишется в виде:

$101^{88}+17\cdot48^{101}+3\equiv16+2+3=21\pmod{31}$

Так как число 21 при делении на 31 дает остаток 21, то и исходное число, равное ему по модулю 31, также при делении на 31 дает остаток 21.

Ответ: 21