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

В теории чисел теорема Лагранжа — это утверждение, названное в честь Жозефа-Луи Лагранжа, о том, как часто многочлен над целыми числами может быть кратен фиксированному простому числу p . Точнее, она утверждает, что для всех целочисленных многочленов выполняется одно из двух: ${\displaystyle \textstyle f\in \mathbb {Z} [x]}$

• каждый коэффициент f делится на p , или
• ${\displaystyle p\mid f(x)}$имеет не более deg f решений в {1, 2, ..., p } ,

где deg f — степень f .​

Это можно сформулировать с помощью классов конгруэнтности следующим образом: для всех многочленов с p простым числом, либо: ${\displaystyle \textstyle f\in (\mathbb {Z} /p\mathbb {Z} )[x]}$

• каждый коэффициент f равен нулю, или
• ${\displaystyle f(x)=0}$имеет не более deg f решений в . ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

Если p не является простым числом, то потенциально может быть больше, чем deg f ( x ) решений. Рассмотрим, например, p=8 и многочлен f(x)=x ² -1 , где 1, 3, 5, 7 — все решения.

Доказательство

Пусть будет целым многочленом, и запишем g ∈ ( Z / p Z )[ x ] многочлен, полученный путем взятия его коэффициентов mod p . Тогда для всех целых чисел x , ${\displaystyle \textstyle f\in \mathbb {Z} [x]}$

${\displaystyle f(x)\equiv 0{\pmod {p}}\quad \Longleftrightarrow \quad g(x)\equiv 0{\pmod {p}}}$.

Более того, по основным правилам модульной арифметики,

${\displaystyle f(x)\equiv 0{\pmod {p}}\quad \Longleftrightarrow \quad f(x{\bmod {p}})\equiv 0{\pmod {p}}\quad \Longleftrightarrow \quad g(x{\bmod {p}})\equiv 0{\pmod {p}}}$.

Таким образом, обе версии теоремы (над Z и над Z / p Z ) эквивалентны. Докажем вторую версию индукцией по степени в случае, когда не все коэффициенты f равны нулю.

Если deg f = 0, то f не имеет корней и утверждение верно.

Если deg f ≥ 1 без корней, то утверждение также тривиально верно.

В противном случае deg f ≥ 1 и f имеет корень . Тот факт, что Z / p Z является полем, позволяет применить алгоритм деления к f и многочлену x − k (степени 1 ), что приводит к существованию многочлена (степени ниже, чем у f ) и константы (степени ниже, чем 1 ) таких, что ${\displaystyle k\in \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle \textstyle g\in (\mathbb {Z} /p\mathbb {Z} )[x]}$ ${\displaystyle \textstyle r\in \mathbb {Z} /p\mathbb {Z} }$

${\displaystyle f(x)=g(x)(x-k)+r.}$

Оценка при x = k дает r = 0. [ ^1] Остальные корни f тогда также являются корнями g , которые по свойству индукции имеют число, не превышающее deg g ≤ deg f − 1. Это доказывает результат.

Обобщение

Пусть p ( X ) — многочлен над областью целостности R со степенью n > 0. Тогда уравнение многочлена p ( x ) = 0 имеет не более n = deg( p ( X )) корней в R . ^[2]

Ссылки

1. Факторная теорема#Доказательство_3
2. "Многочлены и кольца Глава 3: Целостные области и поля" (PDF) .Теорема 1.7.

• LeVeque, William J. (2002) [1956]. Темы теории чисел, тома I и II. Нью-Йорк: Dover Publications. стр. 42. ISBN 978-0-486-42539-9. Збл  1009.11001.
• Таттерсолл, Джеймс Дж. (2005). Элементарная теория чисел в девяти главах (2-е изд.). Cambridge University Press . стр. 198. ISBN 0-521-85014-2. Збл  1071.11002.