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 ${\displaystyle p}$. Lebih tepatnya, teorema ini menyatakan bahwa untuk setiap polinomial bilangan bulat ${\displaystyle f\in \mathbb {Z} [x]}$, maka berlaku salah satu dari dua kemungkinan berikut:

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

dengan ${\displaystyle \operatorname {deg} (f)}$ menyatakan derajat polinomial ${\displaystyle f}$.

Teorema Lagrange dapat dinyatakan ulang menggunakan aritmetika modular sebagai berikut:

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

Teorema ini dinamai berdasarkan Joseph-Louis de Lagrange.

Bukti

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

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

sehingga berdasarkan sifat dasar dari aritmetika modular, maka berlaku

$${\displaystyle 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 ${\displaystyle \mathbb {Z} }$ dan atas himpunan ${\displaystyle \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 ${\displaystyle c_{0}+c_{1}x}$, dengan ${\displaystyle c_{0}}$, ${\displaystyle c_{1}\in \mathbb {Z} }$. Oleh karena ${\displaystyle p}$ adalah bilangan prima, maka akan ditinjau dua kasus berikut:

1. Jika ${\displaystyle \operatorname {FPB} (c_{1},\,p)=p}$, maka kekongruenan linier ${\displaystyle c_{0}+c_{1}x\equiv 0{\pmod {p}}}$ tidak memiliki penyelesaian. Akibatnya, jelas bahwa pernyataan teorema Lagrange benar.
2. Jika ${\displaystyle \operatorname {FPB} (c_{1},\,p)=1}$, maka berdasarkan identitas Bézout, kekongruenan linier ${\displaystyle 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 ${\displaystyle k-1}$.
• Diambil sembarang polinomial berderajat ${\displaystyle k}$, yaitu $${\displaystyle 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 ${\displaystyle c_{i}\in \mathbb {Z} }$ untuk setiap ${\displaystyle i\in \left\{0,\,1,\,2,\,\ldots ,\,k\right\}}$. Terdapat dua kasus yang perlu ditinjau:

1. Jika kekongruenan ${\displaystyle f(x)\equiv 0{\pmod {p}}}$ tidak memiliki penyelesaian, maka jelas bahwa pernyataan teorema Lagrange benar.
2. Jika kekongruenan ${\displaystyle f(x)\equiv 0{\pmod {p}}}$ memiliki setidaknya satu penyelesaian (sebut saja ${\displaystyle a}$, yang berarti bahwa ${\displaystyle f(a)\equiv 0{\pmod {p}}}$), maka perhatikan bahwa $${\displaystyle {\begin{aligned}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}+ax^{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}+ax^{i-2}+a^{2}x^{i-3}+\ldots +a^{i-2}x+a^{i-1})\\&=(x-a)\cdot h(x)\end{aligned}}}$$ Jelas bahwa ${\displaystyle \operatorname {deg} (h)=k-1}$. Oleh karena ${\displaystyle f(a)\equiv 0{\pmod {p}}}$, maka $${\displaystyle {\begin{aligned}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{aligned}}}$$ Dengan kata lain, mencari penyelesaian dari kekongruenan ${\displaystyle f(x)\equiv 0{\pmod {p}}}$ sama saja dengan mencari penyelesaian dari kekongruenan ${\displaystyle (x-a)\cdot h(x)\equiv 0{\pmod {p}}}$. Diketahui bahwa ${\displaystyle p}$ merupakan bilangan prima, maka berdasarkan lema Euclid, berlaku ${\displaystyle x-a\equiv 0{\pmod {p}}}$ atau ${\displaystyle h(x)\equiv 0{\pmod {p}}}$. Berdasarkan hipotesis induktif, maka ${\displaystyle h(x)}$ memiliki paling banyak ${\displaystyle k-1}$ penyelesaian. Akibatnya, ${\displaystyle f(x)}$ memiliki paling banyak ${\displaystyle (k-1)+1}$ penyelesaian dalam himpunan ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$.

Referensi

• LeVeque, William J. (2002) [1956]. Topics in Number Theory, Volumes I and II [Topik dalam Teori Bilangan, Volume I dan II] (dalam bahasa Inggris). New York: Dover Publications. hlm. 42. ISBN 978-0-486-42539-9. Zbl 1009.11001.
• Tattersall, James J. (2005). Elementary Number Theory in Nine Chapters [Teori Bilangan Elementer dalam Sembilan Bab] (dalam bahasa Inggris) (Edisi kedua). Cambridge University Press. hlm. 198. ISBN 0-521-85014-2. Zbl 1071.11002.