Теорема Лагранжа (теория чисел)

В теории чисел теорема Лагранжа — это утверждение, названное в честь Жозефа-Луи Лагранжа, о том, при каких условиях значение многочлена с целочисленными коэффициентами может быть кратным фиксированному простому числу.

Формулировка

Если $p$ — простое число, $f(x)$ — многочлен степени $n$ с целочисленными коэффициентами, то: либо все коэффициенты $f(x)$ кратны $p;$ либо сравнение $f(x)\equiv 0{\pmod {p}}$ имеет не более $n$ решений.

Замечания

• Если все коэффициенты $f(x)$ кратны $p,$ то любое значение $x$ является решением приведённого сравнения.
• Простота модуля $p$ существенна, для составного модуля теорема, вообще говоря, неверна. Например, сравнение: $x^{2}-1\equiv 0{\pmod {8}}$ имеет 4 решения: $x\equiv 1;3;5;7{\pmod {8}}.$

Доказательство теоремы Лагранжа

Пусть $g(x)$ — многочлен над кольцом $\mathbb {Z} /p$, полученный из $f(x)$ заменой каждого коэффициента соответствующим классом вычетов по модулю $p.$

Лемма 1. $f(a)$ делится на $p$ тогда и только тогда, когда $g(a)=0.$ Доказательство. Если $f(a)$ делится на $p,$ то и $g(a)$, по построению, попадает в тот же класс вычетов, что и $p,$ то есть в нулевой класс. И обратно, если $g(a)=0,$ то вычисление $f(a)$ даёт результат из класса вычетов, содержащего $p,$ то есть делится на $p.$ ■

Лемма 2. У многочлена $g(x),$ если он не нулевой многочлен, не может быть более $n$ корней. Доказательство. Поскольку $p$ — простое число, $\mathbb {Z} /p$ является полем, а ненулевой многочлен степени $n$ в любом поле имеет не более $n$ корней, потому что каждый корень $r$ добавляет в разложение многочлена одночлен $(x-r).$ ■

Доказательство теоремы. Если $g(x)$ — нулевой многочлен, то это, согласно его построению, означает, что все коэффициенты $f(x)$ кратны $p.$ В противном случае из первой леммы следует, что число несравнимых по модулю $n$ решений уравнения $f(x)\equiv 0{\pmod {p}}$ совпадает с число корней многочлена $g(x).$ которое, по второй лемме, не превышает $n.$ ■

Вариации и обобщения

Теорема Лагранжа справедлива не только для многочленов над кольцом целых чисел $\mathbb {Z} ,$ но для многочленов над любой другой областью целостности.

Литература

• Виноградов И. М. Основы теории чисел. — М.—Л.: ГИТТЛ, 1952. — С. 60—65. — 180 с.
• Дэвенпорт Г. Высшая арифметика / под ред. Ю. В. Линник, пер. Б. З. Мороз — М.: Наука, 1965. — С. 54—55. — 176 с.
• Лагранжа теорема // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 3. — С. 174.