Задача
NT-B2-M01-P014 Кубический ограничитель
#14
★★★★☆ Уровень 4 из 5
Найдите все простые \(p\), для которых \( \gcd(p^2+1,p^3+1)>1 \).
Исключите \(p^3\) с помощью \(p(p^2+1)\).
Пусть \(d\) - общий делитель. Тогда \(d\mid p^3+1-p(p^2+1)=1-p\). Значит, \(d\mid p-1\). По модулю \(p-1\) имеем \(p\equiv1\), поэтому \(p^2+1\equiv2\). Следовательно, общий делитель может делить только \(2\). Если \(p=2\), то получаем \(\gcd(5,9)=1\). Если \(p\) нечётно, то \(p^2+1\) и \(p^3+1\) чётны, значит НОД равен \(2\). Ответ: все нечётные простые \(p\).
Здесь важно, что \(p\) именно простое: финальная проверка идёт по чётности.