Question

Помогите решить пожалуйста.

Найти остаток от деления 15^231 на 14

Answer 1

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

Например, из этого следует, что если к числу А прибавить (или отнять) некоторое количество раз число N, то получившееся при этом число будет равно А по модулю N:

$A\equiv A+kN\pmod N$

Одно из следствий полезно использовать в этой задаче:

$A^B\equiv (A+kN)^B\pmod N$

Запишем:

$15^{231}=(1+14)^{231}\equiv1^{231}=1\pmod{14}$

1 при делении на 14 дает остаток 1. Значит и равное ему по модулю 14 число $15^{231}$ дает при делении на 14 остаток 1.

Ответ: 1