Kongruensi Bilangan Bulat

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

[latexpage]

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 \ref{modcol} 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]