Teori Bilangan #4

Kelipatan Persekutuan Terkecil

Definisi Jika a dan b bilangan bulat maka bilangan bulat m disebut kelipatan persekutuan terkecil (KPK) dari a dan b jika dan hanya jika:  (i)    m = ka (ii)    m = lb (iii)   Jika p = sa dan p = tb maka p = qm.

Keterangan:

Jika a ≠ 0 dan b ≠ 0 maka jelas bahwa ab adalah suatu kelipatan persekutuan dari a dan b, tetapi belum tentu yang terkecil.

Contoh:

Kelipatan persekutuan dari 8 dan 12 adalah 96 = 8 . 12, 72, dan 24.
Jadi kelipatan persekutuan terkecil dari 8 dan 12 adalah 24.

Himpunan S semua kelipatan persekutuan dari dua bilangan bulat a dan b tertutup di bawah penjumlahan dan pengurangan.

Misalkan

a = k₁a = l₁b
b = k₂a = l₂b

maka diperoleh:

a ± b = (k₁ ± k₂)a = (l₁ ± l₂)b

berarti tertutup di bawah penjumlahan dan pengurangan.

Dengan demikian ada unsur positif terkecil m di dalam S demikian sehingga setiap unsur S merupakan kelipatan dari m.

Jelas m suatu kelipatan persekutuan dari a dan b, sekaligus juga sebagai KPK.

  

Teorema 10

Setiap pasang bilangan bulat a ≠ 0 dan b ≠ 0 mempunyai KPK yang dilambangkan dengan m = [a, b].

Teorema  11

Misalkan M = {x | x = [a, b]}, maka M tertutup di bawah penjumlahan dan pengurangan , sehingga M mempunyai bilangan bulat positif terkecil y dengan x = ky, "x Î M.

Untuk mencari PPB dari a dan b dapat digunakan Algoritma Euclides.

ALGORITMA EUCLIDES

Andaikan a ≠ 0 dan b ≠ 0 (dalam hal ini cukuplah tinjauan kita untuk a > 0 dan b > 0).

a = q1 b + r1 dengan 0 £ r1 < b               dalam hal r1 = 0 maka (a, b) = b b = q2 r1 + r2 dengan 0 £ r2 < r1 r1 = q3 r2 + r3 dengan 0 £ r3 < r2 … dan seterusnya rn – 2 = qn rn – 1 + rn rn – 1 = qn + 1 rn + rn + 1

Tampak bahwa r₁ > r₂ > r₃ > … > r_n > r_{n + 1.}

Jika r_{n + 1} = 0 maka r_{n – 1} = q_{n + 1} r_n sehingga (r_{n – 1}, r_n) = r_n, yaitu sisa terakhir yang tidak nol.

Juga (a, b) = (b, r₁) = (r₁, r₂) = … = (r_{n – 2}, r_{n – 1}) = (r_{n – 1}, r_n).

\ (a, b) = (r_{n – 1}, r_n) = r_n.

Kesimpulan:

PPB dari a dan b adalah sisa tak nol yang terakhir di dalam Algoritma Euclides.

Contoh:

Melalui Algoritma Euclides, tentukanlah PPB dari 1308 dan 1842.

Solusi:
1842 = 1 . 1308 + 534

1308 = 2 . 534 + 240
534  = 2 . 240 + 54

240  = 4 . 54   + 24

54    = 2 . 24   + 6
24    = 4 . 6     + 0
\ (1308, 1842) = 6.

Keterangan:

Dengan Algoritma Euclides dapat pula diperlihatkan penulisan d = (a, b) = s₀a + t₀b.

a = q₁ b + r₁     ®        r₁ = a – q₁ b = 1.a + (–q₁)b              

b = q₂ r₁ + r₂   ®        r₂ = b – q₂ r₁ = b – q₂ (a – q₁ b) = (–q₁)a + (q₁ q₂ + 1)b              

… dan seterusnya
                                 r_{n – 1} = …

Contoh:

Perhatikan “langkah terbalik” dari contoh di atas.

6 = 54 – 2 . 24
   = 54 – 2 (240 – 4 . 54)

   = –2 . 240 + 9 . 54
   = –2 . 240 + 9 (534 – 2 . 240)
   = 9 . 534  + (–20) . 240
   = 9 . 534  + (–20) (1308 – 2 . 534)
   = (–20) . 1308 + 49 . 534
   = (–20) . 1308 + 49 (1842 – 1 . 1308)
   = 49 . 1842 + (–69) . 1308

\ 6 = 49 . 1842 + (–69) . 1308.

             ¯      ¯          ¯         ¯

            s₀        a          t₀           b

______________________________________________________________________________________________________

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

-->