Catatan si Jay

September 24, 2010

Konsep Modulus dan Kekongruenan Bilangan

Filed under: Matematika, Teori Bilangan — Hendra Jaya @ 7:37 am

Di setiap jam dinding yang normal, ada terdapat 12 angka. Yaitu 1, 2, 3, 4, … 12. Pada jam digital, angka 12 diganti dengan angka 0. Sehingga angka-angka yang tersedia adalah 0, 1, 2, 3 … 11. Walaupun jam digital bisa di-setting sehingga menunjukkan angka 0, 1, 2, 3 … 23, banyak orang lebih memilih memakai setting 12-jam, yaitu 0, 1, 2, 3, .. 11. Begitu pula para matematikawan. Mereka lebih suka memakai angka 0, 1, 2, 3, … 11. Jangan tanya kenapa.

Di dalam artikel ini, semua jam akan mengikuti sistem 12-jam ala matematikawan, yaitu jam dinding dengan angka 0, 1, 2, 3 … 11. Angka 0 berada di posisi angka 12. Agara lebih mudah dipahami, perhatikan gambar berikut :

jam dinding

  1. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Dalam 8 jam mendatang, ke angka berapakah jarum jam akan menunjuk?
  2. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Dalam 20 jam mendatang, ke angka berapakah jarum jam akan menunjuk?
  3. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Dalam 32 jam mendatang, ke angka berapakah jarum jam akan menunjuk?
  4. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Empat jam yang lalu, di angka berapakah jarum jam menunjuk?
  5. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Enam belas jam yang lalu, di angka berapakah jarum jam menunjuk?
  6. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Dua puluh delapan jam yang lalu, di angka berapakah jarum jam menunjuk?

Jawaban atas seluruh pertanyaan di atas adalah di angka 8. Sekarang akan kita cari tahu kenapa hal ini bisa terjadi.

Identitas dan Simbol

Kita tahu bahwa dalam 12 jam, jarum jam akan kembali ke posisinya semula, yaitu 0. Kita katakan bahwa jarum jam akan membutuhkan 12 jam untuk melakukan satu “putaran penuh”. Dengan kata lain, satu putaran penuh = 12 jam.

Sekarang, seperti layaknya kebiasaan di dunia matematika yang membosankan, akan kita lakukan ritual simbolisasi.
a menyatakan waktu. Untuk masa lalu diberi tanda negatif (-) dan untuk masa yang akan datang tidak diberi tanda, alias positif (+).
q menyatakan banyaknya putaran
d menyatakan waktu yang diperlukan untuk melakukan satu “putaran penuh”. Dengan demikian d = 12.
r menyatakan sisa waktu setelah berputar-putar.

Pembahasan

  1. Waktu yang dimiliki adalah 8 jam (di masa yang akan datang). Dengan demikian a = 8.
    Dalam 8 jam, jarum jam belum melakukan satu kalipun putaran penuh. Dengan demikian q = 0.
    Karena dalam 8 jam si jarum belum berputar sama sekali, maka sisa waktunya tetap 8 jam. Dengan demikian r = 8.
    Secara matematis dapat dituliskan 8 = 0.12 + 8
  2. Waktu yang dimiliki adalah 20 jam (di masa yang akan datang). Dengan demikian a = 20.
    Dalam 20 jam, jarum jam melakukan satu kali putaran penuh. Dengan demikian q = 1.
    Karena jarum jam berputar satu kali, maka waktu yang sudah dikonsumsi untuk berputar adalah 12 jam. Sisanya adalah 8 jam. Dengan demikian r = 8.
    Secara matematis dapat dituliskan 20 = 1.12 + 8
  3. Waktu yang dimiliki adalah 32 jam (di masa yang akan datang). Dengan demikian a = 32.
    Dalam 32 jam, jarum jam melakukan dua kali putaran penuh. Dengan demikian q = 2.
    Karena jarum jam berputar dua kali, maka waktu yang habis untuk berputar-putar adalah 24 jam. Sisanya adalah 8 jam. Dengan demikian r = 8.
    Secara matematis dapat dituliskan 32 = 2.12 + 8
  4. Waktu yang dimiliki adalah 4 jam (di masa lampau). Dengan demikian a = -4.
    Dalam 4 jam (ke belakang), jarum jam belum melakukan satu kalipun putaran penuh. Dengan demikian q = 0.
    Karena dalam 4 jam (ke belakang) si jarum belum berputar sama sekali, maka sisa waktunya tetap 4 jam. Dengan demikian r = -4 (perhatikan tanda negatif).
    Secara matematis dapat dituliskan -4 = 0.12 + -4
    Karena jam kita tidak memiliki angka -4, maka kita harus mengubahnya menjadi suatu angka yang “dikenali” oleh jam kita. Karena kita tahu dalam 12 jam, si jarum pasti akan kembali ke posisinya semula, maka jam -4 akan menunjukkan angka yang sama dengan jam -4 + 12 alias 8. Dengan demikian, jarum jam di pukul -4.00 akan menunjukkan angka 8.
  5. Waktu yang dimiliki adalah 16 jam (di masa lampau). Dengan demikian a = -16.
    Dalam 16 jam (yang lalu), jarum jam telah berputar sebanyak satu kali. Dengan demikian q = -1 (perhatikan tanda negatif).
    Karena dalam 16 jam silam si jarum telah berputar sebanyak satu kali, maka sisa waktu yang dimilikinya adalah 4 jam. Dengan demikian r = -4 (perhatikan tanda negatif).
    Secara matematis dapat dituliskan -16 = -1.12 + -4
    Sama seperti di soal sebelumnya, kita harus mengubah angka -4 menjadi suatu angka yang “dikenali” oleh jam kita, yaitu dengan menambahkan 12 jam “khayal”. Setelah ditambahkan 12 jam “khayal” ini, jarum jam akan menunjukkan pukul 8.
  6. Waktu yang dimiliki adalah 28 jam (di masa lampau). Dengan demikian a = -28.
    Dalam tempo 28 jam (yang lalu), jarum jam telah berputar sebanyak dua kali. Dengan demikian q = -2 (perhatikan tanda negatif).
    Karena dalam 28 jam yang lalu si jarum telah berputar sebanyak dua kali, maka sisa waktu yang dimilikinya adalah 4 jam. Dengan demikian r = -4 (perhatikan tanda negatif).
    Secara matematis dapat dituliskan -28 = -2.12 + -4
    Sama seperti sebelum-sebelumnya, kita harus mengubah angka -4 menjadi suatu angka yang “dikenali” oleh jam kita, yaitu dengan menambahkan 12 jam “khayal”. Setelah ditambahkan 12 jam “khayal” ini, jarum jam akan menunjukkan pukul 8.

Kekongruenan Bilangan

Hal yang menarik dari kasus ini adalah : Dalam 8 jam ataupun 20 jam ataupun 32 jam ke depan, maupun dalam 4 jam ataupun 16 jam ataupun 28 jam ke belakang, semuanya akan menunjuk ke angka yang sama. Yaitu angka 8.

Fenomena ini, di dalam dunia matematika, diberi nama kongruen.
Definisi 1 : Bilangan bulat a dan bilangan bulat b dikatakan kongruen dalam modulo n jika dan hanya jika keduanya memberikan sisa bagi yang sama ketika dibagi dengan n, dimana a, b, n \in \mathbb{Z}. Secara simbolik dinyatakan dengan a \equiv b \ (mod \ n).

Sekarang, karena a = {q}_{1}.n + r dan b = {q}_{2}.n + r, maka dengan melakukan operasi pengurangan kita memperoleh a - b = {q}_{1}.n - {q}_{2}.n. Dengan memanfaatkan sifat distributif pada perkalian, kita mendapatkan a - b = ({q}_{1} - {q}_{2}).n. Sampai disini, kita dapat menyimpulkan bahwa a – b pasti habis dibagi oleh n. Atau secara simbolis dinyatakan dengan n | a - b.

Dari penjabaran di atas, kekongruenan pun dapat diberi definisi yang lain.
Definisi 2 : Bilangan bulat a dan bilangan bulat b dikatakan kongruen dalam modulo n jika dan hanya jika a – b habis dibagi oleh n. Secara matematis : a \equiv b\ (mod \ n) \leftrightarrow n | a - b.

Menurut definisi 1 dari kekongruenan : 8, 20, 32, -4, -16, -28 adalah kongruen dalam modulo 12 karena semuanya memberikan sisa bagi yang sama. Sisa bagi dalam keenam soal di atas ditandai dengan “kemana jarum jam menunjuk”.
Menurut definisi 2 dari kekongruenan : Ambil dua buah bilangan, terserah yang mana, di antara 8, 20, 32, -4, -16 dan -28. Selisih kedua bilangan tersebut pasti habis dibagi oleh 12.

Jika kita tinjau lagi identitas “jam khayal” pada pembahasan di atas, sebenarnya secara implisit kita telah menyatakan bahwa a \equiv q.12 + a\ (mod\ 12) . Untuk sembarang a, q \in \mathbb{Z}

Di dalam teori bilangan matematika, modulus adalah “bilangan pembagi”. Pada bilangan jam, modulus-nya adalah 12. Dan “mod” bukanlah sebuah fungsi ataupun operator, tetapi menyatakan “di modulus berapa dua buah bilangan dinyatakan kongruen”.

Konsep ini agak abstrak. Tetapi bayangkan jika kita memiliki jam dinding yang hanya memiliki angka 0, 1, dan 2. Jam dinding ini secara matematis dikatakan modulus 3. Selanjutnya, jika kita mulai dari 0, maka 17 dan 11 dalam jam dinding “yang aneh ini” sama-sama akan menunjuk angka 2. Dan (lagi-lagi) secara matematis dikatakan 17 \equiv 11 \ (mod \ 3), yaitu 17 dan 11 kongruen di dalam modulus 3.

Di dalam ilmu komputasi, fungsi mod(x, y) ataupun operator binary mod, dapat dikatakan (walaupun kurang tepat) sebagai fungsi yang mencari sisa pembagian x oleh y. Tolong diingat baik-baik bahwa algoritma pembagian euclid adalah algoritma yang matematis, bukan komputatif. Sehingga mungkin memberikan hasil yang berbeda dengan hasil perhitungan (kalkulasi) komputatif.

Untuk memperjelas maksud saya, perhatikan contoh ini :
Menurut kalkulator : \frac {-17}{12} = -1.41666 = -15/12
Menurut algoritma pembagian : -17 = -2.12 + 7

Mengapa hasil pembagian oleh algoritma pembagian berbeda dengan hasil yang sebenarnya? Jawaban yang paling mudah adalah dengan menyalahkan tanda negatif (-) yang membingungkan. Tetapi ada penjelasan yang lain.

Jika mengikuti hasil perhitungan kalkulator, maka algoritma pembagian dapat menyatakan -17 \div 12 sebagai -17 = -1.12 -5. Hasil ini benar (secara komputatif) tetapi tidak masuk akal di dalam matematika. Mengapa tidak masuk akal? Karena di dalam jam dinding 12-jam seperti yang ada di rumah-rumah, tidak ada angka -5. Hal ini sejalan dengan algoritma pembagian yang memberikan syarat 0 \leq r < |d|.

Sama seperti soal-soal sebelumnya, trik yang kita lakukan untuk mengubah angka -5 menjadi angka yang benar adalah dengan menambahkan “putaran-putaran khayal”. Sehingga, -17 = -1.12 -5 + 1212.
Yang biru adalah putaran khayal.
Yang merah adalah “pengimpas”. Hal ini harus dilakukan agar tidak mengubah dividen (dividen : bilangan yang dibagi). Ingat bahwa 12 – 12 = 0.

Sekarang, dengan menggabungkan -5 dan 12 serta menggabungkan -12 dengan -1.12 kita peroleh
-17 = -1.12 – 12 + (-5 + 12)
-17 = -2.12 + 7

Di dalam bentuk ini, dapat dikatakan bahwa -17 (17 jam yang lalu) dalam jam dinding menunjuk angka 7. Angka 7 ini pula-lah yang dimaksud dengan remainder (sisa bagi) r pada algoritma pembagian euclid. Perhatikan bahwa sekarang r telah memenuhi konstrain 0 \leq r < |d|.

Ada penjelasannya mengapa para matematikawan tidak terlalu tertarik dengan quotient (hasil bagi) q. Mereka jauh lebih tertarik dengan r. Penjelasan itu nanti akan kita pahami pada saat berdiskusi tentang teori bilangan yang lainnya. Sebagai konsekuensi atas “ketidaktertarikan” mereka, angka -2 yang keliru ini diabaikan begitu saja :)

Ingat baik-baik bahwa algoritma pembagian euclid bukan untuk menghitung (to compute) hasil akhir. Melainkan sebagai senjata untuk menyelesaikan persoalan di teori bilangan yang lain.

Sifat-sifat Dasar Kekongruenan

Jika diketahui : a \equiv b \ (mod \ n) dan p \equiv q \ (mod \ n)
Berlaku (semacam operasi pembagian) : a + p \equiv b + q \ (mod \ n)
Berlaku (semacam operasi perkalian) : ap \equiv bq \ (mod \ n)

Asal muasal datangnya kedua sifat tersebut adalah sebagai berikut :

Karena a \equiv b \ (mod \ n), maka n | a - b. Dalam bentuk yang lain dapat dituliskan : a - b = n.x.

Begitu pula  p \equiv q \ (mod \ n). Kekongruenan p dan q ini dapat dituliskan ke dalam bentuk p - q = n.y

Jika dikenakan operasi penjumlahan :

\begin{array}{lcccr} & a - b& =& n.x \\ & p - q& =& n.y \\ & ------& &------& +\\ & (a - b) + (p - q)& =& n.x + n.y \\ & (a + p) - (b + q)& =& n(x + y) \\ \therefore& a+p& \equiv& b+q \ (mod \ n) \end{array}

Sekarang, karena :

\begin{array}{cccr} a - b& =& n.x \\ q(a - b)& =& q.n.x& \text{dimana } q \neq 0 \end{array}

Begitu juga :

\begin{array}{cccr} p - q& =& n.y \\ a(p - q)& =& a.n.y& \text{dimana } a \neq 0 \end{array}

Jika kedua persamaan di atas dikenai operasi penjumlahan :

\begin{array}{lcccr} & q(a - b)& =& q.n.x \\ & a(p - q)& =& a.n.y \\ & ---------& &-------& +\\ & aq - bq + ap - aq& =& q.n.x + a.n.y \\ & ap - bq& =& n(q.x + a.y) \\ \therefore& ap& \equiv& bq \ (mod \ n) \end{array}

Jika salah satu (atau keduanya) dari a atau q bernilai 0, sifat ap \equiv bq \ (mod \ n) pun jelas terpenuhi.

Obat ngantuk

  1. Bintang Berapa sisa pembagian {19}^{1000} \div {3} ?
  2. Bintang Berapa sisa pembagian {2}^{100} \div {3} ?
  3. BintangBintang Berapa sisa pembagian ({22}^{55}+{55}^{22}) \div {7} ?
  4. BintangBintangBintang Buktikan bahwa {2222}^{5555}+{5555}^{2222} habis dibagi 7. (Seleksi Tim Olimpiade Matematika Indonesia 1997). Pembahasan bisa dilihat di sini.
  5. BintangBintangBintang Kira-kira saja, berapa digit-kah {2}^{123456} ? Pembaca hanya diminta memberikan tebakan se-akurat mungkin. Jika pembaca bisa memberikan jawaban persisnya tentu sangat bagus. Pembahasan bisa dilihat di sini.

Seperti yang sudah-sudah, pembahasan terhadap obat-obat ngantuk ini akan diberikan pada post berikutnya.

I punched my boss

Artikel Terkait :

About these ads

3 Komentar »

  1. ap sih bedanya antara ‘sama dengan’, ‘kongruen’ dan ‘ekuivalen’????

    Komentar oleh Irdha — Desember 7, 2010 @ 11:29 am

  2. ap sih beda antara ‘sama dengan’, ‘kongruen’dan ‘ekuivalen’???

    Komentar oleh Irdha — Desember 7, 2010 @ 11:33 am

    • Halo Irdha.
      Terima kasih sudah berkunjung.

      1. Penulis rasa Irdha sudah cukup mengerti dengan “sama dengan” (=)
      2. Kongruen itu maknanya lain dengan “sama dengan”. Kongruen dalam teori bilangan dapat dianalogikan dengan “sejenis”. Walaupun analogi ini tidak terlalu tepat.
      Sebagai contoh angka 4 dan angka 16 adalah dua buah bilangan yang kongruen dalam modulo 12. (Perhatikan jam dinding)
      Artinya, jam 4 dan jam 16 keduanya akan menunjuk angka yang sama.
      Ingat bahwa 4 “tidak sama dengan” 16. Tetapi 4 “kongruen” dengan 16 di dalam modulo 12.
      3. Ekuivalen/jika-hanya-jika sebenarnya lebih ke arah logika.
      Artinya logika ke arah “kanan” pasti dapat dikembalikan ke arah “kiri”
      Perhatikan contoh ini :

      x+2=5\Leftrightarrow x=3
      Jika x ditambahkan dengan 2 maka hasilnya menjadi 5. Maka x adalah 3.
      Kebenaran ini dapat dikembalikan menjadi
      Hanya jika x adalah 3. Maka nilai x setelah ditambah dengan 2 adalah 5.

      Sebaliknya
      x^2=2x\Rightarrow x=2
      Jika x dikalikan dengan dirinya sendiri hasilnya akan sama ketika x dikalikan dengan 2. Maka x adalah 2.
      Kesimpulan ini tidak komplit karena x=0 juga benar.
      Sehingga kebenarannya tidak dapat dikembalikan menjadi
      Hanya jika x bernilai 2 maka nilai x^2 akan sama dengan 2x

      Komentar oleh Hendra Jaya — Desember 8, 2010 @ 7:42 am


Umpan RSS untuk komentar-komentar pada pos ini. TrackBack URI

Berikan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Logout / Ubah )

Twitter picture

You are commenting using your Twitter account. Logout / Ubah )

Facebook photo

You are commenting using your Facebook account. Logout / Ubah )

Google+ photo

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

The Shocking Blue Green Theme. Blog di WordPress.com.

Ikuti

Get every new post delivered to your Inbox.

%d blogger menyukai ini: