Kongruensi Bilangan Bulat

Published by nanang_susyanto on

Kongruensi merupakan cara lain untuk menyajikan keterbagian. Keterbagian merupakan kejadian khusus dari kongrensi ini.
Pada Artikel ini akan dibahas definisi kongruensi dan sifat-sifatnya.

Pengertian dan Definisi Kongruensi

Seperti halnya pada keterbagian, kongruensi berhubungan dengan suatu bilangan bulat tertentu sebut saja n yang nantinya akan disebut dengan modulo n. Notasi dari kongruensi adalah ^{\prime }\equiv ^{\prime } dan dibaca kongruen. Sebagai contoh a\equiv b\left( \mod n\right) dibaca sebagai a kongruen dengan b modulo n. Seringkali untuk menyingkat penulisan, tanda kurung biasanya tidak ditulis. Dalam hal a tidak kongruen dengan b kita tulis dengan a\not\equiv b\mod n.

Definisi 1 (Definisi Modulo)
[box] Diberikan bilangan asli n>1. Untuk sebarang bilangan bulat a dan b kita punya bahwa a\equiv b\mod n jika dan hanya jika n|\left( a-b\right). Dengan kata lain sesuai dengan definisi keterbagian a\equiv b \mod n jika terdapat bilangan bulat k sehingga a=kn+b. [/box]

Contoh 2

4\equiv 2\mod 2, -2010\equiv 1\mod 2011, 5\not\equiv 0\mod 10, dan sebagainya.

 

Langsung dari Definisi 1, dapat diturunkan beberapa sifat yang disajikan pada teorema sebagai berikut.

Teorema 3

[box]

Diberikan sebarang bilangan asli n>1. Untuk setiap a,b,c,d\in\mathbb{Z}
berlaku:

  1. a\equiv a\mod n
  2. Jika a\equiv b\mod n maka b\equiv a\mod n.
  3. Jika a\equiv b\mod n maka a+c\equiv b+c\mod n,a-c\equiv b-c\mod n, dan ac\equiv bc\mod n.
  4. Jika a\equiv b\mod n dan c\equiv d\mod n maka ac\equiv bd\mod n. [/box]

Bukti hampir sama pada bukti saat kita membahas keterbagian dan diserahkan kepada pembaca sebagai latihan.

Dari sifat 4 pada Teorema 3 diperoleh akibat sebagai berikut.

Akibat 4

[box] Jika a\equiv b\mod n, maka a^{m}\equiv b^{m}\mod n, untuk setiap bilangan asli m. [/box]

[learn_more caption=”Bukti:” state=”open”]

Kita punya a\equiv b\mod n, maka menurut sifat 4 pada Teorema 3 akan berlaku a^{2}\equiv b^{2}\mod n, a^{3}\equiv b^{3}\mod n, dan
seterusnya dengan menggunakan induksi matematika dapat diperoleh bahwa a^{m}\equiv b^{m}\mod n.\blacksquare

[/learn_more]

Akibat 4 di atas juga dapat dibuktikan dengan menggunakan Binomial Newton. Salah satu kegunaan dari Akibat ?? adalah untuk mencari satu atau beberapa
digit terakhir dari suatu bilangan asli yang cukup besar.

Contoh 5

Tentukan digit terakhir dari 3^{2010}.

Pembahasan:

Digit terakhir dari suatu bilangan bulat adalah sisa pembagian bilangan tersebut oleh 10. Perhatikan bahwa 3^{2}\equiv -1\mod 10, dengan menggunakan Akibat 4 kita punya bahwa 3^{2020}=\left( 3^{2}\right) ^{1010}\equiv \left( -1\right) ^{1010}\equiv 1\mod 10. Dengan demikian, digit terakhir dari 3^{2020} adalah 1.

Contoh 6

Tentukan dua digit terakhir dari 43^{43^{43}}.~(Soal OSP 2002).

Pembahasan:

Perhatikan bahwa 43^{43}\equiv \left( -1\right) ^{43}\equiv -1\equiv 3\mod 4. Jadi 43^{43}=4k+3 untuk suatu bilangan bulat k. Sekarang kita punya bahwa 43^{43^{43}}=43^{4k+3}=43^{4k}.43^{3}=\left( 43^{2}\right) ^{2k}.43^{3}=\left( 1849\right) ^{2k}.79507\equiv 49^{2k}.7\equiv \left( 2401\right) ^{k}.7\equiv 1^{k}.7\equiv 7\mod 100. Dengan demikian, dua digit terakhir dari 43^{43^{43}} adalah 07.

Selain untuk menentukan digit terakhir dari suatu bilangan asli, kongruensi ini juga dapat digunakan untuk menyelesaikan persamaan baik itu mencari solusi ataupun membuktikan ketidakadaan solusi.

Contoh 7

Tentukan semua solusi asli dari persamaan x^{2}+y^{2}=2^{999}.

Pembahasan:

Karena ruas kanan genap maka ruas kiripun juga genap, dengan demikian x dan y harus sama paritasnya. Perhatikan bahwa jika x\equiv 1\mod 4 maka x^{2}\equiv 1\mod 4 dan jika x\equiv 3\mod 4 maka x^{2}\equiv 1\mod 4. Dengan demikian, jika x dan y keduanya ganjil maka x^{2}+y^{2}\equiv 2\mod 4 yang tentu saja tidak habis dibagi 4, padahal kita tahu bahwa ruas kanan habis dibagi 4. Jadi x dan y keduanya genap. Misalkan x=2x_{1} dan y=2y_{1} untuk suatu bilangan asli x_{1} dan y_{1}. Kita masukkan ke persamaan awal diperoleh 4x_{1}^{2}+4y_{1}^{2}=2^{999} yang ekivalen dengan x_{1}^{2}+y_{1}^{2}=2^{997}. Proses ini dapat kita lanjutkan sampai kita dapat x=2x_{1}=2^{2}x_{2}=...=2^{499}x_{499} dan y=2y_{1}=2^{2}y_{2}=...=2^{499}y_{499} yang selnjutnya diperoleh x_{499}^{2}+y_{499}^{2}=2. Persamaan terakhir ini hanya mempunyai solusi x_{499}=y_{499}=1. Dengan demikian x=2^{499}x_{499}=2^{499} dan y=2^{499}y_{499}=2^{499}. Jadi satu-satunya solusi adalah x=y=2^{499}.

 

Perhatikan kembali sifat ke tiga pada Teorema 3, yakni jika a\equiv b\mod n maka ac\equiv bc\mod n untuk setiap bilangan bulat c. Bagaimana sebaliknya? Jika ac\equiv bc\mod n apakah berakibat a\equiv b\mod n? Jawabannya tida selalu. Sebagai contoh kita punya 5\times 7\equiv 1\times 7\mod 14. Akan tetapi, ini tidak berakibat 5\equiv 1\mod 14. Lantas, syarat apa yang harus ditambahkan agar berlaku sifat demikian?

Teorema 8

[box] Diberikan bilangan asli n>1. Jika ac\equiv bc\mod n dan \left( c,n\right) =1 maka a\equiv b\mod n. [/box]

[learn_more caption=”Bukti:” state=”open”]

Karena ac\equiv bc\mod n maka n|c\left( a-b\right) dan karena \left( c,n\right) =1 maka n|\left( a-b\right) yang tentu saja berarti a\equiv b\mod n.

[/learn_more]

Categories: Materi
Tags:

0 Comments

Leave a Reply

Avatar placeholder

Your email address will not be published.

Related Posts

Materi

Relasi Urutan Pada Bilangan Bulat

Pada himpunan dapat didefinisikan relasi dengan definisi untuk setiap     Berdasarkan relasi didefinisikan relasi dengan definisi untuk setiap     Mudah dibuktikan jika dan hanya jika , sehingga diperoleh jika dan hanya jika dapat Read more…

Materi

Sistem Bilangan Bulat

Seiring dengan perkembangan budaya masyarakat baik dalam ilmu pengetahuan, kehidupan sehari-hari maupun dalam ekonomi sistem bilangan asli yang telah berkembang dianggap masih belum mampu mencukupi fenomena dunia matematika serta kebutuhan masyarakat tentang alat hitung. Khususnya Read more…

Materi

Operasi Perkalian Pada Sistem Bilangan Asli

Berdasarkan operasi penjumlahan pada selanjutnya dikonstruksi operasi perkalian dua bilangan asli. Operasi ini muncul dari penjumlahan secara berulang bilangan asli yang memunculkan pemetaan biner pada sperti dalam teorema berikut ini. Teorema 1 Pada himpunan bilangan Read more…