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

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

Условие

Найдите все простые числа вида  PP + 1  (P – натуральное), содержащие не более 19 цифр.


Решение

  Если  P = mq,  где q нечётно, то  PP + 1  делится на  Pm + 1.  Осталось перебрать случаи когда P – степень двойки.
  11 + 1 = 2,  2² + 1 = 5,  44 + 1 = 257.  88 + 1 = 224 + 1  делится на  28 + 1.  1616 = 264 > 10·260 = 10·10246 > 1019,  то есть содержит больше 19 цифр.


Ответ

1, 2, 4.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 28
Год 1965
вариант
1
Класс 11
Тур 2
задача
Номер 1

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

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