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

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

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

Замечания

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

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

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

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

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

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

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

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

Примечания

Литература

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