Teorema Lagrange (teori bilangan)

Dalam teori bilangan, **teorema Lagrange** adalah teorema yang menyatakan seberapa sering suatu polinomial atas bilangan bulat menghasilkan kelipatan dari suatu konstanta prima p. Lebih tepatnya, teorema ini menyatakan bahwa untuk setiap polinomial bilangan bulat f \in \mathbb{Z}[x], maka berlaku salah satu dari dua kemungkinan berikut:
* setiap koefisien dari f merupakan kelipatan dari p, atau
* terdapat paling banyak \operatorname{deg} (f) nilai x pada himpunan \left\{ 1, \, 2, \, 3, \, \ldots, \, p \right\} sedemikian sehingga f(x) merupakan kelipatan p,
dengan \operatorname{deg} (f) menyatakan derajat polinomial f.

Teorema Lagrange dapat dinyatakan ulang menggunakan aritmetika modular sebagai berikut:

Jika p bukan bilangan prima, maka banyaknya penyelesaian dari kekongruenan f(x) \equiv 0 \pmod{p} mungkin saja lebih dari \operatorname{deg} (f). Misalnya, kekongruenan polinomial x^2 - 1 \equiv 0 \pmod{8} memiliki 4 penyelesaian dalam \mathbb{Z} / 8 \mathbb{Z} (yaitu 1, 3, 5, dan 7).

Teorema ini dinamai berdasarkan Joseph-Louis de Lagrange.

## Bukti

Diambil sembarang bilangan prima p dan misalkan f \in \mathbb{Z}[x] adalah polinomial dengan koefisien bilangan bulat. Didefinisikan g \in (\mathbb{Z} / p \mathbb{Z})[x] sebagai polinomial yang kongruen dengan f(x), tetapi dengan koefisien bilangan bulat modulo p. Untuk setiap bilangan bulat x, perhatikan bahwa

f(x) \equiv 0 \pmod{p} \qquad \Longleftrightarrow \qquad g(x) \equiv 0 \pmod{p}

sehingga berdasarkan sifat dasar dari aritmetika modular, maka berlaku

f(x) \equiv 0 \pmod{p} \qquad \Longleftrightarrow \qquad f(x \bmod{p}) \equiv 0 \pmod{p} \qquad \Longleftrightarrow \qquad g(x \bmod{p}) \equiv 0 \pmod{p}

Akibatnya, kedua versi dari teorema Lagrange (yaitu atas himpunan \mathbb{Z} dan atas himpunan \mathbb{Z} / p \mathbb{Z}) setara. Akan dibuktikan versi kedua dari teorema Lagrange menggunakan induksi matematika beserta pembuktian kasus demi kasus.
* Diambil sembarang polinomial linier c_0 + c_1 x, dengan c_0, c_1 \in \mathbb{Z}. Oleh karena p adalah bilangan prima, maka akan ditinjau dua kasus berikut:
# Jika \operatorname{FPB} (c_1, \, p) = p, maka kekongruenan linier c_0 + c_1 x \equiv 0 \pmod{p} tidak memiliki penyelesaian. Akibatnya, jelas bahwa pernyataan teorema Lagrange benar.
# Jika \operatorname{FPB} (c_1, \, p) = 1, maka berdasarkan identitas Bézout, kekongruenan linier c_0 + c_1 x \equiv 0 \pmod{p} memiliki penyelesaian tunggal. Akibatnya, pernyataan teorema Lagrange juga benar.
* Asumsikan bahwa teorema Lagrange benar untuk setiap polinomial berderajat k - 1.
* Diambil sembarang polinomial berderajat k, yaitu f(x) = c_0 + c_1 x + c_2 x^2 + \ldots + c_k x^k = \sum_{i \, = \, 0}^{k} c_i x^i dengan c_i \in \mathbb{Z} untuk setiap i \in \left\{ 0, \, 1, \, 2, \, \ldots, \, k \right\}. Terdapat dua kasus yang perlu ditinjau:
# Jika kekongruenan f(x) \equiv 0 \pmod{p} tidak memiliki penyelesaian, maka jelas bahwa pernyataan teorema Lagrange benar.
# Jika kekongruenan f(x) \equiv 0 \pmod{p} memiliki setidaknya satu penyelesaian (sebut saja a, yang berarti bahwa f(a) \equiv 0 \pmod{p}), maka perhatikan bahwa \begin{align}
f(x) - f(a) &= \sum_{i \, = \, 0}^{k} c_i x^i - \sum_{i \, = \, 0}^{k} c_i a^i \\
&= \sum_{i \, = \, 0}^{k} (c_i x^i - c_i a^i) \\
&= \sum_{i \, = \, 0}^{k} c_i (x^i - a^i) \\
&= \sum_{i \, = \, 1}^{k} c_i (x^i - a^i) \\
&= \sum_{i \, = \, 1}^{k} c_i (x - a) (x^{i - 1} + a x^{i - 2} + a^2 x^{i - 3} + \ldots + a^{i - 2} x + a^{i - 1}) \\
&= (x - a) \cdot \sum_{i \, = \, 1}^{k} c_i (x^{i - 1} + a x^{i - 2} + a^2 x^{i - 3} + \ldots + a^{i - 2} x + a^{i - 1}) \\
&= (x - a) \cdot h(x)
\end{align} Jelas bahwa \operatorname{deg} (h) = k - 1. Oleh karena f(a) \equiv 0 \pmod{p}, maka \begin{align}
f(x) - f(a) &= (x - a) \cdot h(x) \\
f(x) - f(a) &\equiv (x - a) \cdot h(x) &&\pmod{p} \\
f(x) &\equiv (x - a) \cdot h(x) &&\pmod{p}
\end{align} Dengan kata lain, mencari penyelesaian dari kekongruenan f(x) \equiv 0 \pmod{p} sama saja dengan mencari penyelesaian dari kekongruenan (x - a) \cdot h(x) \equiv 0 \pmod{p}. Diketahui bahwa p merupakan bilangan prima, maka berdasarkan lema Euclid, berlaku x - a \equiv 0 \pmod{p} atau h(x) \equiv 0 \pmod{p}. Berdasarkan hipotesis induktif, maka h(x) memiliki paling banyak k - 1 penyelesaian. Akibatnya, f(x) memiliki paling banyak (k - 1) + 1 penyelesaian dalam himpunan \mathbb{Z} / p \mathbb{Z}.

## Referensi

* 
*