Базовый аппарат сравнений по модулю

Заметим, что так как

Тогда, как легко видеть,

где и Пусть Тогда наш многочлен сравним с 3, и никак не может делиться на

При имеем

то есть наш многочлен делится на нужный.

При наш многочлен сравним с

то есть в этом случае наш многочлен снова делится на нужный. Таким образом, необходимо и достаточно, чтобы не делилось на 3.