Definisi 3… (
Sukirman,2006 )
Jika a dan b bilangan
bulat yang sekurangnya satu diantaranya tidak sama dengan nol, maka faktor
persekutuan terbesar ( FPB ) dari a dan b diberi simbol (a,b) adalah suatu
bilangan bulat positif, misalnya d yang memenuhi :
(i) d|a dan
d|b, serta
(ii) Jika e|a dan e|b,
maka e ≤ d
Contoh :
a. ( -12,30) = 6
b. (8,15) = 1
c. (0,5) = 5
Teorema 3….( Rosen,2011 )
Jika a dan b bilangan
bulat dengan (a,b) = d, maka (a/d,b/d) = 1 ( a/d dan b/d relatif prima )
Bukti
Diketahui :
- a dan b Є Bilanga bulat
- (a,b) = d
Dibuktikan
- ( a/d, b/d ) = 1
Pembuktian
Misal c Є Bilanga bulat
positif sehingga c|( a/d) dan c|(b/d) maka dibuktikan c = 1
c|(a/d) maka ada
bilangan bulat k sehingga (a/d ) = kc
c|(b/d) maka ada
bilngan bulat l sehingga (b/d) = lc
( a/d ) = kc berarti a
= dck
(b/d) = lc berarti b =
dcl
a = dck dan b = dcl
maka dc adalah faktor persekutuan a dan b
Karena d adalah FPB
dari a dan b maka dc ≤ d berarti c = 1
Jadi terbukti (
a/d,b/d ) = 1
Teorema 3….( Rosen, 2011 )
Untuk a,b dan c bilangan bulat, maka ( a + cb,b ) = ( a,b )
Bukti
Diketahui a,b dan c bilangan bulat.
Dibuktikan
Faktor Persekutuan
a+cb dan b = Faktor Persekutuan a dan b
Pembuktian
(i) Jika e faktor
persekutuan a + cb dan b maka e faktor persekutuan a dan b
e faktor persekutuan a
+ cb dan b, dengan teorema keterbagian maka e | ( a + cb ) – cb= e|a sehingga e
faktor persekutuan a dan b
(ii) Jika f faktor persekutuan a dan b maka f faktor persekutuan
a + cb dan b
f |a dan f | b dengan
teorema linearitas keterbagian maka f | ( a + cb ) sehingga f faktor
persekutuan a + cb dan b
Dari (i) dan (ii) maka terbukti ( a + cb,b ) = ( a,b )
Definisi 3….( Rosen,2011 )
Jika a dan b bilangan
bulat, maka terdapat kombinasi linear a dan b dalam bentuk ma + nb, dengan m
dan n bilangan bulat
Contoh :
Kombinasi linear dari
9m + 15n diantaranya -6 = 1.9 + (-1).15 ; -3 = (-2).9 + 1.15 dsb.
Bezout’s Theorem 3….( Rosen,2011 )
Jika a dan b bilangan bulat, maka ada bilangan bulat m dan n
sehingga ma + nb = (a,b)
Bukti
Diketahui a dan b bilangan bulat
Dibuktikan
ma + nb = (a,b)
Pembuktian
Ambil S = {
ma + nb > 0, dengan m dan n bilangan bulat } maka ada bilangan positif
terkecil dari S, misal d maka d = ma + nb, dengan m dan n bilangan bulat, akan
ditunjukkan d|a dan d|b
(i) d|a berdasarkan
Algoritma pembagian a = dq + r , 0 ≤ r < d
sehingga r = a – dq =
a – q(ma + mb)
=
a – qma – qmb
=
a( 1 – qm ) – qmb
Ini berarti r adalah
kombinasi linear a dan b, karena 0 ≤ r < d dan d bilangan positif
terkecil maka r = 0 sehingga a = dq atau d|a
(ii) d|b berdasarkan Algoritma pembagian b = dq + r , 0 ≤ r < d
sehingga r = b – dq =
b – q(ma + mb)
=
b – qma – qmb
=
b( 1 – qm ) – qma
Ini berarti r adalah
kombinasi linear a dan b, karena 0 ≤ r < d dan d bilangan positif
terkecil maka r = 0 sehingga b = dq atau d|b
Dari (i) dan (ii)
telah ditunjukkan bahwa d bilangan bulat terkecil dari kombinasi linear a dan b
adalah faktor persekutuan a dan b.
Selanjutnya dibuktikan
bahwa (a,b) = d
Misal diambil c adalah
sembarang faktor persekutuan a dan b, maka c|a dan c|b dengan sifat linearitas
keterbagian c|( ma + nb ) atau c|d sehingga c|d
Maka terbukti (a,b) = d
atau ma + nb = (a,b)
Teorema 3. ( Rosen,2011)
Bilangan bulat a dan b
relatif prima jika dan hanya jika ada bilangan bulat m dan n yang memenuhi ma +
nb = 1
Bukti
(i) Diketahui (a,b) = 1
Dibuktikan
ma + nb = 1
Pembuktian
(a,b) = 1 berdasarkan
teorema Benzout maka ada m dan n bilangan bulat ma + nb = 1
(ii) Diketahui ma + nb = 1
Dibuktikan
(a,b) =1
Pembuktian
Misal (a,b) = d harus
dibuktikan (a,b) = 1
(a,b) = d maka d|a dan
d|b, menurut sifat linearitas keterbagian maka d|(ma + nb) = d|1 sehingga d =
1. Terbukti (a,b) = 1
Dari (i) dan (ii)
teorema terbukti.
Contoh :
1. Untuk a bilangan positif, tentukan FPB dari a dan a2 (
Rosen,2011: 99 )
Penyelesaian :
Faktor a :
1,a
Faktor a2 :
1,a,a2
Maka ( a, a2 ) =
a
2. Buktikan bahwa FPB dari bilangan genap dan ganjil adalah
ganjil!( Rosen,2011 : 99 )
Penyelesaian :
Diketahui :
a bilangan genap
, maka a = 2k untuk bilangan bulat k
b bilangan
ganjil, maka b = 2l + 1 untuk bilangan bulat l
Buktikan :
( a, b ) = ganjil
Pembuktian :
Misal (a,b) = d
menurut teorema Benzout d = ma + nb
d = m2k + n(2l + 1)
=
2mk + 2nl + n
=
2(mk + nl ) + n
Menurut algoritma
pembagian 0 ≤ n < 2, sehingga n = 1 maka
d = 2 (mk + nl ) +
1 merupakan bilangan ganjil.
Terbukti ( a, b ) =
bilangan ganjil.
3. Buktikan Jika a dan b bilangan bulat dengan ( a,b ) = 1 maka
( a + b, a – b ) = 1 atau 2 (
Rosen,2011 : 99 )
Penyelesaian
Diketahui ;
( a,b ) = 1
Dibuktikan :
( a + b, a – b )
= 1 atau 2
Pembuktian :
Misal ( a + b, a – b )
= d dibuktikan d = 1 atau 2
( a + b, a – b ) = d
maka d | ( a + b ) dan d | ( a – b )
Menurut sifat teorema
keterbagian maka d | ( a + b + a – b ) sehingga d | 2a
Menurut sifat teorema
keterbagian maka d | ( a + b – a + b ) sehingga d | 2b
d | 2a dan d | 2b
menurut sifat teorema keterbagian d | (2a + 2 b)
sehingga d | 2 ( a + b
) yang berarti
d | 2 sehingga d = 1
atau d = 2
Jadi terbukti ( a + b
, a – b ) = 1 atau 2
soal:
1. Untuk a dan b bilangan bulat positif, Tentukan FPB dari a dan
a + 2 !
2. Buktikan bahwa jika a dan b bilangan ganjil dan
keduanya tidak nol, maka ( a,b )
= 2( )
3. Buktikan bahwa jika a,b dan c bilangan bulat
sehingga (a,b) = 1 dan c | ( a + b ),
maka ( c,a ) = ( c,b ) = 1
Jawaban soal
1. Faktor a = a ,1
Faktor a + 2 = 1, ( a+b )
Jadi ( a, ( a + 1 ) ) = 1
2. Diketahui
a dan b bilangan ganjil dan keduanya
tidak nol
Dibuktikan
( a, b ) = 2( )
Pembuktian
a = 2k + 1 → k =
b = 2l + 1 → l =
Misal ( a,b ) = d maka d | a dan d | b
Sehingga d | ( 2k + 1 ) dan d | ( 2l + 1 ) berdasarkan sifat
linearitas keterbagian maka
d | ( 2k + 1 + 2l + 1 )
d | ( 2k + 2l + 2 )
d | 2( + + 1 )
d |
2( – + - + 1 )
d | 2 ( + )
d = ( a,b ) = 2 ( + )
3. Diketahui
( a, b ) = 1 dan c | ( a + b )
Dibuktikan
( c,a ) = ( c,b ) = 1
Pembuktian
c | ( a + b ) sehingga c | a dan c | b dengan c ≤ (
a,b )
sehingga c ≤ 1 karena c bilangan bulat
maka c = 1
( c,a ) = ( 1,a ) = 1
( c,b ) = ( 1,b ) = 1
Terbukti ( c,a ) = (
c,b ) = 1
Tidak ada komentar:
Posting Komentar