Teorema 2.6
Jika (a,m) = 1 dan (b,m) = 1 maka (a-b,m) = 1
Bukti :
Misal d merupakan faktor persekutuan dari (a,m) dan (b,m) dengan d 0 maka sesuai defenisi 2.1 d | a, d | m, dan d | b. Karena d |a dan d | b maka sesuai teorema 1.4 d | (a+b) dan d | (a-b).
Ambil d | (a-b)
Diketahui bahwa (a,m) = (b,m) = 1. Jika 1 merupakan faktor persekutuan terbesar dari (a,m) dan (b,m), dan d merupakan faktor persekutuan dari (a,m) dan (b,m) . Maka sesuai defenisi 2.2 karena maka d = 1.
Jika , ( (a-b),m) = c , dan c merupakan faktor persekutuan terbesar dari ((a-b),m), karena d | (a-b) dan d | m, maka d merupakan faktor persekutuan terbesar dari ( (a-b),m) , sesuai definisi 2.2 d ≤ c
Jika , c = 1 dan d > 0 , maka d = c sehingga , ( (a-b),m) = c = d = 1
Jadi, ( (a-b),m) = 1
Contoh :
( 9 ,7 ) = 1 , ( 4,7 ) = 1 , maka ((9-4),7 ) = ( 5, 7 ) = 1
( 10,13) = 1 , ( 17, 13 ) = 1 , maka ((10-17),13 ) = ( -7, 13) = 1
Teorema 2.7
Jika a,b,c Z, a | bc, dan (a,b) = 1 maka a | c
Bukti :
(a,b) =1, maka sesuai teorema 2.3 ada bilangan bulat positif yang mempunyai ax + by, dengan x,y Z, yaitu ax + by = 1
ax + by = 1, maka c(ax) + c(by) = c atau a(cx) + b(cy) = c.
a | bc, maka menurut teorema 1.1 a | (bc)y untuk setiap y Z
a | acx karena acx mempunyai faktor a
Karena a | (acx + bcy) dan a(cx) + b(cy) = c, maka a | c.
Contoh :
misal, 1. a = 12 , b = 7, c = 72 ,
12 | (7.72) = 12 | 504 , dan ( 12, 7 ) = 1, maka 12 | 72
2. a = 3, b = 13 , c = 12 ,
3 | (13.12) = 3 | 156 , dan ( 3, 13 ) = 1, maka 3 | 12
Teorema 2.8
Misalkan x,y Z, d = (a,b) jika dan hanya jika d 0, d | b, dan f | d untuk setiap factor persekutuan f dari a dan b.
Bukti :
1. Jika d = (a,b), maka d bilangan bulat positif terbesar yang membagi a dan b, berarti , d | a dan d | b, sesuai teorema 2.3 d adalah bilangan bulat terkecil yang mempunyai bentuk ax + by dengan x,y Z, y d = ax + by, f adalah faktor persekutuan dari a dan b maka f | a dan f | b, sehingga f | ax dan f | by untuk setiap x,y Z, dan menurut teorema 1.4, f | ax + by dan d = ax + by, maka f | d.
2. Jika d 0, d | a, d | b, dan f | d ( f adalah faktor persekutuan dari a dan d ), maka d = kf dengan k Z. d | a dan d | b, maka d adalah faktor persekutuan a dan b. d adalah faktor persekutuan a dan b, serta d f (d lebih dari sebarang faktor persekutuan a dan b), maka d = (a,b). Jadi jika d 0, d | a, d | b, dan f | d maka d = (a,b). (Terbukti)
Contoh :
1. Faktor 20 =
Faktor 35 =
Faktor persekutuan 20 dan 35 adalah
Faktor persekutuan terbesar 20 dan 35 atau (20,35) = 5
Jadi, -5 | 5 ; -1 | 5 ; dan 5| 5
2. Faktor 15 =
Faktor 28 =
Faktor persekutuan 15 dan 28 adalah
Faktor persekutuan terbesar 15 dan 28 atau ( 15, 28 ) = 3
Jadi, -3 | 3 , -1 | 3 , 1 | 3 , 3 | 3
Teorema 2.9
Jika , Z, dan , 0, maka
.
.
.
.
Bukti :
Diketahui , Z , dan maka menurut algoritma pembagian, ada bilangan-bilangan dan sehingga dengan Berikutnya, dan maka menurut algoritma pembagian, ada bilangan-bilangan sehingga dengan Dengan cara yang sama dapat ditunjukkan :
.
.
Selanjutnya, sesuai teorema 2.8
Jadi, .
Contoh:
Dengan menggunakan teorema Algoritma Euclides, cari FPB dari 105 dan 60.
105 = 60 . 1 + 45, 0 < 45 < 60 ; (105, 60) = ( 60 . 1 + 45, 60) = (45, 60)
60 = 45. 1 + 15, 0 < 15 < 45 ; (45, 60) = (45, 45. 1 + 15) = (45, 15)
45 = 3. 15 + 0, 0 0 < 15 ; (45, 15) = 15(3, 1) = 15. 1 = 15
Matematikawan Perancis Gabriel Lamรจ (1795-1870) membuktikan bahwa banyaknya langkah yang diperlukan dalam algoritma Euclid ini paling banyak 5 kali banyaknya digit dari bilangan yang lebih kecil. Misalnya , dalam menentukan faktor persekutuan terbesar (12378, 3054) , bilangan 3054 (lebih kecil dari 12378) memiliki empat digit, maka langkah algoritma Euclid tidak akan lebih dari 5 . 4 = 20 langkah. Kenyataannya proses tersebut hanya mnemerlukan 6 langkah.
Perlu dicata pula bahwa langkah dalam algoritma Euclid ini biasanya dapat disingkat lagi dengan memilih sisa sehingga| |< /2. Misal, Contoh soal berikut dapat diselesaikan lebih singkat seperti berikut.
12378 = 4. 3054 + 162
3054 = 19. 162 - 24
162 =1. 138 + 24
138 = 7. 24 - 6
24 = (4)(6)+ 0
Jadi, ( 12378 , 3054 ) = 6
Teorema 2.10
Jika (a,b) = d maka ada bilangan-bilangan x dan y sehingga ax + by = d
Bukti :
Jika a,b z maka sesuai teorema 2.9
a = bq + r
b =
r =
. .
. .
. .
.
maka FPB dari a dan b yaitu yaitu
(a,b) =
apabila a atau b bilangan negatif
(a,b) = (-a,b) = (a,-b) = (-a,-b)
Jika dieliminasi dari (k+1) persamaan diatas yaitu
(a,b) =
Hal ini menunjukan bahwa sebagai kombinasi dari dan yang selanjutnya dapat dibentuk dari koefisien-koefisien bilangan-bilangan
Sehingga (a,b)
Karena maka . Jika proses ini dilanjutkan secara berurut hingga persamaan r = a – bq maka sesuai teorema 2.3 ada bentuk
(a,b) =
Missal bilangan-bilangan bulat itu x dan y maka (a,b) =
Jadi,
Contoh :
Misal a = 32 b = 60, tentukan x dan y sehingga 32x + 60y = 4
Berdasarkan Algoritma Euclides,
60 = 32.1 + 28 .................... ( 1 )
32 = 28.1 + 4 ……………... ( 2 )
28 = 7. 4 + 0
Jadi, (32,60) = 4
Berdasarkan kebalikan dari Algoritma Euclides:
Dari langkah ( 2 ): 4 = ( 32 – 28 . 1)
Dari langkah ( 1 ): 4 = ( 32 – (60 – 32. 1 )
= ( 32 – 60 + 32 )
= 2. 32 + (-1) 60
Jadi, x = 2 dan y = -1
