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

В силу малой теоремы Ферма, мы имеем в , следовательно, степень каждого многочлена не превосходит . Далее будем считать, что , иначе рассматриваемые мночогочлены являются линейным, то есть всегда приводимы.

Количество многочленов степень которых равна ровно

Это так, ведь существует ровно возможных коэффициентов перед и ровно возможных вариантов на каждый из остальных мономов. Таким образом, достаточно найти количество многочленов, приводимых над указанным полем.

Существует ровно два типа указанных многочленов:

Многочлен раскладывается в виде произведения трех линейных многочленов. Количество таких многочленов равно

Поскольку существует ровно коэффициент перед старшей степенью, а множество корней суть множество из трех элементов, каждый из которых лежит в

Многочлен является суть произведением линейного многочлена, а так же многочлена второй степени, неприводимого над Аналогично рассуждениям первого пункта, получим, что количество приводимых многочленов второй степени равно

то есть неприводимых

следовательно общее количество исходных многочленов равно

Наконец, количество приводимых многочленов равно

что после преобразований имеет вид