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

У теорії чисел, теорема Лагранжа — це твердження про те, як часто многочлен над цілими числами може набувати значень кратних до фіксованого простого числа. Точніше, вона стверджує, що якщо p є простим числом і ${\displaystyle \textstyle f(x)\in \mathbb {Z} [x]}$ це многочлен з цілими коефіцієнтами, тоді або:

• кожний коефіцієнт f(x) ділиться на p, або
• ${\displaystyle f(x)\equiv _{p}0}$ має щонайбільше deg f(x) неконгруентних розв'язків.

Розв'язки «неконгруентні», якщо вони відрізняються не на число кратне p. Якщо модуль не простий, тоді можливо мати більше ніж deg f(x) розв'язків.

Дві ключові ідеї такі. Нехай ${\displaystyle \textstyle g(x)\in (\mathbb {Z} /p\mathbb {Z} )[x]}$ буде многочленом отриманим з ${\displaystyle f(x)}$ через ділення коефіцієнтів ${\displaystyle \mod p}$. Тепер (i) ${\displaystyle f(k)}$ ділиться на ${\displaystyle p}$ тоді і тільки тоді, коли ${\displaystyle g(k)=0}$; (ii) ${\displaystyle g(k)}$ має коренів не більше ніж його степінь.

Більш строго, почнемо з зауваження, що ${\displaystyle g(x)=0}$ тоді і тільки тоді, коли кожний коефіцієнт ${\displaystyle f(x)}$ ділиться на ${\displaystyle p}$. Припустимо, що ${\displaystyle g(x)}$ не 0; отже, його степінь чітко визначена. Легко побачити, що ${\displaystyle \textstyle \deg g(x)\leq \deg f(x)}$. Для доведення (i), спершу зауважимо, що ми можемо обчислити ${\displaystyle g(k)}$ або прямо, тобто підставляючи (клас лишків) ${\displaystyle k}$ і виконуючи арифметику в ${\displaystyle \textstyle \mathbb {Z} /p\mathbb {Z} }$, або через обчислення ${\displaystyle f(k)\mod p}$. Звідси ${\displaystyle g(k)=0}$ тоді і тільки тоді, коли ${\displaystyle f(k)\equiv _{p}0}$, тобто, тоді і тільки тоді, коли ${\displaystyle f(k)}$ ділиться на ${\displaystyle p}$. Щоб довести (ii), зауважимо, що ${\displaystyle \textstyle \mathbb {Z} /p\mathbb {Z} }$ є полем. Іншим фактом є те, що ненульовий многочлен над полем має коренів не більше ніж його степінь.

Насамкінець, зауважимо, що два розв'язки ${\displaystyle \textstyle f(k_{1}),f(k_{2})\equiv _{p}0}$ є неконгруентними тоді і тільки тоді, коли ${\displaystyle \textstyle k_{1}\not \equiv _{p}k_{2}}$. Складаючи це все до купи: з (i) кількість неконгруентних розв'язків дорівнює кількості коренів ${\displaystyle g(x)}$, яке по (ii) є не більша ніж ${\displaystyle \deg g(x)}$, яка, в свою чергу, не більша ніж ${\displaystyle \deg f(x)}$.

• LeVeque, William J. (2002) [1956]. Topics in Number Theory, Volumes I and II. New York: Dover Publications. с. 42. ISBN 978-0-486-42539-9. Zbl 1009.11001.
• Tattersall, James J. (2005). Elementary Number Theory in Nine Chapters (вид. 2nd). Cambridge University Press. с. 198. ISBN 0-521-85014-2. Zbl 1071.11002.