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 ℤ [x]$ , maka berlaku salah satu dari dua kemungkinan berikut:

setiap koefisien dari $f$ merupakan kelipatan dari $p$ , atau
terdapat paling banyak $deg (f)$ nilai $x$ pada himpunan ${1, 2, 3, \dots, p}$ sedemikian sehingga $f (x)$ merupakan kelipatan $p$ ,

dengan $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 (\mod p)$ mungkin saja lebih dari $deg (f)$ . Misalnya, kekongruenan polinomial $x^{2} - 1 \equiv 0 (\mod 8)$ memiliki 4 penyelesaian dalam $ℤ / 8 ℤ$ (yaitu $1$ , $3$ , $5$ , dan $7$ ).

Teorema ini dinamai berdasarkan Joseph-Louis de Lagrange.

Bukti

Diambil sembarang bilangan prima $p$ dan misalkan $f \in ℤ [x]$ adalah polinomial dengan koefisien bilangan bulat. Didefinisikan $g \in (ℤ / p ℤ) [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 (\mod p) ⟺ g (x) \equiv 0 (\mod p)$

sehingga berdasarkan sifat dasar dari aritmetika modular, maka berlaku

$f (x) \equiv 0 (\mod p) ⟺ f (x mod p) \equiv 0 (\mod p) ⟺ g (x mod p) \equiv 0 (\mod p)$

Akibatnya, kedua versi dari teorema Lagrange (yaitu atas himpunan $ℤ$ dan atas himpunan $ℤ / p ℤ$ ) 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 ℤ$ . Oleh karena $p$ adalah bilangan prima, maka akan ditinjau dua kasus berikut:

Jika $FPB (c_{1}, p) = p$ , maka kekongruenan linier $c_{0} + c_{1} x \equiv 0 (\mod p)$ tidak memiliki penyelesaian. Akibatnya, jelas bahwa pernyataan teorema Lagrange benar.
Jika $FPB (c_{1}, p) = 1$ , maka berdasarkan identitas Bézout, kekongruenan linier $c_{0} + c_{1} x \equiv 0 (\mod 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} + \dots + c_{k} x^{k} = \sum_{i = 0}^{k} c_{i} x^{i}$ dengan $c_{i} \in ℤ$ untuk setiap $i \in {0, 1, 2, \dots, k}$ . Terdapat dua kasus yang perlu ditinjau:

Jika kekongruenan $f (x) \equiv 0 (\mod p)$ tidak memiliki penyelesaian, maka jelas bahwa pernyataan teorema Lagrange benar.
Jika kekongruenan $f (x) \equiv 0 (\mod p)$ memiliki setidaknya satu penyelesaian (sebut saja $a$ , yang berarti bahwa $f (a) \equiv 0 (\mod p)$ ), maka perhatikan bahwa $\begin{matrix} 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} + \dots + 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} + \dots + a^{i - 2} x + a^{i - 1}) \\ = (x - a) \cdot h (x) \end{matrix}$ Jelas bahwa $deg (h) = k - 1$ . Oleh karena $f (a) \equiv 0 (\mod p)$ , maka $\begin{matrix} f (x) - f (a) & = (x - a) \cdot h (x) \\ f (x) - f (a) & \equiv (x - a) \cdot h (x) & (\mod p) \\ f (x) & \equiv (x - a) \cdot h (x) & (\mod p) \end{matrix}$ Dengan kata lain, mencari penyelesaian dari kekongruenan $f (x) \equiv 0 (\mod p)$ sama saja dengan mencari penyelesaian dari kekongruenan $(x - a) \cdot h (x) \equiv 0 (\mod p)$ . Diketahui bahwa $p$ merupakan bilangan prima, maka berdasarkan lema Euclid, berlaku $x - a \equiv 0 (\mod p)$ atau $h (x) \equiv 0 (\mod 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 $ℤ / p ℤ$ .

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 28688688 (2025-12-11T14:13:44Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.