Kongruensi Polinomial dan Hensel Lemma

Kita sudah mempelajari CRT (Chinese Remainder Theorem) untuk menyelesaikan Kombinasi Kongruensi Linear. Lalu, bagaimana apabila kita menemui kasus yang nonlinear.?? Perhatikan contoh soal di bawah.

1. habis dibagi 200. Tentukan bilangan bulat yang mungkin.

2. bersisa 1 jika dibagi 1331. Tentukan bilangan bulat yang mungkin.

3. Budi mempunyai sejumlah koin. bersisa 67 jika dibagi 3500. Tentukanlah jumlah koin minimum yang dimiliki Budi.

dan masih ada contoh soal lainnya..

====================================================================

Sedikit mengulang. Jika kita ingin memecahkan kongruensi linear. Kita dapat menggunakan persamaan linear diophantine. Contohnya, seperti di bawah:

bersisa 4 jika dibagi 15. Tentukan bilangan bulat yang mungkin.

Jawab:
Kita dapat menotasikan soal di atas menjadi:

Diolah sedikit:

Sekarang, masalahnya seperti persamaan linear diophantine, yaitu menemukan nilai dari persamaan .
15 = 2 x 7 +1
7 = 1 x 7 + 0.
Identitas Bezout-nya adalah:

1 = 1 x 15 + 2x 7.

Kalikan dengan 13, maka hasilnya:

13 = 13 x 15 + 26 x 7.

Pindah ruas:

26 x 7 = -13 x 15 + 13.

Jadi:

Pada post ini, kita akan sering menjumpai istilah "invers modulo". Untuk mendapatkan invers modulo dari , kita cukup mengetahui identitas Bezout-nya, yaitu

1 = 1 x 15 + 2x 7

Dapat kita katakan bahwa "2 adalah invers dari 7 modulo 15".
Kita juga dapat mengatakan bahwa "7 adalah invers dari 2 modulo 15".
Perhatikan juga bahwa invers modulo adalah operasi yang lazim dalam pemindahan ruas.

Untuk menyelesaikan kongruensi nonlinear, kita dapat gunakan Hensel Lemma.

Hensel Lemma

Untuk suatu soal
dimana adalah fungsi polinomial dengan koefisien integer.
_______ adalah bilangan prima.
_______ dan integer
Anggap bahwa adalah solusi dari
Maka:

(i)	Jika , maka akan ada solusi unik integer dimana yang memenuhi . Nilai dapat dicari dengan cara berikut: dimana adalah invers dari modulo .
(ii)	Jika DAN ,maka untuk semua integer.
(iii)	Jika DAN ,maka tidak memiliki solusi untuk

Note: Lemma ini dapat dibuktikan dengan ekspansi Taylor. Bukti belum dapat disertakan di post ini.

Untuk memahami cara menyelesaikan kongruensi polinomial, perhatikan semua contoh soal yang ada di bawah:

Contoh Soal 1:
habis dibagi 97. Tentukan bilangan bulat yang memenuhi.

Jawab:
Soal di atas dapat ditulis ulang menjadi:

Perhatikan bahwa 97 adalah bilangan prima. Hensel Lemma hanya dapat digunakan jika kita ingin mencari dimana . Jadi, di soal ini kita tidak bisa menggunakan Hensel Lemma, karena pangkat primanya 1.

Salah satu cara yang dapat dilakukan untuk soal ini adalah dengan coba-coba.
Masukkan , lalu periksa satu semi satu apakah habis dibagi 97. Namun, cara ini sungguh membuat frustasi...

Ada cara alternatif.

dapat dibentuk menjadi

Jadi, . Karena 97 adalah bilangan prima, maka .

Contoh Soal 2:
Tentukan solusi kongruensi .
Jawab:
Gunakan cara coba-coba. Masukkan . Karena 1 memenuhi dan yang lainnya tidak, maka solusinya adalah .

Contoh Soal 3:
Tentukan solusi kongruensi

Jawab Cara Biasa (Tanpa Hensel Lemma)

Perhatikan contoh soal 2. Kita sudah menemukan solusi untuk yaitu .

Dapat juga ditulis sebagai

dimana semua bilangan bulat..

Anggap
adalah (i)
adalah (ii)

Secara logika, kita tahu bahwa solusi pada (ii) dimiliki oleh (i). Ini juga dapat diketahui karena. Jadi, kita dapat menerapkan sifat (i) pada (ii).

Substitusikan ke (ii):

Berapapun nilai , dan selalu habis dibagi 25. Oleh karenanya dapat kita tiadakan.

Kita menemui kasus linear..

Bagi kedua ruas dengan 5. (Lihat INI pada pembagian kedua ruas)

13 dapat disederhanakan dengan modulo 5.

Maka kita dapatkan solusi untuk , yaitu:

=

Jawab dengan Hensel Lemma
.
Solusi untuk adalah .
.
.
Karena bukan 0, kita menemui kasus (i) dari Hensel Lemma.
karena yang berarti 2 adalah invers dari 3 modulo 5.

Jadi, solusinya adalah
.

Contoh Soal 4:
habis dibagi 200. Tentukan bilangan bulat yang mungkin.
Jawab:

Karena , maka kongruensi di atas dapat dipecah menjadi 2, yaitu:

... (i)
DAN
... (ii)

Solusi untuk (i) dapat diperoleh dengan coba-coba, mulai dari . Kita dapatkan

Solusi untuk (ii) sudah didapat dari contoh soal 3, yaitu .

Selanjutnya, kita dapat menggunakan CRT (Chinese Remainder Theorem) untuk menemukan solusi dari keduanya.
(i) , maka ...(i)
(ii) , maka ... (ii)

Kita cari identitas Bezoutnya dengan algoritma Euclid.
25 = 8x3+1.
Identitas Bezout: 1 = 25 +(8)(-3)
Berarti (-3) adalah invers dari 8 modulo 25.

Substitusikan nilai k ke nilai awal .
.

Contoh Soal 5:
Tentukan solusi kongruensi

Jawab dengan Hensel Lemma:

Sebelumnya cari dulu solusi untuk .

Dengan cara coba-coba, kita dapatkan solusi:

*) Untuk
.
merupakan kasus (i) dari Hensel Lemma.
, karena 4 adalah invers dari 3 modulo 11. Atau bisa ditulis 3x4 = 1 mod 11.

Maka, solusinya adalah

*) Untuk
.
merupakan kasus (i) dari Hensel Lemma.
, karena 1 adalah invers dari 1 modulo 11. Atau bisa ditulis 1x1 = 1 mod 11.
.
Maka, solusinya adalah

*) Untuk

merupakan kasus (i) dari Hensel Lemma.
, karena 6 adalah invers dari 2 modulo 11. Atau bisa ditulis 2x6 = 1 mod 11.

Maka, solusinya adalah .

Jadi, solusi gabungan dari ketiganya:

Contoh Soal 6:
Tentukan solusi kongruensi

Jawab:


Sebelumnya, kita cari dulu solusi untuk
Dengan coba-coba, kita dapatkan .

Kemudian, kita cari solusi untuk

Kita gunakan solusi sebelumnya, yaitu 1.
.

merupakan kasus (ii) dari Hensel Lemma.
Maka, solusinya

Kemudian, kita cari solusi untuk
*) Untuk


merupakan kasus (iii) dari Hensel Lemma.
Maka, tidak mempunyai solusi.

*) Untuk


merupakan kasus (ii) dari Hensel Lemma.
Maka, solusinya

*) Untuk


merupakan kasus (iii) dari Hensel Lemma.
Maka, tidak mempunyai solusi.

Jadi, gabungan solusi kongruensi untuk adalah

Contoh Soal 7:
Tentukan solusi untuk

Jawab:
Sebelumnya, kita cari dulu solusi untuk
Dengan cara coba-coba, kita dapatkan

Kemudian, kita cari solusi untuk


merupakan kasus (i) dari Hensel Lemma.
, karena 2 adalah invers dari 4 modulo 7 Atau bisa ditulis 2x4 = 1 mod 7.

Maka, solusinya adalah

Kemudian, kita cari solusi untuk

merupakan kasus (i) dari Hensel Lemma.
.

Maka, solusinya adalah

Contoh Soal 8:
bersisa 1 jika dibagi 1331. Tentukan bilangan bulat yang mungkin.

Jawab:


Sebelumnya, kita cari solusi untuk .
Dengan coba-coba, kita dapatkan solusi .

Selanjutnya, kita cari solusi untuk .


*) Untuk

merupakan kasus (i) dari Hensel Lemma.


Maka, solusinya adalah

*) Untuk


merupakan kasus (iii) dari Hensel Lemma.
tidak memiliki solusi.

Jadi, solusi untuk adalah

Tahap akhir, kita cari solusi untuk .

merupakan kasus (i) dari Hensel Lemma.


Maka, solusinya adalah .

Contoh Soal 9:
Budi mempunyai sejumlah koin. bersisa 67 jika dibagi 3500. Tentukanlah jumlah koin minimum yang dimiliki Budi.

Jawab:

Soal di atas dapat ditulis ulang menjadi:

Karena , maka kita bisa mereduksi masalah di atas menjadi 3 bagian, yaitu:

... (i)
DAN
... (ii)
DAN
... (iii)

Tinjau (i).

Dengan memasukkan , maka kita dapatkan solusi sbb:

... (a)

Tinjau (ii)
Sebelumnya, selesaikan dahulu kongruensi .
Dengan cara coba-coba, kita dapatkan solusi: .

Kemudian, selesaikan kongruensi .

*) Untuk

merupakan kasus (i) dari Hensel Lemma.




*) Untuk

merupakan kasus (i) dari Hensel Lemma.




*) Untuk

merupakan kasus (i) dari Hensel Lemma.




Maka, solusi gabungan ketiganya adalah

Kemudian, selesaikan kongruensi .
*) Untuk

merupakan kasus (i) dari Hensel Lemma.




*) Untuk

merupakan kasus (i) dari Hensel Lemma.




*) Untuk

merupakan kasus (i) dari Hensel Lemma.




Jadi, solusi kongruensi untuk adalah

... (b)

Tinjau (iii)

Dengan cara coba-coba, kita dapatkan solusi

... (c)

Maka, syarat-syarat di bawah ini harus dipenuhi agar solusi didapat.

... (a)
DAN
... (b)
DAN

... (c)

Perhatikan bahwa syarat (b) adalah syarat yang memiliki angka paling besar. Jadi, solusinya pasti ada di antara 3, yaitu ATAU ATAU
Perhatikan juga bahwa yang diminta soal adalah yang minimum. Jadi, kita akan memulai pengecekan mulai dari .

Cek:
memenuhi syarat (a) karena
juga memenuhi syarat (c) karena
Oleh karena tidak ada bilangan yang lebih kecil dari 69, dan 69 sudah mencukupi syarat yang ada, maka

Jumlah koin minimum yang dimiliki Budi = x min = 69.

====================================================================

Sekian dulu mengenai kongruensi modulo dan Hensel Lemma.

Untuk mengerjakan soal ini awalnya memang rumit, karena harus mengenal hampir banyak bahan dari teori bilangan, seperti PL diophantine, modulo, invers modulo, dan CRT. Namun, sesungguhnya soal ini cukup mudah. Untuk memahaminya, kalian cukup mengerjakan semua latihannya.

Sumber:
1. http://en.wikipedia.org/wiki/Hensel%27s_lemma
2. Buku Elementary Number Theory and its application by Kenneth H Rosen.