Teori Bilangan #2

Algoritma Pembagian

Jika a dan b bilangan bulat, b > 0, ada bilangan bulat q dan r demikian sehingga a = qb + r dengan 0 £  r < b.

Bukti:

Karena b adalah bilangan bulat dan b > 0 maka b ³ 1, sehingga:
- | a | b £ - | a | . 1
- | a | b £ - | a |
- | a | b £ a      hal ini karena b > 0
a - [ - | a | b ] ³ 0
a - x ³ 0 

Jadi terdapat himpunan semua bilangan bulat S yang berbentuk a - x ³ 0 dan tak kosong, karena x = - | a | b memenuhi.

Dengan demikian, menurut WOP, S mengandung bilangan bulat terkecil, sebutlah a – qb dan a – qb ³ 0.

Misalkan a – qb = r, sehingga r ³ 0, maka a = qb + r.

Sekiranya r ³ b maka haruslah r = b + t dengan t ³ 0, sehingga:

a = qb + b + t
a = (q + 1)b + t

a – (q + 1)b = t
Karena t = a – (q + 1)b dan t ³ 0, maka t Î S. Hal ini bertentangan, karena diketahui bilangan bulat terkecil adalah a – qb, sehingga haruslah r < b.

Perluasan Teorema 7 – 1  (Bentuk Umum)

Jika a dan b bilangan bulat, b ≠ 0, maka ada bilangan bulat q dan r demikian sehingga a = qb + r  dengan 0 £ r < | b |.

Keterangan:

Di dalam  a = qb + r dengan 0 £ r < b, masing-masing q dan r tunggal.

(Untuk b < 0, sehingga –b > 0, maka a = q(–b) + r dengan 0 £ r < –b.)

Bukti:

Misalkan

a = q1b + r1  dengan  0 £ r1 < b   dan

a = q2b + r2  dengan  0 £ r2 < b

Akan dibuktikan bahwa q1 = q2  dan  r1 = r2.

Dari nilai a diperoleh:
q1b + r1 = q2b + r2
(q1 - q2)b = r2 - r1              

Tampak bahwa r2 - r1 kelipatan dari b, padahal | r2 - r1 | < | b | = b   (karena b > 0).

Hal ini hanya mungkin terjadi jika r2 - r1 = 0 atau r1 = r2  sehingga:

(q1 - q2)b = 0

q1 - q2 = 0     karena b ≠ 0        

q1 = q2            

Contoh 1

Diketahui a\b dan $c ' a\(b + c).

Buktikan bahwa a\c. 

Bukti:

a\b maka $k ' b = ra                        …………………. (i)

a\(b + c) maka $m ' b + c = ma       …………………. (ii)

Substitusi (i) ke (ii) menghasilkan:

ka + c = ma

c = (m – k)a

\ a\c

Contoh 2

Diketahui a > 0 dan 2 maka, menurut algoritma pembagian, $q dan $r ' a = q.2 + r dengan 0 £ r < 2.

Dalam hal ini r = 0 atau r = 1 sehingga diperoleh:

a = 2q                         (a genap), atau

a = 2q + 1                    (a ganjil)

\ Setiap bilangan bulat positif adalah genap atau ganjil; dan 0 adalah genap karena 0 = 2.0.

_____________________________________________________________________________________________________

Kuliah 2 Teori bilangan oleh Drs. Bachtiar Sjarif, Institut Teknologi Bandung, 30 November 1988

-->