1. найдите остаток при делении 73^37 на 7 2. найдите остаток при делении числа 19^20+21 на 55 3. Найдите такое наибольшее натуральное n, меньше 2015, что число 3 n, его квадрат и куб дают одинаковые остатки при делении на 7.

Математическая запись m ≡ n (mod q) означает, что остаток при делении m на q равен n.

73³⁷ = (10 * 7 + 3) ³⁷ ≡ 3³⁷ (mod 7).

По малой теореме Ферма для простого числа P выполняется:

a^{P - 1} ≡ 1 (mod P).

Для простого числа 7 имеем:

a⁶ ≡ 1 (mod 7).

73³⁷ ≡ 3³⁷ (mod 7) ≡ 3 * (3⁶) ⁶ (mod 7) ≡ 3 (mod 7).

Следовательно, остаток при делении 73³⁷ на 7 равен 3.

По теореме Эйлера

a^φ⁽^b) ≡ 1 (mod b), где φ (b) функция Эйлера.

φ (55) = φ (5) φ (11) = 4 * 10 = 40.

a⁴⁰ ≡ 1 (mod 55),

Преобразуем 19²⁰:

19²⁰ ≡ (19 - 55) ²⁰ ≡ ( - 36) ²⁰ ≡ ( - 6) ⁴⁰ ≡ 6⁴⁰ ≡ 1 (mod 55).

19²⁰ + 21 ≡ (1 + 21) (mod 55) ≡ 22 (mod 55).

Таким образом остаток исходного выражения при делении его на 55 равен 22.

Запишем требуемые условия:

3 n ≡ n² ≡ n³ (mod 7);

Из второго и третьего сравнения вытекает:

n³ ≡ n² (mod 7);

n₁ ≡ 1 (mod 7);

n₂ ≡ 0 (mod 7);

Из второго и первого сравнения вытекает:

3 n ≡ n² (mod 7);

Решение n₁ ≡ 1 (mod 7) приводит к противоречию.

Остаётся решение n₂ ≡ 0 (mod 7);

Это значит, искомое число делится не 7.

N_max = 7 n_max < 2015;

n_max < 2015 / 7 = 287 + 6 / 287;

n_max = 287.

N_max = 2009.