Materi Pembinaan Olimpiade SMA I MAGELANG TEORI BILANGAN Oleh. Nikenasih B SIFAT HABIS DIBAGI PADA BILANGAN BULAT Untuk dapat memahami sifat habis dibagi pada bilangan bulat, sebelumnya perhatikan contoh berikut 234 5 = 46 sisa 4 dan dapat ditulis 234 = 5 x 46 + 4. Secara umum, contoh diatas dapat dinyatakan sebagai berikut Untuk sebarang a dan b bilangan bulat dengan a ≠ 0, maka terdapat q dan r bilangan bulat yang tunggal sedemikian sehingga b dapat dinyatakan sebagai b=axq+r atau b = aq + r dengan 0  r b > 0, maka GCDa,b dapat dicari dengan mengulang algoritma pembagian. a  q1b  r1 0  r1  b b  q2r1  r2 0  r2  r1 r1  q3r2  r3 0  r3  r2  rn 2  qn rn 1  rn 0  rn  rn 1 rn 1  qn 1rn  0 Maka, rn, sisa terakhir dari pembagian diatas yang bukan nol merupakan GCDa,b. Contoh Tentukan GCD4840,1512 ? Akibat dari teorema algoritma euclide yaitu untuk setiap GCD maka terdapat bilangan bulat x dan y sedemikian hingga GCDa,b = ax + by. Misalnya pada contoh diatas, akan dicari x dan y sedemikian hingga 8 = 4840x + 1512y. GCD4840,1512 = 8 = 304 – 296 = 304 – 1512 – 304 x 4 = 304 x 5 – 1512 = 4840 – 1512 x 3 x 5 – 1512 = 5 x 4840 – 15 x 1512 – 1512 = 5 x 4840 – 16 x 1512 Jadi x= 5 dan y = -16. Akibat selanjutnya dari teorema euclide yaitu persamaan linear Diophantine. Teorema 2 Diophantine Suatu persamaan linear Diophantine ax + by = c dengan a,b dan c bilangan bulat mempunyai penyelesaian bilangan bulat jika dan hanya jika GCDa,b membagi habis c. Bukti Dari akibat sebelumnya diketahui bahwa untuk setiap GCD maka terdapat bilangan bulat m dan n sedemikian hingga GCDa,b = am + bn. Selanjutnya Karena GCDa,b membagi habis c maka terdapat bilangan k sedemikian hingga c  k  GCD  a, b  c  k   am  bn  c  a  km   b  kn  Jadi salah satu penyelesain untuk persamaan linear Diophantine tersebut yaitu x  km dan y  kn . Terbukti. Diambil sebarang bilangan bulat k, akan ditunjukkan bahwa jika x0 dan y 0 adalah salah satu penyelesaian persamaan linear diophantine ax + by = c, maka x  x0  b k GCD  a, b  y  y0  a k GCD  a, b  juga merupakan penyelesain persamaan linear Diophantine tersebut. Contoh Tentukan penyelesaian umum persamaan Diophantine 754x+221y=13. BILANGAN – BILANGAN KHUSUS Ada beberapa macam macam bilangan khusus. Pada subbab ini hanya akan dibahas mengenai 3 biangan khusus yaitu bilangan prima, bilangan komposit dan bilangan kuadrat. A. Bilangan Prima Bilangan prima adalah bilangan asli hanya mempunyai dua faktor yaitu 1 dan bilangan itu sendiri. Contoh bilangan prima yaitu 2, 3, 5, 7, … B. Bilangan Komposit Bilangan komposit adalah bilangan yang mempunyai lebih dari 2 faktor. Contoh bilangan komposit yaitu 4, 6, 8, 9, 10, ….. C. Bilangan Bulat Kuadrat Suatu bilangan a disebut bilangan bulat kuadrat jika terdapat bilangan bulat b sedemikian hingga b2 = a. Contoh bilangan bulat kuadrat yaitu 1, 4, 9, 16, 25, … Selanjutnya, di bawah adalah teorema yang berkaitan dengan ketiga bilangan diatas. Teorema 3 Teori Erathosthenes Untuk setiap bilangan komposit n ada bilangan prima p sehingga p  n dan p kurang dari sama dengan akar n. Atau dapat juga dikatakan jika tidak ada bilangan prima p yang dapat membagi n dengan p kurang dari sama dengan akar n maka n adalah bilangan prima. Sifat dari bilangan kuadrat yaitu 1. angka satuan yang mungkin untuk bilangan kuadrat adalah 0, 1, 4, 5, 6, dan 9. 2. setiap bilangan kuadrat dibagi 4 maka sisanya 0 atau 1. 3. jika p bilangan prima dan p membagi habis n2 maka p2 membagi habis n2. Contoh Tunjukkan bahwa kuadrat sebarang bilangan bulat dapat dituliskan dalam bentuk 4k atau 8k+1. Contoh Matematikawan August DeMorgan menghabiskan seluruh usianya pada tahun 1800an. Pada tahun terakhir dalam masa hidupnya dia mengatakan bahwa “Dulu aku berusia x tahun pada tahun x2.” Tentukan pada tahun berapa ia dilahirkan? soal Olimpiade Matematika tk. Kabupaten Contoh Suatu bilangan bulat p  2 merupakan bilangan prima jika faktornya hanyalah p dan 1. Misalkan M menyatakan perkalian 100 bilangan prima yang pertama. Berapa banyakkah angka 0 di akhir bilangan M? soal Olimpiade Matematika tk. Kabupaten KONGRUENSI Misalkan m adalah suatu bilangan bulat positif. Dua buah bilangan a dan b dikatakan kongruen modulo m jka dan hanya jika m  a – b, dan ditulis dengan a  b mod m  Contoh 23 = 3 mod 5. Teorema 4 Misalkan a, b, c, d, x dan y melambangkan bilangan bulat, maka a. a  b mod m  , b  a mod m  dan a  b  0 mod m  adalah pernyataan pernyataan yang setara. b. Jika a  b mod m  dan b  c mod m  maka a  c mod m  . c. Jika a  b mod m  dan d membagi habis m maka a  b mod d  Bukti d. Jika a  b mod m  dan c  d mod m  maka ax  cy  bx  dy mod m  a. dan ac  bd mod m  . a  b mod m  , maka terdapat q sedemikian hingga a – b = qm. Akibatnya   a  b   qm sehingga a  b   q  m . Karena terdapat bilangan bulat q sedemikian hingga b  a   q  m , maka b  a mod m  . Kemudian karena a  b  qm  0 , maka a  b  0 mod m  . Terbukti. Latihan b dan c disediakan sebagai latihan. d. m  a – b dan m  c – d maka m   x  a  b   y  c  d  , atau m  ax  cy    bx  dy  . Sehingga didapatkan ax  cy  bx  dy mod m  . Akibat dari teorema diatas yaitu jika f  x  adalah suatu fungsi polinom dengan koefisien koefisien bulat dan a  b mod m , maka berlaku f  a   f  b  mod m . Berikut adalah contoh penggunaan akibat dari teorema 2. Contoh Buktikan bahwa untuk sebarang bilangan asli n, A  2903n  803n  464n  261n habis dibagi 1897. Jawab Misalkan n suatu bilangan asli. Perhatikan bahwa 1897 = 7 x 271. selanjutnya 2903  803 mod 7  dan 464  261mod 7  Begitu pula 2903  464 mod 271 dan 803  261mod 271 , dengan demikian A habis dibagi 7 dan 271. karena GCD7,271 = 1, maka dapat disimpulkan bahwa A habis dibagi 1897. Contoh Buktikan bahwa kuadrat bilangan suatu bilangan bulat berbentuk  0 atau 1 mod 3  Contoh Buktikan bahwa jika 2n+1 dan 3n+1 keduanya bilangan kuadrat murni, maka n habis dibagi 40 FUNGSI BILANGAN BULAT TERBESAR Untuk x biangan real, lambang  x  menyatakan bilangan bulat terbesar yang lebih kecil atau sama dengan x. jadi  x   x . Teorema 5 Misalkan x dan y bilangan real, maka diperoleh a. b.  x   x   x   1 Dan x  1   x   x, Jika x  0 maka  x    1 . 0  x   x   1. 1 i  x c. Jika m suatu bilangan bulat, maka berlaku  x  m   x   m . d. x   x  adalah bagian pecahan dari x e.    x  adalah biangan bulat terkecil yang lebih besar atau sama dengan x. f.  x  0,5 adalah bilangan bulat yang terdekat pada x. Jika dua bilangan bulat sama dekatnya dengan x maka melambangkan biangan built yang lebih besar dari keduanya. n  g. Jika n dan a bilangan bulat positif,   adalah bilangan bulat diantara 1, 2, a  …, n yang habis dibagi a. Contoh Buktikan bahwa untuk n = 1,2,3,… berlaku  n  1  n  2   n  4   n  8   2    4    8    16     n        