Арифметика полиномов, заданных над конечным полем

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

,

где неотрицательное целое , меньшее , называется остатком (от деления на), называется частным от деления, - делимым, а - делителем.

Поскольку в кольце полиномов определена операция умножения, то, поступая аналогично, можно ввести операцию деления полиномов с остатком. Однако, для полиномов сравнение в терминах «больше-меньше» невозможно, поэтому для получения остатка сравниваются степени полиномов. Возьмем полином и представим произвольный полином как

.

В данном соотношении, возможном для любых и , назовем полиномы , , и делимым, делителем, частным и остатком соответственно. Операция деления полиномов известна под названием алгоритма Евклида. Определение частного и остатка от деления полиномов осуществляется «в столбик», как и при делении целых чисел.

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

,

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