Многочлены над конечным полем

Если то задача сводится к делимости на что возможно только лишь при

Пусть Введём переменную и рассмотрим делимость на Заметим, что

Теперь задача сводится к рассмотрению случаев.

Если чётное, то тогда Заметим, что Если то делимость верна при любом Иначе должно делиться на то есть — cтепень Однако это выражение делится на лишь при Если подставить получим

Это может быть степенью тройки лишь при откуда и

Если нечётное, то получим сравнение с Опять же, если делимость верна для любого В противном случае кратно Заметим, что Значит, снова должно быть степенью тройки, что возможно лишь при Отсюда получаем, что