Задача
NT-B1-M07-P021 Простые делители \(2^p+1\)
#21
★★★★☆ Уровень 4 из 5
Найдите все простые \(p\), для которых \(p\mid 2^p+1\).
Для нечетного \(p\) примените форму \(2^p\equiv2\pmod p\).
При \(p=2\): \(2^2+1=5\), не делится на \(2\). Пусть \(p\) нечетное простое. По Ферма в форме \(a^p\equiv a\pmod p\) имеем \(2^p\equiv2\pmod p\). Тогда \(2^p+1\equiv3\pmod p\). Чтобы \(p\mid2^p+1\), нужно \(p\mid3\), то есть \(p=3\). Проверка: \(2^3+1=9\), делится на \(3\). Ответ: \(p=3\).
Олимпиадный ход: показатель сам равен простому модулю.