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

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

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

Шаблон:Рамка Если $p$ — простое число, $f(x)$ — многочлен степени $n$ с целочисленными коэффициентами, тоШаблон:Sfn:

• либо все коэффициенты $f(x)$ кратны $p;$
• либо сравнение $f(x)\equiv 0(\mathrm{mod}p)$ имеет не более $n$ решений.

|}

Замечания

• Если все коэффициенты $f(x)$ кратны $p,$ то любое значение $x$ является решением приведённого сравнения.
• Простота модуля $p$ существенна, для составного модуля теорема, вообще говоря, неверна. Например, сравнение: $x^2-1\equiv 0(\mathrm{mod}8)$ имеет 4 решенияШаблон:Sfn: $x\equiv 1;3;5;7(\mathrm{mod}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(\mathrm{mod}p)$ совпадает с число корней многочлена $g(x).$ которое, по второй лемме, не превышает $n.$ Шаблон:ЧТД

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

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

Литература

• Шаблон:Книга
• Шаблон:Source
• Шаблон:Книга