Задача
NT-B1-M12-P022 Вариант 5. Простое в делителе
#22
★★★★☆ Уровень 4 из 5
Найдите все простые \(p\), для которых \(p\mid2^p+1\).
Для нечётного простого используйте малую теорему Ферма.
При \(p=2\) имеем \(2^2+1=5\), не делится на \(2\). Пусть \(p\) нечётное. По малой теореме Ферма \(2^p\equiv2\pmod p\). Тогда \(2^p+1\equiv3\pmod p\). Значит нужно \(p\mid3\), откуда \(p=3\). Проверка: \(3\mid9\).
Короткая задача с сильным выбором метода.