Latest Update: March 10, 2017 Pengantar Teori Bilangan (Bagian 3):
Pembagi Persekutuan Terbesar dan Teorema Bezout M. Zaki Riyanto Program Studi Matematika Fakultas Sains dan Teknologi UIN Sunan Kalijaga Yogyakarta
[email protected] http://zaki.sandimath.web.id
1
Pengertian
Diberikan a dan b keduanya adalah bilangan bulat yang tidak semuanya nol, maka keduanya selalu memiliki suatu pembagi yang sama, yaitu 1 dan −1. Sebagai contohnya, bilangan bulat 8 dan 12 memiliki pembagi yang sama yaitu 1,−1,2,−2,3,−3,4 dan −4. Berikut ini diberikan definisi mengenai pembagi persekutuan dari dua bilangan bulat. Definisi 1.1. Diberikan a, b ∈ Z yang tidak semuanya nol. Suatu c ∈ Z disebut dengan pembagi persekutuan (common divisor) dari a dan b jika c|a dan c|b. Pembagi persekutuan sering juga disebut dengan pembagi bersama, faktor persekutuan atau faktor bersama. Sebagai contohnya, 3 adalah pembagi persekutuan dari 8 dan 12, tetapi 6 bukan pembagi persekutuan dari 8 dan 12, sebab 6 tidak membagi habis 6. Setiap bilangan bulat tidak nol a dan b pasti memiliki pembagi persekutuan, yaitu 1 dan −1. Di antara pembagi persekutuan, ada satu yang memiliki sifat yang menarik seperti diberikan pada contoh penyederhanaan 8 bilangan rasional. Misalkan bilangan rasional 12 yang dapat disederhanakan menjadi 23 . 8 = 2·4 = 23 , sedangkan 4 Bilangan rasional 23 dapat diperoleh berdasarkan fakta bahwa 12 3·4 adalah pembagi persekutuan terbesar dari 8 dan 12. Definisi 1.2. Diberikan a, b ∈ Z yang tidak semuanya nol. Suatu d ∈ Z disebut dengan pembagi persekutuan terbesar (greatest common divisor) dari a dan b, dinotasikan dengan gcd(a, b) = d, jika d adalah pembagi persekutuan yang terbesar dari a dan b. Dengan kata lain, gcd(a, b) = d jika memenuhi: 1
(i) d|a dan d|b (ii) jika c ∈ Z dengan c|a dan c|b, maka c ≤ d. Sebagai contohnya, gcd(8, 12) = 4, gcd(9, 12) = 3, gcd(−9, 12) = 3 dan gcd(−9, −12) = 3. 8 menjadi 23 , dapat dilihat bahwa gcd(8, 12) = Pada kasus penyederhanaan bilangan rasional 12 8 , sebab pembagi 4 dan gcd(3, 4) = 1, artinya 32 adalah bentuk yang paling sederhana dari 12 persekutuan terbesar dari 3 dan 4 adalah 1. Berikut ini diberikan definisi yang berkaitan dengan dua bilangan bulat yang memiliki pembagi persekutuan terbesarnya adalah 1. Definisi 1.3. Diberikan a, b ∈ Z dengan a, b 6= 0. Bilangan bulat a dan b dikatakan relatif prima atau saling prima jika gcd(a, b) = 1. Sebagai contoh, 3 dan 4 keduanya relatif prima, sedangkan 8 dan 12 keduanya tidak relatif prima. Konsep relatif prima nantinya sangat penting pada saat pembahasan tentang kongruensi.
2
Sifat-Sifat Pembagi Persekutuan Terbesar
Berikut ini diberikan beberapa sifat pembagi persekutuan terbesar. Teorema 2.1. Diberikan a, b, c ∈ Z. Jika gcd(a, b) = d, maka (i) gcd(a, b) = gcd(b, a) (ii) gcd( ad , db ) = 1 (iii) jika b 6= 0, maka
a b
=
p q
untuk suatu p, q ∈ Z dengan gcd(p, q) = 1.
(iv) gcd(a + cb, b) = gcd(a, b). Bukti: (i) Cukup jelas. (ii) Diberikan a, b ∈ Z dengan gcd(a, b) = d. Akan ditunjukkan bahwa ad dan db tidak memiliki pembagi persekutuan positif lebih dari 1. Dimisalkan e adalah bilangan bulat positif sedemikian hingga e|( ad ) dan e|( db ), maka terdapat k, l ∈ Z sedemikian hingga a = ek dan db = el, diperoleh a = dek dan b = del. Oleh karena itu, de adalah pembagi d persekutuan dari a dan b. Diketahui d adalah pembagi persekutuan terbesar dari a dan b, maka de ≤ d, diperoleh bahwa e yang memenuhi hanyalah e = 1. Dengan demikian, diperoleh bahwa gcd( ad , db ) = 1. 2
(iii) Diberikan a, b ∈ Z dengan b 6= 0. Dibentuk p = ad dan q = db , maka diperoleh p = a/d = ab . Berdasarkan sifat sebelumnya, diperoleh bahwa gcd(p, q) = 1. q b/d (iv) Diberikan a, b, c ∈ Z. Untuk menunjukkan bahwa gcd(a + cb, b) = gcd(a, b), cukup ditunjukkan bahwa pembagi persekutuan dari a dan b sama dengan pembagi persekutuan dari a + cb dan b. Dimisalkan e adalah pembagi persekutuan dari a dan b, maka e membagi habis a + cb. Oleh karena itu, e merupakan pembagi persekutuan dari a + cb dan b. Selanjutnya, dimisalkan f adalah pembagi persekutuan dari a+cb dan b, maka f membagi habis (a + cb) − cb = a. Diperoleh bahwa f merupakan pembagi persekutuan dari a dan b. Dengan demikian, terbukti bahwa gcd(a + cb, b) = gcd(a, b). Konsep pembagi persekutuan terbesar dapat didefinisikan untuk lebih dari dua bilangan bulat, seperti diberikan pada definisi berikut ini. Definisi 2.1. Diberikan bilangan-bilangan bulat a1 , a2 , ..., an ∈ Z yang tidak semuanya nol. Suatu bilangan bulat d disebut pembagi persekutuan terbesar dari a1 , a2 , ..., an , dinotasikan dengan gcd(a1 , a2 , ..., an ) = d, apabila memenuhi kondisi berikut (i) d adalah pembagi persekutuan dari a1 , a2 , ..., an , yaitu d|ai untuk setiap i = 1, 2, ..., n (ii) jika c|ai untuk setiap i = 1, 2, ..., n, maka c ≤ d, dengan c ∈ Z. Sebagai contoh, gcd(4, 6, 8) = 2 dan gcd(10, 15, 20, 25) = 5. Untuk menghitung pembagi persekutuan dari a1 , a2 , ..., an dapat dengan menggunakan cara seperti diberikan pada teorema berikut ini. Teorema 2.2. Diberikan bilangan-bilangan bulat a1 , a2 , ..., an ∈ Z yang tidak semuanya nol, maka gcd(a1 , a2 , ..., an−1 , an ) = gcd(a1 , a2 , ..., gcd(an−1 , an )). Bukti: Sebagai latihan. Sebagai contoh, gcd(5, 6, 9) = gcd(5, gcd(6, 9)) = gcd(5, 3) = 1. Definisi 2.2. Bilangan-bilangan bulat a1 , a2 , ..., an ∈ Z dikatakan relatif prima atau saling prima jika gcd(a1 , a2 , ..., an ) = 1. Sebagai contoh, 5, 6 dan 9 saling relatif prima, sebab gcd(5, 6, 9) = 1.
3
3
Teorema Bezout
Dapat ditunjukkan bahwa pembagi persekutuan terbesar dari dua bilangan bulat tidak nol a dan b dapat dinyatakan sebagai jumlahan dari ma dan nb, untuk suatu m, n ∈ Z. Pernyataan tersebut pernah dikemukakan pada abad ke-18 oleh seorang matematikawan Perancis yang bernama Etienne Bezout. Saat ini pernyataan tersebut dikenal dengan Teorema Bezout. Sebelumnya, diberikan terlebih dahulu pengertian tetang kombinasi linear dari dua bilangan bulat a dan b. Definisi 3.1. Diberikan a, b ∈ Z. Suatu kombinasi linear dari a dan b adalah jumlahan berbentuk ma + nb dengan m, n ∈ Z. Berikut ini diberikan Teorema Bezout yang menyatakan bahwa pembagi persekutuan terbesar dari dua bilangan bulat dapat dinyatakan sebagai kombinasi linear dari a dan b. Teorema ini nantinya sangat bermanfaat untuk pembahasan berikutnya. Teorema 3.1 (Teorema Bezout). Diberikan a, b ∈ Z yang tidak semuanya nol, maka gcd(a, b) adalah kombinasi linear positif terkecil dari a dan b. Lebih lanjut, terdapat m, n ∈ Z sedemikian hingga gcd(a, b) = ma + nb. Bukti: Dibentuk suatu himpunan semua kombinasi linear dari a dan b, namakan himpunan S = {ma + nb|m, n ∈ Z}, selanjutnya dibentuk himpunan T = {s ∈ S|s > 0}, maka T memiliki elemen terkecil, namakan d, misalkan d = ma + nb untuk suatu m, n ∈ Z. Akan ditunjukkan bahwa d adalah pembagi persekutuan dari a dan b. Berdasarkan algoritma pembagian, diperoleh bahwa a = dq + r dengan 0 ≤ r ≤ d − 1. Dari sini diperoleh r = a − dq = a − q(ma + nb) = (1 − qm)a + (−qn)b yaitu r ∈ S. Diketahui 0 ≤ r ≤ d − 1 dan d adalah kombinasi linear positif terkecil dari a dan b, akibatnya satu-satunya r yang memenuhi hanyalah r = 0, diperoleh a = dq yang berarti d|a. Selanjutnya, dengan cara yang sama dapat ditunjukkan bahwa d|b. Dari sini diperoleh bahwa d adalah pembagi persekutuan dari a dan b. Untuk menunjukkan bahwa d adalah pembagi persekutuan dari a dan b, dimisalkan c adalah pembagi persekutuan dari a dan b, maka c|(ma + nb), sehingga diperoleh c|d. Diketahui d > 0, akibatnya c ≤ d. Hal ini menunjukkan bahwa d adalah pembagi persekutuan terbesar dari a dan b. Sebagai contohnya, diketahui gcd(3, 4) = 1, maka terdapat m = −1 dan n = 1 sedemikian hingga 1 = −1 · 3 + 1 · 4. Untuk teknik cara mencari nilai m dan n nantinya akan dibahas pada bagian Algoritma Euclid. 4
Akibat 3.2. Diberikan a, b ∈ Z, maka a dan b relatif prima jika dan hanya jika terdapat m, n ∈ Z sedemikian hingga ma + nb = 1. Bukti: Dimisalkan a dan b relatif prima, maka gcd(a, b) = 1. Berdasarkan Teorema Bezout, maka terdapat m, n ∈ Z sedemikian hingga ma + nb = gcd(a, b) = 1. Sebaliknya, dimisalkan terdapat m, n ∈ Z sedemikian hingga ma + nb = 1. Diketahui bahwa gcd(a, b) adalah kombinasi linear positif terkecil dari a dan b, maka satu-satunya pembagi dari a dan b yang memenuhi hanyalah 1 dan −1. Akibatnya gcd(a, b) = 1, yang berarti bahwa a dan b relatif prima. Berikut ini diberikan sebuah teorema yang menjelaskan hubungan antara himpunan kombinasi linear dari a dan b, dengan himpunan kelipatan dari pembagi persekutuan terbesar dari a dan b. Teorema 3.3. Diberikan a, b ∈ Z dengan a, b > 0, maka himpunan semua kombinasi linear dari a dan b adalah himpunan semua kelipatan dari gcd(a, b), atau dapat ditulis {ma + nb|m, n ∈ Z} = {k · gcd(a, b)|k ∈ Z}. Bukti: Dimisalkan d = gcd(a, b). Dibentuk kombinasi linear ma + nb dengan m, n ∈ Z. Akan ditunjukkan bahwa ma + nb adalah kelipatan dari d. Diketahui d = gcd(a, b), maka d|a dan d|b. Berdasarkan sifat keterbagian, maka d|(ma+nb), artinya terdapat k ∈ Z sedemikian hingga ma + nb = kd. Selanjutnya, dimisalkan ld adalah kelipatan dari d, akan ditunjukkan bahwa ld adalah kombinasi linear dari a dan b. Berdasarkan Teorema Bezout, maka terdapat m, n ∈ Z sedemikian hingga d = ma+nb. Dari sini diperoleh ld = l(ma+nb) = (lm)a+(ln)b, yang berarti bahwa ld adalah kombinasi linear dari a dan b. Berikut ini diberikan sebuah teorema yang berkaitan dengan definisi pembagi persekutuan terbesar. Teorema 3.4. Diberikan a, b ∈ Z dengan a, b 6= 0, maka suatu d ∈ Z adalah pembagi persekutuan terbesar dari a dan b, yaitu gcd(a, b) = d jika dan hanya jika memenuhi: (i) d|a dan d|b (ii) jika c ∈ Z dengan c|a dan c|b, maka c|d. Bukti: (⇒) Diketahui gcd(a, b) = d, maka jelas memenuhi d|a dan d|b. Berdasarkan Teorema Bezout, terdapat m, n ∈ Z sedemikian hingga d = ma + nb. Akibatnya, jika c|a dan c|b, maka 5
menggunakan sifat keterbagian diperoleh bahwa c|(ma + nb), sehingga c|d. (⇐) Misalkan pernyataan (i) dan (ii) dipenuhi. Akan ditunjukkan bahwa d adalah pembagi persekutuan terbesar dari a dan b. Dari (i) telah diketahui bahwa d adalah pembagi persekutuan dari a dan b. Dari (ii) diketahui jika c|a dan c|b, maka c|d. Oleh karena itu, d = cf untuk suatu f ∈ Z, sehingga c = fd . Akibatnya diperoleh c = fd ≤ d, yang berarti d = gcd(a, b).
4
Soal-soal Latihan
(1) Tuliskan semua pembagi persekutuan dari 100 dan 125. (2) Tentukan gcd(100, 125), gcd(0, 125) dan gcd(−90, 120). (3) Diberikan a ∈ Z dengan a > 0. Tentukan gcd(a, a2 ). (4) Buktikan bahwa jika a dan b keduanya genap, maka gcd(a, b) juga genap. (5) Buktikan bahwa jika a genap dan b ganjil, maka gcd(a, b) ganjil. (6) Diberikan a, b ∈ Z yang tidak semuanya nol. Diberikan c ∈ Z dengan c 6= 0. Buktikan bahwa gcd(ca, cb) = |c|gcd(a, b). (7) Diberikan a, b ∈ Z dengan a dan b relatif prima. Buktikan bahwa pembagi persekutuan terbesar dari a + b dan a − b adalah 1 atau 2. (8) Diberikan a adalah suatu bilangan bulat positif. Buktikan bahwa pembagi persekutuan terbesar dari a + 1 dan a2 − a + 1 adalah 1 atau 3. (9) Diberikan a adalah suatu bilangan bulat positif. Buktikan bahwa pembagi persekutuan terbesar dari a2 + 2 dan n3 + 1 adalah 1, 3 atau 9. (10) Buktikan bahwa jika a dan b adalah bilangan genap yang tidak semuanya nol, maka gcd(a, b) = 2gcd( a2 , 2b ). (11) Buktikan bahwa jika a adalah bilangan genap dan b adalah bilangan ganjil, maka gcd(a, b) = gcd( a2 , b). (12) Buktikan bahwa jika a, b dan c adalah bilangan-bilangan bulat dengan gcd(a, b) = 1 dan c|(a + b), maka gcd(a, c) = gcd(b, c) = 1.
6
(13) Diberikan bilangan bulat tidak nol a, b dan c, dan ketiganya saling prima. Buktikan bahwa gcd(a, bc) = gcd(a, b)gcd(a, c). (14) Diberikan a, b, c ∈ Z dengan gcd(a, b) = gcd(a, c) = 1. Buktikan bahwa gcd(a, bc) = 1. (15) Diberikan a1 , a2 , ..., an , b ∈ Z dengan gcd(ai , b) = 1, untuk setiap i = 1, 2, ..., n. Buktikan bahwa gcd(a1 , a2 , ..., an , b) = 1.
7
