Teori Bilangan #3

Teorema 8

Setiap S himpunan bilangan bulat yang tak kosong yang tertutup di bawah penjumlahan dan pengurangan hanya terdiri dari bilangan nol semata-mata atau mengandung bilangan bulat positif terkecil m demikian sehingga setiap unsur dari S adalah suatu kelipatan bulat dari m.

Keterangan:

S suatu himpunan tertutup di bawah penjumlahan, berarti jika a, b Î S maka a + b Î S.
S himpunan semua kelipatan bulat dari suatu bilangan bulat m > 0, tertutup di dalam penjumlahan dan pengurangan.
Misalkan,

a Î S maka a = gm
b Î S maka b = hm
sehingga a + b = (g + h)m Î S dan a – b = (g – h)m Î S

Bukti:

Jika S = {0} maka jelas S tertutup di dalam penjumlahan dan pengurangan.

(Akan diselidiki bahwa jika a ≠ 0, a Î S, maka S mengandung bilangan bulat positif terkecil.)

Misalkan a Î S, a ≠ 0 maka a – a = 0 Î S,
0 Î S, a Î S maka 0 – a = –a Î S,
sehingga ada unsur positif | a | Î S, dengan | a | = a atau | a | = –a.
Menurut WOP, S mengandung unsur (bilangan) positif terkecil, sebutlah b.

(Selanjutnya diselidiki apakah a = qb, "a Î S, b bilangan bulat positif terkecil, dan q Î Z. Lebih dulu diselidiki bahwa qb Î S kemudian digunakan algoritma pembagian.)

Dengan menggunakan Induksi Matematika diperoleh:
1.b = b Î S, hal ini benar.
Misalkan nb Î S, maka nb + b = (n + 1)b Î S.
Jadi berlaku nb Î S, "n Î N.

Berikut ini akan ditunjukkan bahwa setiap unsur a Î S merupakan suatu kelipatan bulat dari b.

Sebutlah a = qb + r dengan b > 0 dan 0 £ r < b, sebagaimana dimaksud dalam Algoritma Pembagian, maka:

r = a – qb                  

Dalam hal ini  a Î S dan qb Î S, sehingga r = a – qb Î S.

Sekiranya 0 < r < b, sedangkan r Î S, maka ada bilangan bulat positif r Î S yang lebih kecil dari b.
Ini bertentangan dengan hal di atas.
Jadi haruslah r = 0, sehingga a = qb, suatu kelipatan dari b.

Pembagi Persekutuan Terbesar

Definisi Jika a dan b bilangan bulat maka bilangan bulat d disebut pembagi persekutuan terbesar (PPB) dari a dan b jika dan hanya jika: (i)    d\a (ii)   d\b (iii)  Jika c\a dan c\b maka c\d.

Contoh:

Diketahui dua bilangan 16 dan 24, maka:

2\16 dan 2\24
4\16 dan 4\24
8\16 dan 8\24

sehingga pembagi persekutuan dari 16 dan 24 adalah 2, 4, dan 8, dengan PPB adalah d = 8.

Keterangan:

PPB dari a dan b tersebut adalah tunggal.
Misalkan d₁ dan d₂ masing-masing PPB dari a dan b.
Jika d₁ pembagi persekutuan dari a dan b sedangkan d₂ PPB dari a dan b, maka d₁\d₂   ………………………  (i)
Jika d₂ pembagi persekutuan dari a dan b sedangkan d₁ PPB dari a dan b, maka d₂\d₁   ………………………  (ii)
Berdasarkan (i) dan (ii) maka d₁ = ± d₂  (dalam hal ini nilai mutlaknya sama). Nilai d₁ dan d₂ yang positif adalah tunggal dan kita nyatakan dengan lambing (a, b).

Hal-hal khusus:

(1)   Jika a = 0 dan b = 0 maka keduanya tidak mempunyai PPB.

(2)  Jika a ≠ 0 dan b = 0 maka keduanya mempunyai PPB = a.

(3)  Jika a = 0 dan b ≠ 0 maka keduanya mempunyai PPB = b.

Teorema 9  (Teorema Eksistensi)

Setiap pasang bilangan bulat a ≠ 0 dan b ≠ 0 mempunyai PPB positif (a, b). (a, b) dapat dinyatakan sebagai kombinasi linear dari a dan b dengan koefisien-koefisien bulat s0 dan t0, yaitu (a, b) = s0a + t0b.

Bukti:

Andaikan S himpunan semua bilangan bulat berbentuk sa + tb, dengan a dan b tertentu sedangkan s dan t variabel.

S tidak kosong, karena:
a = 1.a + 0.b, sehingga a Î S
b = 0.a + 1.b, sehingga b Î S
S juga tertutup di bawah penjumlahan dan pengurangan, karena:
jika s₁a + t₁b Î S dan s₂a + t₂b Î S maka (s₁ ± s₂)a + (t₁ ± t₂)b Î S.

Menurut Teorema 8, S mengandung (unsur) bilangan bulat positif terkecil d.
Jadi $s₀, t₀ ' d = s₀a + t₀b.

Juga, menurut Teorema 8, setiap unsur dari S merupakan kelipatan dari d, sehingga a kelipatan dari d, atau d\a, dan b kelipatan dari d, atau d\b. Dengan demikian d pembagi persekutuan dari a dan b.
Misalkan c\a dan c\b, maka c\s₀a + t₀b, atau c\d, sehingga menurut definisi, d adalah PPB dari a.

______________________________________________________________________________________________________

Kuliah 3 Teori bilangan oleh Drs. Bachtiar Sjarif, Institut Teknologi Bandung, 3 Desember 1988

-->