ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73678
Темы:    [ Делимость чисел. Общие свойства ]
[ Простые числа и их свойства ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 3+
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

Найдите наименьшее натуральное число 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.

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1972
выпуск
Номер 5
Задача
Номер М143

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .