Teorema di Lagrange (teoria dei numeri)
# Teorema di Lagrange (teoria dei numeri)

In teoria dei numeri, il teorema di Lagrange è un enunciato che prende il nome da Joseph-Louis Lagrange su quanto frequentemente un polinomio sugli interi può assumere valore uguale a un multiplo di un numero primo fissato. Più precisamente, esso afferma che se $p$ è un numero primo e $f(x)\in \mathbb {Z} [x]$ è un polinomio a coefficienti interi, allora:

* ogni coefficiente di $f(x)$ è divisibile per $p$, oppure
* $f(x)\equiv 0{\bmod {p}}$ ha, al massimo, grado di $f(x)$ soluzioni incongruenti.

Le soluzioni sono "incongruenti" se non differiscono di un multiplo di $p$. Se il modulo non è primo, allora è possibile che ci siano più di grado di $f(x)$ soluzioni.

## Una dimostrazione del teorema di Lagrange

Le due idee chiave sono le seguenti. Sia $g(x)\in (\mathbb {Z} /p\mathbb {Z} )[x]$ il polinomio ottenuto da $f(x)$ prendendo i coefficienti $\mod p$. Ora (i) $f(k)$ è divisibile per $p$ se e solo se $g(k)=0$; (ii) $g(k)$ non ha più radici del suo grado.

Più rigorosamente, cominciamo ad osservare che $g(x)=0$ se e solo se ogni coefficiente di $f(x)$ è divisibile per $p$. Supponiamo che $g(x)$ non sia 0; il suo grado è, quindi, ben definito. È facile vedere che $\textstyle {\text{grado di }}g(x)\leq {\text{grado di }}f(x)$. Per dimostrare (i), prima osserviamo che possiamo calcolare $g(k)$ o direttamente, cioè inserendo (la classe residua di) $k$ ed eseguendo operazioni aritmetiche in $\textstyle \mathbb {Z} /p\mathbb {Z}$, o riducendo $f(k)\mod p$. Quindi $g(k)=0$ se e solo se $f(k)\equiv 0{\bmod {p}}$, cioè se e solo se $f(k)$ è divisibile per $p$. Per dimostrare (ii), osserviamo che $\mathbb {Z} /p\mathbb {Z}$ è un campo, il che è un fatto normale; una dimostrazione rapida consiste nell'osservare che, poiché $p$ è primo, $\mathbb {Z} /p\mathbb {Z}$ è un dominio d'integrità finito, quindi è un campo. Un altro fatto normale è che un polinomio non-nullo su un campo ha al massimo tante radici quanto il suo grado; ciò segue dall'algoritmo di divisione.

Infine, osserviamo che due soluzioni $f(k_{1}),f(k_{2})\equiv 0{\bmod {p}}$ sono incongruenti se e solo se $k_{1}\not \equiv k_{2}{\bmod {p}}$. Mettendo tutto insieme: il numero di soluzioni incongruenti, per via di (i), è lo stesso del numero di radici di $g(x)$, che, per via di (ii), è al massimo ${\text{grado di }}g(x)$, che è al massimo ${\text{grado di }}f(x)$.

