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 $\textstyle 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{\pmod {p}}$ tem no máximo $\mathrm {grau} \ f(x)$ soluções incongruentes

onde $\mathrm {grau} \ 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 {grau} \ 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 ${\bmod {p}}$. 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 {grau} \ 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)\neq 0$; seu grau é, portanto, bem definido. É fácil ver que ${\displaystyle \mathrm {grau} \ g(x)}\leq {\displaystyle \mathrm {grau} \ 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){\bmod {p}}$. Logo, $g(k)=0$ se e somente se $f(k)\equiv 0{\pmod {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{\pmod {p}}$ são incongruentes se e somente se $k_{1}\not \equiv k_{2}{\pmod {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 {grau} \ g(x)$, que é no máximo $\mathrm {grau} \ f(x)$.