Relasi Keterbagian

Dalam teori bilangan, semesta pembicaraan adalah himpunan semua bilangan bulat yang dinyatakan dengan huruf-huruf latin kecil seperti  a, b, c, dan sebagainya. Salah satu relasi yang menjadi topik utama dalam teori bilangan adalah relasi keterbagian. Beberapa sifat dan relasi yang lain seperti kekongruenan dikembangkan dari masalah keterbagian.

A. RELASI KETERBAGIAN
Perhatikan bentuk-bentuk persamaan berikut:
- 13 = 2 × 5 + 3
- 7   = 2 × 5 + 1
- 18 = 3 × 5 + 3
Secara umum, jika a adalah suatu bilangan bulat dan  b suatu bilangan bulat positif, maka ada tepat satu bilangan bulat q dan r sedemikian sehingga a = qb + r,

0 ≤ r < b.

Bilangan bulat q disebut hasil bagi dan r disebut sisa pembagian. Jika r = 0 maka dikatakan a habis dibagi oleh b dan ditulis b|a. Jika r ≠0 maka ditulis b | a.

Sifat-sifat keterbagian:
1. a | a ( sifat refleksif)
2. a | b dan b | c maka a | c ( sifat transitif)
3. a | b maka a | mb , untuk setiap bilangan bulat m.
4. a | b dan a | c maka a | b + c , a | b – c  atau a | bc
5. ab | c maka b | c dan a | c
6. a | b dan a |c maka a |( bx + by ) untuk setiap bilangan bulat x dan y.

Bukti:
Di sini akan dibuktikan sifat ke -2 dan ke-5.
(2). a | b maka b = ka.   b | c maka c = mb  = m (ka) = ( mk ) a  . Jadi a | c.
(5). ab | c  ⇒ c = (ab) k  =  a ( bk)  ⇒  a | c
       ab | c ⇒ c = (ab) k = (ba)k = b (ak) ⇒ a | c