Rabu, 06 Maret 2013

Teori Bilangan (Olimpiade)


TEORI BILANGAN
1.1.        BILANGAN REAL

Pada materi kali ini, kita akan mempelajari konsep dasar bilangan real dimulai dari operasi dasar pada bilangan real dan diakhiri dengan  Problem Set  mengenai bilangan real.



1.1.1.  Operasi dasar bilangan real

Definisi:
Jika n1 dan n2 adalah bilangan real, maka ada suatu bilangan real yang ditulis sebagai n1 + n2 yang merupakan jumlah dari n1 dan n2. Juga ada suatu bilangan real n1 × n2 (atau ditulis sebagai n1. n2 atau n1n2) yang merupakan hasil kali dari n1 dan n2.


1.1.2.  Sifat-sifat operasi himpunan bilangan real

Beberapa sifat operasi pada bilangan real antara lain adalah:

1.      Sifat tertutup

Himpunan bilangan real R dikatakan tertutup terhadap operasi penjumlahan dan perkalian, karena jumlah dan hasil kali dari 2 bilangan real merupakan bilangan real pula. Dalam notasi matematika biasa ditulis sebagai berikut:
a.      Penjumlahan
Untuk setiap n1, n2 Î R, berlaku (n1 + n2) Î R
b.      Perkalian
Untuk setiap n1, n2 Î R, berlaku (n1n2) Î R


2.      Sifat Komutatif

a.      Penjumlahan
      Untuk setiap n1, n2 Î R, berlaku n1 + n2  = n2 + n1
b.      Perkalian
      Untuk setiap n1, n2 Î R, berlaku n1n2 = n2n1

3.      Sifat Asosiatif

a.      Penjumlahan
      Untuk setiap n1, n2, n3 Î R, berlaku (n1 + n2) + n3 = n1 + (n2 + n3)
b.      Perkalian
      Untuk setiap n1, n2, n3 Î R, berlaku (n1n2)n3 = n1(n2n3)

4.      Sifat Identitas

a.      Penjumlahan
Untuk setiap n Î R, berlaku n + 0 = 0 + n = n dimana 0 sebagai identitas penjumlahan
b.      Perkalian
Untuk setiap n Î R, berlaku n × 1 = 1 × n = n dimana 1 sebagai identitas pekalian

5.      Sifat Kebalikan (invers)

a.      Penjumlahan
Untuk setiap n Î R akan terdapat –n Î R  sedemikian sehingga berlaku sifat n + (–n) = (–n) + n = 0. –n disebut invers atau kebalikan dari n terhadap operasi penjumlahan
b.      Perkalian
Untuk setiap n ¹ 0 Î R akan terdapat 1/n Î R sedemikian sehingga berlaku sifat n × 1/n = 1/n × n = 1. 1/n disebut invers atau kebalikan dari n terhadap operasi perkalian

6.      Sifat Distributif

a.      Distributif kiri
      Untuk setiap n1, n2, n3 Î R, berlaku (n1 + n2) n3 = n1n3 + n2n3
b.      Distributif kanan
      Untuk setiap n1, n2, n3 Î R, berlaku n1 (n2 + n3) = n1n2 + n1n3


1.1.3.  Skema himpunan bilangan real

Rounded Rectangle: Bilangan Irrasional Rounded Rectangle: Bilangan GanjilRounded Rectangle: Bilangan PecahanRounded Rectangle: Bilangan Real ( R )Rounded Rectangle: Bilangan Rasional ( Q )Rounded Rectangle: Bilangan Bulat ( Z )Rounded Rectangle: Bilangan Bulat Negatif ( Z- )Rounded Rectangle: Bilangan Cacah ( C )Rounded Rectangle: Bilangan NolRounded Rectangle: Bilangan Asli ( N )Rounded Rectangle: Bilangan GenapRounded Rectangle: Bilangan PrimaRounded Rectangle: Bilangan Komposit
Secara umum himpunan bilangan real terbagi menjadi dua himpunan besar yaitu himpunan bilangan rasional dan himpunan bilangan irrasional. Namun sebelum diberikan definisi bilangan rasional dan irrasional akan diuraikan definisi bilangan yang lainnya.

Definisi bilangan bulat positif (asli):
Bilangan asli atau bilangan alam adalah bilangan-bilangan yang disimbolkan dengan angka 1, 2, 3, ….

Kumpulan semua bilangan asli disebut himpunan bilangan asli , yaitu N = {1, 2, 3, 4, …}. Sedangkan gabungan antara bilangan nol dan himpunan bilangan asli disebut himpunan bilangan cacah, yaitu C = N È {0} = {0, 1, 2, 3, …}.

Definisi bilangan bulat negatif:
Sebuah bilangan x disebut bilangan bulat negatif bila bilangan x merupakan kebalikan (invers) dari suatu bilangan bulat positif. Jika a merupakan suatu bilangan bulat positif maka x disimbolkan dengan x = –a

Kumpulan semua bilangan bulat negatif disebut himpunan bilangan bulat negatif, yaitu {–1, –2, –3, … }.


Definisi faktor pembagi:
Jika a, b, dan c adalah bilangan-bilangan bulat, serta berlaku ab=c maka a dan b disebut faktor pembagi dari c, sedangkan c disebut kelipatan dari a dan b.


Definisi bilangan genap dan ganjil:
Sebuah bilangan bulat positif a disebut bilangan genap bila salah satu faktor dari a adalah 2. Bilangan yang bukan genap disebut bilangan ganjil.

Kumpulan semua bilangan genap disebut himpunan bilangan genap. Sedangkan kumpulan semua bilangan ganjil disebut himpunan bilangan ganjil.


Definisi bilangan komposit:
Sebuah bilangan bulat positif k ¹ 1disebut bilangan komposit bila bilangan k tersebut dapat dinyatakan sebagai hasil kali dua atau lebih bilangan bulat positif  ¹ 1.

Kumpulan semua bilangan komposit disebut himpunan bilangan komposit.


Definisi bilangan prima:
Sebuah bilangan bulat positif p ¹ 1 disebut bilangan prima bila bilangan p tersebut merupakan perkalian antara 1 dan p, atau bilangan p hanya mempunyai 2 faktor yaitu 1 dan p sendiri.

Kumpulan semua bilangan prima disebut himpunan bilangan prima, yaitu {2, 3, 5, 7, …}


Definisi bilangan rasional:
Sebuah bilangan r disebut bilangan rasional jika bilangan r tersebut dapat dinyatakan sebagai pembagian dari dua buah bilangan bulat. Dalam notasi matematika sebagai berikut:

Kumpulan semua bilangan rasional disebut himpunan bilangan rasional yang merupakan gabungan dari himpunan bilangan bulat dan himpunan bilangan pecahan. Sebuah bilangan rasional dapat mudah kita kenal dari bilangan desimalnya dimana pada bilangan desimalnya terdapat pengulangan bilangan yang secara teratur.


Contoh 1.1
Beberapa bilangan rasional yang dapat dilihat dari pola bilangan desimalnya adalah:
·        
·        
·        
·        


Definisi bilangan irrasional:
Sebuah bilangan c disebut bilangan irrasional jika bilangan c tersebut tidak dapat dinyatakan sebagai pembagian dari dua buah bilangan bulat. Sebuah bilangan irrasional dapat mudah kita kenal dari bilangan desimalnya dimana pada bilangan desimalnya tidak terdapat pengulangan bilangan yang secara teratur.


Contoh 1.2
Beberapa contoh bilangan yang merupakan bilangan irrasional:

Kumpulan semua bilangan irrasional disebut himpunan bilangan irrasional.

Problem Set

1.      Manakah di antara bilangan decimal berikut yang bukan merupakan bilangan rasional? Jelaskan !
a.       0,959599595…
b.      0,696969…
c.       –5,344344433…
d.      –2,889889889…
e.       7,79977997799…

2.      Tentukan bilangan pecahan dari bilangan-bilangan rasional di bawah ini:
a.       0,799999…
b.      0,659659659…
c.       1,333333…
d.      –2,898989…
e.       5,799979997999…

3.      Manakah dari pernyataan-pernyataan berikut yang benar? Jelaskan!
a.       Hasil penjumlahan antara dua bilangan rasional adalah bilangan rasional
b.      Hasil penjumlahan antara dua bilangan irrasional adalah bilangan irrasional
c.       Hasil perkalian antara dua bilangan rasional adalah bilangan rasional
d.      Hasil perkalian antara dua bilangan irrasional adalah bilangan irrasional


1.2.        BILANGAN ASLI

Materi ini akan membahas materi tentang bilangan asli. Bilangan asli sendiri mempunyai sifat-sifat yang hampir sama dengan bilangan real, namun ada beberapa sifat dari bilangan real yang tidak dimiliki oleh bilangan asli.

1.2.1.        Operasi dasar bilangan asli

Sama seperti bilangan real, pada bilangan asli terdapat dua buah operasi dasar yaitu operasi penjumlahan dan perkalian.

Definisi:
Jika n1 dan n2 adalah bilangan real, maka ada suatu bilangan real yang ditulis sebagai n1 + n2 yang merupakan jumlah dari n1 dan n2. Juga ada suatu bilangan real n1 × n2 (atau ditulis sebagai n1. n2 atau n1n2) yang merupakan hasil kali dari n1 dan n2.

1.2.2.        Sifat-sifat operasi himpunan bilangan asli

Beberapa sifat operasi pada bilangan asli antara lain adalah:

1.      Sifat tertutup

Himpunan bilangan asli N dikatakan tertutup terhadap operasi penjumlahan dan perkalian, karena jumlah dan hasil kali dari 2 bilangan asli merupakan bilangan asli pula. Dalam notasi matematika biasa ditulis sebagai berikut:
a.       Penjumlahan
Untuk setiap n1, n2 Î N, berlaku (n1 + n2) Î N
b.      Perkalian
Untuk setiap n1, n2 Î N, berlaku (n1n2) Î N

2.      Sifat Komutatif

a.      Penjumlahan
Untuk setiap n1, n2 Î N, berlaku n1 + n2  = n2 + n1
b.      Perkalian
Untuk setiap n1, n2 Î N, berlaku n1n2 = n2n1

3.      Sifat Asosiatif

a.      Penjumlahan
Untuk setiap n1, n2, n3 Î N, berlaku (n1 + n2) + n3 = n1 + (n2 + n3)
b.      Perkalian
Untuk setiap n1, n2, n3 Î N, berlaku (n1n2)n3 = n1(n2n3)

4.      Sifat Identitas
a.      Penjumlahan
Untuk setiap n Î N, berlaku n + 0 = 0 + n = n
(0 sebagai bukan identitas penjumlahan, 0 Ï N)
b.      Perkalian
Untuk setiap n Î N, berlaku n × 1 = 1 × n = n
(1 sebagai identitas pekalian, 1 Î N)

5.      Sifat Distributif
a.       Distributif kiri
Untuk setiap n1, n2, n3 Î N, berlaku (n1 + n2)n3= n1n3 + n2n3
b.      Distributif kanan
Untuk setiap n1, n2, n3 Î N, berlaku n1 (n2 + n3) = n1n2 + n1n3


1.2.3.        Bilangan genap

Sebuah bilangan bulat positif a disebut bilangan genap bila salah satu faktor dari a adalah 2. Kumpulan semua bilangan genap disebut himpunan bilangan genap.

1.2.4.        Bilangan ganjil

Bilangan yang bukan genap disebut bilangan ganjil. Kumpulan semua bilangan ganjil disebut himpunan bilangan ganjil.


1.2.5.        Bilangan komposit

Sebuah bilangan bulat positif k ¹ 1 disebut bilangan komposit bila bilangan k tersebut dapat dinyatakan sebagai hasil kali dua atau lebih bilangan bulat positif  ¹ 1. Kumpulan semua bilangan komposit disebut himpunan bilangan komposit.

1.2.6.        Bilangan prima

Sebuah bilangan bulat positif p ¹ 1 disebut bilangan prima bila bilangan p tersebut merupakan perkalian antara 1 dan p, atau bilangan p hanya mempunyai 2 faktor yaitu 1 dan p sendiri. Kumpulan semua bilangan prima disebut himpunan bilangan prima, yaitu {2, 3, 5, 7, …}

Definisi faktor prima:
Setiap bilangan komposit k dapat dinyatakan sebagai perkalian unik antar beberapa bilangan prima . Secara notasi matematika sebagai berikut:
dimana p1, p2, ..., pn merupakan bilangan-bilangan prima berbeda dan e1, e2,  …, en merupakan bilangan-bilangan cacah. p1, p2, ..., pn disebut sebagai faktor prima dari k.

Di dalam himpunan bilangan asli, kita bisa melihat sifat-sifat penting lainnya yang berhubungan dengan faktor dan kelipatan persekutuan dari bilangan-bilangan asli. Di antaranya adalah FPB dan KPK.

a.                 Faktor persekutuan terbesar (FPB)

Faktor persekutuan terbesar (FPB) dari dua atau lebih bilangan asli adalah bilangan asli terbesar yang merupakan anggota himpunan semua faktor persekutuan dari bilangan-bilangan itu atau bilangan asli terbesar yang habis membagi bilangan-bilangan tersebut.

Contoh 1.3
Tentukan FPB dari 8 dan 36.

Penyelesaian :
Himpunan faktor dari 8 = {1, 2, 4, 8}
Himpunan faktor dari 36 = {1, 2, 3, 4, 6, 9, 12, 18, 36}
Jadi himpunan faktor dari 8 dan 36 adalah: {1, 2, 4}, sehingga FPB dari 8 dan 36 adalah 4.


·               Menentukan FPB

Untuk menentukan FPB dari dua atau lebih bilangan asli dapat dilakukan dengan berbagai macam metode, yaitu:

·         Mendaftarkan semua faktor dari bilangan-bilangan tersebut

Metode ini merupakan metode yang sangat sederhana, yaitu dengan mendaftarkan semua faktor dari setiap bilangan tersebut ke dalam sebuah himpunan, setelah itu  menentukan irisan himpunan-himpunan tersebut dan dicari elemen terbesar dari irisan  himpunan tersebut. Contoh 1.3 menggunakan metode ini.
·         Metode faktor prima

Metode ini merupakan metode yang sangat umum digunakan, yaitu dengan menguraikan setiap bilangan tersebut sebagai perkalian antar faktor primanya. Kemudian untuk menentukan FPB dengan cara:
o   Tentukan semua faktor prima yang sama antar bilangan tersebut
o   Tentukan bilangan terkecil dari pemangkatan setiap faktor prima yang sama di atas yang berada pada bilangan-bilangan tersebut
o   FPB dari bilangan-bilangan tersebut adalah perkalian antar semua bilangan terkecil yang sudah diperoleh di atas
Namun metode ini dapat dilakukan jika bilangan-bilangan asli yang ingin dicari FPB nya merupakan bilangan komposit. Secara matematis sebagai berikut:
Misalkan a, b bilangan asli yang mempunyai faktorisasi prima:
a =  dan b =
dimana pangkat adalah bilangan bulat tidak negatif, dan semua prima yang muncul di faktorisasi a atau b muncul di faktorisasi kedua-duanya, bisa dengan pangkat nol.
Maka FPB(a,b) adalah
FPB (a, b) =
dimana min(x, y) menyatakan nilai terkecil antara x dan y.


Contoh 1.4
Tentukan FPB dari 48 dan 72

Penyelesaian :
Perhatikan bahwa:
48 = 24 ´ 3
            72 = 23 ´ 32
Faktor-faktor prima yang sama dari 48 dan 72 adalah 2 dan 3. Sedangkan pemangkatan terkecil yang diambil adalah 23 dan 3. Sehingga FPB(48, 72) = 23 ´ 3 = 24.

·         Algoritma Euclid

Secara sederhana metode yang dilakukan algoritma Euclid adalah mencari faktor persekutuan terbesar dari bilangan-bilangan yang telah direduksi terus menerus. Cara mereduksi bilangan ini adalah dengan melihat sisa pembagian antara satu bilangan dengan bilangan yang lain. Sisa tak nol terakhir adalah nilai FPB yang dimaksud.



Misalkan ingin dicari FPB(91, 287).

Langkah pertama, bagi bilangan yang lebih besar dengan  bilangan yang lebih kecil, diperoleh
287 = 91.3 + 14           atau                 287 – 91.3 = 14
Artinya pembagi dari 91 dan 287 adalah juga pembagi dari 14 atau
FPB(91, 287) = FPB(14, 91),
sehingga selanjutnya adalah mencari FPB(14, 91).
Bagi bilangan yang lebih besar dengan  bilangan yang lebih kecil, diperoleh
91 = 14.6 + 7               atau                 91 – 14.6 = 7  
Artinya FPB(91, 287) = FPB(14, 91) = FPB(7, 14).
Bagi bilangan yang lebih besar dengan  bilangan yang lebih kecil, diperoleh
14 = 7.2 + 0
Artinya FPB(7, 14) = 7.
Sehingga FPB(91, 287) = FPB(14, 91) = FPB(7, 14) = 7.

Lemma Misalkan a = bq + r, dengan  a, b, q dan r adalah bilangan bulat. Maka FPB(a, b) = FPB(b, r).

Contoh 1.5
Tentukan FPB dari 8 dan 36, 48 dan 72.

Penyelesaian :
FPB (8, 36)  = FPB (8, 8´4+4)
                        = FPB(8, 4)
                        = 4

FPB(48, 72) = FPB(48, 48+24)
                        = FPB(48, 24)
                        = 24

b.                Kelipatan persekutuan terkecil (KPK)

Kelipatan persekutuan terkecil dari dua atau lebih bilangan asli adalah bilangan asli terkecil yang merupakan anggota himpunan semua kelipatan persekutuan antara bilangan-bilangan tersebut atau bilangan asli terkecil yang habis dibagi oleh bilangan-bilangan tersebut.

Contoh 1.6
Tentukan KPK dari 2 dan 3   

Penyelesaian :
Himpunan kelipatan dari 2 = {2, 4, 6, 8, 10, 12, …}
Himpunan kelipatan dari 3 = {3, 6, 12, 15, …}
Jadi himpunan kelipatan dari 2 dan 3 adalah: {6, 12, …}, sehingga KPK dari 2 dan 3 adalah 6.

·               Menentukan KPK

Untuk menentukan KPK dari dua atau lebih bilangan asli dapat dilakukan dengan berbagai macam metode, yaitu:

·         Mendaftarkan semua kelipatan dari bilangan-bilangan tersebut

Metode ini merupakan metode yang sangat sederhana, yaitu dengan mendaftarkan semua kelipatan dari setiap bilangan tersebut ke dalam sebuah himpunan, setelah itu  menentukan irisan himpunan-himpunan tersebut dan dicari elemen terkecil dari irisan  himpunan tersebut. Contoh 1.6 menggunakan metode ini.





·         Metode faktor prima

Metode ini merupakan metode yang sangat umum digunakan, yaitu dengan menguraikan setiap bilangan tersebut sebagai perkalian antar faktor primanya. Kemudian untuk menentukan KPK dengan cara:
o   Tentukan semua faktor prima yang sama antar bilangan tersebut
o   Tentukan bilangan terbesar dari pemangkatan setiap faktor prima yang sama di atas yang berada pada bilangan-bilangan tersebut
o   FPB dari bilangan-bilangan tersebut adalah perkalian antar semua bilangan terbesar yang sudah diperoleh di atas dan semua pemangkatan faktor prima yang berbeda yang ada di setiap bilangan tersebut.
Namun metode ini hanya dapat dilakukan jika bilangan-bilangan asli yang ingin dicari KPK nya merupakan bilangan komposit. Secara matematis sebagai berikut:
Seperti FPB, KPK antara dua bilangan bulat juga dapat dicari dengan  faktorisasi prima dari masing-masing bilangan, dengan  KPK(a, b) adalah  
KPK (a, b) =
dimana maks(x, y) menyatakan nilai terbesar antara x dan y.

Contoh 1.7
Tentukan KPK dari 48 dan 72, 12 dan 15

Penyelesaian :
Perhatikan bahwa:
48 = 24 ´ 3
            72 = 23 ´ 32
Faktor-faktor prima yang sama dari 48 dan 72 adalah 2 dan 3. Sedangkan pemangkatan terbesar yang diambil adalah 24 dan 32. Sehingga KPK(48, 72) = 24 ´ 32 = 144.
Perhatikan bahwa:
12 = 22 ´ 3
            15 = 3 ´ 5
Faktor-faktor prima yang sama dari 12 dan 15 adalah 3. Sedangkan pemangkatan terbesar yang diambil adalah  3. Semua pemangkatan faktor prima yang berbeda dari dua bilangan tersebut adalah 22 dan 5.  Sehingga KPK(12, 15) = 3 ´ 22 ´ 5 = 60.


c.                  Sifat-sifat FPB dan KPK

Beberapa sifat FPB dan KPK yang penting adalah:

            Misalkan a, b, c, d, n adalah bilangan-bilangan asli, maka:

o   FPB(ca, cb) = c ´ FPB(a, b)
o   FPB(a, bc) = FPB (a, c ´ FPB(a, b))
o   FPB(an, bn) = (FPB(a, b))n
o   Jika FPB(a, b) = d, maka FPB(a/d, b/d) = 1
o   FPB(a, b) ´ KPK(a, b) = ab


Problem Set

1.      rJika m dan n adalah dua bilangan asli dan mn = n + 15, maka carilah semua bilangan n yang mungkin.

2.      Bila diketahui bahwa hasil dari perkalian dari dua bilangan asli adalah 84, tentukanlah hasil penjumlahan dua bilangan asli tersebut yang mungkin terjadi.

3.      Tentukan semua bilangan asli x dan y, jika x2 + y2 = 63

4.      Jika 200 × 201 × 202 × … × 210 dapat ditulis dalam bentuk 2n.m, dimana m merupakan bilangan ganjil. Berapakah nilai dari n ?

5.      Jika sembarang bilangan asli yang terdiri dari dua digit kalian pilih. Berapakah hasil yang kalian temukan jika bilangan tersebut dikurangi dengan jumlah dari kedua digitnya dan kemudian hasilnya dibagi dengan 9 ? Jelaskan jawaban kalian !

6.      Apakah benar setiap selisih kuadrat bilangan ganjil positif dengan bilangan satu merupakan kelipatan 4? Jelaskan !

7.      Apabila suatu bilangan terdiri dari 3 digit dikalikan dengan 4, maka hasil kalinya terdiri dari 3 digit dan mempunyai digit-digit yang sama namun digit pertama dan digit ketiga saling bertukar. Carilah bilangan tersebut.

8.      Apabila suatu bilangan terdiri dari 4 digit dikalikan dengan 9, maka hasil kalinya terdiri dari 4 digit dan mempunyai digit-digit yang sama namun digit pertama dan digit keempat saling bertukar. Carilah kemugkinan bilangan terbesarnya.

9.      Jika 2006 dapat dinyatakan salam penjumlahan dari beberapa bilangan asli berurutan, maka berapa banyak cara penjumlahan tersebut.

10.   Jika x, y dan z adalah bilangan-bilangan asli yang memenuhi persamaan
x + 3y + 7z = 50
      Tentukan semua tripel (x, y, z) yang memenuhi persamaan tersebut.

11.  Suatu bilangan asli terdiri dari 3 digit ‘abc’ yang mempunyai sifat-sifat sebagai berikut:
a.  digit ratusan = digit puluhan + digit satuan
b. b(c + 1) = 52 – 4a  
      Tentukan semua bilangan yang memenuhi sifat-sifat tersebut.

12.  Suatu bilangan asli terdiri dari 4 digit yang mempunyai sifat-sifat sebagai berikut:
a.  digit ribuan = digit puluhan
b. digit ratusan = satu lebihnya dari digit satuan
      Tentukan semua bilangan yang memenuhi sifat-sifat tersebut.

13.  Tentukan semua bilangan bulat n sehingga  juga bulat

14.  Buktikan bahwa semua bilangan yang terdiri dari 6 digit ‘abcabc’ selalu habis dibagi 91

15.  Sebuah bilangan terdiri dari 3 digit yang habis dibagi 12 dan hasil baginya merupakan jumlah-jumlah dari digit-digit bilangan tersebut. Tentukanlah bilangan yang yang dimaksud tersebut.


1.3.         KETERBAGIAN

Definisi  
Jika a dan b bilangan bulat dan a ¹ 0, dikatakan a membagi b jika ada bilangan bulat s sehingga b = as. Jika a membagi b maka disebut a faktor dari b dan b adalah kelipatan dari a. Notasi a|b jika a membagi b dan ab jika a tidak membagi b.

Teorema
Jika a, b, dan c bilangan bulat, maka
1.      Jika a|b dan a|c maka a|(b + c)
2.      Jika a|b maka a|bx untuk sebarang bilangan bulat x
3.      Jika a|b dan b|c maka a|c

Sifat-sifat pembagian oleh 2n
Suatu bilangan bulat habis dibagi 2n jika n bilangan terakhir dari bilangan tersebut habis dibagi 2n.
  1. n = 1, suatu bilangan habis dibagi 2 jika angka terakhir bilangan tersebut habis dibagi 2.
  2. n = 2, suatu bilangan habis dibagi 4 (22) jika bilangan 2 angka terakhir bilangan tersebut habis dibagi 4.
  3. i = 3, suatu bilangan habis dibagi 8 (23) jika bilangan 3 angka terakhir bilangan tersebut habis dibagi 8.

Teorema
Misalkan a = anan-1 ... a3a2a1a0 sembarang bilangan bulat.
1.      3|a  jika dan hanya jika 3|( an + an-1 + ... + a3 + a2 + a1 + a0)
2.      5|a  jika dan hanya jika a0=0 atau a0=5
3.      7|a  jika dan hanya jika 7| anan-1... a3a2a1 2a0  atau 7| anan-1... a3a2a1 +5a0
4.      9|a  jika dan hanya jika 9|( an + an-1 + ... + a3 + a2 + a1 + a0)
5.      11|a  jika dan hanya jika 11|( anan-1 + an-2an-3 + …)
6.      13|a  jika dan hanya jika 13| anan-1... a3a2a1 9a0  atau 13| anan-1... a3a2a1 +4a0
7.      17|a  jika dan hanya jika 17| anan-1... a3a2a1 5a0  atau 17| anan-1... a3a2a1 +12a0
8.      19|a  jika dan hanya jika 19| anan-1... a3a2a1 17a0  atau 19| anan-1... a3a2a1 +2a0


Teorema Algoritma pembagian.
Misalkan a bilangan bulat dan d bilangan bulat positif. Terdapat bilangan bulat q dan r yang unik, dengan  0 £ r < d sehingga a = dq + r

Definisi
Dalam persamaan yang diberikan pada algoritma pembagian, d disebut pembagi (divisor), a disebut yang dibagi (divident), q disebut hasil bagi (quotient), dan r disebut sisa (remainder)

Contoh 1.8
Berapakah hasil bagi dan sisa jika 101 dibagi 11?

Penyelesaian
Karena 101 = 11´9 + 2, maka hasil baginya adalah 9 dan sisanya adalah 2
Contoh 1.9
Berapakah hasil bagi dan sisa jika –11 dibagi 3?

Penyelesaian
Karena –11 = 3 ´ –4 + 1, maka hasil baginya adalah –4  dan sisanya adalah 1

Problem Set

1.      Hitung 123123 : 1001

2.      Tunjukkan bahwa 7 membagi 22225555 + 55552222

3.      Tentukan angka terakhir dari

4.      Misalkan N adalah hasil kali dari tiga bilangan bulat positif yang nilainya sama dengan 6 kali penjumlahan ketiga bilangan tersebut. Satu dari bilangan tersebut adalah penjumlahan dari dua bilangan yang lainnya. Tentukan jumlah dari semua nilai yang mungkin untuk N

5.      n adalah sebuah bilangan yang terdiri dari 4 digit bilangan bulat dengan urutan menurun dari kiri ke kanan. Carilah jumlah semua nilai sisa yang mungkin jika n dibagi 3

6.      Pilih satu bilangan sembarang yang lebih besar dari 1. Bilangan berikutnya diperoleh dari pembagian antara bilangan yang lebih besar 1 dari bilangan yang dipilih dengan bilangan yang lebih kecil 1 dari bilangan yang dipilih. Kemudian lakukan hal yang sama sekali lagi. Apakah yang terjadi? Jelaskan





1.4.         PERSAMAAN DIOPHANTINE

Suatu peramaan berbentuk ax + by = c dengan a, b, dan c bilangan bulat dan a, b tidak nol disebut persamaan diopanthine, jika penyelesaiannya dicari pada himpunan bilangan bulat.

Teorema
Persamaan diopanthine ax + by = c mempunyai penyelesaian jika dan hanya jika FPB(a, b) membagi c.

Contoh 1.10
Uji apakah persamaan 24x + 78y = 34 mempunyai penyelesaian di himpunan bilangan bulat.


Penyelesaian
Pertama-tama kita cari FPB dari 24 dan 78 dengan algoritma euclid sebagai berikut:
            78 = 3´24 + 6
24 = 4´6 + 0
Sehingga FPB(24,78)=6, karena 6 adalah sisa pembagian terakhir yang tak nol. Karena 6  34, maka persamaan 24x + 78y = 34 tidak mempunyai penyelesaian di himpunan bilangan bulat.

Teorema
Jika d = FPB(a, b) dan x0, y0 adalah penyelesaian dari persamaan diopanthine ax + by = c, maka penyelesaian umum dari persamaan tersebut adalah
 dan
dengan k parameter bilangan bulat.

Contoh 1.11
Cari penyelesaian dari persamaan 56x + 72y = 40.


Penyelesaian
Pertama-tama kita cari FPB dari 56 dan 72 dengan algoritma euclid sebagai betikut:
            72 = 1´56 + 16
56 = 3´16 + 8
16 = 2´8 + 0

Sehingga FPB(56,72)=8, karena 8 adalah sisa pembagian terakhir yang tak nol. Karena 8|40, maka persamaan 56x + 72y = 40  mempunyai penyelesaian di himpunan bilangan bulat. Selanjutnya kita mencari nilai x0 dan y0. Perhatikan bahwa :
            40 = 5´8 = 5´(56 – 3´16)
                            = 5´56 – 15´16
                            = 5´56 – 15´(72 – 1´56)
                            = 20´56 – 15´72
Sehingga nilai x0=20 dan y0= –15. Akhirnya solusi umum dari persamaan diophantine 56x + 72y = 40 adalah :
                        x = 20 + 9k dan y = –15 – 7k
dengan k parameter bilangan bulat.


Problem Set

Ujilah apakah persamaan berikut mempunyai penyelesaian di bilangan bulat. Jika mempunyai penyelesaian, carilah penyelesaian tersebut.
a.       14x + 35y = 93
b.      24x + 138y = 18
c.       754x + 221y = 13




1.5.         ARITMATIKA MODULAR

 

Jika waktu sekarang adalah jam 7, jam berapakah 50 jam dari sekarang? Untuk mengetahui jam tersebut, kita harus mencari sisa pembagian 50 dengan  24 dan menambahkannya ke jam 7. Ada banyak kasus-kasus seperti ini dimana yang diperlukan hanyalah sisa pembagian sementara hasil baginya tidak penting.

Definisi
Misalkan a bilangan bulat dan m bilangan bulat positif. Digunakan a mod m untuk menyatakan sisa hasil pembagian a oleh m.

Contoh 1.12
Berapakah 17 mod 5 dan 133 mod 9 ?

Penyelesaian
Perhatikan bahwa 17 = 3´5 + 2, sehingga 17 mod 5 = 2, sedangkan 133 = 14´9 + 7, sehingga 133 mod 9 = 7

Definisi
Jika a dan b bilangan bulat dan m bilangan bulat positif, maka a adalah kongruen dengan  b modulo m jika m | (a – b). Digunakan notasi a º b (mod m) untuk menyatakan a kongruen dengan b modulo m. Jika a dan b tidak kongruen modulo m, ditulis ab (mod m).

Contoh 1.13
Periksa apakah apakah 17 kogruen ke 5 modulo 6.

Penyelesaian
Perhatikan bahwa, karena 6 | (17 – 5)=12, maka 17 º 5 (mod 6)


Teorema
Misalkan m bilangan bulat positif. Bilangan bulat a dan b adalah kongruen modulo m jika dan hanya jika ada bilangan bulat k sehingga  a = b + km.


Teorema
Misalkan m bilangan bulat positif. Jika a º b (mod m) dan c º d (mod m), maka a + c º b + d (mod m) dan ac º bd (mod m)


Contoh  1.14
Tentukan angka satuan pada bilangan 32005.

Penyelesaian
Untuk mencari angka satuan kita gunakan sisa hasil pembagian dengan 10. Karena 32º –1 (mod 10) , maka:
            32005 º (32)1002 ´ 3 (mod  10)
                     º (-1)1002 ´ 3 (mod 10)
                     º 1 ´ 3 (mod 10)
                     º  3 (mod 10)
Sehingga angka satuan dari 32005 adalah 3.

Teorema
Misalkan m bilangan bulat positif dan a, b, dan c bilangan bulat. Jika ac º bc (mod m) dan gcd(c, m) = 1, maka a º b (mod m).





1.6.         CHINESE REMAINDER THEOREM

Bila x dibagi 3 bersisa 2, x dibagi 5 bersisa 3, dan x dibagi 7 bersisa 2, berapakah x?
Masalah di atas dapat diterjemahkan menjadi masalah berikut:


Berapakah x sehingga
x º 2 (mod 3)
x º 3 (mod 5)
x º 2 (mod 7).
Masalah seperti ini dapat diselesaikan dengan the chinese remainder theorem.

Teorema The Chinese remainder theorem.
Misalkan m1, m2, …, mn bilangan bulat yang saling relatif prima. Sistem
x º a1 (mod m1)
x º a2 (mod m2)
x º an (mod mn)
memiliki satu solusi tunggal modulo m = m1 m2mn. Dengan  kata lain, terdapat satu dan hanya satu x dengan  0 £ x < m yang memenuhi sistem tersebut.

Contoh 1.15
Tentukan x yang memenuhi sistem
x º 2 (mod 3)
x º 3 (mod 5)
x º 2 (mod 7)





Penyelesaian
Perhatikan bahwa sistem di atas ekivalen dengan sistem berikut:
35x º 70 (mod 105)
21x º 63 (mod 105)
15x º 30 (mod 105)

Karena x º 36x – 35x º (21x +15x) – 35x º (63+30) – 70 º 23 mod 105, maka x = 23 + 105k, dimana k adalah parameter bilangan bulat.


Problem Set

Cari penyelesaian dari sistem persamaan berikut:
a.       x º 1 (mod 2), x º 2 (mod 3)
b.      x º 5 (mod 15), 4x º 7 (mod 11)
c.       x º 1 (mod 2), x º 3 (mod 3), x º 1 (mod 5)
d.      x º 1 (mod 2), x º 2 (mod 3), x º 4 (mod 5)

Tidak ada komentar:

Posting Komentar