bahan ajar · 2016. 6. 14. · dan memberkahi kita dengan hidayah dan karunia-nya yang begitu...
TRANSCRIPT
BAHAN AJAR
TEORI BILANGAN
DOSEN PENGAMPU
RINA AGUSTINA, S. Pd., M. Pd.
NIDN. 0212088701
PENDIDIKAN MATEMATIKA
FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN
UNIVERSITAS MUHAMMADIYAH METRO
2015
KATA PENGANTAR
حِيْماللهِبسِْمِ ا حْمٰنِ الرَّ الرَّ
Segala puji bagi Allah SWT yang telah memberikan kehidupan bagi kita
dan memberkahi kita dengan hidayah dan karunia-Nya yang begitu melimpah.
Shalawat serta salam tetap tercurah kepada Nabi Besar Muhammad SAW
yang selalu menjadi panutan untuk kehidupan semua umat Islam.
Adapun isi bahan ajar ini meliputi materi Strategi Pembuktian,
Keterbagian, Algoritma Pembagian, Kongruensi dan Sistem Residu. Semoga
bahan ajar ini dapat memberikan manfaat dalam bidang pendidikan
khususnya dalam pembelajaran Teori Bilangan bagi mahasiswa Pendidikan
Matematika
Metro, September 2015
Penyusun
BAB I
STRATEGI PEMBUKTIAN
Teknik Pembuktian:
1. Pembuktian Langsung
2. Pembuktian Tidak Langsung
2.1 Pembuktian dengan kontraposisi
2.2 Pembuktian dengan kontradiksi
3. Induksi Matematika
Teknik Pembuktian Langsung:
Misalkan P dan Q merupakan pernyataan-pernyataan.
Pernyataan bahwa P dapat mengambil pernyatan P sebagai pernyataan
yang diketahui dan pernyataan Q yang akan dibuktikan.
Contoh:
Jika n suatu bilangan bulat genap, maka suatu bilangan bulat genap!
Bukti:
Misalkan n bulat genap, yaitu n = 2k, maka
= =
karena k bilangan bulat, maka bilangan bulat.
Pembuktian Tidak Langsung:
Ada 2 tipe dasar dari pembuktian tidak langsung, yaitu : pembuktian dengan
kontraposisi dan pembuktian dengan kontradiksi.
1. Pembuktian dengan kontraposisi
Dalam pembuktian P kita akan membuktikan dengan kontraposisinya
yaitu:
Contoh:
Jika n suatu bilangan bulat, dan adalah ganjil, maka n adalah ganjil !
Bukti:
Akan dibuktikan denga kontraposisi,
Andaikan n bukan ganjil, maka n genap yaitu n = 2p
Maka = =
Karena n genap, maka juga genap.
Sehingga terbukti bahwa bukan ganjil.
II. Pembuktian dengan kontradiksi
Metode pembuktian ini menggunakan pernyataan bahwa
jika C suatu kontradiksi, maka pernyataan ekuivalen dengan P
Contoh:
Misalkan a > 0 merupakan bilangan real.
Jika a > 0, maka
> 0 !
Bukti:
Andaikan
< 0, maka
bernilai negatif.
Karena 1 positif, maka a bernilai negatif.
Dengan kata lain, a < 0
Maka kontradiksi dengan a > 0.
Induksi Matematika:
Induksi matematika merupakan metode yang digunakan untuk membangun
kevalidan pernyataan yang diberikan dalam istilah-istilah bilangan asli.
Prinsip induksi matematika menyatakan bahwa:
Misalkan yang mempunyai sifat-sifat :
(1)
(2) K , maka k + 1
Contoh:
Buktikan + + … + n = n + n !
Bukti:
Untuk n = 1, maka
2 n = n (1 + n)
2 . 1 = 1 (1 + 1)
2 = 2 (terbukti)
Selanjutnya, asumsikan benar untuk n = k, maka
+ + … + k = k + k
Maka akan dibuktikan benar untuk n = k + 1, bukti:
+ + … + k + k + = k + k + k +
= k + + 2k + 2 = + 3k + 2
= (k + 1) (k + 2) = (k + 1)[ + k + ]
Sehingga terbukti bahwa : + + … + n = n + n
KETERBAGIAN
DEFINISI
Suatu bilangan bulat b adalah habis dibagi oleh suatu bilangan bulat
jika = dan dituliskan dengan a|b. Jika tidak habis dibagi
oleh a, maka dituliskan a . “a|b” dibaca a membagi b berarti bahwa a adalah
pembagi dari b, dengan kata lain bahwa b adalah kelipatan dari a.
Teorema 2.1
(1) | maka |
(2) | dan b|c maka |
(3) | dan | maka | +
(4) | dan | maka =
(5) | maka
(6) | |
Pembuktian:
(1) | maka |
Bukti:
a|b berdasarkan definisi = .
Akibatnya berlaku pula bahwa:
= = .
Karena pada bilangan bulat berlaku sifat tertutup pada perkalian, maka
berarti :
= berlaku = = .
Sehingga berdasarkan definisi:
= .
Maka dapat disimpulkan bahwa | .
(2) | dan b|c maka |
Bukti:
| maka =
| maka =
Sehingga = = = = , dengan =
Sehingga berdasarkan definisi terbukti bahwa |
(3) | dan | maka | +
Bukti:
| maka =
| maka =
Akibatnya berlaku :
=
=
Sehingga :
+ = +
= +
= dengan = +
Berdasarkan definisi, maka dapat disimpulkan bahwa :
| +
(4) | dan | maka =
Bukti:
| maka =
| maka =
Akibatnya berlaku:
= = = atau =
=
Karena maka = 0 atau =1
Persamaan =1 dipenuhi untuk:
= =
atau = =
Sehingga didapatkan bahwa:
=
Contoh:
Buktikan bahwa merupakan suatu kelipatan dari 169,
!
Bukti:
Ambil P(n) adalah pernyataan = n .
(1) Untuk n =1, maka = =
yang berarti dapat dibagi oleh 169.
jadi P(n) benar untuk n = 1.
(2) Asumsikan benar untuk n = k – 1, k >1
diperoleh = k = 169M
sehingga untuk n = k, diperoleh:
=
= +
= 27 . 169 M + 169 . 4k
Yang dapat dibagi oleh 169, yang berarti bahwa:
P(n) benar untuk n = k.
Dari (1) dan (2) disimpulkan terbukti bahwa
merupakan suatu kelipatan dari 169,
Teorema 2.2
Algoritma Pembagian
Jika dengan maka
= +
Jika , maka r memenuhi ketaksamaan .
Dalam situasi ini,
q dinamakan hasil bagi, r dinamakan sisa ketika b dibagi a.
Bukti:
(i) Adib : = +
Untuk dan >0 dapat dibentuk barisan aritmatika:
… , b – 2a, , + …
yang mempunyai bentuk umum suku adalah .
Ambil himpunan S yang anggotanya adalah suku-suku yang tidak negatif,
yaitu:
S = { | }
Menurut prinsip urutan, S mempunyai anggota terkecil yaitu r
Maka r dapat dinyatakan dalam bentuk
r = = +
Jadi terbukti = + .
(ii) Adib :
Andaikan tidak benar.
Karena ( tidak negatif), maka
Dipihak lain, =
=
= + = = +
Karena dan = ,
Maka sehingga ( ) merupakan anggota S yang lebih kecil dari .
Hal ini kontradiksi dengan pengambilan r sebagai anggota terkecil S.
Jadi terbukti bahwa
(iii) Adib : q dan r tunggal
Andaikan q dan tidak tunggal, yaitu dan memenuhi:
= +
= +
sehingga :
+ = +
+ = 0
( =
Yang berarti |
Dipihak lain dan
Berakibat | | atau
Dengan demikian | berakibat = 0, sehingga =
Dari ( = diperoleh = 0
Karena maka = atau = .
Jadi terbukti bahwa q dan r tunggal.
Dari (i), (ii), dan (iii) maka terbukti algoritma pembagian.
Contoh:
1. Tunjukkan bahwa | +
Bukti:
, maka = +
Berarti r = 0 atau r = 1
(i) Untuk r = 0, berarti = sehingga
+ = + = { + } = 2k
Untuk suatu k = +
Karena maka = + .
Karena ada k , sehingga + = maka | +
(ii) Untuk r = 1, berarti = + sehingga
+ = + + +
+ = + + +
= ( + ) . ( + = + + =
Untuk t = + +
Karena = + +
Karena ada t , sehingga + = maka | +
Berdasarkan (i) dan (ii), terbukti bahwa : | +
2. Tunjukkan bahwa habis dibagi 8,
Bukti:
(i) Untuk n = 1, maka 8| ,(benar)
(ii) Asumsikan benar untuk n = k, 8|
Selanjutnya akan dibuktikan untuk n = k + 1 maka :
8| maka =
8| maka =
= +
Karena n k , maka:
8| = 8| = 8|
= 8|9( + ) – 1 = 8|9. + – 1
8| = 8|9. + – 1 = 8 | 9. 8x + = 8 | 8(9x + 1)
= 8|8m, untuk m = 9x+1
Terbukti bahwa n = k+1 maka 8| .
Dari (i) dan (ii), terbukti bahwa : habis dibagi 8,
KONGRUENSI
DEFINISI
Jika sebuah bilangan bulat m yang tidak nol, membagi selisih a – b, maka
dikatakan a kongruen dengan b modulo m, dan ditulis:
Jika a – b tidak habis dibagi oleh m, maka dikatakan a tidak kongruen dengan b
modulo m, dan ditulis:
Selanjutnya b dinamakan sisa dari a ketika dibagi oleh m.
Contoh:
1. 27 , karena (27 – 2) terbagi oleh 5
2. 35 , karena (35 – 6) tidak terbagi 7
Dari definisi dan contoh diatas, dapat dikatakan bahwa:
jika m > 0 dan m|(a – b) maka = .
Sehingga , ini sama artinya dengan atau beda
antara a dan b merupakan kelipatan m.
Jadi dapat juga dinyatakan a = mt + b, yaitu a sama dengan b
ditambah kelipatan m.
Teorema 3.1
Andaikan a, b, c dan m bilangan asli, maka berlaku sifat:
i. Refleksif,
ii. Simetris, jika ( ) maka b ( )
iii. Transitif, jika dan b maka a
Bukti:
Andaikan a, b, c dan m bilangan asli, maka berlaku sifat:
i. Refleksif, ( )
Akan dibuktikan: ( )
Jika m 0 maka m|0, berarti m|(a – a)
Jadi ( ), dan m 0
Cara lain:
( ), sebab a – a = 0 dan m 0 .
ii. Akan dibuktikan: jika ( ) maka b ( )
( ) berarti m|a – b, menurut definisi keterbagian:
m|a – b dapat dinyatakan a – b = tm, t
Jika kedua ruas dikalikan negatif, diperoleh:
-(a – b) = -tm
b – a = (-t)m, -t
Jadi m|b – a atau b ( )
Teorema 3.2
Andaikan a, b, c dan m
Jika maka + +
Bukti:
berarti m|(a – b)
Menurut definisi keterbagian:
m|a – b dapat dinyatakan a – b = tm,
(a – b) + 0 = tm
(a +c) – (b + c)= tm
Jadi m|(a + c) – (b + c) atau a + c +
Teorema 3.3
Andaikan a, b, c dan m
Jika maka
Bukti:
berarti m|(a – b)
Menurut definisi keterbagian m|(a – b) dapat dinyatakan:
a – b = tm, t
a – b = tm, t
(a – b)c = (tm)c
ac – bc = (tc) m
Jadi m|(ac – bc) atau
Contoh:
1. Tentukan sisa ketika dibagi oleh 37 !
Jawab:
= 6 . = 6 .
Karena = -1 (mod 37), maka:
= 6 . = 6 = -6
Jadi = -6 = -43 (mod 37)
Sehingga sisa pembagian adalah -43
2. Apakah dapat dibagi 3 ?
Jawab :
Karena 4 = 1 (mod 3) sehingga:
= = 1 (mod 3)
Jadi dapat dibagi 3
3. Selesaikan 6x ( )?
Jawab :
6x = 15 (mod 33) 2x = 5 (mod 11)
2x = 16 (mod 11), x = 8 (mod 11)
Sehingga nilai x yang memenuhi adalah 8, 19, 30
Teorema 3.4
Andaikan dan
Jika ( )dan c ( ) maka + + ( )
Bukti:
( ) berarti m|a - b
c ( ) berarti m|c - d
Menurut definisi keterbagian:
m|a – b dapat dinyatakan a – b = m,
m|c – d dapat dinyatakan c – d = m,
Jika dijumlahkan, maka diperoleh:
(a+c) – (b + d) = ( + )m, ( + )
Jadi m|(a+c) – (b+d) atau + + ( )
Teorema 3.5
Andaikan dan
Jika ( ) dan c ( ) maka ( )
Bukti:
( ) berarti m|a - b
c ( ) berarti m|c - d
Menurut definisi keterbagian:
m|a – b dapat dinyatakan a – b = m,
m|c – d dapat dinyatakan c – d = m,
Jika dikurangi, maka diperoleh:
(a - c) – (b – d) = ( )m, ( )
Jadi m|(a - c) – (b – d) atau ( )
Teorema 3.6
Andaikan dan
Jika ( ) dan d|m maka ( )
Bukti:
( ) berarti m|a – b
Jika m|a – b dan d|m, maka d|a – b
Jadi d|a – b berarti ( )
Teorema 3.7
Andaikan dan
Jika ( ) dan c ( ) maka + + ( )
Bukti:
( ) berarti m|a – b
( ) berarti m|c – d
Menurut definisi keterbagian:
m|a – b dapat dinyatakan a – b = m,
(a – b) x = ( m)x
ax – bx = ( )m,
m|c – d dapat dinyatakan c – d = m,
(c – d) y = ( m)y
cy – dy = ( )m,
Apabila dijumlahkan, diperoleh:
ax – bx = ( )m,
cy – dy = ( )m,
(ax + cy) – (bx + dy) = ( + )m, +
Jadi m|(ax + cy) – (bx + dy) atau a + c b + d (mod m)
Contoh:
1. Cari digit terakhir dari !
Jawab:
= 1 (mod 4)
Bagian pangkat: = . 7 = . 7 = 7 = 3 (mod 4)
Sehingga dengan definisi algortima pembagian diperoleh : = 3 + 4t
Dipihak lain:
= -1 (mod 10)
= . 7 = -1 . 7 = -7 = 3 (mod 10)
Sehingga = = . = . 3 (mod 10)
= . 3 (mod 10) = 3 (mod 10)
Jadi digit terakhir adalah 3.
2. Tentukan bilangan-bilangan kuadrat sempurna di modulo 13 !
Jawab:
Misal bilangan kuadrat tersebut adalah :
Karena modulo 13, sehingga =
Maka han a akan dipenuhi oleh r = … 6.
Diamati bahwa : = 0, = 1, = 4, dan = 9
= 3 (mod 13), = 12 (mod 13), dan = 10 (mod 13)
Jadi kuadrat sempurna di modulo 13 yaitu, 0, 1, 4, 9, 3, 12, dan 10.
Teorema 3.8
Andaikan dan
Jika ( ) dan c ( ) maka ( )
Bukti:
( ) berarti m| - b
c ( ) berarti m|c - d
Menurut definisi keterbagian:
m|a – b dapat dinyatakan a – b = m,
(a – b)c = ( m)c
ac – bc = ( c)m , …
m|c – d dapat dinyatakan c – d = m,
(c – d)b = ( m)b
bc – bd = ( b)m , …
Dari 1) dan 2) dijumlahkan sehingga didapat :
ac – bc = ( c)m
bc – bd = ( b)m
ac – bd = ( c + b)m , c + b
Ini berarti m|ac – bd atau ac bd (mod m).
Teorema 3.9
Andaikan dan
Jika ( ) maka ( )
Bukti:
( ) berarti m| – b
Menurut definisi keterbagian:
m|a – b dapat dinyatakan a – b = m,
(a – b)c = ( m)c
ac – bc = ( )mc
Ini berarti mc|ac – bc atau ac bc (mod mc).
Teorema 3.10
Andaikan dan
Jika ( ), maka ( ) untuk n bilangan bulat positif.
Bukti:
( ) berarti m|a – b
Menurut definisi keterbagian:
m|a – b dapat dinyatakan a – b = m,
Kita kenal bahwa bentuk :
= + + …+ +
Karena a– b|a – b, maka
a – b| ( + + …+ + )
Ini berarti a – b|
Menurut teorema keterbagian:
Jika m|a – b dan a – b| , maka m|
Jadi m| atau ( )
Teorema 3.11
Andaikan f suatu polinom dengan koefisien bilangan bulat.
Jika ( ), maka f ( )
Bukti:
Andaikan f(x) = +
+ …+ +
Dengan … bilangan bulat
= maka f(a) = +
+ …+ +
= maka f(b) = +
+ …+ +
Jika kedua dikurangkan, diperoleh:
f( ) – f(b) = +
+ +
Dengan menerapkan teorema: ( )
( ) dst…
Dengan menggunakan teorema keterbagian, diperoleh:
m| +
+ +
Berarti m|f( ) – f(b) atau f ( )
Contoh:
1. Cari bilangan-bilangan bulat n sedemikian sehingga + 27 dapat dibagi 7!
Jawab:
Diamati bahwa
= 2 = 4
= 1 (mod 7) = 2 (mod 7)
= 4 (mod 7) = 1 (mod 7)
Selain itu, = 1 (mod 7),
Karena itu + 27 = 1 + 27 = 0 (mod 7)
2. Tentukan semua penyelesaian tak negatif ( … ) di modulo 16
jika +
+ … + = 1599
Jawab:
Perlu diamati bahwa semua pangkat 4 sempurna di modulo 16 adalah 0, 1
(mod 16)
Ini berarti bahwa +
+ … +
Memiliki nilai paling besar adalah 14 (mod 16)
Sedangkan 1599 = 15 (mod 16).
Jadi terlihat tidak ada penyelesaian tak negatif di modulo 16.
SISTEM RESIDU
DEFINISI
Suatu bilangan bulat dikatakan suatu sistem residu lengkap modulo n jika
setiap bilangan bulat kongruen dengan salah satu dari himpunan itu. Atau
dengan kata lain
Himpunan , … dikatakan sistem residu lengkap modulo m, jika
sehingga
Contoh:
Misalkan n = 4.
Untuk sembarang bilangan bulat a, akan terdapat sisa tepat satu bilangan
bulat q sehingga:
a = 4 q a = 4q + 1
atau
a = 4q + 2 a = 4q + 3
Hal itu mengatakan bahwa bilangan bulat dapat dibagi ke dalam empat kelas
bagian, yaitu:
{4q | q B} = {… -8, - …}
{4q + 1 | q B} = {… -7, - …}
{4q + 2 | q B} = {… -6, - …}
{4q + 3 | q B} = {… -5, - …}
Karena {0, 1, 2, 3} merupakan semua kemungkinan dari sisa pembagian
dengan 4, maka keempat himpunan itu berturut-turut dapat dituliskan dalam
pengertian kongruensi sebagai berikut:
[0] = {k B | k } [1] = {k B | k }
[2] = {k B | k } [3] = {k B | k }
Perhatikan bahwa untuk setiap bilangan bulat akan tepat berada dalam salah
satu himpunan [0], [1], [2] atau [3].
Atau dengan kata lain himpunan {0, 1, 2, 3} ini dinamakan sistem residu
lengkap modulo 4.
Teorema 4.1
Untuk sembarang bilangan bulat a dan b, a ( ) jika dan hanya jika a
dan b memiliki sisa yang sama apabila dibagi dengan n.
1) Adib : a ( ) maka a dan b memiliki sisa yang sama apabila
dibagi dengan n
Bukti:
Misalkan a ( ) dan sisa pembagian b dengan n adalah r, yaitu
b = qn + r dengan 0
Akan ditunjukkan bahwa r juga merupakan sisa pembagian dari bilangan bulat
a dengan n.
Untuk itu, dituliskan a = pn + r
a ( ) dengan defini keterbagian diperoleh:
a – b = kn, k
Dipihak lain: b = qn + r, sehingga:
a – (qn + r) = kn
a = kn + qn + r = (k + q)n + r
a = (k + q)n + r
a = pn + r, dengan p = k + q
Ini menunjukkan bahwa sisa pembagian a dengan n sama dengan sisa
pembagian b dengan n, yaitu r.
Sehingga terbukti: a ( ) maka a dan b memiliki sisa yang sama
apabila dibagi dengan n
ii) Adib: a dan b memiliki sisa yang sama jika dibagi dengan n,
maka a ( )
Bukti:
Misalkan a = + dan = + dengan sisa pembagian yang sama yaitu
r. maka akan ditunjukkan bahwa a b (mod n).
a = + dan = + , jika dikurangkan diperoleh:
a – b = ( + ) – ( + ) = (
a – b = (
a – b = k n, dengan k =
Dengan kata lain bahwa a ( )
Dari i dan ii, disimpulkan bahwa a ( ) jika dan hanya jika a dan b
memiliki sisa yang sama apabila dibagi dengan n.
LATIHAN
1. Buktikan bahwa:
+ + + … + n =
+
2. Buktikan bahwa:
1 + + + … + n – 1) =
3. Buktikan bahwa :
+ + + … + =
4. Buktikan bahwa : selalu habis dibagi oleh 5 !
5. Buktikan bahwa !
6. Buktikan | maka
7. Buktikan | |
8. Tunjukkan bahwa 3| n !
9. Buktikan bahwa jika | maka |
10. Buktikan bahwa jika | maka | | | |
11. Transitif, jika dan b maka a
12. Buktikan bahwa : 7|( +
13. Selesaikan 26 x = 17 (mod 33) !
14. Buktikan bahwa : 7|( +
15. Cari semua x yang memenuhi persamaan 7 + x = 4 (mod 5) !