Teori Bilangan

Kekongruenan Bilangan Bulat

Definisi: (Kekongruenan)

Jika n Î Z+.dan x, y Î Z, n membagi x – y (ditulis: n½(x – y)), kita katakan bahwa x kongruen dengan y modulo n, dan ditulis x º y (mod n). Jika n tidak membagi x – y, kita katakan x tidak kongruen dengan y modulo n, dan ditulis x º y (mod n).

Contoh:

(a) –17 º 28 (mod 3), sebab 3 ½(-17 – 28).

(b) 30 º 10 (mod 5), sebab 5 ½(30 – 10).

(c) 39 º 12 (mod 4), sebab 4 ½ (39 -12).

(d) 8 º 18 (mod 7), sebab 7 ½ (8 – 18).

Teorema:

x º y (mod n) jika dan hanya jika ada bilangan bukat k sedemikian hingga y = nk + x

Bukti:

x º y (mod n) jika dan hanya jika n½(y – x).

n ½(y – x) jika dan hanya jika y – x = nk atau y = x + nk.

Contoh:

(a)10 º 24 (mod 7), sebab ada bilangan bulat 2

sedemikian hingga 24 = 2.7 + 14.

(b) 5 º 29 (mod 8), sebab ada bilangan bulat 3

sedemikian hingga 29 = 3.8 + 5.

(c) 23 = 4.5 + 3, sebab 23 º 3 (mod 5).

(d) 47 = 5.9 + 2, sebab 47 º 2 (mod 9).

Karena x – y habis dibagi n jika dan hanya jika x – y habis dibagi –n, maka kita dapat secara umum hanya memperhatikan pada modulo bilangan bulat positif saja. Jika x bilangan bulat dan n bilangan bulat positif, maka menurut teorema algoritma pembagian terdapat bilangan bulat q dan r sedemikian hingga

x = qn + r dengan 0 £ r < n

Ini berarti x – r = qn atau n½(x – r), yakni: x º r (mod n). Bilangan bulat r yang memnuhi x = qn + r disebut sisa pembagian atau residu bilamana x dibagi n.

Jika 0 £ r < n, dalam hal demikian r disebut juga residu terkecil dari x modulo n.

Karena 0 £ r < n, maka terdapat n buah pilihan untuk r, yaitu : 0, 1, 2, … , n-1. Jadi setiap bilangan bulat akan kongruen dengan tepat satu di antara 0, 1, 2,… , n-1.

Contoh:

(a) Residu terkecil dari 35 modulo 5 adalah 0.

(b) Resido terkecil dari 50 modulo 7 adalah 1

Teorema:

Dua bilangan bulat x dan y kongruen modulo n jika dan hanya jika keduanya mempunyai residu yang sama jika dibagi n

Bukti:

Misalkan x = qn + r dengan 0 £ r < n dan

y = q’n + r’ dan 0 £ r’ < n. Maka

x – y = (q – q’)n + (r – r’)

dan juga n½(x – y) jika dan hanya jika n½(r – r’). Karena 0 £ r < n dan 0 £ r’ < n, maka

n½(r – r’) jika dan hanya jika r = r’.

Contoh:

(a) 10 º 34 (mod 4) karena residu terkecil dari

10 dan 34 modulo 4 masing-masing adalah 2.

(b) 23 = 4.5 + 3 dan 48 = 9.5 + 3 maka 23 º 48 (mod 5).

Definisi: (sistem residu lengkap modulo)

Himpunan bilangan bulat {r1, r2, r3, …, rn} disebut sistem residu lengkap modulo n jika dan hanya jika setiap bilangan bulat kongruen modulo n dengan tepat satu di antara r1, r2, r3, …, atau rn.

Contoh:

Himpunan A = {-12, -5, 32, -45, 28, 41} merupakan sistem residu lengkap modulo 6, karena setiap sembarang bilangan bulat x yang kita ambil pasti kongruen modulo 6 dengan salah satu bilangan di himpunan A.

Atau karena

-12 º 0 (mod 6)

-5 º 1 (mod 6)

32 º 2 (mod 6)

-45 º 3 (mod 6)

28 º 4 (mod 6)

41 º 5 (mod 6)

Karenanya setiap bilangan bulat x yang kita ambil pasti kongruen modulo 6 dengan 0, 1, 2, 3, 4, atau 5.

Contoh:

Himpunan A = {-12, -5, 32, -45, 28, 41} merupakan sistem residu lengkap modulo 6, karena setiap sembarang bilangan bulat x yang kita ambil pasti kongruen modulo 6 dengan salah satu bilangan di himpunan A.

About these ads

2 Comments »

  1. aufa Said:

    kalau boleh aku kasih saran, boleh juga diupload,,, biar teman-teman yang butuh materi nya bisa tinggal download aja.. trims

  2. bisa kasih penjelasan yang lebih terperinci untuk materi ke kongruenan gak mbak?


{ RSS feed for comments on this post}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: