teori bilangan tugas uas 2014.docx

8/10/2019 Teori Bilangan Tugas UAS 2014.docx

1/35

Tugas Akhir Teori Bilangan

Tulisan ini dibuat untuk melengkapi tugas akhir mata kuliah Teori Bilangan

Nama : Egi Pratama Hidayat

No. Reg : 3125140586

Jurusan Matematika

Fakultas Matematika dan Ilmu Pengetahuan Alam

Universitas Negeri Jakarta


2/35

Bukti Langsung

Banyak sifat dan teorema yang ketika sekolah dulu kita gunakan tanpa tahu

asal usul pembuktiannya, tapi ketika kita kuliah di matematika, sudah tidak

asing lagi dengan pembuktian sifat-sifat atau teorema. Untuk

membuktikannya tidak lepas dari teknik yang digunakan. Teknik yang biasa

digunakan yaitu teknik Pembukitan Langsung, teknik Tidak Langsung dan

Induksi Matematika. Tulisan ini akan membahas sedikit tentang teknik

pembuktian langsung.

Bukti langsung adalah salah satu cara pembuktian sifat atau teorema

matematika dengan penarikan kesimpulan dengan memanfaatkan

silogisme, modus ponens dan modus tollens. Secara logika pembuktian q

benar secara langsung atau ekuivalen dengan membuktikan bahwa

pernyataan q benar dimana diketahui p benar.

Metode pembuktian langsung adalah suatu proses pembuktian pembuktian

menggunakan alur maju, mulai dari hipotesis dengan menggunakan

implikasi logic sampai pada pernyataan kesimpulan. Hukum-hukum dalam

matematika pada umumnya berupa proposisi atau pernyataan berbentuk

implikasi (p q) atau biimplikasi (p q) atau pernyataan kuantifikasi yangdapat diubah bentuknya menjadi pernyataan implikasi. Misal kita punya

teorema p \Rightarrow q, dengan p disini sebagai hipotesis yang digunakan

sebagai fakta yang diketahui atau sebagai asumsi. Selanjutnya, dengan

menggunakan p kita harus menunjukkan bahwa berlaku q.

Contoh 1 :

Buktikan, jika x bilangan ganjil maka x2bilangan ganjil.

Bukti :

Diketahui x ganjil, jadi dapat didefinisikan sebagai x := 2n + 1, untuk suatu n

Z. Selanjutnya, x2 = (2n + 1)2 = 4n2 + 4n + 1 = 2 (2n2 + 2) + 1, dengan

mengambil m := 2n2 + 2, m dengan n Z maka x2 = 2m + 1. Karena m

merupakan bilangan bulat maka disimpulkan x2ganjil.


3/35

Contoh 2 :

Buktikan bahwa jika a membagi b dan b membagi c maka a membagi c

dengan a, b, dan c bilangan bulat.

Bukti :

a | b artinya b = ka untuk suatu k Z (i)

b | c artinya c = lb untuk suatu l Z (ii)

akan dibuktikan bahwa c = ma untuk suatu m Z

substitusi (i) ke (ii), sehingga diperoleh

c = lb = l(ka) = (lk)a

karena lk adalah perkalian bilangan bulat yang hasilnya bilangan bulat juga

(sifat tertutup perkalian bilangan bulat), maka ambil m := lk untuk dengan m

Z, sehingga diperoleh

c = ma untuk suatu m Z

Contoh 3 :

Buktikan bahwa a + b bilangan ganjil jika dan hanya jika a atau b bilangan

ganjil dengan a dan b bilangan bulat.

Bukti :

Pernyataan diatas ekuivalen dengan

(i) jika a + b bilangan ganjil maka a atau b bilangan ganjil

(ii) jika a atau b bilangan ganjil maka a + b bilangan ganjil

Jadi pada pembuktian ini kita akan membuktikan (i) dan (ii).

Bukti bagian (i)

misalkan a dan b bilangan bulat sebarang dan a + b bilangan ganjil.

akan dibuktikan a atau b bilangan ganjil.


4/35

tanpa mengurangi perumuman akan dibuktikan a ganjil

klaim : b bilangan genap (b := 2m untuk suatu m Z)

a + b bilangan ganjil

a + b = 2k + 1 untuk suatu k Z

substitusi b = 2m sehingga diperoleh

a + 2m = 2k + 1

a = 2k2m + 1 = 2(km) + 1

karena tertutup terhadap operasi pengurangan, maka ambil l := k m,

sehingga diperoleh

a = 2l + 1, jadi a bilangan ganjil

selanjutnya akan dibuktikan b bilangan ganjil

klaim : a bilangan genap (a := 2p untuk suatu p Z)

a + b bilangan ganjil

a + b = 2q + 1 untuk suatu k Z

substitusi a = 2p sehingga diperoleh

2p + b = 2q + 1

b = 2q2p + 1 = 2(pq) + 1

karena tertutup terhadap operasi pengurangan, maka ambil r := p q,

sehingga diperoleh

b = 2r + 1, jadi b bilangan ganjil


5/35

Bukti bagian (ii)

misal a dan b bilangan bulat sebarang dan a bilangan ganjil (a := 2m + 1

untuk suatu m Z) dan b bilangan genap (b := 2n untuk suatu n Z).

Sehingga

a + b = 2m + 1 + 2n = 2(m + n) + 1

karena tertutup terhadap operasi penjumlahan bilangan bulat, ambil p := m

+ n, sehingga

a + b = 2p + 1 untuk suatu p Z

jadi a + b bilangan ganjil

Contoh 4 :

Buktikan bahwa perkalian tiga bilangan asli berurutan habis dibagi 3

Bukti :

misal tiga bilangan asli berurutan didefinisikan sebagai n, n + 1 dan n + 2

untuk suatu n Z dan perkalian tiga bilangan asli adalah m. Disini kita akan

menggunakan 3 kasus, yaitu 3k, 3k + 1, 3k + 2

(i) m = (n)(n + 1)(n + 2)

= (3k)(3k + 1)(3k + 2)

= 3k(9k2 + 9k + 2)

= 3(9k3 + 9k + 3)

m adalah bilangan kelipatan 3

(ii) m = (n)(n + 1)(n + 2)

= (3k + 1)(3k + 1 + 1)(3k + 1 + 2)

= (3k + 1)(3k + 2)(3k + 3)

= (3k + 1)(9k2 + 15k + 6)

= 27k3 + 54k2 + 21k + 6

= 3(9k3 + 18k3+ 7k + 2)



6/35

(iii) m = (n)(n + 1)(n + 2)

= (3k + 2)(3k + 2 + 1)(3k + 2 + 2)

= (3k + 2)(3k + 3)(3k + 4)

= (3k + 2)(9k2 + 21k + 12)

= 27k3 + 81k2 + 78k + 24

= 3(9k3 + 27k2 + 26k + 8)


dari (i), (ii), dan (iii) terlihat bahwa m merupakan bilangan kelipatan 3

berakibat m habis dibagi 3.


7/35

Bukti Tak Langsung

Untuk membuktikan dengan menggunakan bukti tidak langsung, digunakan

cara dengan membuat pernyataan pengingkaran dari yang harusdibuktikan. Jika dari pernyataan yang diingkari tersebut diperoleh suatu

kontradiksi (bertentangan dengan ketentuan yang diberikan) atau

kemustahilan, berarti pernyataan yang harus dibuktikan adalah benar.

Untuk membuktikan p benar, kita harus membuktikan jika ~p salah.

Berikut ini adalah contoh pembuktian tidak langsung.

Contoh 1:

Buktikan bahwa bilangan irasional.

Bukti:

Andaikan bilangan rasional, = . Dengan m dan n bilangan bulat yang relatif

prima yaitu mempunyai faktor persekutuan terbesar (FPB)= 1. Jika kedua ruas

dikuadratkan diperoleh 2= adalah bilangan genap adalah bilangan genap

.

Berarti genap genap m dan n mempunyai faktor persekutuan 2. Padahal m

dan n prima relatif mempunyai FPB =1. Jadi pengandaian bilangan rasionaladalah salah. Jadi tidak dapat dinyatakan sebagai , berarti adalah

bilangan irasional.

Contoh 2:

Buktikan jumlah 2 bilangan genap adalah bilangan genap.

Bukti:

Misalkan jumlah 2 bilangan genap adalah bilangan ganjil

Misalkan bilangan pertama = 2p, dan bilangan kedua = 2q, di mana p dan q

bilangan cacah. Jumlah bilangan pertama dan kedua = 2p + 2q = 2

(p+q)=2r,

dengan r = p+q sehingga r bilangan cacah. Ternyata jumlah 2 bilangan

genap adalah bilangan genap. Hal ini bertentangan dengan yang

dimisalkan. Sehingga dapat disimpulkan jumlah 2 bilangan genap adalah

bilangan genap.


8/35

Induksi Matematika

Induksi Matematika merupakan suatu teknik yang dikembangkan untuk

membuktikan pernyataan. Induksi Matematika digunakan untuk mengecekhasil proses yang terjadi secara berulang sesuai dengan pola tertentu.

Indukasi Matematika digunakan untuk membuktikan universal statements.

A S(n) dengan A N dan N adalah himpunan bilangan positif atau

himpunan bilangan asli.

S(n) adalah fungsi propositional.

TAHAPAN INDUKSI MATEMATIKA

1. Basis Step : Tunjukkan bahwa S(1) benar

2. Inductive Step : Sumsikan S(k) benar, akan dibuktikan S(k)

S(k+1) benar

3.

Conclusion : S(n) adalah benar untuk setiap n bilangan integer

positif

PEMBUKTIAN INDUKSI MATEMATIKA

Contoh 1 :

Buktikan bahwa :

1 + 2 + 3 + + n = n(n+1)

untuk setiap n bilangan integer positif

Jawab :

Basis : Untuk n = 1 akan diperoleh :

1 = 1 . (1+1)

Induksi : misalkan untuk n = k asumsikan 1 + 2 + 3 + + k = k (k+1)

adib. Untuk n = k+1 berlaku

1 + 2 + 3 + + (k+1) = (k+1) (k+2)

Jawab :


9/35

1 + 2 + 3 + + (k+1) = (k+1) (k+2) / 2

1 + 2 + 3 + + k + (k+1) = (k+1) (k+2) / 2

k (k+1) / 2 + (k+1) = (k+1) (k+2) / 2

(k+1) [ k/2 +1 ] = (k+1) (k+2) / 2

(k+1) (k+2) = (k+1) (k+2) / 2

(k+1) (k+2) / 2 = (k+1) (k+2) / 2

Kesimpulan : 1 + 2 + 3 + + n = n (n +1) Untuk setiap bilanga bulat positif n

Contoh 2 :

Buktikan bahwa :

1 + 3 + 5 + + n = (2n - 1) = n2

untuk setiap n bilangan bulat positif

Jawab :


1 = 12 1 = 1

Induksi : misalkan untuk n = k asumsikan 1 + 3 + 5 + + (2k 1) = k2

adib. Untuk n = k + 1 berlaku

1 + 3 + 5 + + (2 (k + 1) 1) = (k + 1)2

1 + 3 + 5 + + (2k + 1) = (k + 1)2

1 + 3 + 5 + + ((2k + 1) 2) + (2k + 1) = (k + 1)2

1 + 3 + 5 + + (2k - 1) + (2k + 1 ) = (k + 1)2

k 2 + (2K + 1) = (k + 1)2

k 2 + 2K + 1 = k 2 + 2K + 1

Kesimpulan : 1 + 3 + 5 + + n = (2n - 1) = n2, Untuk setiap bilangan bulat

positif n


10/35

Contoh 3 :

Buktikan bahwa :

N 3 + 2n adalah kelipatan 3

untuk setiap n bilangan bulat positif

Jawab :


1 = 13+ 2(1) 1 = 3 , kelipatan 3

Induksi : misalkan untuk n = k asumsikan k 3 + 2k = 3x

adib. Untuk n = k + 1 berlaku

(k + 1)3 + 2(k + 1) adalah kelipatan 3

(k 3 + 3k 2 + 3 k+1) + 2k + 2

(k 3 + 2k) + (3k 2 + 3k + 3)

(k 3 + 2k) + 3 (k 2 + k + 1)

Induksi

3x + 3 (k 2 + k + 1)

3 (x + k 2 + k + 1)

Kesimpulan : N 3 + 2n adalah kelipatan 3

Untuk setiap bilangan bulat positif n


11/35

Teori Binomial

Di aljabar, penjumlahan dua suku, seperti a+ b, disebut binomial. Teorema

binomial memberikan bentuk ekspansi dari pangkat binomial (a+ b)n, untuk

setiap nbilangan bulat tidak negatif dan semua bilangan real adan b.

Perhatikan apa yang terjadi ketika kita menghitung beberapa pangkat yang

pertama dari a+ b. Berdasarkan sifat distributif, kita mendapatkan bahwa

pangkat dari a+ bmerupakan penjumlahan dari suku-suku yang berupa

kombinasi perkalian dari adan b. Perhatikan ilustrasi berikut.

Sekarang perhatikan ekspansi dari (a+ b)4. Suku-suku dari ekspansi ini

diperoleh dengan mengalikan satu dari dua suku faktor pertama dengan

satu dari dua suku faktor kedua dengan satu dari dua suku faktor ketiga dan

dengan satu dari dua suku faktor keempat. Sebagai contoh,

suku ababdiperoleh dengan mengalikan suku-suku adan byang ditandai

dengan tanda panah.

Karena ada dua kemungkinan adan bdari setiap suku yang dipilih pada 1

dari 4 faktor suku-suku ekspansi binomial, maka akan ada 24= 16 suku

ekspansi (a+ b)4.

Selanjutnya, suku-suku serupa, yaitu suku-suku yang memiliki

faktor adan bsama banyak dapat dikombinasikan karena perkalian bersifat

komutatif. Tetapi kita perlu mengetahui banyaknya masing-masing sukuyang serupa tersebut. Sebagai contoh kita akan menentukan banyaknya


12/35

suku yang terdiri dari tiga adan satu b. Untuk menentukan banyaknya suku

ini sama dengan menentukan banyaknya cara kita mengambil 1 bilangan 1

sampai 4 sebagai nomor urut dari faktor b. Salah satu contohnya kita

mungkin mendapat bilangan 3 yang merepresentasikan aaba(3 merupakan

nomor urut dari b, sedangkan sisanya menjadi nomor urut a). Contoh lain,

kita mungkin mendapat bilangan 1 yang merepresentasikan baaa. Sehingga

banyaknya suku yang terdiri dari tiga adan satubadalah kombinasi 1 dari 4

yaitu 4. Semua suku yang terdiri dari tiga adan satu badalah

aaab, aaba, abaa, dan baaa.

Berdasarkan sifat komutatif dan asosiatif perkalian, keempat suku tersebut

memiliki nilai yang sama dengan a3b. Karena suku-suku yang sama

dengan a3bberjumlah 4, maka koefisien dari a3badalah 4, yang diperolehdari kombinasi 1 (pangkat dari salah satu faktor a3b, yaitu b) dari 4 (jumlah

pangkat dari semua faktor a3b).

Dengan cara yang sama, kita akan mendapat 6 (diperoleh dari kombinasi 2

dari 4) suku yang terdiri dari dua adan dua b,

yaitu aabb, abab, abba, baab, baba, dan bbaa. Sehingga koefisien dari

suku a2b2 adalah 6. Cara ini juga berlaku untuk menentukan koefisien dari

suku-suku ekspansi (a+ b)4lainnya.

Teorema binomial menggeneralisasi rumus di atas untuk sembarang

pangkat nbilangan bulat tidak negatif.

Teorema BinomialDiberikan sembarang bilangan real a dan b, serta bilangan bulat tidak

negatif


13/35

Perhatikan bahwa bentuk kedua dan pertama pada persamaan di atas

adalah sama, karena kombinasi 0 dari n sama dengan satu, demikian juga

dengan kombinasi ndari n. Untuk lebih memahami mengenai penggunaan

teorema binomial dalam pemecahan masalah, perhatikan contoh berikut.

Contoh: Penggunaan Teorema Binomial dalam Pemecahan Masalah

Dengan menggunakan teorema binomial, tunjukkan bahwa

untuk semua bilangan bulat n0.

PembahasanKarena 2 = 1 + 1, maka 2n = (1 + 1)n. Dengan menerapkan

teorema binomial dengan a= 1 dan b= 1, diperoleh

Karena 1nk= 1 dan 1k= 1. Akibatnya,

Apabila diperhatikan, rumus di atas sama dengan banyaknya semua

himpunan bagian dari himpunan yang memiliki nanggota/elemen, karena

setiap himpunan bagian tersebut terdiri dari kombinasi 0, 1, 2,

,ndari nyang merupakan banyaknya anggota dari himpunan tersebut.


14/35

Algoritma Pembagian

Keterbagian

Misalkan a dan b adalah dua bilangan bulat dengan syarat b > 0. Jika

a dibagi dengan b maka terdapat dua bilangan tunggal q (quotient) dan r

(remainder) sedemikian sehingga :

a = qb + r, 0< r


15/35

TEOREMA 2.1(Algoritma Pembagian)

Pada bilangan-bilangan bulat a dan b, dengan b>o, terdapat bilangan

bulat q dan r yang memenuhi

a= qb+r or


16/35

Dengan menambahkan bahwa pertidaksamaan b


17/35

catatan yang kita peroleh adalah kuadrat sebuah bilangan bulat akan

mempunyai sisa 0 atau 1 jika dibagi 4.

Kita juga dapat menunjukan hal berikut : Kuadrat dari bilangan bulat ganjil

memilki bentuk 8k +1. dalam pembagian Algoritma seluruh bilangan bulat

memiliki salah astu dari 4 bentuk, 3 bentuk 4q, 4q+1, 4q+2, 4q+3. dalam

pengelompokan ini, hanya bilangan bulat yang berbentuk 4q + 1 dan 4q +

3 yang merupakan bilangan ganjil, yang jika dikuadratkan menjadi

(4q+1)2= 8 (2q2+q)+1 = 8k + 1

Dan sama pula dengan

(4q+3)2= 8(2q2+3q+1) +1 = 8k +1

Sebagai contoh kuadrat dari bilangan bulat 7 adalah 72 = 49 = 8.6+1 ,sementara kuadrat dari 13 adalah 132=169 = 8.21 +1


18/35

Faktor Persekutuan Terbesar

Definisi

Bilangan bulat d disebut Faktor Persekutuan Terbesar (FPB) dari a dan b

apabila memenuhi

1. d > 0

2. d|a dan d|b,

3. jika c|a dan c|b, maka c d.

Dengan kata lain, FPB dari dua bilangan bulat adalah bilangan bulat

terbesar yang dapat membagi kedua bilangan tersebut.

Kita menggunakan notasi (a, b) untuk FPB dari a dan b. Jadi, jika d adalah

FPB dari a dan b, maka d = (a, b).

Contoh

Faktor dari 12 adalah {1, 2, 3, 4, 6, 12}

Faktor dari 30 adalah {1, 2, 3, 5, 6, 10, 15, 30}

Faktor persekutuan dari 12 dan 30 adalah {1, 2, 3, 6}. Jadi (12, 30) = 6

Teorema

Kita akan membuktikan tiga sifat FPB:

Teorema 1

(a, b) = d (a/d, b/d) = 1.

Bukti. Misalkan a dan b adalah bilangan bulat dengan (a, b) = d.

Kita akan menunjukkan bahwa a/d dan b/d tidak memiliki faktor

persekutuan lain kecuali 1. Misalkan e Z+ adakah faktor persekutuan dari

a/d dan b/d, yaitu e|(a/d) dan e|(b/d) sehingga ada k, Z sehingga a/d

= ke dan b/d = e, atau a = dek danb = de.

Jadi kita lihat bahwa de adalah faktor persekutuan dari a dan b. Tetapi,

karena d adalah faktor persekutuan terbesar, maka

de d sehingga e = 1.


19/35

Teorema 2 [Bezout]

(a, b) = d m, n Z am + bn = d.

Bukti. Misalkan S adalah himpunan semua kombinasi linier dari a dan b; yaitu

S = {am + bn|m, n Z}

S tak kosong sebab a = a 1 + b 0 dan b = a 0 + b 1 dan karenanya a,

b S.

Jadi S berisi bilangan bulat positif elemen terkecil, sebut saja d = ax + by.

Akan dibuktikan bahwa d = (a, b). Menurut algoritma pembagian,

a = dq + r , 0 r < d,

sehingga diperoleh

r = d dq

= a (ax + by)q

= a(1 qx) + b(qy).

Ini menunjukkan bahwa r S sedangkan 0 r < d dan d adalah bilangan

bulat positif terkecil dalam S. Jadi r = 0 dan d|a. Dengan cara yang sama

dapat pula ditunjukkan bahwa d|b. Selanjutnya, jika c|a dan c|b, makac|ax + by = d.

Hal ini membuktikan bahwa d = (a, b).

Teorema 3

a = bq + r (a, b) = (b, r ).

Bukti. Di sini cukup ditunjukkan bahwa a, b, dan r memiliki faktor persekutuan

yang sama. Untuk itu, misalkan k|a dan k|b, maka k|a bq = r .

Selanjutnya, misalkan |b dan |r , maka |bq + r = a. Ini berarti, semua

faktor persekutuan dari a dan b juga merupakan faktor persekkutuan dari b

dan r , termasuk faktor persekutuan terbesarnya, yaitu (a, b) = (b, r ).


20/35

Faktor Persekutuan Terkecil (KPK)

Ada suatu konsep yang paralel dengan konsep faktor persekutuan terbesar

(FPB), yang dikenal faktor persekutuan terkecil (KPK). Suatu bilangan bulat cdisebut kelipatan persekutuan dari bilangan-bilangan bulat tak nol a dan b

jika a c dan b c. Hal ini berarti pula nol adalah kelipatan persekutuan dari a

dan b. Perlu diingat pula bahwa ab dan(ab) adalah kelipatan persekutuan

dari a dan b, dan salah satunya positif. Dengan menggunakan prinsip terurut

sempurna (well ordering principle), himpunan kelipatan persekutuan dari a

dan b harus sebuah bilangan bulat terkecil; kita menyebutnya kelipatan

persekutuan terkecil dari a dan b, dan ditulis KPK(a, b).

Definisi

Kelipatan persekutuan terkecil dari dua bilangan bulat tak nol a dan b,

dilambangkan [a, b], adalah bilangan positif m yang memenuhi:

a | m dan b | m.

Jika a | c dan b | c dengan c > 0 maka m c.

Sebagai ilustrasi, kelipatan persekutuan positif dari12 dan 30 adalah 60, 120,180, .

Dengan demikian, KPK(-12, 30) = 60.

Dari konsep diatas, kita dapat secara jelas menyatakan bahwa jika diberikan

dua bilangan tak nol a dan b maka [a, b] selalu ada, dan [a, b] ab .

Selanjutnya, bagaimana hubungan antara KPK dan FPB? Berikut ini sifat yang

menjelaskan hubungan antara keduanya.

Sifat 1

Untuk bilangan-bilangan bulat positif a dan b, berlaku

(a, b). [a, b] = ab

Bukti:

Misalkan d = (a, b) dan kita tulis a = dr, b = ds untuk bilangan-bilangan bulat r

dan s. Jika m = ab/d maka m = as = rb. Akibatnya adalah m (positif) adalah

suatu kelipatan persekutuan a dan b.


21/35

Sekarang misalkan c adalah sebarang bilangan bulat positif yang

merupakan kelipatan persekutuan a dan b. c = au = bv. Sebagaimana kita

ketahui, ada bilangan-bilangan bulat x dan y yang memenuhi d = ax + by.

Konsekuensinya,

c/m = cd/ab = (c(ax + by))/ab = (c/b)x + (c/a)y = vx + uy

Persamaan ini menyatakan bahwa m | c, dan kita dapat menyimpulkan

bahwa mc.

Dengan demikian, m = [a, b]; Hal ini berarti bahwa

[a,b]=ab/d=ab/((a,b))

Sifat 2

Untuk suatu bilangan-bilangan bulat positif a an b, [a, b]= ab jika dan hanya

jika (a, b) = 1.

Sifat 2 ini hanya merupakan akibat langsung dari sifat 1.

Sebagai ilustrasi, Karena FPB(3054, 12378) = 6, kita dapat dengan cepat

memperoleh KPK(3054, 12378), yaitu:

KPK (3053, 12378) = 3053.12378 / FPB(3054, 12378)

= 3053.12378 / 6

= 6300402

Perlu diketahui pula bahwa faktor persekutuan terbesar dapat diperluas

untuk lebih dari dua bilangan bulat. Dalam kasus tiga buah bilangan bulat,

a, b, c tak nol, FPB(a, b, c) didefinisikan sebagai suatu bilangan bulat positif d

yang memenuhi:

d adalah faktor dari setiap a, b, c.

Jika e faktor dari a, b, c, maka e d.


22/35

Contoh soal:

1. Tentukan KPK dari 12 dan 18

Jawab:

[a,b]=ab/((ab))

(12,18) b=18,a=12 q=1,r=6

b=qa+r

18=12.1+6

12=2.6

FPB = 6

[12,18]=12.18/6

=36

Jadi KPK dari 12 dan 18 adalah 36

2. Tentukan KPK dari 12 dan 15

Jawab:

[a,b]=ab/((ab))

(12,15) b=15,a=12,q=1,r=3

b=qa+r

15=1.12+3

12=4.3

FPB = 3

[12,15]=12.15/3

=60

Jadi KPK dari 12 dan 15 adalah 60


23/35

Persamaan Diophantine

Suatu persamaan berbentuk ax + by = c dengan a, b, c bilangan-bilangan

bulat dan a, b dua-duanya bukan nol disebut persamaan liner diophantinejika penyelesaiannya dicari untuk bilangan-bilangan bulat.

Teorema :

Persamaan liner diophantine ax + by = c mempunyai penyelesaian jika dan

hanya jika pembagi persekutuan terbatas dari a dan b membagi c.

Bukti :

Misalkan d = GCD (a, b) dan d|c

d|c ada k bulat sehingga c = kd.

d|GCD (a, b) ada bilangan bulat m dan n sehingga am + bn = d.

a(km) + b (kn) = kd

a(km) + b (kn) = c

berarti x = mk dan y = nk

Teorema :

Jika d = GCD (a, b) dan x0 , y0 penyelesaian persamaan diophantine ax + by

= c, maka penyelesaian umum persamaan tersebut adalah :

x = x0 + dan y = y0dengan k parameter bilangan bulat.

Contoh soal:

Tentukan penyelesaian umum persamaan diophantine 738x + 621y = 45

Penyelesaian :

Mencari GCD (738, 621) dengan Algoritma Euclide.

738 = 1 X 621 + 117

621 = 5 X 117 = 36


24/35

117 = 3 X 36 + 9

36 = 4 X 9 + 0

Jadi GCD (738, 621). Karena 9|45 maka persamaan di atas mempunyai

penyelesaian.

Menentukan 9 sebagai kombinasi 738 dan 621.

9 = 1173 . 36

= 1173 (6215 X 117) = -3 X 621 + 16 X 117

= -3 X 621 + 16 (738621)

9 = 16 X 73819 X 621

Kalikan kedua ruas dengan 5

45 = 80 X 73895 X 621

Sehingga didapat x0 = 80, y0 = -95

Penyelesaian umumnya adalah :

x = 80 + 69t

x = - 95 72t

Contoh soal

Tentukan x dan y bulat positif yang memenuhi persamaan 7x + 5y = 100

Penyelesaian :

GCD (7, 5) = 1. Karena 1|100 maka persamaan mempunyai penyelesaian.

Dengan mudah bisa ditulis.

1 = 3 . 74 . 5

100 = 7 X 300 + 5 X (-400). Maka x0 = 300, y0 = -400

Penyelesaian umumnya adalah :

x = 300 + 5k Y = -4007k


25/35

Karena yang diinginkan penyelesaian positif, maka harus dipenuhi kedua

pertidaksamaan :

300 + 5k > 0

-4007k > 0

Yaitu : 60 < k < -57

Jadi persamaan diophantine 7x + 5y = 100 mempunyai tepat dua

penyelesaian positif yaitu untuk k = -59, dan k = -58 maka x = 5, y = 13 dan

untuk k -58 maka x = 10, y = 6.


26/35

Bilangan Prima dan Komposit

Bilangan prima adalah bilangan asli yang hanya dapat dibagi oleh bilangan

itu sendiri dan satu. Dengan perkataan lain, bilangan prima hanyamempunyai dua faktor. Misalnya 2, 3, 5, 7, 11, bilangan asli yang

mempunyai lebih dari dua faktor disebut bilangan komposit (majemuk). Misal

4, 6, 8, 9,

Teorema : (Topik Erotosthenes)

Untuk setiap bilangan komposit n ada bilangan prima p sehingga p|n dan p

.

Teorema di atas mempunyai makna yang sama dengan jika tidak adabilangan prima p yang dapat membagi n dengan p maka n adalah bilagan

prima.

Contoh soal:

Tentukan bilangan-bilangan berikut merupakan bilangan prima atau

majemuk.

a). 157 b). 221

penyelesaian :

a). Bilangan-bilangan prima yang adalah 2, 3, 5, 7, 11. Karena tidak ada dari

bilangan-bilangan prima 2, 3, 5, 7, 11 yang dapat dibagi 157, maka 157

merupakan bilangan prima.

b). Bilangan-bilangan prima yang adalah 2, 3, 5, 7, 11, 13. Karena 13|221

maka 221 merupakan bilangan komposit.

Contoh soal:

Tentukan pasangan-pasangan bilangan asli a dan b sehingga a2 b2 =

1991.

Penyelesaian :

Karena 1991 merupakan bilangan komposit (1991 = 11 X 181) maka :


27/35

A2b2 = 1991

(ab)(a + b) = 1991 (1 X 1991 atau 11 X 181) atau (ab)(a + b) = 11 X 181

Kemungkinan I Kemungkinan II

a + b = 1991 a + b = 181

a b = 1 + a b = 11 +

2a = 1992 2a = 192

a = 996 a = 96

b = 995 b = 85

Jadi pasangan-pasangan bilangan asli a dan b yang memenuhi a2 b2 =1991 adalah (996, 995) dan (96, 85)


28/35

Kekongruenan

Diberikan bilangan bulat n yang lebih besar dari 1 dan bilangan-bilangan

bulat a dan b. Bilangan a dikatakan kongruen dengan b modulo n, dituliskandengan a b (mod n) jika a dan b memberikan sisa yang sama apabila

dibagi oleh n.

Contoh soal:

Jika a dan b kongruen modulo m, buktikan bahwa selisishnya dapat dibagi

m.

Bukti :

a b (mod m) a = q1m + r dan b = q2m + r

ab = (q1q2)m, akibatnya m | (ab)

Contoh soal:

Buktikan bahwa (an + b)m = bm mod (n)

Bukti :

Membuktikan (an + b)m

bm mod (n) sama artinya dengan membuktikan ada bilangan bulat k

sehingga (an + b)mbm = kn.

Bukti :

(an + b)mbm = (an)m + m(an)m-1. b + + m(an)bm-1 + bmbm

= {a(an)m-1 + am(an)m-2 + + am(b)m-1}n

= kn (terbukti )

Rumusan pada contoh nomor 11 di atas dapat digunakan menentukan sisa

pembagian bilangan yang cukup benar.


29/35

Contoh soal:

Tentukan angka satuan bilangan 19971991.

Penyelesaian :

Angka satuan 19971991 sia pembagian 19971991 oleh 10

(199 X 10 + 7)1991 mod (10)

71991 mod (10)

74 X 497 + 3 mod (10)

(74)487 X 73 mod (10)

(2421)497 X 343 mod (10)

1 X 3 mod (10)

3 mod (10)

Jadi angka satuan 19971991 adalah 3.

Contoh soal:

Tentukan sisa jika 319 dibagi oleh 14.

Penyelesaian :

319 mod (14) 33 X 6 + 1 mod (14)

(33)6 X 31

mod (14)

(2 X 141)6 X 3 mod (14)

(-1)6 X 3 mod (14)

319 3 mod (14)

Jadi sisa pembagian 319 oleh 14 adalah 3.

Contoh soal:

Tentukan sisa 31990 jika dibagi 41.


30/35

Penyelesaian :

31990 m od (41) 34 X 497 + 2 mod (41)

(34)497 X 32 mod (41)

(2 X 411)497 X 9 mod (41)

(-1)497 X 9 mod (41)

-9 mod (41)

(419) mod (41)

31 mod (41)

Jadi sisa 31990 dinagi oleh 41 adalah 32.


31/35

Kekongruenan Linier

Kekongruenan linier adalah kongruen yang berbentuk

ax b (mod m)

m = bilangan bulat positif

a dan b = bilangan bulat

x = peubah bilangan bulat.

Nilai-nilai x dicari sebagai berikut:

ax = b + km atau

dengan k adalah sembarang bilangan bulat. k = 0, 1, 2, dan k = 1,2,

yang menghasilkan x sebagai bilangan bulat.

Contoh :

Tentukan solusi: 4x 3 (mod 9) dan 2x 3 (mod 4)

Penyelesaian:

4x 3 (mod 9)

k = 0 x = (3 + 0 9)/4 = 3/4 (bukan solusi)

k = 1 x = (3 + 1 9)/4 = 3

k = 2 x = (3 + 2 9)/4 = 21/4 (bukan solusi)

k = 3, k = 4 tidak menghasilkan solusi

k = 5 x = (3 + 5 9)/4 = 12


32/35

k =1 x = (31 9)/4 =6/4 (bukan solusi)

k =2 x = (32 9)/4 =15/4 (bukan solusi)

k =3 x = (33 9)/4 =6

k =6 x = (36 9)/4 =15

Nilai-nilai x yang memenuhi: 3, 12, dan 6,15,

2x 3 (mod 4)

Karena 4k genap dan 3 ganjil maka penjumlahannya menghasilkan ganjil,

sehingga hasil penjumlahan tersebut jika dibagi dengan 2 tidak

menghasilkan bilangan bulat. Dengan kata lain, tidak ada nilai-nilai x yang

memenuhi 2x 3 (mod 5).


33/35

Teorema China

Pada abad pertama, seorang matematikawan China yang bernama Sun Tse

mengajukan pertanyaan sebagai berikut:

Tentukan sebuah bilangan bulat yang bila dibagi dengan 5 menyisakan 3,

bila dibagi 7 menyisakan 5, dan bila dibagi 11 menyisakan 7.

Pertanyaan Sun Tse dapat dirumuskan kedalam sistem kongruen lanjar:

x 3 (mod 5)

x 5 (mod 7)

x 7 (mod 11)

Teorema 4. (Chinese Remainder Theorem) Misalkan m1, m2, , mn adalah

bilangan bulat positif sedemikian sehingga PBB(mi, mj) = 1 untuk i j. Maka

sistem kongruen lanjar

x ak (mod mk) k = 1, 2, 3, ...

mempunyai sebuah solusi unik modulo m = m1 m2 mn.

Contoh :

Tentukan solusi dari pertanyaan Sun Tse di atas.

x 3 (mod 5)

x 5 (mod 7)

x 7 (mod 11)


34/35

Penyelesaian:

Menurut persamaan diatas, kongruen pertama,

x 3 (mod 5), x = 3 + 5k1 untuk beberapa nilai k.

Sulihkan ini ke dalam kongruen kedua menjadi,

x 5 (mod 7), 3 + 5k1 5 (mod 7)

k1 6 (mod 7)

k1 = 6 + 7k2 , untuk beberapa nilai k2.

Jadi kita mendapatkan

x = 3 + 5k1

= 3 + 5(6 + 7k2)

= 33 + 35k2

yang mana memenuhi dua kongruen pertama. Jika x memenuhi kongruen

yang ketiga, maka :

x 7 (mod 11) 33 + 35k2 7 (mod 11)

k2 9 (mod 11)

k2 = 9 + 11k3.

Sulihkan k2 ini ke dalam kongruen yang ketiga menghasilkan :

x = 33 + 35k2

= 33 + 35(9 + 11k3)

348 + 385k3 (mod 11).

Dengan demikian, x 348 (mod 385) yang memenuhi ketiga konruen

tersebut. Dengan kata lain, 348 adalah solusi unik modulo 385. Catatlah

bahwa 385 = 5 7 11.


35/35

Solusi unik ini mudah dibuktikan sebagai berikut.

m = m1 m2 m3

= 5 7 11

= 5 77

= 11 35.

Karena 77 3 1 (mod 5), 55 6 1 (mod 7), dan 35 6 1 (mod 11), solusi unik

dari sistem kongruen tersebut adalah :

x 3 77 3 + 5 55 6 + 7 35 6 (mod 385)

3813 (mod 385) 348 (mod 385)

teori bilangan tugas uas 2014.docx

Documents