Если  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.