Русская Википедия:Теорема Лагранжа (теория чисел)
Шаблон:Другие значения В теории чисел теорема Лагранжа — это утверждение, названное в честь Жозефа-Луи Лагранжа, о том, при каких условиях значение многочлена с целочисленными коэффициентами может быть кратным фиксированному простому числу.
Формулировка
Шаблон:Рамка Если <math>p</math> — простое число, <math>f(x)</math> — многочлен степени <math>n</math> с целочисленными коэффициентами, тоШаблон:Sfn:
- либо все коэффициенты <math>f(x)</math> кратны <math>p;</math>
- либо сравнение <math>f(x) \equiv 0 \pmod p</math> имеет не более <math>n</math> решений.
|}
Замечания
- Если все коэффициенты <math>f(x)</math> кратны <math>p,</math> то любое значение <math>x</math> является решением приведённого сравнения.
- Простота модуля <math>p</math> существенна, для составного модуля теорема, вообще говоря, неверна. Например, сравнение: <math>x^2-1 \equiv 0 \pmod {8}</math> имеет 4 решенияШаблон:Sfn: <math>x \equiv 1; 3; 5; 7 \pmod 8.</math>
Доказательство теоремы Лагранжа
Пусть <math>g(x)</math> — многочлен над кольцом <math>\mathbb{Z}/p</math>, полученный из <math>f(x)</math> заменой каждого коэффициента соответствующим классом вычетов по модулю <math>p.</math>
Лемма 1. <math>f(a)</math> делится на <math>p</math> тогда и только тогда, когда <math>g(a) = 0.</math> Доказательство. Если <math>f(a)</math> делится на <math>p,</math> то и <math>g(a)</math>, по построению, попадает в тот же класс вычетов, что и <math>p,</math> то есть в нулевой класс. И обратно, если <math>g(a) = 0,</math> то вычисление <math>f(a)</math> даёт результат из класса вычетов, содержащего <math>p,</math> то есть делится на <math>p.</math> Шаблон:ЧТД
Лемма 2. У многочлена <math>g(x),</math> если он не нулевой многочлен, не может быть более <math>n</math> корней. Доказательство. Поскольку <math>p</math> — простое число, <math>\mathbb{Z}/p</math> является полем, а ненулевой многочлен степени <math>n</math> в любом поле имеет не более <math>n</math> корней, потому что каждый корень <math>r</math> добавляет в разложение многочлена одночлен <math>(x-r).</math> Шаблон:ЧТД
Доказательство теоремы. Если <math>g(x)</math> — нулевой многочлен, то это, согласно его построению, означает, что все коэффициенты <math>f(x)</math> кратны <math>p.</math> В противном случае из первой леммы следует, что число несравнимых по модулю <math>n</math> решений уравнения <math>f(x) \equiv 0 \pmod p</math> совпадает с число корней многочлена <math>g(x).</math> которое, по второй лемме, не превышает <math>n.</math> Шаблон:ЧТД
Вариации и обобщения
Теорема Лагранжа справедлива не только для многочленов над кольцом целых чисел <math>\mathbb{Z},</math> но для многочленов над любой другой областью целостностиШаблон:Sfn.
Примечания
Литература
