Catatan si Jay

Oktober 19, 2010

Faktor Persekutuan Terbesar (FPB) & Kelipatan Persekutuan Terkecil (KPK)

Filed under: Algoritma, Matematika, Teori Bilangan — Hendra Jaya @ 7:34 am

Faktor Persekutuan Terbesar

Faktor Persekutuan Terbesar (FPB) di dalam bahasa Inggris disebut dengan Greatest Common Divisor (GCD). Untuk membiasakan pembaca dengan istilah yang umum dipakai di dalam matematika, artikel ini akan menggunakan GCD alih-alih FPB.

Definisi : GCD dari dua buah bilangan bulat tidak nol a dan b adalah bilangan bulat positif terbesar d yang habis membagi baik a maupun b.
Secara matematis : gcd(a,b)=max\{d|a\text{ dan }d|b,d\in\mathbb{Z_+}\}
Secara komputatif : gcd(a,b)=d

Contoh 1 :
Faktor-faktor positif (positive divisors) dari 12 adalah : 1, 2, 3, 4, 6, 12
Faktor-faktor positif (positive divisors) dari 18 adalah : 1, 2, 3, 6, 9, 18
Faktor bersama (common divisors) dari 12 dan 18 adalah : 1, 2, 3, 6.
Faktor bersama yang paling besar (Greatest Common Divisor) dari 12 dan 18 adalah : 6.
gcd(12,18)=6
gcd(18,12)=6

Pada contoh di atas, 12 dan 18 memiliki beberapa faktor yang sama. Faktor-faktor tersebut adalah 1, 2, 3, dan 6. Dari ke-empat faktor bersama ini, tentu saja ada yang terbesar. Yang terbesar adalah 6. Faktor bersama yang terbesar inilah yang disebut dengan Greatest Common Divisor (GCD). Dalam contoh ini, dapat disimpulkan bahwa gcd(12,18)=6.

Contoh 2 :
Faktor-faktor positif (positive divisors) dari 15 adalah : 1, 3, 5, 15
Faktor-faktor positif (positive divisors) dari 20 adalah : 1, 2, 4, 5, 10, 20
Faktor bersama (common divisors) dari 15 dan 20 adalah : 1, 5
Faktor bersama yang paling besar (Greatest Common Divisor) dari 15 dan 20 adalah : 5.
gcd(15,20)=5
gcd(20,15)=5

Contoh 3 :
Faktor-faktor positif (positive divisors) dari 6 adalah : 1, 2, 3, 6
Faktor-faktor positif (positive divisors) dari 24 adalah : 1, 2, 3, 4, 6, 8, 12, 24
Faktor bersama (common divisors) dari 6 dan 24 adalah : 1, 2, 3, 6
Faktor bersama yang paling besar (Greatest Common Divisor) dari 6 dan 24 adalah : 6.
gcd(6,24)=6
gcd(24, 6)=6

Contoh 4 :
Faktor-faktor positif (positive divisors) dari 10 adalah : 1, 2, 5, 10
Faktor-faktor positif (positive divisors) dari 7 adalah : 1, 7
Faktor bersama (common divisors) dari 10 dan 7 adalah : 1
Faktor bersama yang paling besar (Greatest Common Divisor) dari 10 dan 7 adalah : 1.
gcd(10,7)=1
gcd(7,10)=1

Contoh 5 :
Faktor-faktor positif (positive divisors) dari 15 adalah : 1, 3, 5, 15
Faktor-faktor positif (positive divisors) dari 10 adalah : 1, 2, 5, 10
Faktor bersama (common divisors) dari 15 dan 10 adalah : 1, 5
Faktor bersama yang paling besar (Greatest Common Divisor) dari 15 dan 10 adalah : 5.
gcd(15,10)=5
gcd(10,15)=5

Contoh 6 :
Faktor-faktor positif (positive divisors) dari 4 adalah : 1, 2, 4
Faktor-faktor positif (positive divisors) dari 9 adalah : 1, 3, 9
Faktor bersama (common divisors) dari 4 dan 9 adalah : 1
Faktor bersama yang paling besar (Greatest Common Divisor) dari 4 dan 9 adalah : 1.
gcd(4,9)=1
gcd(9,4)=1

Intermezzo : Pada contoh ke-4 dan ke-6, GCD dari 10 dan 7 dan juga GCD dari 4 dan 9 adalah 1. Di dalam dunia matematika, jika GCD dari dua buah bilangan bulat a dan b bernilai 1 maka  kedua bilangan tersebut dikatakan relatif prima (relatively prime). Ada juga yang menyebutnya koprima (coprime). Blog ini menggunakan istilah koprima. Tentang “mengapa” matematikawan menggunakan istilah relatif prima/koprima, tentu ada sebabnya. Hal itu belum akan kita bahas di artikel ini. Sebagai gambaran saja, hal ini memang erat kaitannya dengan bilangan prima.

Dalam teori himpunan, a dan b dikatakan koprima jika himpunan faktor-faktor a dan himpunan faktor-faktor b saling lepas. Seperti pada gambar berikut :

coprime

Perhatikan bahwa GCD bersifat komutatif, yaitu gcd(a,b)=gcd(b,a). Penulis kira hal ini sudah cukup jelas, sehingga tidak perlu disediakan ruang khusus untuk membahasnya.

Teknik Menghitung GCD

Sebelum masuk ke dalam teknik menghitung GCD. Kita akan mundur sebentar ke dalam algoritma pembagian.

Misalkan gcd(a,b)=d. Sesuai dengan definisi, d pasti habis membagi a dan juga habis membagi b. Jika definisi ini kita tuangkan ke dalam algoritma pembagian, kita akan memperoleh :
a=x.d
b=y.d

Menurut algoritma pembagian, a dapat dituliskan sebagai a=q.b+r. Arti dari persamaan ini adalah “jika a dibagi dengan b, maka kita akan memperoleh sisa bagi (remainder) r yang memenuhi 0\leq r<|b|“.

Dengan men-substitusikan persamaan a=q.b+r, kita memperoleh q.b+r=x.d

Karena kita tahu bahwa b=y.d, kita substitusikan persamaan ini sehingga mendapatkan q.y.d+r=x.d

Tidak perlu diragukan lagi, sisi kanan dari persamaan, yaitu x.d, pasti habis dibagi dengan d. Begitu pula dengan q.y.d.

Lantas, apakah r pasti habis dibagi d? Karena “temannya” r, yaitu q.y.d sudah memberikan kepastian bahwa dia pasti habis dibagi oleh d, maka mau tidak mau r pasti habis juga dibagi d. Karena r habis dibagi oleh d, berarti d adalah divisor (faktor) dari r.

Bagaimana jika d tidak habis membagi r? Itu artinya d bukan gcd dari a dan b (kontradiktif). Habis perkara.

Di paragraf sebelumnya, secara logis kita telah menyimpulkan bahwa d adalah salah satu dari sekian banyak faktor (divisor) dari r. Pertanyaan logis berikutnya adalah “Faktor (divisor) yang mana?”. Lagi-lagi, karena kita bicara soal faktor terbesar (greatest divisor), jawabannya adalah “sebesar mungkin”.

Misalkan r memiliki sekian banyak faktor positif, sebut saja r_1,r_2,r_3,...r_n. Faktor mana yang akan kita pilih? Karena kita berusaha mencari “faktor terbesar yang mungkin”, kita akan lakukan pemeriksaan mulai dari yang paling kanan, yaitu r_n,r_{n-1},...r_3,r_2,r_1. Kita akan memeriksa apakah sebuah faktor, sebut saja r_i, habis membagi b.

Pemeriksaan berakhir jika r_i alias d terbukti habis membagi b.

Mengapa hanya b? Mengapa a tidak? Kita hanya memeriksa b karena itu sudah cukup (syarat cukup) untuk menjamin bahwa a juga pasti habis dibagi oleh d. Penjelasannya adalah sebagai berikut :

Perhatikan persamaan q.b+r=a.

Karena r_i adalah faktor dari r, maka kita boleh menulis persamaan di atas menjadi q.b+n.r_i=a. Tidak perlu pusing dengan variabel-variabel “dummy” seperti q dan n. Kita tidak tertarik untuk membahasnya.

Sekarang, jika r_i habis membagi b, maka persamaan dapat kita tulis ulang menjadi q.m.r_i+n.r_i=a. Sekali lagi, abaikan semua variabel-variabel tidak penting seperti q, m dan n.

Dengan memanfaatkan sifat distributif perkalian, kita memperoleh r_i.(q.m+n)=a.

Nah, sekarang jelas terlihat bahwa a juga pasti habis dibagi oleh r_i. Dengan demikian, pemeriksaan terhadap b sudah cukup (syarat cukup) untuk meyakinkan kita bahwa a tidak perlu diperiksa lagi.

Hal ini sangat menarik. Pemeriksaan yang kita lakukan di beberapa paragraf sebelumnya sebenarnya mencari faktor bersama (common divisor) yang habis membagi baik r, maupun b. Karena pemeriksaan dilakukan dari “kanan”, maka r_i yang memenuhi kriteria ini pastilah faktor bersama yang terbesar (greatest common divisor) yang dimiliki baik oleh r, maupun oleh b.

Apa yang sebenarnya kita lakukan di beberapa paragraf sebelumnya adalah mencari GCD dari r dan b. Aneh bukan? Memang benar bahwa di awal sekali, kita ingin mencari GCD dari a dan b. Tetapi, analisa matematika membuktikan bahwa GCD dari a dan b sebenarnya sama dengan GCD dari r dan b. Dimana r adalah sisa bagi a oleh b :

\begin{array}{ccl} gcd(a, b)& =& gcd(r, b) \\ gcd(a, b)& =& gcd(b, r) \\ gcd(a, b)& =& gcd(b, mod(a, b)) \end{array}

Fenomena ini pertama kali diamati oleh Euclid sekitar 2300 tahun yang lalu dan sampai saat ini masih dipelajari di sekolah-sekolah dan kampus-kampus di seluruh dunia.

Teknik pencarian GCD dari a dan b yang diajukan oleh Euclid adalah sebagai berikut :

  1. Jika b=0, maka GCD dari a dan b adalah a.
  2. Jika b\neq 0, maka :
    1. Carilah r, yaitu sisa bagi a oleh b.
    2. Anggap b sebagai a dan r sebagai b.
    3. Kembali ke step 1

Contoh 1 (lagi) : Menghitung gcd(12,18)

  • a = 12, b = 18.
  • Karena 18 \neq 0, maka :
  • 12 = 0.18 + 12, sehingga r = 12.
    • a = 18, b = 12
    • Karena 12 \neq 0, maka :
    • 18 = 1.12 + 6, sehingga r = 6
      • a = 12, b = 6
      • Karena 6 \neq 0, maka :
      • 12 = 2.6 + 0, sehingga r = 0
        • a = 6, b = 0
        • Karena 0 = 0, maka hasilnya adalah 6.

Secara grafis :

gcd

Contoh 2 (lagi) : Menghitung gcd(15, 20)

  • a = 15, b = 20.
  • Karena 20 \neq 0, maka :
  • 15 = 0.20 + 15, sehingga r = 15.
    • a = 20, b = 15
    • Karena 15 \neq 0, maka :
    • 20 = 1.15 + 5, sehingga r = 5
      • a = 15, b = 5
      • Karena 5 \neq 0, maka :
      • 15 = 3.5 + 0, sehingga r = 0
        • a = 5, b = 0
        • Karena 0 = 0, maka hasilnya adalah 5.

Secara grafis :

gcd

Contoh 3 (lagi) : Menghitung gcd(6, 24)

  • a = 6, b = 24.
  • Karena 24 \neq 0, maka :
  • 6 = 0.24 + 6, sehingga r = 6.
    • a = 24, b = 6
    • Karena 6 \neq 0, maka :
    • 24 = 4.6 + 0, sehingga r = 0
      • a = 6, b = 0
      • Karena 0 = 0, maka hasilnya adalah 6.

Secara grafis :

gcd

Contoh 4 (lagi) : Menghitung gcd(10, 7)

  • a = 10, b = 7.
  • Karena 7 \neq 0, maka :
  • 10 = 1.7 + 3, sehingga r = 3.
    • a = 7, b = 3
    • Karena 3 \neq 0, maka :
    • 7 = 2.3 + 1, sehingga r = 1
      • a = 3, b = 1
      • Karena 1 \neq 0, maka :
      • 3 = 3.1 + 0, sehingga r = 0
        • a = 1, b = 0
        • Karena 0 = 0, maka hasilnya adalah 1.

Secara grafis :

gcd

Contoh 5 (lagi) : Menghitung gcd(15, 10)

  • a = 15, b = 10.
  • Karena 10 \neq 0, maka :
  • 15 = 1.10 + 5, sehingga r = 5.
    • a = 10, b = 5
    • Karena 5 \neq 0, maka :
    • 10 = 2.5 + 0, sehingga r = 0
      • a = 5, b = 0
      • Karena 0 = 0, maka hasilnya adalah 5.

Secara grafis :

gcd

Contoh 6 (lagi) : Menghitung gcd(4, 9)

  • a = 4, b = 9.
  • Karena 9 \neq 0, maka :
  • 4 = 0.9 + 4, sehingga r = 4.
    • a = 9, b = 4
    • Karena 4 \neq 0, maka :
    • 9 = 2.4 + 1, sehingga r = 1
      • a = 4, b = 1
      • Karena 1 \neq 0, maka :
      • 4 = 4.1 + 0, sehingga r = 0
        • a = 1, b = 0
        • Karena 0 = 0, maka hasilnya adalah 1.

Secara grafis :

gcd

Better Luck Next Year

Satu pertanyaan yang paling sering dilontarkan adalah : “Mengapa b dianggap a dan r dianggap b?”.

Sebenarnya, teknik asli yang dilontarkan oleh Euclid mengharuskan a \geq b. Jika ternyata ditemukan bahwa a < b, maka Euclid mengharuskan kedua bilangan itu dipertukarkan. Ingat bahwa gcd adalah sebuah fungsi yang komutatif dimana gcd(a,b)=gcd(b,a) sehingga mempertukarkan posisi a dengan b tidak akan mengubah hasil perhitungan.

Akan tetapi, dengan majunya ilmu komputasi, “penganggapan” b sebagai a dan r sebagai b, terbukti lebih efisien karena kita tidak perlu pusing-pusing memeriksa apakah a \geq b.
Hal ini dapat dijelaskan melalui algoritma pembagian yang telah memberikan kepastian bahwa 0\leq r<|b|. Sehingga, step untuk memeriksa invarian (relasi) a\geq b tidak perlu dilakukan lagi.

Bagaimana jika salah satu atau keduanya dari a dan b adalah bilangan negatif?

Hal ini juga sangat sering ditanyakan. Pembahasan tentang pertanyaan ini akan kita tunda dulu. Pembahasan lengkapnya akan kita bahas di artikel “Sifat-sifat GCD dan LCM”. Ide utamanya adalah bilangan negatif merupakan suatu perkalian bilangan positif dengan -1.

Kelipatan Persekutuan Terkecil

Kelipatan Persekutuan Terkecil (KPK) di dalam bahasa Inggris dikenal dengan nama Least Common Multiple (LCM). Sama seperti GCD, blog ini akan membiasakan pembaca untuk menggunakan istilah yang lazim dipakai. Oleh karena itu blog ini akan menggunakan istilah LCM.

Definisi : LCM dari dua buah bilangan bulat a dan b adalah bilangan bulat positif terkecil yang merupakan kelipatan bersama dari a dan b.
Secara matematis : lcm(a,b)=\frac{|a.b|}{gcd(a, b)}
Secara komputatif : lcm(a, b)=\frac{abs(a.b)}{gcd(a, b)}
Catatan : definisi asli dari LCM menggunakan “bilangan rasional”. Artikel ini menyederhanakan definisi tersebut ke dalam “bilangan bulat” agar lebih mudah dipahami.

Contoh 1 :
Kelipatan (multiple) dari 12 adalah : 12, 24, 36, 48, 60, 72, 84, 96, 108, …
Kelipatan (multiple) dari 18 adalah : 18, 36, 54, 72, 90, 108, …
Kelipatan bersama (common multiple) dari 12 dan 18 adalah : 36, 72, 108, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 12 dan 18 adalah : 36.
lcm(12,18)=36
lcm(18,12)=36

Pada contoh di atas, 12 dan 18 memiliki banyak kelipatan yang sama. Kelipatan-kelipatan tersebut adalah 36, 72, 108, …. Dari semua kelipatan-kelipatan ini, yang terkecil adalah 36. Kelipatan bersama yang terkecil inilah yang disebut dengan Least Common Multiple (LCM). Dalam contoh ini, terlihat bahwa lcm(12,18)=36.

Contoh 2 :
Kelipatan (multiple) dari 15 adalah : 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, 165, 180, 195, …
Kelipatan (multiple) dari 20 adalah : 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, …
Kelipatan bersama (common multiple) dari 15 dan 20 adalah : 60, 120, 180, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 15 dan 20 adalah : 60.
lcm(15,20)=60
lcm(20,15)=60

Contoh 3 :
Kelipatan (multiple) dari 6 adalah : 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, …
Kelipatan (multiple) dari 24 adalah : 24, 48, 72, 96, 120, 144, 168, 192, …
Kelipatan bersama (common multiple) dari 6 dan 24 adalah : 24, 48, 72, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 6 dan 24 adalah : 24.
lcm(6,24)=24
lcm(24,6)=24

Contoh 4 :
Kelipatan (multiple) dari 10 adalah : 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 160, 170, 180, 190, 200, 210, …
Kelipatan (multiple) dari 7 adalah : 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 105, 112, 119, 126, 133, 140, 147, …
Kelipatan bersama (common multiple) dari 10 dan 7 adalah : 70, 140, 210, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 10 dan 7 adalah : 70.
lcm(10,7)=70
lcm(7,10)=70

Contoh 5 :
Kelipatan (multiple) dari 15 adalah : 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, …
Kelipatan (multiple) dari 10 adalah : 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, …
Kelipatan bersama (common multiple) dari 15 dan 10 adalah : 30, 60, 90, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 15 dan 10 adalah : 30.
lcm(15,10)=30
lcm(10,15)=30

Contoh 6 :
Kelipatan (multiple) dari 4 adalah : 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, …
Kelipatan (multiple) dari 9 adalah : 9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99, 108, 117, 126, …
Kelipatan bersama (common multiple) dari 4 dan 9 adalah : 36, 72, 108, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 4 dan 9 adalah : 36.
lcm(4,9)=36
lcm(9,4)=36

Sama seperti GCD, LCM juga bersifat komutatif (dapat dipertukarkan tanpa mengurangi kebenarannya). Yaitu lcm(a,b)=lcm(b,a).

Secara matematis, untuk menghitung LCM dari dua buah bilangan bulat a dan b dapat dilakukan dengan mengikuti rumus lcm(a,b)=\frac{|a.b|}{gcd(a,b)}
Hal ini sangat mudah dilakukan karena sebelumnya kita telah mengetahui teknik pencarian gcd(a,b) ala Euclid.

Secara komputatif, untuk menghitung LCM dilakukan dengan invarian lcm(a,b)=\frac{abs(a.b)}{gcd(a,b)}

Contoh 1 (lagi) :
lcm(12,18)=\frac{|12.18|}{gcd(12,18)}=\frac{216}{6}=36

Contoh 2 (lagi) :
lcm(15,20)=\frac{|15.20|}{gcd(15,20)}=\frac{300}{5}=60

Contoh 3 (lagi) :
lcm(6,24)=\frac{|6.24|}{gcd(6,24)}=\frac{144}{6}=24

Contoh 4 (lagi) :
lcm(10,7)=\frac{|10.7|}{gcd(10,7)}=\frac{70}{1}=70

Contoh 5 (lagi) :
lcm(15,10)=\frac{|15.10|}{gcd(15,10)}=\frac{150}{5}=30

Contoh 6 (lagi) :
lcm(4,9)=\frac{|4.9|}{gcd(4,9)}=\frac{36}{1}=36

Sebenarnya penulis tidak terlalu tertarik untuk membahas asal muasal datangnya rumus LCM ini. Tetapi, untuk mengantisipasi keingintahuan pembaca. Berikut akan dipaparkan asal muasal rumus LCM.

Misalkan gcd(a,b)=d dan lcm(a,b)=e.
Maka a dan b bisa ditulis ulang menjadi :

a=x.d

b=y.d

gcd(x,y)=1

Intermezzo : Mengapa gcd(x,y)=1?
Untuk menjawabnya, penulis akan membuktikan dengan metode kontradiktif. Asumsikan gcd(x,y)=n, dimana n>1. Sehingga :

x=t.n

y=u.n

akibatnya,

a=x.d=t.n.d

b=y.d=u.n.d

dan dengan demikian, gcd(a,b)=n.d

Kalimat di atas secara langsung mengatakan bahwa GCD dari a dan b bukanlah d, melainkan n.d. Dimana n.d>d karena n>1.
Suatu kontradiktif yang mengakibatkan asumsi kita salah.

Dengan demikian gcd(x,y) haruslah 1. Dalam diagram venn dinyatakan sebagai himpunan yang saling lepas.

Sekarang kita lanjutkan ke pembahasan asal muasal rumus LCM…

Nilai e terkecil yang habis membagi x.d dan y.d adalah x.y.d. Mengapa x.y.d? Sukar untuk dijelaskan dengan kata-kata. Biarkan diagram venn di bawah ini yang berbicara :D

x adalah yang berwarna cyan (telor asin)

d adalah yang berwarna pink (merah jambu)

y adalah yang berwarna purple (ungu)

lcm

Nilai e setidak-tidaknya harus dapat membagi x, y, dan d. Sehingga e haruslah merupakan perkalian ketiganya, yaitu x.y.d

\begin{array}{lll}lcm(a,b)&=&x.y.d\\&=&\frac{x.y.d^2}{d}\\&=&\frac{x.d.y.d}{gcd(a,b)}\\&=&\frac{a.b}{gcd(a,b)}\end{array}

Mengingat lcm(a,b) adalah bilangan bulat positif, maka sisi kanan haruslah positif juga.

Karena penyebut dari sisi kanan, yaitu gcd(a,b), pasti bilangan positif, maka ke-positif-an pembilangnya harus dipastikan dengan fungsi abs(x).

\therefore lcm(a,b)=\frac{abs(a.b)}{gcd(a,b)}

Obat Ngantuk

  1. BintangBintang Rancanglah algoritma untuk mencari GCD dari himpunan bilangan bulat S={a,b,c,d,...}, dimana |S|\geq 2.
    Notasi |S| menyatakan kardinalitas (jumlah elemen) dari himpunan.
  2. BintangBintang Rancanglah algoritma untuk mencari LCM dari himpunan bilangan bulat S={a,b,c,d,...}, dimana |S|\geq 2.
    Notasi |S| menyatakan kardinalitas (jumlah elemen) dari himpunan.

You Don't Trust Management

Oktober 18, 2010

Obat Ngantuk Konsep Modulus 1

Filed under: Matematika, Puzzle, Teori Bilangan — Hendra Jaya @ 5:29 am

Problem

Buktikan bahwa {2222}^{5555}+{5555}^{2222} habis dibagi 7.

Sumber : Seleksi Tim Olimpiade Matematika Indonesia 1997

Pra-Pembahasan 1

Menurut algoritma pembagian, a=d.q+r dengan 0\leq r<|d|
Jika kita nyatakan sisa pembagian a oleh d sebagai mod(a,d) maka r=mod(a,d)

Salah satu sifat dalam fungsi mod(a, d) adalah sifat distributif-asosiatif, sebagai berikut:

\begin{array}{clllclcr}a&=&d&.&q_1&+&r_1\\b&=&d&.&q_2&+&r_2\\---&-&-&-&----&-&----&+\\a+b&=&d&.&(q_1+q_2)&+&(r_1+r_2)\end{array}

Karena r_1+r_2 mungkin lebih besar dari d, maka :

r_1+r_2=d.q_3+r_3

Sehingga

\begin{array}{lllllll}a+b&=&d&.&(q_1+q_2)&+&(r_1+r_2)\\a+b&=&d&.&(q_1+q_2)&+&d.q_3+r_3\\a+b&=&d&.&(q_1+q_2+q_3)&+&r_3\end{array}

Sekarang, karena

r_1=mod(a,d)
r_2=mod(b,d)
r_3=mod(a+b,d) dan
r_3=mod(r_1+r_2,d)

Maka mod(a+b,d)=mod(mod(a,d)+mod(b,d), d)
Dengan cara yang sama juga kita peroleh mod(a.b,d)=mod(mod(a,d).mod(b,d), d).

Perhatikan bahwa dalam algoritma pembagian, a dikatakan habis dibagi oleh d jika dan hanya jika r=0 atau mod(a,d)=0.

Pra-Pembahasan 2

Menurut Binomial Newton :

\begin{array}{lll}a&=&d.q+r\\a^b&=&(d.q+r)^b\\a^b&=&k_0.d^b.q^b.r^0+k_1.d^{b-1}.q^{b-1}.r^1+k_2.d^{b-2}.q^{b-2}.r^2+...+k_{b-2}.d^2.q^2.r^{b-2}+k_{b-1}.d^1.q^1.r^{b-1}.q+k_b.d^0.q^0.r^b\\a^b&=&k_0.d^b.q^b.r^0+k_1.d^{b-1}.q^{b-1}.r^1+k_2.d^{b-2}.q^{b-2}.r^2+...+k_{b-2}.d^2.q^2.r^{b-2}+k_{b-1}.d^1.q^1.r^{b-1}.q+k_b.r^b\end{array}

Semua suku, kecuali suku ke-b (terakhir), memiliki d sebagai faktor.
Ini memberikan kita kesimpulan bahwa semua suku, kecuali suku ke-b, habis dibagi oleh d.

Karena semua suku, kecuali suku ke-b, habis dibagi oleh d, maka sisa pembagian a^b oleh d bergantung sepenuhnya kepada suku ke-b.

Nilai dari suku ke-b adalah :

\begin{array}{llll}U(b)&=&k_b.r^b\\U(b)&=&C(b,b).r^b\\U(b)&=&1.r^b\\U(b)&=&r^b\end{array}

Dengan demikian sisa bagi a^b oleh d bergantung sepenuhnya kepada r^b dimana r adalah sisa bagi a oleh d. Secara matematis :

\begin{array}{lllclllr}a&=&d.q_1+r&\text{ alias }&a&\equiv&r&\text{(modulo d)}\\a^b&=&d.q_2+r^b&\text{ alias }&a^b&\equiv&r^b&\text{(modulo d)}\end{array}

Pembahasan

Sisa bagi {2222}^{5555}+{5555}^{2222} oleh 7 dapat dinyatakan sebagai :

mod({2222}^{5555}+{5555}^{2222},7)=mod(mod({2222}^{5555},7)+mod({5555}^{2222},7),7)

Bagian 1 : Mencari nilai mod({2222}^{5555},7) :

Karena

{2222}^{5555}={(7.317+3)}^{5555}

Maka

mod({2222}^{5555},7)=mod({3}^{5555},7)

Karena

\begin{array}{lll}{3}^{5555}&=&3.{3}^{5554}\\&=&3.{(3^2)}^{2777}\\&=&3.{9}^{2777}\\&=&3.{(7.1+2)}^{2777}\end{array}

Maka

mod({3}^{5555},7)=mod(3.mod({2}^{2777},7),7)

Karena

\begin{array}{lll}{2}^{2777}&=&{2}^{2}.{2}^{2775}\\&=&4.{(2^3)}^{925}\\&=&4.{(2^3)}^{925}\\&=&4.{8}^{925}\\&=&4.{(7.1+1)}^{925}\end{array}

Maka

\begin{array}{lll}mod({2}^{2777},7)&=&mod(4.mod({1}^{925},7),7)\\&=&mod(4.mod(1,7),7)\\&=&mod(4.1,7)\\&=&mod(4,7))\\&=&4\end{array}

Sehingga

\begin{array}{lll}mod({3}^{5555},7)&=&mod(3.mod({2}^{2777},7),7)\\&=&mod(3.4,7)\\&=&mod(12,7)\\&=&5\end{array}

Sehingga

\begin{array}{lll}mod({2222}^{5555},7)&=&mod({3}^{5555},7)\\&=&5\end{array}

Bagian 2 : Mencari nilai mod({5555}^{2222},7) :

Karena

{5555}^{2222}={(7.793+4)}^{2222}

maka

mod({5555}^{2222},7)=mod({4}^{2222},7)

Karena

\begin{array}{lll}{4}^{2222}&=&4^2.{4}^{2220}\\&=&16.{(4^3)}^{740}\\&=&16.{64}^{740}\\&=&16.{(7.9+1)}^{740}\end{array}

maka

\begin{array}{lll}mod({4}^{2222},7)&=&mod(16.mod({1}^{740},7),7)\\&=&mod(16.mod(1,7),7)\\&=&mod(16.1,7)\\&=&mod(16,7)\\&=&2\end{array}

Sehingga

\begin{array}{lll}mod({5555}^{2222},7)&=&mod({4}^{2222},7)\\&=&2\end{array}

Kesimpulan

\begin{array}{lll}mod({2222}^{5555}+{5555}^{2222},7)&=&mod(mod({2222}^{5555},7)+mod({5555}^{2222},7),7)\\&=&mod(5+2,7)\\&=&mod(7,7)\\&=&0\end{array}

Dengan demikian sisa bagi dari {2222}^{5555}+{5555}^{2222} oleh 7 adalah 0. Alias {2222}^{5555}+{5555}^{2222} habis dibagi oleh 7.

Mathematician Steroids

September 24, 2010

Konsep Modulus dan Kekongruenan Bilangan

Filed under: Matematika, Teori Bilangan — Hendra Jaya @ 7:37 am

Di setiap jam dinding yang normal, ada terdapat 12 angka. Yaitu 1, 2, 3, 4, … 12. Pada jam digital, angka 12 diganti dengan angka 0. Sehingga angka-angka yang tersedia adalah 0, 1, 2, 3 … 11. Walaupun jam digital bisa di-setting sehingga menunjukkan angka 0, 1, 2, 3 … 23, banyak orang lebih memilih memakai setting 12-jam, yaitu 0, 1, 2, 3, .. 11. Begitu pula para matematikawan. Mereka lebih suka memakai angka 0, 1, 2, 3, … 11. Jangan tanya kenapa.

Di dalam artikel ini, semua jam akan mengikuti sistem 12-jam ala matematikawan, yaitu jam dinding dengan angka 0, 1, 2, 3 … 11. Angka 0 berada di posisi angka 12. Agara lebih mudah dipahami, perhatikan gambar berikut :

jam dinding

  1. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Dalam 8 jam mendatang, ke angka berapakah jarum jam akan menunjuk?
  2. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Dalam 20 jam mendatang, ke angka berapakah jarum jam akan menunjuk?
  3. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Dalam 32 jam mendatang, ke angka berapakah jarum jam akan menunjuk?
  4. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Empat jam yang lalu, di angka berapakah jarum jam menunjuk?
  5. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Enam belas jam yang lalu, di angka berapakah jarum jam menunjuk?
  6. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Dua puluh delapan jam yang lalu, di angka berapakah jarum jam menunjuk?

Jawaban atas seluruh pertanyaan di atas adalah di angka 8. Sekarang akan kita cari tahu kenapa hal ini bisa terjadi.

Identitas dan Simbol

Kita tahu bahwa dalam 12 jam, jarum jam akan kembali ke posisinya semula, yaitu 0. Kita katakan bahwa jarum jam akan membutuhkan 12 jam untuk melakukan satu “putaran penuh”. Dengan kata lain, satu putaran penuh = 12 jam.

Sekarang, seperti layaknya kebiasaan di dunia matematika yang membosankan, akan kita lakukan ritual simbolisasi.
a menyatakan waktu. Untuk masa lalu diberi tanda negatif (-) dan untuk masa yang akan datang tidak diberi tanda, alias positif (+).
q menyatakan banyaknya putaran
d menyatakan waktu yang diperlukan untuk melakukan satu “putaran penuh”. Dengan demikian d = 12.
r menyatakan sisa waktu setelah berputar-putar.

Pembahasan

  1. Waktu yang dimiliki adalah 8 jam (di masa yang akan datang). Dengan demikian a = 8.
    Dalam 8 jam, jarum jam belum melakukan satu kalipun putaran penuh. Dengan demikian q = 0.
    Karena dalam 8 jam si jarum belum berputar sama sekali, maka sisa waktunya tetap 8 jam. Dengan demikian r = 8.
    Secara matematis dapat dituliskan 8 = 0.12 + 8
  2. Waktu yang dimiliki adalah 20 jam (di masa yang akan datang). Dengan demikian a = 20.
    Dalam 20 jam, jarum jam melakukan satu kali putaran penuh. Dengan demikian q = 1.
    Karena jarum jam berputar satu kali, maka waktu yang sudah dikonsumsi untuk berputar adalah 12 jam. Sisanya adalah 8 jam. Dengan demikian r = 8.
    Secara matematis dapat dituliskan 20 = 1.12 + 8
  3. Waktu yang dimiliki adalah 32 jam (di masa yang akan datang). Dengan demikian a = 32.
    Dalam 32 jam, jarum jam melakukan dua kali putaran penuh. Dengan demikian q = 2.
    Karena jarum jam berputar dua kali, maka waktu yang habis untuk berputar-putar adalah 24 jam. Sisanya adalah 8 jam. Dengan demikian r = 8.
    Secara matematis dapat dituliskan 32 = 2.12 + 8
  4. Waktu yang dimiliki adalah 4 jam (di masa lampau). Dengan demikian a = -4.
    Dalam 4 jam (ke belakang), jarum jam belum melakukan satu kalipun putaran penuh. Dengan demikian q = 0.
    Karena dalam 4 jam (ke belakang) si jarum belum berputar sama sekali, maka sisa waktunya tetap 4 jam. Dengan demikian r = -4 (perhatikan tanda negatif).
    Secara matematis dapat dituliskan -4 = 0.12 + -4
    Karena jam kita tidak memiliki angka -4, maka kita harus mengubahnya menjadi suatu angka yang “dikenali” oleh jam kita. Karena kita tahu dalam 12 jam, si jarum pasti akan kembali ke posisinya semula, maka jam -4 akan menunjukkan angka yang sama dengan jam -4 + 12 alias 8. Dengan demikian, jarum jam di pukul -4.00 akan menunjukkan angka 8.
  5. Waktu yang dimiliki adalah 16 jam (di masa lampau). Dengan demikian a = -16.
    Dalam 16 jam (yang lalu), jarum jam telah berputar sebanyak satu kali. Dengan demikian q = -1 (perhatikan tanda negatif).
    Karena dalam 16 jam silam si jarum telah berputar sebanyak satu kali, maka sisa waktu yang dimilikinya adalah 4 jam. Dengan demikian r = -4 (perhatikan tanda negatif).
    Secara matematis dapat dituliskan -16 = -1.12 + -4
    Sama seperti di soal sebelumnya, kita harus mengubah angka -4 menjadi suatu angka yang “dikenali” oleh jam kita, yaitu dengan menambahkan 12 jam “khayal”. Setelah ditambahkan 12 jam “khayal” ini, jarum jam akan menunjukkan pukul 8.
  6. Waktu yang dimiliki adalah 28 jam (di masa lampau). Dengan demikian a = -28.
    Dalam tempo 28 jam (yang lalu), jarum jam telah berputar sebanyak dua kali. Dengan demikian q = -2 (perhatikan tanda negatif).
    Karena dalam 28 jam yang lalu si jarum telah berputar sebanyak dua kali, maka sisa waktu yang dimilikinya adalah 4 jam. Dengan demikian r = -4 (perhatikan tanda negatif).
    Secara matematis dapat dituliskan -28 = -2.12 + -4
    Sama seperti sebelum-sebelumnya, kita harus mengubah angka -4 menjadi suatu angka yang “dikenali” oleh jam kita, yaitu dengan menambahkan 12 jam “khayal”. Setelah ditambahkan 12 jam “khayal” ini, jarum jam akan menunjukkan pukul 8.

Kekongruenan Bilangan

Hal yang menarik dari kasus ini adalah : Dalam 8 jam ataupun 20 jam ataupun 32 jam ke depan, maupun dalam 4 jam ataupun 16 jam ataupun 28 jam ke belakang, semuanya akan menunjuk ke angka yang sama. Yaitu angka 8.

Fenomena ini, di dalam dunia matematika, diberi nama kongruen.
Definisi 1 : Bilangan bulat a dan bilangan bulat b dikatakan kongruen dalam modulo n jika dan hanya jika keduanya memberikan sisa bagi yang sama ketika dibagi dengan n, dimana a, b, n \in \mathbb{Z}. Secara simbolik dinyatakan dengan a \equiv b \ (mod \ n).

Sekarang, karena a = {q}_{1}.n + r dan b = {q}_{2}.n + r, maka dengan melakukan operasi pengurangan kita memperoleh a - b = {q}_{1}.n - {q}_{2}.n. Dengan memanfaatkan sifat distributif pada perkalian, kita mendapatkan a - b = ({q}_{1} - {q}_{2}).n. Sampai disini, kita dapat menyimpulkan bahwa a – b pasti habis dibagi oleh n. Atau secara simbolis dinyatakan dengan n | a - b.

Dari penjabaran di atas, kekongruenan pun dapat diberi definisi yang lain.
Definisi 2 : Bilangan bulat a dan bilangan bulat b dikatakan kongruen dalam modulo n jika dan hanya jika a – b habis dibagi oleh n. Secara matematis : a \equiv b\ (mod \ n) \leftrightarrow n | a - b.

Menurut definisi 1 dari kekongruenan : 8, 20, 32, -4, -16, -28 adalah kongruen dalam modulo 12 karena semuanya memberikan sisa bagi yang sama. Sisa bagi dalam keenam soal di atas ditandai dengan “kemana jarum jam menunjuk”.
Menurut definisi 2 dari kekongruenan : Ambil dua buah bilangan, terserah yang mana, di antara 8, 20, 32, -4, -16 dan -28. Selisih kedua bilangan tersebut pasti habis dibagi oleh 12.

Jika kita tinjau lagi identitas “jam khayal” pada pembahasan di atas, sebenarnya secara implisit kita telah menyatakan bahwa a \equiv q.12 + a\ (mod\ 12) . Untuk sembarang a, q \in \mathbb{Z}

Di dalam teori bilangan matematika, modulus adalah “bilangan pembagi”. Pada bilangan jam, modulus-nya adalah 12. Dan “mod” bukanlah sebuah fungsi ataupun operator, tetapi menyatakan “di modulus berapa dua buah bilangan dinyatakan kongruen”.

Konsep ini agak abstrak. Tetapi bayangkan jika kita memiliki jam dinding yang hanya memiliki angka 0, 1, dan 2. Jam dinding ini secara matematis dikatakan modulus 3. Selanjutnya, jika kita mulai dari 0, maka 17 dan 11 dalam jam dinding “yang aneh ini” sama-sama akan menunjuk angka 2. Dan (lagi-lagi) secara matematis dikatakan 17 \equiv 11 \ (mod \ 3), yaitu 17 dan 11 kongruen di dalam modulus 3.

Di dalam ilmu komputasi, fungsi mod(x, y) ataupun operator binary mod, dapat dikatakan (walaupun kurang tepat) sebagai fungsi yang mencari sisa pembagian x oleh y. Tolong diingat baik-baik bahwa algoritma pembagian euclid adalah algoritma yang matematis, bukan komputatif. Sehingga mungkin memberikan hasil yang berbeda dengan hasil perhitungan (kalkulasi) komputatif.

Untuk memperjelas maksud saya, perhatikan contoh ini :
Menurut kalkulator : \frac {-17}{12} = -1.41666 = -15/12
Menurut algoritma pembagian : -17 = -2.12 + 7

Mengapa hasil pembagian oleh algoritma pembagian berbeda dengan hasil yang sebenarnya? Jawaban yang paling mudah adalah dengan menyalahkan tanda negatif (-) yang membingungkan. Tetapi ada penjelasan yang lain.

Jika mengikuti hasil perhitungan kalkulator, maka algoritma pembagian dapat menyatakan -17 \div 12 sebagai -17 = -1.12 -5. Hasil ini benar (secara komputatif) tetapi tidak masuk akal di dalam matematika. Mengapa tidak masuk akal? Karena di dalam jam dinding 12-jam seperti yang ada di rumah-rumah, tidak ada angka -5. Hal ini sejalan dengan algoritma pembagian yang memberikan syarat 0 \leq r < |d|.

Sama seperti soal-soal sebelumnya, trik yang kita lakukan untuk mengubah angka -5 menjadi angka yang benar adalah dengan menambahkan “putaran-putaran khayal”. Sehingga, -17 = -1.12 -5 + 1212.
Yang biru adalah putaran khayal.
Yang merah adalah “pengimpas”. Hal ini harus dilakukan agar tidak mengubah dividen (dividen : bilangan yang dibagi). Ingat bahwa 12 – 12 = 0.

Sekarang, dengan menggabungkan -5 dan 12 serta menggabungkan -12 dengan -1.12 kita peroleh
-17 = -1.12 – 12 + (-5 + 12)
-17 = -2.12 + 7

Di dalam bentuk ini, dapat dikatakan bahwa -17 (17 jam yang lalu) dalam jam dinding menunjuk angka 7. Angka 7 ini pula-lah yang dimaksud dengan remainder (sisa bagi) r pada algoritma pembagian euclid. Perhatikan bahwa sekarang r telah memenuhi konstrain 0 \leq r < |d|.

Ada penjelasannya mengapa para matematikawan tidak terlalu tertarik dengan quotient (hasil bagi) q. Mereka jauh lebih tertarik dengan r. Penjelasan itu nanti akan kita pahami pada saat berdiskusi tentang teori bilangan yang lainnya. Sebagai konsekuensi atas “ketidaktertarikan” mereka, angka -2 yang keliru ini diabaikan begitu saja :)

Ingat baik-baik bahwa algoritma pembagian euclid bukan untuk menghitung (to compute) hasil akhir. Melainkan sebagai senjata untuk menyelesaikan persoalan di teori bilangan yang lain.

Sifat-sifat Dasar Kekongruenan

Jika diketahui : a \equiv b \ (mod \ n) dan p \equiv q \ (mod \ n)
Berlaku (semacam operasi pembagian) : a + p \equiv b + q \ (mod \ n)
Berlaku (semacam operasi perkalian) : ap \equiv bq \ (mod \ n)

Asal muasal datangnya kedua sifat tersebut adalah sebagai berikut :

Karena a \equiv b \ (mod \ n), maka n | a - b. Dalam bentuk yang lain dapat dituliskan : a - b = n.x.

Begitu pula  p \equiv q \ (mod \ n). Kekongruenan p dan q ini dapat dituliskan ke dalam bentuk p - q = n.y

Jika dikenakan operasi penjumlahan :

\begin{array}{lcccr} & a - b& =& n.x \\ & p - q& =& n.y \\ & ------& &------& +\\ & (a - b) + (p - q)& =& n.x + n.y \\ & (a + p) - (b + q)& =& n(x + y) \\ \therefore& a+p& \equiv& b+q \ (mod \ n) \end{array}

Sekarang, karena :

\begin{array}{cccr} a - b& =& n.x \\ q(a - b)& =& q.n.x& \text{dimana } q \neq 0 \end{array}

Begitu juga :

\begin{array}{cccr} p - q& =& n.y \\ a(p - q)& =& a.n.y& \text{dimana } a \neq 0 \end{array}

Jika kedua persamaan di atas dikenai operasi penjumlahan :

\begin{array}{lcccr} & q(a - b)& =& q.n.x \\ & a(p - q)& =& a.n.y \\ & ---------& &-------& +\\ & aq - bq + ap - aq& =& q.n.x + a.n.y \\ & ap - bq& =& n(q.x + a.y) \\ \therefore& ap& \equiv& bq \ (mod \ n) \end{array}

Jika salah satu (atau keduanya) dari a atau q bernilai 0, sifat ap \equiv bq \ (mod \ n) pun jelas terpenuhi.

Obat ngantuk

  1. Bintang Berapa sisa pembagian {19}^{1000} \div {3} ?
  2. Bintang Berapa sisa pembagian {2}^{100} \div {3} ?
  3. BintangBintang Berapa sisa pembagian ({22}^{55}+{55}^{22}) \div {7} ?
  4. BintangBintangBintang Buktikan bahwa {2222}^{5555}+{5555}^{2222} habis dibagi 7. (Seleksi Tim Olimpiade Matematika Indonesia 1997). Pembahasan bisa dilihat di sini.
  5. BintangBintangBintang Kira-kira saja, berapa digit-kah {2}^{123456} ? Pembaca hanya diminta memberikan tebakan se-akurat mungkin. Jika pembaca bisa memberikan jawaban persisnya tentu sangat bagus. Pembahasan bisa dilihat di sini.

Seperti yang sudah-sudah, pembahasan terhadap obat-obat ngantuk ini akan diberikan pada post berikutnya.

I punched my boss

Artikel Terkait :

September 23, 2010

Beberapa Fungsi Dasar : absolute, floor, ceil dan mod

Filed under: Matematika, Teori Bilangan — Hendra Jaya @ 9:07 am

Fungsi abs(x)

Definisi : abs(x) adalah fungsi yang akan mengembalikan bentuk tidak negatif dari sebuah bilangan real (\mathbb{R}) x.
Secara matematis dinyatakan dengan |x| = \begin{cases} x, & \mbox{jika } x \geq 0 \\ -x, & \mbox{jika } x<0 \end{cases}
Secara komputatif dinyatakan dengan : abs(x)

Fungsi floor(x)

Definisi : floor(x) adalah fungsi yang akan mengembalikan bilangan bulat (\mathbb{Z}) terbesar yang tidak lebih besar dari bilangan real (\mathbb{R}) x.
Secara matematis dinyatakan dengan : \lfloor x \rfloor = max\{m \in \mathbb{Z}, m \leq x\}
Secara komputatif dinyatakan dengan floor(x)

Secara logis, persamaan \lfloor x \rfloor = m , ekivalen (jika dan hanya jika) dengan pertidaksamaan-pertidaksamaan di bawah ini :

\begin{array}{lllllllll} \lfloor x \rfloor = m & \leftrightarrow & x - 1 & < &  m & \leq & x \\ \lfloor x \rfloor = m & \leftrightarrow & & & m & \leq & x & < & m + 1 \\ \lfloor x \rfloor = m & \leftrightarrow & x - 1 & < &  m & \leq & x & < & m + 1 \end{array}

Gunakan garis bilangan untuk memahami pertidaksamaan-pertidaksamaan di atas.

Fungsi ceil(x)

Definisi : ceil(x) adalah fungsi yang akan mengembalikan bilangan bulat (\mathbb{Z}) terkecil yang tidak lebih kecil dari bilangan real (\mathbb{R}) x.
Secara matematis dinyatakan dengan : \lceil x \rceil = min\{n \in \mathbb{Z}, n \geq x\}
Secara komputatif dinyatakan dengan ceil(x)

Secara logis, persamaan \lceil x \rceil = n , ekivalen (jika dan hanya jika) dengan pertidaksamaan-pertidaksamaan di bawah ini :

\begin{array}{lllllllll} \lceil x \rceil = n & \leftrightarrow & n - 1 & < &  x & \leq & n \\ \lceil x \rceil = n & \leftrightarrow & & & x & \leq & n & < & x + 1 \\ \lceil x \rceil = n & \leftrightarrow & n - 1 & < &  x & \leq & n & < & x + 1 \end{array}

Gunakan garis bilangan untuk memahami pertidaksamaan-pertidaksamaan di atas.

Relasi floor(x) dan ceil(x)

Di dalam garis bilangan floor(x) dan ceil(x) memiliki relasi ketidaksamaan sebagai berikut :

\begin{array}{llclllcll} x - 1 & < & m & \leq & x & \leq & n & < & x + 1 \\ x - 1 & < & \lfloor x \rfloor & \leq & x & \leq & \lceil x \rceil & < & x + 1 \\ x - 1 & < & floor(x) & \leq & x & \leq & ceil(x) & < & x + 1 \end{array}

Quotient (hasil bagi) dalam algoritma pembagian

Blog ini mengikuti algoritma pembagian euclidean dan mengikuti definisi q (quotient/hasil bagi) yang diajukan oleh Raymond T. Boute. Pemakaian definisi q yang ini dilakukan karena definisi yang diberikan oleh Pak Boute selaras dengan algoritma pembagian euclid. Sebagai intermezzo, ada beberapa definisi q yang diajukan. Antara lain truncated division yang populer serta floored division yang diajukan oleh Donald Knuth. Untuk lebih jelasnya, silahkan pembaca lihat di sini.

Menurut euclidean definition, quotient (q) adalah :

q = \begin{cases} \lfloor \frac{a}{d} \rfloor, & \mbox{jika } d > 0 \\ \lceil \frac{a}{d} \rceil, & \mbox{jika } d < 0 \end{cases}

Fungsi mod(x, y)

Fungsi mod(x, y) sangat erat kaitannya dengan r (remainder/sisa bagi). Walaupun demikian, mod(x, y) berbeda dengan r. Dua perbedaan yang paling mencolok adalah :

  1. Remainder (r) adalah suatu bilangan bulat tidak negatif sementara mod(x, y) boleh negatif. Ingat bahwa r harus memenuhi konstrain 0 \leq r < |d|
    Di dalam signed integer alias bilangan bertanda (+/-), perbedaan ini akan langsung terasa. Implementasi fungsi mod(x, y) antara bahasa pemrograman yang satu dengan yang lain berbeda-beda. Silahkan lihat dokumentasi bahasa pemrograman favorit anda.
  2. Remainder (r) didefinisikan sebagai sisa bagi dari dua buah bilangan bulat sementara mod(x, y) menerima bilangan real x, y \in \mathbb{R}

Definisi mod(x, y) yang dipakai dalam blog ini mengikuti definisi Donald Knuth : mod(x, y) = x - y\lfloor \frac{x}{y} \rfloor

Di dalam garis bilangan, berlaku pertidaksamaan-pertidaksamaan berikut :

Untuk y > 0 :
0 \leq mod(x, y) < y

Untuk y < 0 :
0 \geq mod(x, y) > y

Serupa dengan remainder, mod(x, y) bernilai 0 jika dan hanya jika y habis membagi x.

Catatan

Sangat mungkin terjadi perselisihan pendapat, terutama tentang quotient (q), remainder (r) dan mod(x, y). Oleh karena itu berbagai ralat, kritik, masukan dan tanggapan sangat diharapkan.

Duty Calls

September 20, 2010

Algoritma Pembagian 2 : Pembahasan FakPos

Filed under: Algoritma, Matematika, Puzzle, Teori Bilangan — Hendra Jaya @ 6:53 am

Obat ngantuk 1

Jika dituliskan ke dalam bentuk perkalian faktor (a . b), 24 dapat dituliskan sebagai :

\begin{array}{rcrcl}\text{index}&|&a&.&b\\---&|&-&-&-\\1&|&1&.&24\\2&|&2&.&12\\3&|&3&.&8\\4&|&4&.&6\end{array}

Perhatikan bahwa dalam bentuk perkalian di atas (a . b),  terdapat beberapa pola :

  1. a\leq b
  2. a_1<a_2<a_3<a_4 ...
  3. b_1>b_2>b_3>b_4 ...

Dan jika dihitung, maka pada data di atas terdapat 4 buah baris dan 2 buah kolom. Sehingga siapapun dapat menghitung dengan cepat banyaknya elemen dalam “tabel”. Tinggal kalikan jumlah baris dan jumlah kolom maka akan diperoleh banyaknya elemen, yaitu 8.

Dengan cara yang sama, 84 juga dapat dituliskan ke dalam bentuk perkalian faktor (a . b) :

\begin{array}{rcrcl}\text{index}&|&a&.&b\\---&|&-&-&-\\1&|&1&.&84\\2&|&2&.&42\\3&|&3&.&28\\4&|&4&.&21\\5&|&6&.&14\\6&|&7&.&12\end{array}

Sehingga banyaknya elemen dalam “tabel” juga dapat diperoleh dengan mengalikan jumlah baris dan jumlah kolom. Untuk 84, terdapat 6 baris dan “so pasti” 2 kolom. Sehingga banyaknya elemen yang ada di dalam “tabel” adalah 12.

Karena “2 kolom” adalah suatu keterjadian (hal yang mutlak), maka – jika direpresentasikan ke dalam bentuk tabel perkalian faktor semua bilangan pasti memiliki jumlah elemen dalam bentuk 2 . baris, yaitu suatu bilangan genap. Sayangnya, jumlah elemen di dalam tabel tidak merepresentasikan jumlah faktor yang sebenarnya. Karena, tabel “perkalian faktor” ini tidak menjamin keunikan/uniqueness dari elemen-elemen yang ada.

“Mengapa setiap faktor harus unik?”
Untuk memahaminya, silahkan bayangkan jika anda diperbolehkan untuk menuliskan faktor secara tidak unik. Untuk angka 24, anda dapat menuliskan faktornya sebagai 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, …. 24. Totalnya ada tidak terhingga banyaknya faktor.

Setelah memahami sifat “unik” dari setiap faktor dengan faktor lainnya, sebuah pertanyaan kritis akan muncul.

“Apakah mungkin elemen-elemen pada tabel perkalian faktor tidak unik?”
Mungkin saja, yaitu ketika a=b. Sebagai contoh, angka 25, jika direpresentasikan ke dalam tabel perkalian faktor adalah sebagai berikut :

\begin{array}{rcrcl}\text{index}&|&a&.&b\\---&|&-&-&-\\1&|&1&.&25\\2&|&5&.&5\end{array}

Jumlah elemen pada tabel perkalian faktor adalah 4 (genap dan akan selalu genap) sementara jumlah faktor yang sebenarnya adalah 3, yaitu 1, 5, dan 25.

Pertanyaan berikutnya yang mungkin muncul adalah “Berapa kali kasus a = b muncul?”
Konstrain a_1<a_2<a_3<a_4<... secara implisit mengatakan bahwa b_1>b_2>b_3>b_4...  Sekarang, misalkan kasus a=b pertama kali terjadi di baris ke-lima, yaitu pada a_5=b_5 .

Apakah mungkin di baris-baris berikutnya kasus a=b terulang kembali?
Setelah baris ke-lima kita tentu menemui baris ke-enam. Di baris ke-enam akan muncul a_6 yang lebih besar dari a_5, yakni a_6>a_5. Dan akan muncul pula b_6 yang lebih kecil dari b_5, yakni b_5>b_6.

Karena a_5=b_5=m , maka a_6>m>b_6. Suatu hal yang tidak boleh kita lakukan karena di setiap baris kita sudah menyepakati bahwa a\leq b. Dengan demikian, jika kasus a=b terjadi di baris ke-lima dapat dipastikan tidak akan ada baris lagi di bawah baris ke-lima. Atau secara umum dapat kita katakan kasus a=b hanya bisa terjadi maksimal satu kali, dan jika hal itu terjadi di baris ke-n maka pasti n adalah baris terbawah.

Dengan demikian, dapat disimpulkan bahwa kasus ketidak-unikan elemen yang menyebabkan keganjilan jumlah faktor hanya akan muncul di saat baris terbawah dari tabel perkalian faktor-nya dalam bentuk a=b.

Sekarang, apa makna dari a=b? Makna dari a=b adalah bilangan yang dimaksud (c) dapat dituliskan ke dalam bentuk c=a.b=a.a=b.b=a^2=b^2 . Yaitu sebuah bilangan kuadrat. Dengan demikian, kasus keganjilan jumlah faktor hanya akan muncul pada saat c adalah sebuah bilangan kuadrat.

Tour Accounting

Obat Ngantuk 2

Faktor-faktor untuk 1 dapat dituliskan sebagai :

1 = 1

Faktor-faktor untuk 2, yakni 2^1, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\end{array}

Faktor-faktor untuk 4, yakni {2}^{2}, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\end{array}

Faktor-faktor untuk 8, yakni {2}^{3}, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\\8&=&1.2^3\end{array}

Faktor-faktor untuk 24, yakni 2^3.3^1, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\\8&=&1.2^3\\3&=&1.3^1\\6&=&1.2^1.3^1\\12&=&1.2^2.3^1\\24&=&1.2^3.3^1\end{array}

Faktor-faktor untuk 72, yakni {2}^{3}.{3}^{2}, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\\8&=&1.2^3\\3&=&1.3^1\\6&=&1.2^1.3^1\\12&=&1.2^2.3^1\\24&=&1.2^3.3^1\\9&=&1.3^2\\18&=&1.2^1.3^2\\36&=&1.2^2.3^2\\72&=&1.2^3.3^2\end{array}

Catatan : Penulisan faktor di atas dilakukan terurut berdasarkan “kedatangan” faktor prima dan pangkatnya.

Apakah ada pola-nya?
Ada, yaitu :

  • Tentukan 1 sebagai awalan (origin of species)
  • Ketika 2^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 2^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2^1
  • Ketika 2^3 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2^1 ataupun 2^2
  • Ketika 3^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 3^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 3^1
  • dst..

Tanpa mengurangi kebenarannya, kita modifikasi sedikit menjadi :

  • Tentukan 1 sebagai awalan (origin of species)
  • Ketika 2^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 2^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 2^3 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 3^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 3^2 datang, kalikan dengan semua, kecuali dengan bilangan yang mengandung 3
  • dst..

Sekarang, kita tambahkan sedikit logika.

Ketika 2^1 datang (step 2), belum ada bilangan yang mengandung 2. Begitu juga ketika 3^1 datang (step 4), belum ada bilangan yang mengandung 3. Sehingga, tanpa mengurangi kebenarannya, pola yang terbentuk dapat kita tulis ulang lagi menjadi :

  • Tentukan 1 sebagai awalan (origin of species)
  • Ketika 2^1 datang, kalikan dengan semua faktor yang ada, kecuali dengan faktor yang mengandung 2
  • Ketika 2^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 2^3 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 3^1 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 3
  • Ketika 3^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 3
  • dst..

Nah akhirnya terbentuk satu pola yang sangat mudah dibaca. Ketika 2^1 (ataupun keluarganya) datang, semuanya menolak untuk dikalikan dengan bilangan-bilangan yang mengandung 2. Begitu juga ketika 3^1 (ataupun keluarganya) datang, semuanya menolak untuk dikalikan dengan bilangan-bilangan yang mengandung 3.

Sehingga, secara umum, ketika p^1 (ataupun keluarganya) datang, semuanya menolak untuk dikalikan dengan bilangan-bilangan yang mengandung p.

Sekarang kita tulis lagi pola kita :

  • Tentukan 1 sebagai awalan.
  • Ketika 2 (atau keluarganya) datang, kalikan dengan semua faktor yang ada, kecuali dengan faktor yang mengandung 2.
  • Ketika 3 (atau keluarganya) datang, kalikan dengan semua faktor yang ada, kecuali dengan faktor yang mengandung 3.
  • dst..

Misalkan “anggota keluarga” 2 ada k buah, maka :

  • Ketika 1 ditentukan sebagai awalan, jumlah faktor = 1
  • Ketika 2^1 datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
  • Ketika 2^2 datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
  • Ketika 2^3 datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
  • Ketika 2^k datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1

Mengapa semua “anggota keluarga” 2 hanya mau dikalikan dengan satu buah faktor, yaitu 1? Karena mereka takut terjadi “incest”, yaitu perkawinan dengan bilangan “sedarah”, yaitu bilangan yang mengandung angka 2. Hanya ada 1 faktor yang pasti tidak “sedarah” dengan mereka, yaitu 1. Karena perkawinan ini terjadi sebanyak k kali, maka total faktor sekarang ada k+1.

Misalkan “anggota keluarga” 3 ada l buah. Serupa dengan 2, semua bilangan “berdarah” 3 mengharamkan “incest” dan dengan demikian :

  • Ketika 3^1 datang, dia hanya mau dikawinkan dengan k+1 buah bilangan,
  • Ketika 3^2 datang, dia hanya mau dikawinkan dengan k+1 buah bilangan,
  • Ketika 3^3 datang, dia hanya mau dikawinkan dengan k+1 buah bilangan,
  • Ketika 3^l datang, dia hanya mau dikawinkan dengan k+1 buah bilangan

Karena terjadi l kali perkawinan, maka total bilangan baru adalah l.(k+1). Dan jika ditambahkan dengan yang sebelumnya, yaitu k+1. Maka total bilangan (faktor) sekarang adalah l.(k+1)+(k+1)=(l+1).(k+1)

Jika dituliskan ulang polanya menjadi :

  • 1 (awalan)
  • k.1+1=(k+1)
  • l.(k+1)+(k+1)=(l+1).(k+1)
  • m.(l+1).(k+1)+(l+1).(k+1)=(m+1).(l+1).(k+1)
  • dst..

Kesimpulan :

  1. Banyaknya faktor dapat dihitung dengan tepat tanpa harus mengetahui faktor-faktornya.
  2. Banyaknya faktor tidak tergantung kepada faktor prima-nya. Alih-alih, tergantung kepada “pangkat” dari faktor prima-nya.

Technical Jibba-Jabba :

Pseudo-Code :

function FakPos([exp], lower, upper)
  result = 1
  for each i in lower to upper exclusive
    result = result * (1 + exp[i])
  return result

Implementasi Java : Ideone
Implementasi C++ : Sabar subur

Validitas algoritma ini cocok dengan fungsi d(n) seperti dijelaskan pada divisor function.

Secara matematis, FakPos(n) atau d(n) dirumuskan sebagai : d(n)=\prod_{i=1}^{r}(e_i + 1) dimana e_i adalah pangkat/eksponen dari faktor prima ke-i dari n.

Number Order

September 16, 2010

Algoritma Pembagian

Filed under: Matematika, Teori Bilangan — Hendra Jaya @ 10:05 am

Teorema 1 : Untuk sembarang bilangan bulat a dan d, dimana d\neq 0. Pasti ada bilangan bulat q dan r yang memenuhi a=qd+r dimana 0\leq r<|d|
Secara matematis : Untuk a,d\in\mathbb{Z}, dimana d\neq 0. Pasti ada q,r\in\mathbb{Z} yang memenuhi a=qd+r dimana 0\leq r<\mid d\mid

Selanjutnya :

  • a disebut dividend (bilangan yang dibagi)
  • d disebut divisor (bilangan pembagi/faktor)
  • q disebut quotient (hasil bagi)
  • r disebut remainder (sisa bagi)

Teorema 2 : d dinyatakan habis membagi a jika dan hanya jika r=0. Sebaliknya, d dinyatakan tidak habis membagi a jika dan hanya jika r\neq 0
Secara matematis : d\mid a\Leftrightarrow r=0. Sebaliknya, d\nmid a\Leftrightarrow r\neq 0

Contoh 1 :

\begin{array}{rlrl}2&\mid&6&\text{Baca : 2 habis membagi 6}\\\\-9&\mid&36&\text{Baca : -9 habis membagi 36}\\\\25&\mid&-100&\text{Baca : 25 habis membagi -100}\\\\3&\mid&21&\text{Baca : 3 habis membagi 21}\\\\197&\mid&0&\text{Baca : 197 habis membagi 0}\\\\-11&\mid&-33&\text{Baca : -11 habis membagi -33}\end{array}

Contoh 2 :

\begin{array}{rlrl}3&\nmid&14&\text{Baca : 3 tidak habis membagi 14}\\\\8&\nmid&-53&\text{Baca : 8 tidak habis membagi -53}\\\\-9&\nmid&37&\text{Baca : -9 tidak habis membagi 37}\\\\-9&\nmid&-30&\text{Baca : -9 tidak habis membagi -30}\\\\5&\nmid&17&\text{Baca : 5 tidak habis membagi 17}\\\\13&\nmid&25&\text{Baca : 13 tidak habis membagi 25}\\\\22&\nmid&20&\text{Baca : 22 tidak habis membagi 20}\end{array}

Teorema 3 :  Untuk bilangan bulat a, b, dan c. Jika a habis membagi b dan b habis membagi c, maka a habis membagi c
Secara matematis : Untuk a,b,c\in\mathbb{Z}. Jika a\mid b dan b\mid c maka a\mid c

Teorema 4 : Untuk bilangan bulat a, b, m dan n. Jika c habis membagi a dan c habis membagi b, maka c habis membagi (ma+nb)
Secara matematis : Untuk a,b,m,n\in\mathbb{Z}. Jika c\mid a dan c\mid b maka c\mid (ma+nb)

Dalam algoritma pembagian a=qd+r, perhatikan bahwa sisa bagi/remainder (r) BUKAN hal yang sama dengan fungsi mod(a,d) pada ilmu komputasi. Memang ada hubungannya, tetapi kedua hal ini adalah hal yang berbeda. Serupa dengan algoritma pembagian, d dikatakan habis membagi a jika dan hanya jika mod(a,d)=0.

Contoh 1 (lagi) :

\begin{array}{rlrlrll}6&=&3&.&2&+&0\\\\36&=&-4&.&-9&+&0\\\\-100&=&-4&.&25&+&0\\\\21&=&7&.&3&+&0\\\\ 0 &=&0&.&197&+&0\\\\-33&=&3&.&-11&+&0\end{array}

Contoh 2 (lagi) :

\begin{array}{rlrlrll}14&=&4&.&3&+&2\\\\-53&=&-7&.&8&+&3\\\\37&=&-4&.&-9&+&1\\\\-30&=&-4&.&-9&+&6\\\\17&=&3&.&5&+&2\\\\25&=&1&.&13&+&12\\\\20&=&0&.&22&+&20\end{array}

Untuk selanjutnya, kita definisikan istilah faktor (divisor) dari bilangan bulat a adalah bilangan bulat d yang habis membagi a.
Secara matematis : Faktor/divisor dari a adalah d yang memenuhi d\mid a, dimana a,d\in\mathbb{Z}.

Contoh 3 :

  • Faktor-faktor (divisors) dari 24 : \pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\pm 8,\pm 12,\pm 24
  • Faktor-faktor (divisors) dari 84 : \pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\pm 7,\pm 12,\pm 14,\pm 21,\pm 28,\pm 42,\pm 84

Cobol Programmer

Obat Ngantuk

  1. Bintang Dengan hanya mempertimbangkan faktor-faktor (divisors) positif, maka faktor dari 24 adalah : 1, 2, 3, 4, 6, 8, 12, 24. Totalnya ada 8 faktor positif untuk 24. Dengan aturan yang sama, faktor-faktor positif dari 84 adalah 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84 dan banyaknya ada 12 buah. Ternyata, sebagian besar bilangan memiliki faktor positif dalam jumlah genap. Hanya ada segelintir bilangan yang memiliki faktor positif dalam jumlah ganjil. Cari tahu bilangan jenis apa yang memiliki faktor positif dalam jumlah ganjil dan jelaskan mengapa bisa begitu. Pembahasan ada di sini.
  2. BintangBintang Rancanglah suatu fungsi – sebut saja FakPos(n) – yang mengembalikan banyaknya faktor positif dari suatu bilangan bulat positif n. Sebagai contoh, FakPos(24) = 8 dan FakPos(84) = 12. Untuk mempermudah proses pemfaktoran, akan disediakan test case dalam format :
    <number> <pi>^<ei> <pj>^<ej> <pk>^<ek>…<pn>^<en>

    Contoh input :

    24 2^3 3^1
    84 2^2 3^1 7^1
    337500 2^2 3^3 5^5
    384813 3^2 11^1 13^2 23^1  

    Contoh output :
    8
    12
    72
    36

    Karakteristik input :
    1< \text{number}<10^{13}\text{, number}\in\mathbb{Z}
    p_i<p_j<p_k<...<p_n\text{ dimana }p\in\text{Bilangan Prima}
    \text{number}=p_i^{e_i}p_j^{e_j}p_k^{e_k}...p_n^{e_n}
    Setiap baris berisi satu test case.
    Jumlah test case = 100

    Time Limit
    2 detik

    Test Case(s)
    Ambil di sini.

    Pembahasan
    Problem dibahas di sini.

September 14, 2010

Barisan Bilangan 1 : Deret Aritmatika (Arithmetic Progression)

Filed under: Barisan Bilangan, Matematika, Teori Bilangan — Hendra Jaya @ 7:07 am

Deret

Deret : Sederhana saja, deret adalah daftar/barisan bilangan.
Definisi : Setiap bilangan pada deret disebut sebagai suku/elemen/term. Dilambangkan dengan U.

Deret Aritmatika

Definisi : Deret/barisan bilangan aritmatika adalah sekumpulan bilangan yang disusun sedemikian rupa sehingga jarak/selisih/difference antara setiap suku dengan suku berikutnya selalu tetap (konstan).
Definisi: Setiap bilangan pada deret disebut sebagai suku/element/term

Selanjutnya, jika setiap suku pada deret diberi index, maka deret dapat dituliskan sebagai berikut :
U_1,U_2,U_3,...,U_n.

Contoh-contoh deret aritmatika :

  • 1,3,5,7,10. Deret aritmatika terhingga (finite), yaitu jumlahnya terbatas. Selisih tiap suku dengan suku berikutnya adalah 2.
  • 1,2,3,4,5,6. Deret aritmatika terhingga. Selisih tiap suku dengan suku berikutnya adalah 1.
  • 1,2,3,4,5,6,.... Deret aritmatika tak terhingga (infinite), yaitu jumlahnya tidak terbatas. Selisih tiap suku dengan suku berikutnya adalah 1.
  • 3,2,1,0,-1,-2. Deret aritmatika terhingga. Selisih tiap suku dengan suku berikutnya adalah -1.
  • 4,1,-2,-5,-8,-11,.... Deret aritmatika tak terhingga. Suku pertamanya adalah 4 dan selisih tiap suku dengan suku berikutnya adalah -3.
  • 0,2.5,5,7.5,10,12.5,.... Deret aritmatika tak terhingga. Suku pertamanya adalah 0 dan selisih tiap suku dengan suku berikutnya adalah 2.5
  • \frac{5}{7},\frac{6}{7},\frac{7}{7},\frac{8}{7},\frac{9}{7},\frac{10}{7},.... Deret aritmatika tak terhingga. Suku pertamanya adalah \frac{5}{7} dan selisih tiap suku dengan suku berikutnya adalah \frac{1}{7}
  • a,a+d,a+2d,a+3d,a+4d,a+5d,.... Deret aritmatika tak terhingga. Suku pertamanya adalah a dan selisih tiap suku dengan suku berikutnya adalah d.
  • a,a+d,a+2d,a+3d,a+4d,a+5d,...,a+(n-1)d. Deret aritmatika terhingga. Suku pertamanya adalah a dan selisih tiap suku dengan suku berikutnya adalah d.

Perhatikan baik-baik contoh terakhir.

Di dalam matematika, barisan bilangan seringkali dinyatakan dengan U_1,U_2,U_3,...,U_n dimana U_1=a, U_2=a+d, U_3=a+2d, … dan U_n=a+(n-1)d. Notasi ini dalam matematika bermakna :

Suku pertama (U_1) adalah a dan suku ke-n (U_n) adalah a+(n-1)d dimana d adalah jarak/selisih antara suatu suku dengan suku berikutnya, yakni jarak antara U_m dengan U_{m+1} dimana 1\leq m\leq n. Blog mengikuti notasi ini.

Definisi formalnya :

\begin{array}{llll}U_1&=&a&U_1\text{ adalah suku ke-1}\\U_n&=&a+(n-1)d&U_n\text{ adalah suku ke-n, dengan }n\text{ adalah sembarang bilangan yang memenuhi }n>1\text{ dan }n\in\mathbb{Z}\\d&=&U_{m+1}-U_{m}&d\text{ adalah jarak antara suku ke-m (}U_m\text{) dengan suku berikutnya (}U_{m+1}\text{), dengan }m\text{ adalah sembarang bilangan yang memenuhi }m>1\text{ dan }m\in\mathbb{Z}\end{array}

Contoh barisan aritmatika yang lain :

  • Deret bilangan cacah \mathbb{N}_0 : 0, 1, 2, 3, 4, 5 …
    Tak terhingga dengan d=1, U_1=0 dan U_n=n-1
  • Deret bilangan asli \mathbb{N}_1 : 1, 2, 3, 4, 5, 6 …
    Tak terhingga dengan d=1, U_1=1 dan U_n=n.
  • Deret bilangan genap : 0, 2, 4, 6, 8, 10,…
    Tak terhingga dengan d=2, U_1=0 dan U_n=2.(n-1)
  • Deret bilangan ganjil : 1, 3, 5, 7, 9, 11, 13, 15, ….
    Tak terhingga dengan d=2, U_1=1 dan U_n=2n-1
  • Deret bilangan kelipatan 2 : 2, 4, 6, 8, 10, 12, 14, 16 … 2n
    Terhingga dengan d=2, U_1=2 dan U_n=2n
  • Deret bilangan kelipatan 3 : 3, 6, 9, 12, 15, 18, 21 … 3n
    Terhingga dengan d=3, U_1=3 dan U_n=3n
  • Deret bilangan kelipatan 3 : 0, 3, 6, 9, 12, 15, 18, 21 … 3(n-1)
    Terhingga dengan d=3, U_1=0 dan U_n=3(n-1)

Sifat-sifat Deret Aritmatik

Perhatikan aljabar di bawah ini :

\begin{array}{lllrclrr}&&U_m&=&U_1&+&(m-1)d\\&&U_n&=&U_1&+&(n-1)d\\-&-&-&-&----&-&----&-\\U_m&-&U_n&=&(m-1)d&-&(n-1)d\\U_m&-&U_n&=&(m-n)d\\&&U_m&=&U_n&+&(m-n)d\end{array}

Kita peroleh sifat pertama dari deret aritmatika, yaitu U_m=U_n+(m-n)d.

Penjabaran yang lain :

\begin{array}{rllrrllr}&&U_m&=&U_1&+&(m-1)d\\&&U_{m+2n}&=&U_1&+&(m+2n-1)d\\--&-&---&-&--&-&------------&+\\U_m&+&U_{m+2n}&=&2.U_1&+&(m-1)d+(m+2n-1)d\\U_m&+&U_{m+2n}&=&2.U_1&+&(2m+2n-2)d\\U_m&+&U_{m+2n}&=&2.U_1&+&2.(m+n-1)d\end{array}

Mengingat

\begin{array}{rlrlr}U_{m+n}&=&U_1&+&(m+n-1)d\\2.U_{m+n}&=&2.U_1&+&2.(m+n-1)d\end{array}

Maka bisa disimpulkan sifat kedua dari deret aritmatika, yaitu U_m+U_{m+2n}=2.U_{m+n}

Sifat kedua inilah yang nantinya akan menjadi dasar teori untuk rataan aritmatik (Arithmetic Mean). Sebagai gambaran saja, sifat kedua ini dapat dituliskan menjadi \frac{U_m+U_{m+2n}}{2}=U_{m+n} yang dapat diterjemahkan secara statistik : “nilai rata-rata dari U_m dan U_{m+2n} adalah U_{m+n}“.

Jumlah Semua Suku Pada Deret

Alkisah, Carl Friedrich Gauss, salah satu matematikawan terbaik dan yang paling berpengaruh sepanjang masa, menemukan metode untuk menghitung nilai dari 1+2+3+4+...+100 ketika beliau masih berusia 10 tahun. Metode yang diperkenalkan oleh Gauss di usia belia itu masih belum tergantikan hingga saat ini. Untuk menghormati jasa beliau, metode ini dinamai metode Gaussian.

Metode Gaussian adalah sebagai berikut :

\begin{array}{llllrlrlrlrlrlrlrlrlrr}&&total&=&1&+&2&+&3&+&4&+&...&+&97&+&98&+&99&+&100\\&&total&=&100&+&99&+&98&+&97&+&...&+&4&+&3&+&2&+&1\\-&-&---&=&---&-&--&-&--&-&--&-&-&-&--&-&--&-&--&-&--&+\\2&.&total&=&101&+&101&+&101&+&101&+&...&+&101&+&101&+&101&+&101\\2&.&total&=&100&.&101\\&&total&=&\frac{100.101}{2}\\&&total&=&5050\end{array}

Lantas, bagaimana caranya menghitung jumlah dari suku-suku pada sebuah deret aritmatik?

Untuk menghitung jumlah dari suku-suku pada sebuah deret aritmatik, kita akan meminjam metode Gaussian ini sebentar :

\begin{array}{llllrlrlrlrlrlrlrlrlrr}&&S_n&=&a&+&a+d&+&a+2d&+&a+3d&+&...&+&a+(n-4)d&+&a+(n-3)d&+&a+(n-2)d&+&a+(n-1)d\\&&S_n&=&a+(n-1)d&+&a+(n-2)d&+&a+(n-3)d&+&a+(n-2)d&+&...&+&a+3d&+&a+2d&+&a+d&+&a\\-&-&-&=&--------&-&--------&-&--------&-&--------&-&-&-&--------&-&--------&-&--------&-&--------&+\\2&.&S_n&=&a+a+(n-1)d&+&a+a+(n-1)d&+&a+a+(n-1)d&+&a+a+(n-1)d&+&...&+&a+a+(n-1)d&+&a+a+(n-1)d&+&a+a+(n-1)d&+&a+a+(n-1)d\\2&.&S_n&=&U_1+U_n&+&U_1+U_n&+&U_1+U_n&+&U_1+U_n&+&...&+&U_1+U_n&+&U_1+U_n&+&U_1+U_n&+&U_1+U_n\\2&.&S_n&=&n.(U_1+U_n)\\&&S_n&=&\frac{n.(U_1+U_n)}{2}\end{array}

Dengan demikian kita peroleh rumus untuk menghitung total nilai seluruh suku pada deret aritmatika, yaitu S_n=\frac{n.(U_1+U_n)}{2}. Dimana :

S_n menyimbolkan jumlah (sum) dari suku-suku pada deret.
U_1 menyimbolkan suku pertama pada deret.
U_n menyimbolkan suku terakhir pada deret.
n menyimbolkan banyaknya suku pada deret.

Karena deret aritmatika berbentuk U_1,U_2,U_3,...,U_{n-2},U_{n-1},U_n maka kita boleh saja meng-asumsikan bahwa ada suku U_m yang letaknya berada di rentang U_1\leq U_m\leq U_n (well-order principle) sehingga deret aritmatika dapat dituliskan sebagai U_1,U_2,U_3,...,U_m,U_{m+1},U_{m+2},....,U_{n-2},U_{n-1},U_n.

Sekarang jika kita pandang secara parsial (sebagian), yakni deret kita mulai dari suku ke-m, maka kita memperoleh deret baru, yaitu U_m,U_{m+1},U_{m+2},....,U_{n-2},U_{n-1},U_n.

Ada berapa banyak suku pada deret ini?

Sebelumnya, deret memiliki n suku. Tetapi karena kita hanya mengambil sepotong saja dari deret tersebut, artinya ada sebagian suku yang kita tinggalkan. Banyaknya suku yang kita tinggalkan adalah m-1 suku. Dan dengan demikian banyaknya suku yang kita “pakai” adalah n-(m-1) suku, yaitu n-m+1 suku.

Berapa jumlah nilai suku-suku pada deret baru ini?

Suku pertama pada deret ini adalah U_m dan suku terakhir adalah U_n. Banyaknya suku ada n-m+1 buah. Sesuai dengan rumus yang tadi kita peroleh, jumlah nilai suku-suku pada deret ini adalah S_{n-m+1}=\frac{(n-m+1).(U_m+U_n)}{2}

Rumus ini adalah rumus umum untuk mencari jumlah nilai suku-suku pada deret. Baik secara parsial ataupun secara utuh. Jika ingin menghitung secara utuh, gunakan m=1.

Einstein's First Equation

Rataan Aritmatika

Sesuai dengan judulnya, rataan aritmatika (Arithmetic Mean/AM) adalah nilai rata-rata pada barisan aritmatika. Baik secara parsial ataupun secara utuh.

Sebagai contoh :

  1. Nilai rata-rata dari deret 1,2,3,4,5,6,7,8,9,10 adalah \frac{1+2+3+4+5+6+7+8+9+10}{10}=\frac{55}{10}=5.5
  2. Nilai rata-rata dari deret 1,2,3,4,5,6,7,8,9 adalah \frac{1+2+3+4+5+6+7+8+9}{9}=\frac{45}{9}=5
  3. Nilai rata-rata dari deret 3,4,5,6,7,8,9 adalah \frac{3+4+5+6+7+8+9}{7}=\frac{42}{7}=6
  4. Nilai rata-rata dari deret 1,2,3,4,5,6,7 adalah \frac{1+2+3+4+5+6+7}{7}=\frac{28}{7}=4
  5. Nilai rata-rata dari deret 1,2,3,4 adalah \frac{1+2+3+4}{4}=\frac{10}{4}=2.5
  6. Nilai rata-rata dari deret 1,2,3 adalah \frac{1+2+3}{3}=\frac{6}{3}=2
  7. Nilai rata-rata dari deret 1,3 adalah \frac{1+3}{2}=\frac{4}{2}=2
  8. Nilai rata-rata dari deret 2 adalah \frac{2}{1}=2

Apakah ada pola yang menarik?

Ada. Ternyata nilai rata-rata pada berbagai deret aritmatik di atas sangat dekat atau bahkan persis dengan nilai tengah (median) dari deret tersebut.

Secara umum, rataan aritmatika dirumuskan sebagai berikut :

AM=\frac{U_1+U_2+U_3+...+U_n}{n}

Jika kita ambil kasus sederhana yaitu deret dengan tiga buah suku U_1,U_2,U_3, maka AM=\frac{U_1+U_2+U_3}{3}.

Akan tetapi, ilmu barisan bilangan tidak berhenti sampai disitu saja. Perhatikan penjabaran berikut ini :

\begin{array}{llllclclc}3&.&AM&=&U_1&+&U_2&+&U_3\\3&.&AM&=&a&+&a+d&+&a+2d\\3&.&AM&=&3a+3d\\&&AM&=&a+d\\&&AM&=&a+(2-1)d\\&&AM&=&U_2\end{array}

Hal ini menarik perhatian kita karena secara langsung penjabaran di atas menyatakan bahwa AM=\frac{U_1+U_2+U_3}{3}=U_2

Ingat bahwa di bagian atas dari artikel ini kita telah membahas sifat kedua dari barisan aritmatika, yaitu U_m+U_{m+2n}=2.U_{m+n}. Dengan mengambil m=1 dan n=1 kita peroleh :

\begin{array}{lllll}U_m&+&U_{m+2n}&=&2.U_{m+n}\\U_1&+&U_{1+2.1}&=&2.U_{1+1}\\U_1&+&U_3&=&2.U_2\end{array}

Atau dengan menuliskan ke dalam bentuk lain kita peroleh \frac{U_1+U_3}{2}=U_2.

Apa yang sebenarnya terjadi? Mengapa rataan dari tiga buah suku dan dua buah suku menghasilkan hasil yang sama?

Mari kita bahas perlahan-lahan.

Misalkan k=m dan l=m+2n. Maka \frac{k+l}{2}=m+n.

Seperti yang sudah kita ketahui melalui sifat kedua dari barisan aritmatik, U_k dan U_l akan memiliki nilai rata-rata yang sama dengan U_{\frac{k+l}{2}}, yaitu suku yang berada di tengah-tengah mereka. Hal ini berlaku umum untuk setiap suku pada barisan aritmatik.

Bagaimana jika k+l tidak habis dibagi 2?

Jika k+l tidak habis dibagi 2, maka suku ke-\frac{k+l}{2} adalah suku fiktif. Walaupun demikian, konsepnya tidak berubah. Suku fiktif ini secara logis akan berada di tengah-tengah dari U_k dan U_l.

Dengan demikian, fenomena di atas dapat dijelaskan sebagai berikut :

\begin{array}{llllllll}&&U_1&+&U_3&=&2.U_2&\text{Rata-rata dari }U_1\text{ dan }U_3\text{ adalah }U_2\\&&&&U_2&=&U_2&\text{Tambahkan dengan }U_2\\-&-&-&-&-&-&---&+\\U_1&+&U_2&+&U_3&=&3.U_2\end{array}

Terlihat jelas bahwa nilai rata-rata dari U_1, U_2 dan U_3 adalah \frac{U_1+U_2+U_3}{3}=U_2 lagi.

Mari kita perbesar kasusnya dengan mencari rata-rata dari U_1,U_2,U_3,U_4,U_5 :

\begin{array}{llllllllllll}&&&&&&U_1&+&U_5&=&2.U_3&\text{Rata-rata dari }U_1\text{ dan }U_5\text{ adalah }U_3\\&&&&&&U_2&+&U_4&=&2.U_3&\text{Rata-rata dari }U_2\text{ dan }U_4\text{ adalah }U_3\\&&&&&&&&U_3&=&U_3&\text{Tambahkan dengan }U_3\\-&-&-&-&-&-&-&-&-&-&---&+\\U_1&+&U_2&+&U_3&+&U_4&+&U_5&=&5.U_3\end{array}

Nilai-rata-rata dari U_1,U_2,U_3,U_4,U_5 adalah \frac{U_1+U_2+U_3+U+4+U_5}{5}=U_3, yaitu suku tengah (median) pada deret.

Mari kita lihat kasus parsial dengan mencari rata-rata dari U_4,U_5,U_6,U_7,U_8 :

\begin{array}{llllllllllll}&&&&&&U_4&+&U_8&=&2.U_6&\text{Rata-rata dari }U_4\text{ dan }U_8\text{ adalah }U_6\\&&&&&&U_5&+&U_7&=&2.U_6&\text{Rata-rata dari }U_5\text{ dan }U_7\text{ adalah }U_6\\&&&&&&&&U_6&=&U_6&\text{Tambahkan dengan }U_6\\-&-&-&-&-&-&-&-&-&-&---&+\\U_4&+&U_5&+&U_6&+&U_7&+&U_8&=&5.U_6\end{array}

Nilai-rata-rata dari U_4,U_5,U_6,U_7,U_8 adalah \frac{U_4+U_5+U_6+U+7+U_8}{5}=U_6, yaitu suku tengah (median) pada deret.

Secara umum, bisa disimpulkan bahwa deret U_1,U_2,U_3,...,U_n akan memiliki nilai rata-rata yang sama dengan nilai rata-rata dari U_1,U_n, yaitu AM=\frac{U_1+U_n}{2}.

Atau, untuk kasus parsial seperti deret U_m,U_{m+1},U_{m+2},...,U_n, akan memiliki nilai rata-rata yang sama dengan nilai rata-rata dari U_m,U_n, yaitu AM=\frac{U_m+U_n}{2}.

Sifat ini amat sangat membantu kita untuk mencari nilai rata-rata dari sebuah deret aritmatika. Karena tidak perduli berapa banyaknya suku pada deret, kita dapat dengan mudah mencari nilai rata-rata dengan menghitung rata-rata dari dua buah suku saja. Yaitu rata-rata dari suku pertama dan suku terakhir. Atau secara parsial, suku ke-m dan suku ke-n.

Computer Holy Wars

Obat Ngantuk

  1. Dengan mengambil rentang 1\leq n\leq 150,
    1. Ada berapa banyak bilangan kelipatan 2 di rentang tersebut?
    2. Berapa jumlah bilangan kelipatan 2 di rentang tersebut?
    3. Ada berapa banyak bilangan kelipatan 3 di rentang tersebut?
    4. Berapa jumlah bilangan kelipatan 3 di rentang tersebut?
  2. Dengan mengambil rentang 1\leq n\leq 150,
    1. Ada berapa banyak bilangan kelipatan 2 atau 3 di rentang tersebut?
    2. Berapa jumlah bilangan kelipatan 2 atau 3 di rentang tersebut?
    3. Ada berapa banyak bilangan kelipatan 3 atau 5 di rentang tersebut?
    4. Berapa jumlah bilangan kelipatan 3 atau 5 di rentang tersebut?
  3. Konsep
    1. Barisan bilangan fibonacci adalah 1, 1, 2, 3, 5, 8, 13, 21, ….
      Apakah barisan bilangan fibonacci merupakan barisan bilangan aritmatika atau bukan? Jelaskan jawaban anda.
    2. Barisan bilangan prima adalah 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …
      Apakah barisan bilangan prima adalah barisan bilangan aritmatika atau bukan? Jelaskan jawaban anda.
  4. Bintang Carilah rumus suku ke-n (U_n) pada barisan-barisan bilangan di bawah ini dan jelaskan mengapa mereka bukan barisan bilangan aritmatika. Pembahasan ada di sini.
    1. Barisan pertama : 1, 4, 9, 16, 25, 36, 49, 64, 81, ….
    2. Barisan kedua : 0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, …
    3. Barisan ketiga : 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ….
    4. Barisan keempat : 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, …
  5. Bintang Misalkan U_1,U_2,U_3,...,U_k adalah sebuah barisan bilangan aritmatik.
    Diketahui U_4+U_7+U_{10}=17 dan U_4+U_5+U_6+...+U_{12}+U_{13}+U_{14}=77
    Carilah nilai k dimana U_k=13 (American High School Mathematics Examination). Pembahasan ada di sini.
  6. BintangBintang Hitunglah nilai dari \frac{1}{1.2}+\frac{1}{2.3}+\frac{1}{3.4}+...+\frac{1}{98.99}+\frac{1}{99.100}. Pembahasan ada di sini.
  7. Bintang Untuk T\in\mathbb{R}, diketahui tiga buah suku pertama pada barisan aritmatik adalah 2T, 5T-1 dan 6T+2. Berapakah nilai suku ke-4? Pembahasan ada di sini.
  8. Bintang Diketahui \frac{b+c-a}{a}, \frac{c+a-b}{b} dan \frac{a+b-c}{c} adalah tiga buah suku berurutan pada sebuah barisan aritmatik. Pembahasan ada di sini.
    Buktikan bahwa \frac{1}{a}, \frac{1}{b} dan \frac{1}{c} juga merupakan tiga buah suku berurutan pada sebuah barisan aritmatik (tidak harus barisan yang sama). Pembahasan ada di sini.
  9. Bintang Ada berapa banyak nilai n sedemikian rupa sehingga 1+2+3+4+...+n habis membagi 6n. (American Mathematics Competition 12^{th} grade). Pembahasan ada di sini.
  10. Bintang Dalam sebuah barisan aritmatika U_1,U_2,U_3..., diketahui U_8=2001. Jika jarak antar suku satu dengan suku yang lain (d) adalah sebuah bilangan bulat, berapa nilai minimum d agar U_{17}>10000? (Introduction to Algebra). Pembahasan ada di sini.
  11. BintangBintang Hitunglah nilai dari \frac{1}{1}+\frac{1}{3}+\frac{1}{6}+\frac{1}{10}+...+\frac{1}{5050}. Pembahasan ada di sini.
  12. Bintang Dalam sebuah deret aritmatika, diketahui fakta-fakta berikut :
    1. U_1+U_2+U_3+...+U_{100}=100
    2. U_{101}+U_{102}+U_{103}+...+U_{200}=200
    3. Berapakah nilai dari U_1? Pembahasan ada di sini.
  13. BintangBintangBintang Diketahui bahwa : (Pembahasan ada di sini)
    1. Setiap serangga tampan membelah diri menjadi seekor serangga buruk rupa dan seekor serangga bodoh.
    2. Setiap serangga buruk rupa membelah diri menjadi dua ekor serangga tampan.
    3. Setiap serangga bodoh membelah diri menjadi seekor serangga buruk rupa dan seekor serangga tampan.
    4. Serangga hanya membelah diri ketika dia mati.
    5. Masa hidup setiap serangga (tidak perduli jenisnya) adalah sama.
    6. Pada awalnya hanya ada seekor serangga tampan (origin of species). Serangga ini disebut sebagai serangga generasi pertama. Berapa jumlah
      1. Total seluruh serangga generasi ke-5?
      2. Serangga (masing-masing jenis) generasi ke-5?
      3. Total seluruh serangga generasi ke-n?
      4. Serangga (masing-masing jenis) generasi ke-n?

    Dept Math & Frustration

The Shocking Blue Green Theme. Create a free website or blog at WordPress.com.

Ikuti

Get every new post delivered to your Inbox.