Задача
NT-B2-M03-P016 Простой делитель \(3^4+1\)
#16
★★★★☆ Уровень 4 из 5
Найдите все простые \(p\), для которых \(p\mid3^4+1\).
Сначала вычислите число, затем объясните ограничение через порядок.
\(3^4+1=82=2\cdot41\). Значит, возможны \(p=2\) и \(p=41\). Для понимания метода: если \(p\ne2\) делит \(3^4+1\), то \(3^4\equiv-1\), значит порядок \(3\) по модулю \(p\) равен \(8\), и потому \(8\mid p-1\). Из делителей \(82\) это выполняется только для \(41\).
Задача показывает, как порядок объясняет факторизацию.