Teorema de Lagrange (teoria dos números)

Na teoria dos números, o teorema de Lagrange é uma afirmação, que leva o nome de Joseph-Louis Lagrange, sobre a frequência com que um polinômio sobre os inteiros pode ser avaliado como um múltiplo de um primo fixo. Mais precisamente, afirma que se $p$ é um número primo e $f(x)\in \mathbb{Z}[x]$ é um polinômio com coeficientes inteiros, então:

• todo coeficiente de $f(x)$ é divisível por $p$, ou
• $f(x)\equiv 0(\mathrm{mod}p)$ tem no máximo $\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{u}f(x)$ soluções incongruentes

onde $\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{u}f(x)$ é o grau do polinômio $f(x)$. As soluções são "incongruentes" se não diferirem por um múltiplo de $p$. Se o módulo não for primo, então é possível que haja mais de $\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{u}f(x)$ soluções.

Uma prova do teorema de Lagrange

As duas idéias principais são as seguintes. Seja $g(x)\in (\mathbb{Z}/p)[x]$ o polinômio obtido de $f(x)$ tomando os coeficientes $modp$. Agora:

1. $f(k)$ é divisível por $p$ se e somente se $g(k)=0$; e
2. $g(x)$ não tem mais do que $\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{u}g(x)$ raízes.

Mais rigorosamente, começando a observar-se que $g(x)=0$ se e somente se cada coeficiente de $f(x)$ é divisível por $p$. Suponha que $g(x)\ne 0$; seu grau é, portanto, bem definido. É fácil ver que $\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{u}g(x)\le \mathrm{g}\mathrm{r}\mathrm{a}\mathrm{u}f(x)$. Para provar (1), primeiro observe que podemos calcular $g(k)$ diretamente, ou seja, conectando (a classe de resíduo de) $k$ e executando aritmética em $\mathbb{Z}/p$, ou reduzindo $f(k)modp$. Logo, $g(k)=0$ se e somente se $f(k)\equiv 0(\mathrm{mod}p)$, ou seja, se e somente se $f(k)$ for divisível por $p$. Para provar (2), observe que $\mathbb{Z}/p$ é um corpo, o que é um fato padrão (uma prova rápida é notar que, como $p$ é primo, $\mathbb{Z}/p$ é um domínio integral finito, portanto, é um corpo). Outro fato padrão é que um polinômio diferente de zero sobre um campo tem no máximo tantas raízes quanto seu grau; isso segue do algoritmo de divisão.

Finalmente, observe-se que duas soluções $f(k_1)\equiv f(k_2)\equiv 0(\mathrm{mod}p)$ são incongruentes se e somente se $k_1\equiv ̸k_2(\mathrm{mod}p)$. Juntando tudo, o número de soluções incongruentes por (1) é o mesmo que o número de raízes de $g(x)$, que por (2) é no máximo $\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{u}g(x)$, que é no máximo $\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{u}f(x)$.