Заметим, что если a и b дают такие же остатки при делении на n, что и x, y, то ab даёт такой же остаток при делении на n, что и xy. (Доказательство: a = np + x, b = nq + y для некоторых целых p, q. Тогда ab = (np + x)(nq + y) = n(npq + qx + py) + xy. Первое слагаемое делится на n, значит, ab даёт такой же остаток, что и xy). Из этого следует, что если у a и x одинаковые остатки, то и у любых их натуральных степеней a^m, x^m будут одинаковые остатки. Дальше для сокращения записей будет использоваться такое обозначение: "если a ≡ x(mod n), то a^k ≡ x^k (mod n).
ответ внизу на фото
Объяснение: