Задача
NT-B2-M03-P009 Простые из \(2^p+1\)
#9
★★★☆☆ Уровень 3 из 5
Найдите все простые \(p\), для которых \(p\mid2^p+1\).
Для нечётного \(p\) используйте \(2^p\equiv2\pmod p\).
При \(p=2\) делимости нет. Если \(p\) нечётно, то по малой теореме Ферма \(2^p\equiv2\pmod p\). Тогда \(2^p+1\equiv3\pmod p\), значит \(p\mid3\), откуда \(p=3\). Проверка: \(2^3+1=9\) делится на \(3\).
Задача выглядит степенной, но решается коротким циклом по простому модулю.