Первое решение. Обозначим то есть степени рассматриваемых многочленов равны

Лемма. Существует единственный многочлен степени (со старшим коэффициентам ) такой, что степень полученного многочлена будет меньше, чем

Доказательство. Запишем наш многочлен как

Обозначим и это — многочлены степени со старшим коэффициентом

В многочлене коэффициент участвует лишь в членах степени, не большей Значит, для любого коэффициент при в многочлене зависит лишь от коэффициентов при С другой стороны, коэффициент при этой же степени в есть где зависит лишь от коэффициентов при Если мы хотим, чтобы степень была меньше, чем то эти коэффициенты должны быть равны; это равенство даёт однозначное выражение через (в частности, находится единственным образом). Значит, из этих равенств по очереди находятся все коэффициенты многочлена

Теперь достаточно предъявить многочлен такой, что степень окажется меньше, чем — по лемме, он единственный, и он и даст минимальную степень Положим Тогда многочлен

имеет степень всего лишь Значит, наименьшая возможная степень и есть

Второе решение. Используем те же обозначение и что и в первом решении. Мы будем считать, что

(впоследствии мы увидим, что это возможно; поэтому для многочлена минимальной степени так считать можно).

Предположим, что в многочлене есть одночлен степени, не кратной пусть — такой одночлен наибольшей степени. Тогда коэффициент многочлена при равен что противоречит неравенству.

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

то есть где

при этом а предположение означает, что

Рассмотрим многочлен тогда Аналогично рассуждению выше, предположим, что то есть в многочлене есть одночлены, кроме пусть — такой одночлен наибольшей степени. Тогда в многочлене есть одночлен что противоречит неравенству Таким образом, а тогда и Мы приходим к тому же примеру, что и в первом решении (и видим, что в этом случае степень действительно удовлетворяет (*)).