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

У Вікіпедії є статті про інші значення цього терміна: Теорема Лагранжа (значення).

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

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

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

Доведення

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

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

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