Задача 78580

Темы:    [ Простые числа и их свойства ] [ Десятичная система счисления ] [ Разложение на множители ] [ Перебор случаев ]

Сложность: 3+ Классы: 8,9,10

Условие

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

Решение

  Если  P = mq,  где q нечётно, то  P^P + 1  делится на  P^m + 1.  Осталось перебрать случаи когда P – степень двойки.
  1¹ + 1 = 2,  2² + 1 = 5,  4⁴ + 1 = 257.  8⁸ + 1 = 2²⁴ + 1  делится на  2⁸ + 1.  16¹⁶ = 2⁶⁴ > 10·2⁶⁰ = 10·1024⁶ > 10¹⁹,  то есть содержит больше 19 цифр.

Ответ

1, 2, 4.

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

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