4 Докажи, что эта сумма делится на 2, 3 и 5. Подсказка: Малая теорема ферма
6 Вырази число 11…11 в виде суммы степеней числа 10 и попробуй как-то свернуть эту сумму
7 Так же как и с предыдущим пунктом
- Смелое предположение найти p \in \mathbb{P}:
239 \equiv 30 (mod p)
и попробовать доказать что
239^{30} + 30^{239} \equiv 0 (mod p)
А можно с помощью малой теоремы ферма:
- Найти p такое, что 239^{30} \equiv 1 \mod{p}
- Посчитать 30 \text{ mod } p. окажется что это очень интересное число
- На этом этапе уже все должно быть понятно)
Можете 7 и 2 подробнее расписать?
Это число можно выразить как
Воспользуемся тем, что 10^p\equiv 10\ (mod\ p) и получим, что это число
Осталось доказать, что \frac{10^{p-1}-1}{10-1}\equiv1\ (mod\ p). Это несложно доказать, рассмотрев p=3 (потому что 3|9) и p>3.
По малой теореме ферма если p простое, то \forall a \in \mathbb{Z}
В случае 239^{30} \equiv 1 \mod{p}, можно предположить что p-1=30. Тогда p=31. 31 – это простое число, значит к нему применима МТФ и 239^{30} \equiv 1 \mod{p}.
Теперь, что такое 30 \text{ mod } 31?
Заметим, что 30 \equiv -1 \mod{31}
Тогда
Поскольку 239 нечетное число
Если a \equiv b \mod{p} и c \equiv d \mod{p}, то a + c \equiv b + d \mod{p}. Тогда
Это значит, что p | 239^{30} + 30^{239}. Очевидно, что 31 \neq 239^{30} + 30^{239}, значит у числа 239^{30} + 30^{239} есть делитель отличный от 1 и его самого. Значит это составное. QED
У Вас кажется ошибка:
(1 + 10 + ... + 10^{p-1}) = \dfrac{10^p-1}{10-1}
Тогда, как раз-таки и последует, что
\frac{10^p-1}{10-1} \equiv 1 \pmod {p}, ведь 10^p \equiv 10 \pmod {p}
А, да, ты прав