Sunday, January 10, 2010

SAP : Aplikasi Kekongruenan

SATUAN ACARA PERKULIAHAN


MATA KULIAH : TEORI BILANGAN
KODE MATA KULIAH : GMA 232
BOBOT SKS : 3
SEMESTER : 3
PROGRAM STUDI : PENDIDIKAN MATEMATIKA


I. TUJUAN PEMBELAJARAN UMUM
Mahasiswa memahami sifat – sifat bilangan bulat dan konsep kekongruenan dan menggunakannya dalam aljabar.

II. TUJUAN PEMBELAJARAN KHUSUS
1. Mahasiswa dapat menentukan bilangan bulat n terbagi oleh 2j.
2. Mahasiswa dapat menentukan bilangan bulat n terbagi oleh 5j.
3. Mahasiswa dapat menentukan bilangan bulat n terbagi oleh 3 atau 9.
4. Mahasiswa dapat menentukan bilangan bulat n terbagi oleh 11.
5. Mahasiswa dapat menentukan bilangan bulat n terbagi oleh prima 7, 11, atau 13.
6. Mahasiswa dapat menerapkan teorema 4.1, 4.2, dan 4.3 dalam pengujian keterbagian dengan
menggunakan repsesentasi basis b (b merupakan bilangan bulat positif).
7. Mahasiswa dapat menjadwalkan turnamen Round-Robin untuk tim N ganjil.
8. Mahasiswa dapat menjadwalkan turnamen Round-Robin untuk tim N genap.




III. POKOK BAHASAN DAN SUB POKOK BAHASAN
1. Aplikasi kekongruenan.
1.1. Pengujian keterbagian pada bilangan bulat dengan menggunakan repsentasi desimal.
1.1.1. Pengujian keterbagian bilangan perpangkatan 2.
1.1.2. Pengujian keterbagian bilangan perpangkatan 5.
1.1.3. Pengujian keterbagian oleh 3 atau 9.
1.1.4. Pengujian keterbagian oleh 11.
1.1.5. Pengujian keterbagian bilangan prima 7, 11, dan 13.
1.1.6. Pengujian keterbagian dengan menggunakan repsentasi
basis b, dengan b merupakan bilangan bulat positif.
1.2. Turnamen Round-Robin
1.2.1. Menjadwalkan turnamen Round-Robin untuk tim N ganjil.
1.2.2. Menjadwalkan turnamen Round-Robin untuk tim N genap.

IV. MEDIA
Laptop , LCD, Whiteboard , Hand out (terlampir)

V. KEGIATAN PEMBELAJARAN

1. PENDAHULUAN ( 10 menit )
1. Sebagai apersepsi, mahasiswa diingatkan kembali tentang kekongruenan modulo 9 dan
bilangan dasar (basis), seperti basis 16 (hexadecimal).

2. KEGIATAN INTI ( 110 menit )
1. Dosen ( Mahsiswa PPL ) membahas pengujian keterbagian yang menggunakan notasi desimal
sebagai berikut :
 Misalkan n = (akak-1…a1a0)10,
maka : n = ak10k + ak-110k-1 + …+ a110 + a0,
dengan 0 ≤ aj ≤ 9 untuk j = 0,1,2,…,k.


Contoh :
n = (3725)10
n = 3.103 + 7.102 + 2.10 + 5

2. Dosen bersama mahasiswa membahas pengujian keterbagian bilangan perpangkatan 2.
 Karena 10 ≡ 0 (mod 2),
maka : 10j ≡ 0 (mod 2j), untuk semua bilangan bulat positif j,
karenanya :
n ≡ (a0)10 (mod 21).
n ≡ (a1a0)10 (mod 22).
n ≡ (a2a1a0)10 (mod 23).
.
.
.
n ≡ (aj-1aj-2 …a2a1a0)10 (mod 2j).
 Kongruensi ini menunjukkan bahwa untuk menentukan apakah bilangan bulat n terbagi 2, kita hanya perlu menguji angka terakhir dari n.
 Untuk menentukan apakah n dapat dibagi 4, kita hanya perlu mengecek bilangan bulat yang terdiri atas dua angka terakhirnya dari n.
 Secara umum :
Untuk menguji keterbagian oleh 2j, kita hanya perlu mengecek bilangan bulat yang terbentuk dari angka j terakhir dari n.
 Suatu bilangan terbagi oleh 2j jika dan hanya jika bilangan yang dinyatakan oleh j angka terakhir dari bilangan itu terbagi oleh 2j.
 Contoh :
Selidiki apakah n = 23866088 terbagi oleh 2,4,8,16 atau 32 ?


Jawab :
n = 23866088
2 | n karena 2 | 8 ; 4 | n karena 4 | 88 ; 8 | n karena 8 | 88,
16 | n karena 16 | 6088 ; 32 | n karena 32 | 66088.

3. Dosen bersama mahasiswa membahas pengujian keterbagian bilangan perpangkatan 5.
 Karena 10 ≡ 0 (mod 5), maka 10j ≡ 0 (mod 5j).
Sehingga : Untuk menentukan apakah n terbagi oleh 5j, maka kita uji bilangan bulat yang terdiri atas angka j terakhir dari n.
 Contoh :
Misalkan n = 51353585.
Ujilah apakah n terbagi oleh 5,25,125 dan 625 ?
Jawab :
n = 51353875
5 | n karena 5 | 5 ; 25 | n karena 25 | 75 ; 125 | n karena 125 | 875 ; 625 | n karena 625 | 3875

4. Dosen bersama mahasiswa membahas pengujian keterbagian 3 atau 9.
 Jika 10 ≡ 1 (mod 3) dan 10 ≡ 1 (mod 9)
Karenanya : 10k ≡ 1 (mod 3) dan (mod 9)
Sehingga :
(akak-1…a1a0) = ak10k + ak-110k-1 + … + a110 + a0
≡ ak+ak-1+…+a1+a0 (mod 3) dan (mod 9)
maka :
n bilangan bulat dapat dibagi 3 atau 9 jika jumlah angka terakhir dari n dapat dibagi 3 atau 9.
 Contoh :
Misalkan: n = 5415654,
Maka : jumlah angka dari n adalah 5+4+1+5+6+5+4= 30.
Karena 3 | 30 tetapi 9 | 30 ; maka 3 | n tetapi 9 | n.

4. Dosen bersama mahasiswa membahas pengujian keterbagian oleh 11.
 Karena 10 ≡ -1 (mod 11), maka
(akak-1…a1a0)10 = ak10k + ak-110k-1 + … + a110 + a0
≡ ak(-1)k + ak-1(-1)k-1 +… -a1 + a0 (mod 11)
Hal ini menunjukkan :
(akak-1…a1a0)10 terbagi oleh 11 jika dan hanya jika
a0 – a1 + a2 -... + (-1)k ak .
 Untuk menguji keterbagian oleh 11 adalah dengan cara menjumlahkan dan mengurangkan angka-angka dari bilangan tersebut dan dimulai dari angka terakhirnya.
 Contoh :
1. Ujilah apakah bilangan dibawah ini dapat dibagi 11 !
(a). n = 723160823
(b). m = 33678924
Jawab :
(a). n = 723160823, secara bergantian mengurangkan dan menjumlahkan angka-angkanya menghasilkan :
3 – 2 + 8 – 0 + 6 – 1 + 3 – 2 + 7 = 22
karena 11 | 22, maka 11 | n
(b). m = 33678924, secara bergantian mengurangkan dan menjumlahkan angka-angkanya menghasilkan :
4 – 2 + 9 – 8 + 7 - 6 + 3 – 3 = 4
karena 11 | 4, maka 11 | m

5. Dosen bersama mahasiswa membahas pengujian keterbagian bilangan prima 7, 11, atau 13
 Perhatikan :
7.11.13 = 1001 dan 103 = 1000 ≡ -1 (mod 1001).
Karenanya :
(akak-1…a1a0)10 = ak10k + ak-110k-1 + … + a110 + a0
≡ (a0+10a1+100a2) + 1000(a3+10a4+100a5) + (1000)2(a6 + 10a7 + 100a8) + ….
≡ (100a2 + 10a1 + a0) – (100a5 + 10a4 + a3) + (100a8 + 10a7 + a6) -…
≡ (a2a1a0)10 – (a5a4a3)10 + (a8a7a6)10 - ….(mod 1001)
Hal diatas membuktikan bahwa bilangan bulat kongruen modulo 1001 pada bilangan bulat yang terbentuk secara berturut-turut menjumlahkan dan mengurangkan bilangan bulat 3 angka dengan ekspansi desimal yang terbentuk dari blok 3 angka desimal berturut-turut dari bilangan asalnya, dengan angka dikelompokkan yang dimulai dari angka yang paling kanan.
Akibatnya, karena 7,11,dan 13 merupakan pembagi 1001.
Maka untuk menguji keterbagian bilangan prima 7,11, atau 13 adalah dengan cara menguji apakah jumlah dan selisih yang berselang–seling dari blok tiga angka dapat dibagi 7,11, atau 13.
 Contoh :
Ujilah apakah n = 93527408 terbagi oleh 7,11, dan 13.
Jawab :
n = 28527408, karena jumlah dan selisih yang berselang-seling dari bilangan bulat yang terbentuk dari blok tiga angka:
408 – 527+ 28= -91
-91 terbagi oleh 7 dan 13, tetapi tidak terbagi oleh 11.
Jadi n terbagi oleh 7 dan 13, tetapi tidak terbagi oleh 11.

6. Dosen bersama mahasiswa membahas pengujian keterbagian dengan menggunakan representasi basis b, dengan b merupakan bilangan bulat positif sebagai penerapan teorema 4.1, 4.2, dan 4.3.
Teorema 4.1
Jika d | b dan j dan k merupakan bilangan bulat positif dengan
j < k, maka (ak...a1a0)b dapat dibagi dj jika dan hanya jika
(aj-1...a1a0)b dapat dibagi dj.
Bukti :
b ≡ 0 (mod d), dan bj ≡ 0 (mod dj).
Maka : (ak...a1a0)b = akbk + ...+ ajbj + aj-1bj-1 + … + a1b + a0
= aj-1bj-1 + … + a1b + a0
≡ (aj-1...a1a0)b (mod dj).
Akibatnya : d | (akak-1...a1a0)b jika dan hanya jika d | (aj-1...a1a0)b

Teorema 4.2
Jika d | (b-1), maka n = (ak...a1a0)b dapat dibagi d jika dan hanya jika ak +...+ a1 + a0 dapat dibagi d.
Bukti:
Karena d | (b-1), maka b ≡ 1 (mod d), sehingga bj ≡ 1 (mod d) (teorema 3.7), untuk semua bilangan bulat positif b,
Karenanya :
n = (ak...a1a0)b = akbk + ... + a1b + a0 ≡ ak + ... + a1 + a0 (mod d).
Hal ini menunjukkan bahwa d | n jika dan hanya jika d | (ak+...+a1+a0). □

Teorema 4.3
Jika d | (b+1), maka n = (ak...a1a0)b dapat dibagi d jika dan hanya jika (-1)kak +...- a1 + a0 dapat dibagi d.
Bukti :
d | (b+1), maka b ≡ -1 (mod d).
Karena : bj ≡ (-1)j(mod d),
dan akibatnya, n = (ak...a1a0)b ≡ (-1)kak +...- a1 + a0 (mod d)
Karenanya : d | n jika dan hanya jika d | ((-1)k ak + ...- a1 + a0). □
 Contoh 1 :
Diketahui : n = (7F28A6)16
Ditanya : Ujilah apakah n terbagi oleh :
a. 2 atau 4
b. 3, 5, dan 15
c. 17

Jawab :
a. Berdasarkan teorema 4.1 diperoleh :
Karena 2 | 16, dan 2 | 6, maka 2 | n.
Karena 4 | 16, dan 4 | 6, maka 4 | n
b. Berdasarkan teorema 4.2 diperoleh :
karena 3 | (16-1), 5 | (16-1), dan 15 | (16-1),
dan n = (7F28A6)16 = 7 + F + 2 + 8 + A + 6 ≡ (48)16,
bahwa 3 | n, karena 3 | (48)16, 5 | (48)16 dan 15 | (48)16.
Maka : 3 | n , 5 | n dan 15 | n
c. Berdasarkan teorema 4.3 diperoleh :
Karena 17 | (16 + 1) dan n = (7F28A6)16 = 6 – A + 8 – 2 + F – 7 ≡ (A)16 (mod 17), sehingga 17 | (A)16 , maka : 17 | n,

 Contoh 2 :
Ujilah apakah n = (1001001111)2 habis dibagi 3
Jawab :
Dengan menggunakan teorema 4.3, diperoleh :
n = (1001001111)2 ≡ 1-1+1-1+0-0+1-0+0-1 ≡ 0 (mod 3)
dan 3 | (2 +1), maka 3 | n

7. Dosen ( Mahasiswa PPL ) memberikan kesempatan bertanya kepada mahasiswa yang belum mengerti.

8. Dosen bersama mahasiswa membahas penjadwalan turnamen Round-Robin untuk tim N ganjil dan tim N genap.
Kekongruenan dapat digunakan untuk menjadwalkan turnamen Round-Robin. Dalam turnamen ini akan ditunjukkan bagaimana menjadwalkan turnamen untuk N tim yang berbeda sehingga setiap tim bermain dengan setiap tim lainnya tepat satu kali. Metode ini dikembangkan oleh Freund.
Pertama perhatikan jika N ganjil, tidak semua tim dapat dijadwalkan dalam setiap ronde, karena saat tim dipasangkan, jumlah tim yang bermain akan genap. Sehingga jika N ganjil, maka ditambahkan tim dummy. Jika suatu tim dipasangkan dengan tim dummy saat ronde tertentu, maka tim tersebut bermain bye dalam ronde itu dan tidak perlu bermain lagi. sehingga diasumsikan jumlah tim genap.
Perhatikan: mula-mula N team diberi label 1,2,3,...,N-1, N. Bentuk jadwal yang memasangkan setiap tim dengan cara berikut ini :
Misal ada tim i (i ≠ N, dan N = tim dummy) bermain dengan tim j (j ≠ N dan j ≠ i) dalam ronde ke –k. Akan ada satu tim i bermain dengan tim N dalam ronde ke-k, dengan 2i ≡ k (mod N-1). Hal ini terjadi berdasarkan teorema 3.10 yang menjelaskan bahwa kekongruenan 2x ≡ k (mod N-1) memiliki tepat satu solusi dengan 1 ≤ x ≤ N-1, karena (2, N-1) = 1.
Jika tim i bermain dengan tim j dalam ronde k dan k’, maka i + j ≡ k’ (mod N-1) yang merupakan kontradiksi karena k ≠ k’ (mod N-1). Karena setiap tim N-1 pertama bermain dengan N-1 permainan, dan tidak bermain dengan tim lainnya lebih dari satu kali, tim tersebut bermain dengan setiap tim lainnya tepat satu kali. Tim N juga bermain dalam N-1 permainan, dan karenanya setiap tim lainnya bermain dengan tim N tepat satu kali, tim N bermain dengan setiap tim lainnya tepat satu kali.
 Contoh :
Buatlah jadwal turnamen Round-Robin untuk :
a. 5 tim
b. 6 tim
Jawab :
a. Untuk menjadwalkan turnamen Round-Robin dengan 5 tim, beri label 1,2,3,4, dan 5, serta sisipkan tim dummy yang diberi label 6.
Ronde 1 :
i + j ≡ k (mod N-1)
1 + j ≡ 1 (mod 5) → j = 5
2 + j ≡ 1 (mod 5) → j = 4
3 + j ≡ 1 (mod 5) → j = 3
karena i = 3, maka 2i ≡ 1 (mod 5) → 2(3) ≡ 1 (mod 5) → Bye
4 + j ≡ 1 (mod 5) → j = 2
5 + j ≡ 1 (mod 5) → j = 1

Ronde 2 :
i + j ≡ k (mod N-1)
1 + j ≡ 2(mod 5) → j = 1
karena i = 1, maka 2i ≡ 2 (mod 5) → 2(1) ≡ 2 (mod 5) → Bye
2 + j ≡ 2(mod 5) → j = 5
3 + j ≡ 2(mod 5) → j = 4
4 + j ≡ 2 (mod 5) → j = 3
5 + j ≡ 2 (mod 5) → j = 2

Ronde 3 :
i + j ≡ k (mod N-1)
1 + j ≡ 3 (mod 5) → j = 2
2 + j ≡ 3 (mod 5) → j = 1
3 + j ≡ 3 (mod 5) → j = 5
4 + j ≡ 3 (mod 5) → j = 4
karena i = 4, maka 2i ≡ 3 (mod 5) → 2(4) ≡ 3 (mod 5) → Bye
5 + j ≡ 3 (mod 5) → j = 3

Ronde 4 :
i + j ≡ k (mod N-1)
1 + j ≡ 4 (mod 5) → j = 3
2 + j ≡ 4 (mod 5) → j = 2
karena i = 2, maka 2i ≡ 4 (mod 5) → 2(2) ≡ 4 (mod 5) → Bye
3 + j ≡ 4 (mod 5) → j = 1
4 + j ≡ 4(mod 5) → j = 5
5 + j ≡ 4(mod 5) → j = 2


Ronde 5 :
i + j ≡ k (mod N-1)
1 + j ≡ 5 (mod 5) → j = 5
2 + j ≡ 5 (mod 5) → j = 4
3 + j ≡ 5 (mod 5) → j = 3
4 + j ≡ 5 (mod 5) → j = 2
5 + j ≡ 5 (mod 5) → j = 1
karena i = 5, maka 2i ≡ 5 (mod 5) → 2(5) ≡ 5 (mod 5) → Bye

Jadwal turnamen Round Robin untuk 5 tim
1 2 3 4 5
1 5 4 bye 2 1
2 bye 5 4 3 2
3 2 1 5 bye 3
4 3 bye 1 5 4
5 4 3 2 1 bye


b. Turnamen Round Robin untuk 6 tim.
Untuk menjadwalkan turnamen Round-Robin dengan 6 tim, beri label 1,2,3,4, 5 dan 6.
Ronde 1 :
i + j ≡ k (mod N)
1 + j ≡ 1 (mod 6) → j = 6
2 + j ≡ 1 (mod 6) → j = 5
3 + j ≡ 1 (mod 6) → j = 4
4 + j ≡ 1 (mod 6) → j = 3
5 + j ≡ 1 (mod 6) → j = 2
6 + j ≡ 1 (mod 6) → j = 1
Ronde 2 :
i + j ≡ k (mod N)
1 + j ≡ 2 (mod 6) → j = 1
karena i = 1, maka 2i ≡ 2 (mod 6) → 2(1) ≡ 2 (mod 6) → j = 4
2 + j ≡ 2 (mod 6) → j = 6
3 + j ≡ 2 (mod 6) → j = 5
4 + j ≡ 2 (mod 6) → j = 4
karena i = 4, maka 2i ≡ 2 (mod 6) → 2(4) ≡ 2 (mod 6) → j = 1
5 + j ≡ 2 (mod 6) → j = 3
6 + j ≡ 2 (mod 6) → j = 2
Ronde 3 :
i + j ≡ k (mod N)
1 + j ≡ 3 (mod 6) → j = 2
2 + j ≡ 3 (mod 6) → j = 1
3 + j ≡ 3 (mod 6) → j = 6
4 + j ≡ 3 (mod 6) → j = 5
5 + j ≡ 3 (mod 6) → j = 4
6 + j ≡ 3 (mod 6) → j = 3
Ronde 4 :
i + j ≡ k (mod N)
1 + j ≡ 4 (mod 6) → j = 3
2 + j ≡ 4 (mod 6) → j = 2
karena i = 2, maka 2i ≡ 4 (mod 6) → 2(2) ≡ 4 (mod 6) → j = 5
3 + j ≡ 4 (mod 6) → j = 1
4 + j ≡ 4 (mod 6) → j = 6
5 + j ≡ 4 (mod 6) → j = 5
karena i = 5, maka 2i ≡ 4 (mod 6) → 2(5) ≡ 4 (mod 6) → j = 2
6 + j ≡ 4 (mod 6) → j = 4
Ronde 5 :
i + j ≡ k (mod N)
1 + j ≡ 5 (mod 6) → j = 4
2 + j ≡ 5 (mod 6) → j = 3
3 + j ≡ 5 (mod 6) → j = 2
4 + j ≡ 5 (mod 6) → j = 1
5 + j ≡ 5 (mod 6) → j = 6
6 + j ≡ 5 (mod 6) → j = 5

Ronde 6 :
i + j ≡ k (mod N)
1 + j ≡ 6 (mod 5) → j = 5
2 + j ≡ 6 (mod 5) → j = 4
3 + j ≡ 6 (mod 5) → j = 3
karena i = 3, maka 2i ≡ 6 (mod 6) → 2(3) ≡ 6 (mod 6) → j = 6
4 + j ≡ 6 (mod 5) → j = 2
5 + j ≡ 6 (mod 5) → j = 1
6 + j ≡ 6 (mod 6) → j = 6
karena i = 6, maka 2i ≡ 6 (mod 6) → 2(6) ≡ 6 (mod 6) → j = 3

Jadwal turnamen Round Robin untuk 6 tim
1 2 3 4 5 6
1 6 5 4 3 2 1
2 4 6 5 1 3 2
3 2 1 6 5 4 3
4 3 5 1 6 2 4
5 4 3 2 1 6 5
6 5 4 6 2 1 3


9. Dosen ( Mahasiswa PPL ) memberikan kesempatan bertanya kepada mahasiswa yang belum
mengerti.

10. Dosen memberikan soal untuk dikerjakan secara berkelompok.

11. Dosen berkeliling mengamati mahasiswa menyelesaikan soal tersebut.

12. Masing-masing kelompok mahasiswa mempresentasikan jawaban soal tersebut oleh salah
satu anggota kelompoknya di depan kelas. ( soal dan jawaban terlampir).

3. Penutup (30 menit)
 Dosen membimbing mahasiswa untuk menyimpulkan materi perkuliahan pada pertemuan ini.
Kesimpulan :
 Suatu bilangan terbagi oleh 2j jika dan hanya jika bilangan yang dinyatakan oleh j angka terakhir dari bilangan itu terbagi oleh 2j.
 Untuk menentukan apakah n terbagi oleh 5j, maka kita uji bilangan bulat yang terdiri atas angka j terakhir dari n.
 n bilangan bulat dapat dibagi 0leh 3 atau 9 jika jumlah angka terakhir dari n dapat dibagi 3 atau 9
 Untuk menguji keterbagian oleh 11 adalah dengan cara menjumlahkan dan mengurangkan angka-angka dari bilangan tersebut dan dimulai dari angka terakhirnya.
 Untuk menguji keterbagian bilangan prima 7,11, atau 13 adalah dengan cara menguji apakah jumlah dan selisih yang berselang-seling dari blok tiga angka bilangan tersebut dapat dibagi 7, 11, atau 13.
 Jika d | b dan j dan k merupakan bilangan bulat positif dengan j < k, maka (ak...a1a0)b dapat dibagi dj jika dan hanya jika (aj-1...a1a0)b dapat dibagi dj.
 Jika d | (b-1), maka n = (ak...a1a0)b dapat dibagi d jika dan hanya jika ak +...+ a1 + a0 dapat dibagi d.
 Jika d | (b+1), maka n = (ak...a1a0)b dapat dibagi d jika dan hanya jika (-1)kak +...- a1 + a0 dapat dibagi d.
 Kekongruenan dapat digunakan untuk menjadwalkan turnamen Round-Robin untuk tim N genap dan tim N ganjil. Dalam turnamen ini akan dibuat jadwal turnamen untuk tim N yang berbeda sehingga setiap tim bermain dengan setiap tim lainnya tepat satu kali.
 Jika tim N ganjil maka ditambahkan tim dummy, dimana tim yang dipasangkan dengan tim
dummy ini akan bermain bye dan tidak perlu bermain lagi. Hal ini didasarkan atas teorema
3.10 yang menjelaskan bahwa kekongruenan 2x ≡ k (mod N-1) memiliki tepat satu solusi
dengan 1 ≤ x ≤ N-1, karena (2, N-1) = 1.
 Jika tim i bermain dengan tim j dalam ronde k, maka i + j ≡ k (mod N-1) untuk N ganjil dan i +
j ≡ k (mod N) untuk N genap.

 Sebagai evaluasi, pada akhir pembelajaran mahasiswa diberikan soal untuk diselesaikan
sebagai tugas individu. (soal dan jawaban terlampir)
 Pada akhir perkuliahan, Dosen memberikan hand out.

No comments:

Post a Comment