Задача
Найдите наименьшее натуральное число n, для которого выполнено следующее условие: если число p – простое и n делится на p – 1, то n делится на p.
Решение
Пусть n удовлетворяет этому условию. Поскольку n делится на 1 = 2 – 1, оно должно делиться на 2, но тогда оно делится на 3 = 2 + 1, на
7 = 2·3 + 1 и на 43 = 2·3·7 + 1. Поэтому n должно делиться на 1806 = 2·3·7·43. Следовательно, минимальное n (если оно существует) не меньше 1806.
С другой стороны, для 1806 условие задачи выполнено. Вот все делители числа 1806: 1, 2, 3. 6, 7, 14, 21, 42, 43, 86, 129, 301, 1806. Увеличив теперь каждый из них на единицу, получим: 2, 3, 4. 7, 8, 15, 22, 43, 44, 87, 130, 302, 1807.
Остаётся отобрать все простые числа из второго набора и убедиться, что они входят в первый набор (1807 – не простое, оно делится на 13).
Ответ
n = 1806.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь