Привет!
Разберём четверговую задачу — найдём остаток от деления числа 300³⁰⁰⁰–1 на 1001.

Для решения нам пригодятся три факта:
1) Малая теорема Ферма:
Если p — простое число и a — целое число, которое не делится на p, то aᵖ⁻¹-1 нацело делится на p.
2) Если два числа сравнимы по модулю третьего, то их натуральные степени также сравнимы. То есть если a ≡ b (mod c), то для любого натурального k верно, что aᵏ ≡ bᵏ (mod c).
3) Если a ≡ b (mod c), n ≡ m (mod c), то a*n ≡ b*m (mod c).

Решение

Число 1001 — составное, раскладывается на множители как 7*11*13. Эти множители простые — то, что нужно для применения теоремы.

Посмотрим, что с остатками от деления 300³⁰⁰⁰ на каждый из множителей.

Возьмём p=7. Теперь представим число 300³⁰⁰⁰ в таком виде, чтобы в степени было p-1=6. Для этого разложим степень на множители:
300³⁰⁰⁰ = (300⁵⁰⁰)⁶.
К такой записи уже можно применить теорему: p=7, a=300⁵⁰⁰,
и значит (300⁵⁰⁰)⁶ ≡ 1 (mod 7). 

Теперь возьмём p равным следующему множителю. Для p=11 имеем:
300³⁰⁰⁰ = (300³⁰⁰)¹⁰ ≡ 1 (mod 11).
Для p=13 будет:
300³⁰⁰⁰ = (300²⁵⁰)¹² ≡ 1 (mod 13).

Получается, что число 300³⁰⁰⁰ сравнимо с 1 по всем трём модулям: и по 7, и по 11, и по 13.
Отсюда 300³⁰⁰⁰ ≡ 1 (mod 7*11*13). Такое верно только при если модули были взаимно просты: у нас 7, 11 и 13 как раз такие.
И тогда 300³⁰⁰⁰ – 1  ≡ 0 (mod 1001), то есть это число делится на 1001 нацело!

Ответ: 0.

Если у вас остались вопросы по решению, задавайте их в комментариях.