Представление функций полиномами
Определение. Полиномом по модулю k от переменных x
, …, x
называет-ся выражение вида: a
+ a· X + … + a
· X, где коэффициенты a
принадлежат
множеству E
, а X – либо некоторая переменная, либо произведение переменных, причем
сумма и произведения берутся по модулю k.
Говорят, что некоторая функция из P представима полиномом по модулю k, если существует
полином по модулю k, равный этой функции.
Теорема. Представление каждой функции
из P полиномом по модулю k возможно в том и только в том случае, когда k
простое число. Если k – составное число, то в P имеются функции, представимые
полиномами по модулю k , и функции не представимые полиномами.
Например, константы 0, 1, …, k-1 и “полиномиальные “ функции
x, x
, x ·
y, x + y
представимы полиномами, а функции j(x),
max (x,y),
min (x,y),
x ч y