Заметим, что если 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).
(Доказательство: 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).
1) 27^n + 12 ≡ 1^n + 12 ≡ 13 ≡ 0 (mod 13)
2) 17^n + 15 ≡ 1^n + 15 ≡ 16 ≡ 0 (mod 16)
3) 8^n + 15^n - 2 ≡1^n + 1^n - 2 ≡ 0 (mod 7)
4) 3 * 9^n + 7 * 7^(2n) = 3 * 9^n + 7 * 49^n ≡ 3 * (-1)^n + 7 * (-1)^n = (-1)^n * 10 ≡ 0 (mod 10)