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

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

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

Если ${\displaystyle p}$ — простое число, ${\displaystyle f(x)}$ — многочлен степени ${\displaystyle n}$ с целочисленными коэффициентами, то[1]: либо все коэффициенты ${\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 решения[2]: ${\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} ,}$ но для многочленов над любой другой областью целостности[3].

Примечания

1. Виноградов, 1952, с. 60.
2. Дэвенпорт, 1965, с. 55.
3. Математическая энциклопедия, 1982, с. 174.

Литература

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