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

• Если все коэффициенты ${\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].

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