teori bilangan -...

ii

Teori Bilangan

Edisi 1

Nego Linuhung, M.Pd

Pendidikan Matematika UM Metro

iv

KATA PENGANTAR

Assalamu’alaikum warahmatullahi wabarakatuh.

Segala puji bagi Allah SWT. yang telah memberikan nikmat serta hidayah-

Nya terutama nikmat kesempatan dan kesehatan, sehingga penulis dapat

menyelesaikan modul ini. Kemudian shalawat beserta salam senantiasa kita sanjung

agungkan kepada Nabi besar Muhammad SAW. yang telah memberikan pedoman

hidup yakni Al-qur’an dan Sunnah untuk keselamatan umat di dunia.

Modul ini merupakan salah satu modul yang harus dipelajari oleh

mahasiswa khususnya program studi pendidikan matematika. Dalam

penyusunannya, penulis memperoleh banyak bantuan dari berbagai pihak, karena

itu penulis mengucapkan terima kasih yang sebesar-besarnya kepada semua pihak

yang telah membantu dalam penyusunan modul ini. Meskipun penulis berharap isi

dari modul ini bebas dari kekurangan dan kesalahan, namun selalu ada yang kurang.

Oleh karena itu, penulis mengharapkan kritik dan saran yang membangun agar

modul ini dapat lebih baik lagi.

Nego Linuhung

v

DAFTAR ISI

Cover ............................................................................................................ i

Cover dalam ................................................................................................. ii

Lembar pengesahan ..................................................................................... iii

Kata Pengantar ............................................................................................. iv

Daftar Isi ...................................................................................................... v

A. Rencana Pembelajaran Semester (RPS) ............................................... 1

B. Faktor Persekutuan Terbesar (FPB) dan Kelipatan Persekutuan

Terkecil (KPK) di Sekolah Dasar (SD) ................................................ 12

C. Keterbagian ........................................................................................... 15

D. Algoritma Pembagian ........................................................................... 16

E. Pembagi Bersama ................................................................................. 16

F. Teorema Euclidean ............................................................................... 17

G. Faktor Persekutuan Terbesar (FPB) ...................................................... 17

H. Algoritma Euclidean ............................................................................. 18

I. Relatif Prima ......................................................................................... 19

J. Kelipatan Persekutuan Terkecil (KPK) ................................................ 20

K. Aritmetika Modulo ............................................................................... 22

L. Kongruen .............................................................................................. 23

M. Balikan Modulo (modulo invers) .......................................................... 26

N. Kekongruenan Lanjar............................................................................. 28

O. Chinese Remainder Problem ................................................................ 30

P. Bilangan Prima (Basit).......................................................................... 31

Q. Teorema Fermat .................................................................................... 33

R. Fungsi Euler ....................................................................................... 35 S. Latihan-latihan Soal .............................................................................. 36

T. Tugas Terstruktur .................................................................................. 38

DAFTAR PUSTAKA .................................................................................. 39

1

A. RENCANA PEMBELAJARAN SEMESTER

2. Nama Mata Kuliah : TEORI BILANGAN

3. Kode/SKS : ……../ 2 SKS

4. Prasarat :

5. Status Mata Kuliah : Wajib

6. Bentuk

Pembelajaran

: Kuliah

7. Dosen Pengampu : Nego Linuhung, M.Pd/ Rina Agustina, M.Pd.

8. Deskripsi Singkat Mata Kuliah

Mata kuliah ini masih merupakan mata kuliah dasar dalam matematika dimana

secara umum berkaitan dengan bilangan bulat. Komposisi dari materi ini meliputi:

induksi matematika dan teorema binomial; sistem bilangan bulat; kekongruenan,

keterbagian, FPB dan KPK; bilangan prima; teorema fermat dan fungsi Phi Euler

serta trampil menerapkannya dalam berbagai masalah.

9. Capaian Pembelajaran

Capaian Pembelajaran Program Studi Pendidikan Matematika yang

Terkait Mata Kuliah Matematika Diskrit

a. CP – ST ( Capaian Pembelajaran Sikap dan Tata Nilai )

1) Bertakwa kepada Tuhan Yang Maha Esa dan mampu menunjukkan

sikap religius

2) Bekerja sama dan memiliki kepekaan sosial serta kepedulian terhadap

masyarakat dan lingkungan

3) Menginternalisasi nilai, norma, dan etika akademik

4) Menunjukkan sikap bertanggungjawab atas pekerjaan di bidang

keahliannya secara mandiri

5) Mempunyai karakter islami

b. CP – KU ( Capaian Pembelajaran Keterampilan Umum )

1) Menerapkan pemikiran logis, kritis, sistematis, dan inovatif dalam

konteks pengembangan atau implementasi ilmu pengetahuan dan/atau

teknologi sesuai dengan bidang keahliannya.

2) Mengambil keputusan secara tepat dalam konteks penyelesaian

masalah di bidang keahliannya, berdasarkan hasil analisis terhadap

informasi dan data.

c. CP – KK ( Capaian Pembelajaran Keterampilan Khusus )

1) Mampu mengambil keputusan yang tepat di bidang pendidikan

matematika berdasarkan informasi dan data yang relevan

2) Mampu memberikan petunjuk dalam memilih berbagai alternatif

solusi masalah di bidang pendidikan matematika secara mandiri dan

kelompok

3) Mampu bertanggung jawab terhadap pekerjaan sendiri di bidang

pendidikan matematika

d. CP – PP ( Capaian Pembelajaran Penguasaan Pengetahuan )

1) Menguasai konsep dan pola pikir matematika ( aljabar, statistika,

2

geometri, analisis, terapan) yang diperlukan untuk melaksanakan

pembelajaran di pendidikan sekolah menengah pertama serta untuk

studi lanjut

2) Menguasai metodologi dan konsep – konsep matematika yang

terkait dengan nilai – nilai keislaman

10. Capaian Pembelajaran Perkuliahan

1. Mahasiswa, mampu menentukan langkah induksi dalam pembuktian

dan terampil menggunakan langkah-langkah pembuktian dengan

induksi matematika

2. Mahasiswa mampu menurunkan dan menerapkan sifat-sifat koefisien

binomial dalam memecahkan masalah yang terkait.

3. Mahasiswa mampu membuktikan sifat yang berlaku pada operasi

penjumlahan, pengurangan, perkalian dan pembagian bilangan bulat

4. Mahasiswa mampu mengidentifikasi konsep kekongruenan

5. Mahasiswa mampu menunjukan pembuktian sifat kekongruenan dan

mampu menerapkan sifat kekongruenan dalam memecahkan masalah

matematika yang terkait

6. Mahasiswa mampu menunjukan banyak solusi suatu pengkongruenan

linier dan mampu memecahkan masalah matematika yang terkait

7. Mahasiswa mampu menunjukkan pembuktian teorema yang

berkenaan dengan keterbagian, faktor persekutuan, kelipatan

persekutuan, FPB, dan KPK bilangan-bilangan bulat.

8. Mahasiswa mampu menentukan FPB dan KPK bilangan-bilangan

bulat

9. Mahasiswa mampu menunjukkan pembuktian teorema yang

berkenaan dengan bilangan prima dan mampu menyatakan bentuk

kanonik suatu bilangan

10. Mahasiswa mampu menentukan FPB dan KPK dari beberapa

bilangan dengan faktorisasi prima dan mampu menunjukan pengujian

apakah suatu bilangan merupakan bilangan prima atau bukan

11. Mahasiswa mampu mengidentifikasi persyaratan dari teorema Fermat

12. Mahasiswa mampu menerapkan teorema Fermat dalam

menyelesaikan masalah matematika yang terkait

13. Mahasiswa mampu menunjukkan proses untuk menentukan

himpunan residu sederhana modulo m

14. Mahasiswa mampu menghitung harga fungsi Phi dan Euler,

kemudian memecahkan masalah matematika yang terkait

11. Materi Pembelajaran

1. Induksi Matematika Dan Teorema Binomial

2. Sistem Bilangan Bulat

3. Sifat-Sifat Keterbagian Elementer

4. Algoritma Pembagian Dan Identitas Aljabar

5. Kekongruenan

6. Persamaan Kongruensi

7. Uji Keterbagian

3

8. Faktor Persekutuan Terbesar (FPB)

9. Kelipatan Persekutuan Tekecil (KPK)

10. Bilangan Prima

11. Faktorisasi Tunggal

12. Teorema Fermat

13. Teorema Euler

14. Algoritma Euclid

12. Metode Pembelajaran

Strategi pembelajaran pada mata kuliah ini mengacu pada kooperatif learning tipe

Thing Pair Share (TPS) dengan skema pembelajaran sebagai berikut:

1. Penyampaian materi dengan mengutamakan pemberian kata kunci untuk

setiap topic masalah yang diberikan.

2. Kemudian mahasiswa mendalami dan menghayati tentang apa yang

disampaikan dalam penyampaian materi, kemudian dalam situasi ini

mahasiswa dituntut untuk mampu memberikan pandangan dengan cara

menghimpun apa yang menjadi hambatan siswa dalam memahami

permasalahan yang disampaikan dalam penyampaian materi.

3. Hamabatan-hambatan yang diungkap oleh mahasiswa menjadi dasar

untuk penjelasan selanjutnya, dimana solusi untuk hambatan ini dibagi

menjadi 2 tahapan: 1) membarikan kesempatan kepada mahasiswa lain

untuk memberikan tanggapan dan meluruskan masalah, 2) selanjutnya

dosen memberikan penekanan dan atau meluruskan masalah yang

menjadi hambatan tersebut.

4. Memberikan kesempatan kepada mahasiswa untuk berdiskusi atas

mahasiswa, antar kelompok yang memungkinkan mahasiswa membagi

secara luas informasi yang ia miliki dan memungkinkan juga dalam

konteks mencari solusi sampai ia menemukan solusi dari masalah yang ia

punya, sehingga diskusinya menjadi sangat interaktif ke beberapa

mahasiswa.

5. Dalam penyelesaian soal/masalah dalam matematika mahasiswa tidak

hanya di tuntut bagaimana ia bisa menyelesaikan masalah tersebut namun

juga mahasiswa di tuntut untuk bisa mengembangkan/menunjukkan

situasi lain dari soal yang ada (mengembangkan soal dalam situasi lain).

Mengutamakan diskusi yang interaktif dan diskusi yang menyebar/melibatkan

semua mahasiswa dalam kelas tersebut.

13. Bentuk Penugasan yang Direncanakan

A. Tugas individu

Tugas individu berupa memberikan latihan-latihan soal dan

dikumpulkan pada setiap pertemuan

B. Tugas kelompok

Tugas kelompok yaitu tugas mempelajari materi dan

mempresentasikannya didepan kelas, tugas ini diberikan pada pertemuan

ketiga. Pada pertemuan ke empat dan seterusnya, kelompok yang telah

ditentukan menyampaikan materi yang dipelajari yang berkaitan dengan

materi yang telah dibagikan pada setiap kelompok.

4

14. Penilaian yang Direncanakan

Aturan yang terdapat pada pedoman akademik yang dikeluarkan Universitas

maupun fakultas tentang PBM, diberlakukan juga pada PBM mata kuliah

Teori Bilangan.Yang berhak untuk mengikuti Ujian Tengah Semester (UTS)

adalah mahasiswa yang mengikuti perkulihan (tatap muka) minimal 35% dan

yang mengikuti Ujian Akhir Semester (UAS) adalah mahasiswa yang

mengikuti perkulihan (tatap muka) minimal 80%.

Bobot setiap tugas, Ujian Tengah Semester (UTS ) dan Ujian Akhir Semester

( UAS ) memiliki persentase yang berbeda. Skor akhir yang diperoleh

mahasiswa mengikuti formula :

Pendekatan penilaian yang digunakan berupa Penilaian Acuan Patokan ( PAP

). Grade nilai akhir mata kuliah dikategorikan sebagai berikut :

NO SKOR GRADE

1 Skor ≥ 77 A

2 70 ≤ Skor < 77 AB

3 63 ≤ Skor < 70 B

4 56 ≤ Skor < 63 BC

5 50 ≤ Skor < 56 C

6 35 ≤ Skor < 50 D

7 Skor < 35 E

Sumber Referensi

1. Beukers, Frits. 2013. Elementary Number Theory. (Online),

http://www.staff.science.uu.nl/~beuke106/getaltheorie/getalscript.pdf

2. Niven, I., Zuckerman, H.S., Montgomery, H. L. 1991. An Introduction to

the Theory of Numbers (Fifth Edition). USA:Courier Companies, Inc.

(online), http://editorialdinosaurio.files.wordpress.com/2012/03/itn-

niven.pdf

3. Raji, Wisman. An Introductory Course in Elementary Number Theory.

(Online), http://www.saylor.org/site/wp-content/uploads/2013/05/An-

Introductory-in-Elementary-Number-Theory.pdf

4. Sukarman, Harry, 2001, Teori Bilangan Modul UT, Depdikbud, Jakarta.

http://www.staff.science.uu.nl/~beuke106/getaltheorie/getalscript.pdf

http://editorialdinosaurio.files.wordpress.com/2012/03/itn-niven.pdf

http://editorialdinosaurio.files.wordpress.com/2012/03/itn-niven.pdf

http://www.saylor.org/site/wp-content/uploads/2013/05/An-Introductory-in-Elementary-Number-Theory.pdf

http://www.saylor.org/site/wp-content/uploads/2013/05/An-Introductory-in-Elementary-Number-Theory.pdf

5

15. Rencana Kegiatan Pembelajaran Mingguan

Ming

gu ke- Indikator

Materi

Ajar Waktu Media Metode

Evalua

si Mahasiswa

1 1. Mahasiswa,

mampu

menentukan

langkah induksi

dalam pembuktian

dan terampil

menggunakan

langkah-langkah

pembuktian

dengan induksi

matematika

2. Mahasiswa

mampu

menurunkan dan

menerapkan sifat-

sifat koefisien

binomial dalam

memecahkan

masalah yang

terkait

Induksi

Matematik

a dan

Teorema

Binomial

2 x 50’ Handout,

LCD,

papan

tulis

Presentas

i, diskusi,

tutorial

1. Melakukan doa

bersama

sebelum

perkuliahan

dimulai

2. Memperhatika

n dan

mendengarkan

penjelas

an dosen

tentang materi

– perkuliahan

untuk satu

semester

3. Membuat

kontrak

perkuliahan

dengan dosen

4. Memperhatika

n penjelasan

dosen tentang

materi

perkuliahan

yang dipelajari

5. Bertanya atau

mengemukan

pendapat

terkait dengan

mater

pembelajaran

6. Membentuk

kelompok

diskusi

7. Membuat

kesimpulan

secara bersama

dengan

mahasiswa

tentang matri

perkuliahan

yang sudah

disampaiakan

8. Berdoa

bersama selesai

pembelajaran

Kehadi

ran,

Tugas

aktivit

as di

kelas

2 1. Mahasiswa teliti

dalam

memperlihatkan

apakah definisi-

definisi operasi

bilangan cacah

berlaku pada setiap

bilangan bulat

2. Mahasiswa

mampu

membuktikan sifat

Sistem

Bilangan

Bulat

2 x

50’

Handout,

LCD,

papan

tulis

Presentas

i, diskusi,

tutorial

1. Melakukan doa

bersama

sebelum

perkuliahan

dimulai

2. Memperhatika

n penjelasan

dosen tentang

materi

perkuliahan

yang dipelajari

Kehadi

ran,

Tugas

aktivit

as di

kelas

6

yang berlaku pada operasi

penjumlahan,

pengurangan,

perkalian dan

pembagian

bilangan bulat

3. Mahasiswa

mampu memilih

dan memilah

mana-mana sifat

urutan yang

berlaku dalam

sistem bilangan

bulat

3. Mempresentasikan materi

tugas

kelompoknya

4. Mengerjakan

soal – soal

latihan

5. Membuat

kesimpulan

secara bersama

dengan

mahasiswa

tentang matri

perkuliahan

yang sudah

disampaiakan

6. Melakukan

refleksi tentang

pembelajaran

yang

dilaksanakan

7. Berdoa

bersama selesai

pembelajaran

3 1. Mahasiswa

mampu

membuktikan sifat

yang berlaku pada

operasi

penjumlahan,

pengurangan,

perkalian dan

pembagian

bilangan bulat

2. Mahasiswa

mampu memilih

dan memilah

mana-mana sifat

urutan yang

berlaku dalam

sistem bilangan

bulat

Sifat-sifat

keterbagia

n

elementer

2 x

50’

Handout,

LCD,

papan

tulis

Presentas

i, diskusi,

tutorial

1. Melakukan doa

bersama

sebelum

perkuliahan

dimulai

2. Memperhatika

n penjelasan

dosen tentang

materi

perkuliahan

yang dipelajari

3. Mempresentasi

kan materi

tugas

kelompoknya

4. Mengerjakan

soal – soal

latihan

5. Membuat

kesimpulan

secara bersama

dengan

mahasiswa

tentang matri

perkuliahan

yang sudah

disampaiakan

6. Melakukan

refleksi tentang

pembelajaran

yang

dilaksanakan

7. Berdoa

bersama selesai

pembelajaran

Kehadi

ran,

Tugas

aktivit

as di

kelas

4 1. Memahami

algoritma

pembagian dan

sifat-sifat

Algoritma

Pembagian

dan

identitas

2 x

50’

Handout,

LCD,

papan

tulis

Presentas

i, diskusi,

tutorial

1. Melakukan doa

bersama

sebelum

perkuliahan

Kehadi

ran,

Tugas

aktivit

7

keterbagian bilangan bulat

serta dapat

menerapkan-nya

pada masalah yang

memuat

pembagian

bilangan bulat

aljabar dimulai 2. Memperhatika

n penjelasan

dosen tentang

materi

perkuliahan

yang dipelajari

3. Mempresentasi

kan materi

tugas

kelompoknya

4. Mengerjakan

soal – soal

latihan

5. Membuat

kesimpulan

secara bersama

dengan

mahasiswa

tentang matri

perkuliahan

yang sudah

disampaiakan

6. Melakukan

refleksi tentang

pembelajaran

yang

dilaksanakan

7. Berdoa

bersama selesai

pembelajaran

as di kelas

5 1. Mahasiswa mampu

mengidentifikasi

konsep

kekongruenan

2. Mahasiswa

mampu

menunjukan

pembuktian sifat

kekongruenan dan

mampu

menerapkan sifat

kekongruenan

dalam memecahkan

masalah

matematika yang

terkait

Kekongruen

an

2 x

50’

Handout,

LCD,

papan

tulis

Presentas

i, diskusi,

tutorial

1. Melakukan doa

bersama

sebelum

perkuliahan

dimulai

2. Memperhatika

n penjelasan

dosen tentang

materi

perkuliahan

yang dipelajari

3. Mempresentasi

kan materi

tugas

kelompoknya

4. Mengerjakan

soal – soal

latihan

5. Membuat

kesimpulan

secara bersama

dengan

mahasiswa

tentang matri

perkuliahan

yang sudah

disampaiakan

6. Melakukan

refleksi tentang

pembelajaran

yang

dilaksanakan

Kehadi

ran,

Tugas

aktivit

as di

kelas

8

7. Berdoa bersama selesai

pembelajaran

6 1. Mahasiswa

mampu

menunjukan

banyak solusi

suatu

pengkongruenan

linier dan mampu

memecahkan

masalah

matematika yang

terkait

Persamaan

kongruensi

2 x

50’

Handout,

LCD,

papan

tulis

Presentas

i, diskusi,

tutorial

1. Melakukan doa

bersama

sebelum

perkuliahan

dimulai

2. Memperhatika

n penjelasan

dosen tentang

materi

perkuliahan

yang dipelajari

3. Mempresentasi

kan materi

tugas

kelompoknya

4. Mengerjakan

soal – soal

latihan

5. Membuat

kesimpulan

secara bersama

dengan

mahasiswa

tentang matri

perkuliahan

yang sudah

disampaiakan

6. Melakukan

refleksi tentang

pembelajaran

yang

dilaksanakan

7. Berdoa

bersama selesai

pembelajaran

Kehadi

ran,

Tugas

aktivit

as di

kelas

7 1. Mahasiswa

mampu

menunjukkan

pembuktian

teorema yang

berkenaan dengan

keterbagian

Uji

keterbagia

n

2 x

50’

Handout,

LCD,

papan

tulis

Presentas

i, diskusi,

tutorial

1. Melakukan doa

bersama

sebelum

perkuliahan

dimulai

2. Memperhatika

n penjelasan

dosen tentang

materi

perkuliahan

yang dipelajari

3. Mempresentasi

kan materi

tugas

kelompoknya

4. Mengerjakan

soal – soal

latihan

5. Membuat

kesimpulan

secara bersama

dengan

mahasiswa

tentang matri

perkuliahan

Kehadi

ran,

Tugas

aktivit

as di

kelas

9

yang sudah disampaiakan

6. Melakukan

refleksi tentang

pembelajaran

yang

dilaksanakan

7. Berdoa

bersama selesai

pembelajaran

8


menunjukkan

pembuktian

teorema yang

berkenaan dengan

FPB bilangan

bulat.

2. Mahasiswa mampu menentukan FPB

bilangan-bilangan

bulat

3. Mahasiswa mampu menerapkan

konsep dan sifat-

sifat, FPB dalam

memecahkan

masalah

matematika yang

tekait

Faktor

Persek

utuan

terbesa

r

(FPB)

2 x

50’

Handout,

LCD,

papan

tulis

1. Melakukan doa bersama

sebelum perkuliahan

dimulai

2. Memperhatikan penjelasan

dosen tentang materi

perkuliahan yang dipelajari


tugas kelompoknya

4. Mengerjakan soal – soal

latihan

5. Membuat kesimpulan secara

bersama dengan mahasiswa

tentang matri perkuliahan


6. Melakukan refleksi tentang

pembelajaran yang

dilaksanakan


pembelajaran

Kehadi

ran,

Tugas

aktivita

s di

kelas

10 1. Mahasiswa mampu menunjukkan

pembuktian

teorema yang

berkenaan dengan

KPK bilangan

bulat.

2. Mahasiswa mampu

menentukan KPK

bilangan-bilangan

bulat


konsep dan sifat-

sifat, KPK dalam

memecahkan

masalah

matematika yang

tekait

Kelipatan

Persek

utuan

Tekecil

(KPK)

2 x

50’

Handout,

LCD,

papan

tulis


sebelum perkuliahan

dimulai





tugas kelompoknya


latihan






pembelajaran yang

dilaksanakan


pembelajaran

Kehadi

ran,

Tugas

aktivita

s di

kelas


menunjukkan

pembuktian

teorema yang

berkenaan dengan

bilangan prima dan

mampu

menyatakan bentuk

kanonik suatu

bilangan

Bilangan

Prima

2 x

50’

Handout,

LCD,

papan

tulis


sebelum perkuliahan

dimulai





tugas kelompoknya


latihan




Kehadi

ran,

Tugas

aktivita

s di

kelas

10

yang sudah disampaiakan 6. Melakukan refleksi tentang

pembelajaran yang

dilaksanakan


pembelajaran


menunjukkan

fungsi δ dan σ,

kemudian mampu

menentukan harga

fungsi δ dan σ

dari beberapa

bilangan

Fungsi δ

dan σ

2 x

50’

Handout,

LCD,

papan

tulis


sebelum perkuliahan

dimulai





tugas kelompoknya


latihan






pembelajaran yang

dilaksanakan


pembelajaran

Kehadi

ran,

Tugas

aktivita

s di

kelas

13 1. Mahasiswa

mampu

mengidentifikasi

persyaratan dari

teorema Fermat


teorema Fermat

dalam

menyelesaikan

masalah

matematika yang

terkait

Teorema

Ferma

t

2 x

50’

Handout,

LCD,

papan

tulis


sebelum perkuliahan

dimulai





tugas kelompoknya


latihan






pembelajaran yang

dilaksanakan


pembelajaran

Kehadi

ran,

Tugas

aktivita

s di

kelas

14 1. Mahasiswa mampu menghitung harga

fungsi Phi dan

Euler, kemudian

memecahkan

masalah

matematika yang

terkait

Teorema

Euler

2 x

50’

Handout,

LCD,

papan

tulis


sebelum perkuliahan

dimulai





tugas kelompoknya


latihan






pembelajaran yang

dilaksanakan


pembelajaran

Kehadi

ran,

Tugas

aktivita

s di

kelas

11

15 1. Mahasiswa mampu memecahkan

masalah

matematika yang

terkait dengan

Algoritma Euclid

Algoritma

Euclid

2 x 50’

Handout, LCD,

papan

tulis

1. Melakukan doa bersama sebelum perkuliahan

dimulai





tugas kelompoknya


latihan






pembelajaran yang

dilaksanakan


pembelajaran

Kehadiran,

Tugas

aktivita

s di

kelas

16. Monitoring dan Umpan Balik

Proses monitoring perkuliahan dilakukan dengan melihat unjuk kerja (

performance ) mahasiswa dalam mengerjakan latihan di kelas maupun

pekerjaan rumah yang diberikan. Untuk evaluasi pembelajaran menggunakan

Edom ( Evaluasi Dosen oleh Mahasiswa ) yang telah dibuat oleh Lembaga

Penjaminan Mutu ( LPM ) Universitas Muhammadiyah Metro. Proses

mendapatkan umpan balik untuk perbaikan perkuliahan berdasarkan hasil

analisis isian Edom yang terekam pada borang Evaluasi Dosen tersebut.

Analisis data EDoM dilakukan oleh Tim Univesitas Muhammadiyah Metro.

12

B. Faktor Persekutuan Terbesar (FPB) dan Kelipatan Persekutuan

Terkecil (KPK) di Sekolah Dasar (SD)

Apakah yang dimaksud Faktor, Faktor Prima dan Faktorisasi?

Jawab:

Faktor suatu bilangan adalah bilangan-bilangan yang habis

untuk membagi bilangan itu.

Faktor prima suatu bilangan adalah bilangan prima yang

terkandung dalam faktor bilangan itu.

Faktorisasi adalah bentuk perkalian bilangan-bilangan prima

suatu bilangan.

1. Menentukan Faktor Persekutuan Terbesar (FPB)

Cara menentukan FPB:

Tuliskan bilangan itu dalam bentuk perkalian faktor prima

(faktorisasi).

Ambil faktor yang sama dari bilangan-bilangan itu.

Jika faktor yang sama dari setiap bilangan, tetapi banyaknya berbeda,

ambil faktor yang sedikit.

Contoh:

1) Carilah FPB dari 18 dan 24.

Jawab:

18 = 2 x 3 x 3. (faktorisasi)

24 = 2 x 2 x 2 x 3 (faktorisasi)

FPB dari 18 dan 24 = 2 x 3 = 6.

2) Carilah FPB dari 24, 36, dan 40.

Jawab:

24 = 2 x 2 x 2 x 3. (faktorisasi)


13


FPB dari 24, 36, dan 40 = 2 x 2 = 4.

Latihan:

Cari FPB dari:

1) 18, 20, dan 24

2) 32, 48, dan 80

2. Kelipatan Persekutuan Terkecil (KPK)

Setiap bilangan adalah hasil kali faktor-faktor primanya. Oleh karena

itu, bilangan yang akan dicari KPK-nya, harus ditentukan lebih dulu

faktor-faktor primanya, kemudian menuliskannya ke dalam bentuk

perkalian faktor prima (faktorisasi).

Cara menentukan KPK.

1) Tulislah bilangan-bilangan itu dalam bentuk perkalian faktor prima

(faktorisasi).

2) Ambil semua faktor, yang sama atau tidak sama, dari bilangan-

bilangan itu.

3) Jika faktor yang sama dari setiap bilangan, tetapi banyaknya berbeda,

ambillah faktor yang paling banyak atau dari pangkat yang terbesar.

Contoh:

1) Carilah KPK dari 12 dan 18

Jawab:

12 = 2 x 2 x 3 = 22 x 3 (faktorisasi)

18 = 2 x 3 x 3 = 2 x 32 (faktorisasi)

KPK dari 12 dan 18 = 2 x 2 x 3 x 3 = 22 x 3

2 = 4 x 9 = 36

2) Carilah KPK dari 15, 20, dan 30.

Jawab:

15 = 3 x 5 = 3 x 5 (faktorisasi)

14

20 = 2 x 2 x 5 = 22 x 5 (faktorisasi)

30 = 2 x 3 x 5 = 2 x 3 x 5 (faktorisasi)

KPK dari 15, 20, dan 30 = 22 x 3 x 5 = 4 x 3 x 5 = 60

3) Tentukan KPK dan FPB dari 24, 30, dan 42.

Cara I

24 = 2 x 2 x 2 x 3

30 = 2 x 3 x 5

42 = 2 x 3 x 7

KPK dari 24, 30, dan 42 = 2 x 2 x 2 x 3 x 5 x 7

= 8 x 3 x 5 x 7

= 840

FPB dari 24, 30, dan 42 = 2 x 3 = 6.

Cara II

24 30 42

12 15 21

6 15 21

3 15 21

1 5 7

1 1 7

1 1 1

KPK dari 24, 30, dan 42

= 2 x 2 x 2 x 3 x 5 x 7

= 8 x 3 x 5 x 7 = 840

2

2

2

3

5

7

15

FPB dari 24, 30, dan 42 = 2 x 3 = 6.

Soal:

Ada 3 buah lampu, merah, kuning, dan hijau. Mula-mula ketiga lampu itu

menyala serentak bersamaan. Kemudian, lampu merah menyala setiap 4

detik, lampu kuning menyala setiap 5 detik, dan lampu hijau menyala setiap

6 detik. Tiap berapa detik ketiga lampu itu menyala bersamaan?

C. Keterbagian

Definisi:

“Bilangan bulat b disebut terbagi oleh bilangan bulat a, jika ada

bilangan bulat x sehingga b=ax, dapat ditulis sebagai a │b untuk “a

membagi b” atau “b terbagi a“.

Catatan: istilah “membagi” dan “terbagi” di sini diartikan “membagi

habis” atau “terbagi habis” sehingga tidak ada sisa (tak bersisa)

Untuk b = ax, maka

a di sebut faktor b, atau pembagi b.

b di sebut juga kelipatan a.

x di sebut hasil bagi (untuk a ≠0)

Contoh:

4 membagi 24 atau 24 terbagi 4 karena ada bilangan x sehingga

24 = 4.x (dimana x = 6, merupakan hasil bagi).

4 tidak membagi 35 karena tidak ada bilangan x, sehingga 35 =

4.x (tidak ada nilai x yang memenuhi)

16

D. Algoritma Pembagian

Teorema:

Untuk bilangan bulat sebarang m dan n dengan n>0, ada bilangan

bulat q dan r sehingga: m = qn + r dengan 0 ≤ r < n.

dimana bilangan r disebut sisa pembagian m oleh n dan q disebut

sisa hasil bagi m oleh n.

E. Pembagi Bersama

Istilah pembagi bersama di SD sering disebut faktor persekutuan.

Defenisi:

Suatu bilangan bulat a disebut pembagi bersama b dan c, jika a

membagi b dan a membagi c (a│b dan a│c)

Tiap bilangan bulat tak nol hanya memiliki sejumlah terbatas pembagi

saja (faktor saja), sehingga banyaknya pembagi bersama untuk b dan c

hanya ada sejumlah terbatas saja, kecuali untuk kasus b = c = 0.

Bilangan 1 akan membagi tiap bilangan. Maka 1 merupakan pembagi

bersama dua bilangan bulat sembarang a dan b sehingga tiap pasang

bilangan bulat akan selalu memiliki pembagi bersama (faktor

persekutuan).

Contoh:

Tentukan faktor pembagi bersama dari 45 dan 36!

Faktor pembagi 45: 1, 3, 5, 9, 15, 45;

Faktor pembagi 36: 1, 2, 3, 4, 9, 12, 18, 36;

Faktor pembagi bersama dari 45 dan 36 adalah 1, 3, 9

17

F. Teorema Euclidean

Teorema 1 (Teorema Euclidean). Misalkan m dan n adalah dua buah

bilangan bulat dengan syarat n > 0. Jika m dibagi dengan n maka

terdapat dua buah bilangan bulat unik q (quotient) dan r (remainder),

sedemikian sehingga

m = nq + r, dengan 0 ≤ r < n.

……………(1)

Contoh

1) 1987 dibagi dengan 97 memberikan hasil bagi 20 dan sisa 47:

1987 = 97 × 20 + 47

2) –22 dibagi dengan 3 memberikan hasil bagi –8 dan sisa 2:

–22 = 3(–8) + 2

tetapi –22 = 3(–7) – 1 salah karena r = –1 tidak memenuhi syarat 0 ≤

r < n.

G. Faktor Persekutuan Terbesar (FPB)

Misalkan a dan b bilangan bulat tidak nol.

Pembagi bersama terbesar (FPB – greatest common divisor atau gcd)

dari a dan b adalah bilangan bulat terbesar d sedemikian hingga

1) d | a dan d | b.

2) Bila c | a dan c | b, maka d ≥ c

Dalam hal ini kita nyatakan bahwa FPB(a, b) = d.

Penjelasan di atas dapat disajikan sebagai berikut:

Teorema:

Jika (a,b) = d, yaitu d FPB untuk a dan d maka berlaku “d membagi a”

dan “d membagi b”. jika ada c yang membagi a dan b, maka c ≤ d.

18

Contoh 1.

Faktor pembagi 45: 1, 3, 5, 9, 15, 45;

Faktor pembagi 36: 1, 2, 3, 4, 9, 12, 18, 36;

Faktor pembagi bersama dari 45 dan 36 adalah 1, 3, 9

FPB(45, 36) = 9

Teorema.

Misalkan m dan n bilangan bulat, dengan syarat n > 0 sedemikian

sehingga

m = nq + r , 0 ≤ r < n. maka FPB(m, n) = FPB(n, r)

Contoh 2:

m = 60, n = 18,

60 = 18 · 3 + 12

Maka FPB(60, 18) = FPB(18, 12) = 6

H. Algoritma Euclidean

1) Algoritma Euclidean adalah algoritma untuk mencari FPB dari dua

buah bilangan bulat.

2) Euclid, penemu algoritma Euclidean, adalah seorang matematikawan

Yunani yang menuliskan algoritmanya tersebut dalam bukunya yang

terkenal, Element.

Misalkan m dan n adalah bilangan bulat tak negatif dengan m ≥ n.

Misalkan r0 = m dan r1 = n.

Lakukan secara berturut-turut pembagian untuk memperoleh

r0 = r1q1 + r2, 0 ≤ r2 ≤ r1,

r1 = r2q2 + r3, 0 ≤ r3 ≤ r2,

.

.

.

19

rn-2= rn-1 qn-1 + rn 0 ≤ rn ≤ rn-1,

rn-1 = rnqn + 0

Menurut Teorema:

FPB(m, n) = FPB (r0, r1) = FPB (r1, r2) = … = FPB (rn-2, rn-1) = FPB

(rn-1, rn) = FPB(rn, 0) = rn

Jadi, FPB dari m dan n adalah sisa terakhir yang tidak nol dari

runtunan pembagian tersebut

Berdasarkan Algoritma Euclidean di atas berikut tahapannya:

1) Jika n = 0 maka m adalah FPB (m, n); stop.

tetapi jika n ≠0, lanjutkan ke langkah 2.

2) Bagilah m dengan n dan misalkan r adalah sisanya.

3) Ganti nilai m dengan nilai n dan nilai n dengan nilai r, lalu ulang

kembali ke langkah 1.

Contoh:

m = 80, n = 12 dan dipenuhi syarat m ≥ n

80 = 6 ·12 + 8

12 = 1 · 8 + 4

8 = 2 · 4 + 0

Sisa pembagian terakhir sebelum 0 adalah 4, maka FPB(80, 12) = 4

I. Relatif Prima

Dua buah bilangan bulat a dan b dikatakan relatif prima jika FPB(a,

b) = 1.

Contoh 1

20 dan 3 relatif prima sebab FPB(20, 3) = 1.

20

Begitu juga 7 dan 11 relatif prima karena FPB(7, 11) = 1.

Tetapi 20 dan 5 tidak relatif prima sebab FPB(20, 5) = 5 ≠ 1.

Jika a dan b relatif prima, maka terdapat bilangan bulat m dan n

sedemikian sehingga ma + nb = 1 ……………….. (2)

Contoh 2

Bilangan 20 dan 3 adalah relatif prima karena FPB(20, 3) =1, atau dapat

ditulis

2 · 20 + (–13) · 3 = 1

dengan m = 2 dan n = –13. Tetapi 20 dan 5 tidak relatif prima karena

FPB(20, 5) = 5 ≠ 1 sehingga 20 dan 5 tidak dapat dinyatakan dalam m .

20 + n . 5 = 1.

J. Kelipatan Persekutuan Terkecil (KPK)

Defenisi:

Bilangan-bilangan bulat a1, a2, a3,…….,an, masing-masing tak nol,

memiliki kelipatan bersama b, jika ai | b untuk i = 1, 2, 3, …………..,n.

Untuk bilangan-bilangan bulat a1, a2, a3,…….,an, masing-masing tak nol,

Kelipatan Persekutuan Terkecil (KPK) mereka adalah bilangan

positif yang terkecil diantara kelipatan-kelipatan bersama untuk a1, a2,

a3,…….,an, itu. Kita lambangkan [a1, a2] sebagai KPK a1 dan a2 dan [a1,

a2, a3,…….,an] sebagai KPK dari a1, a2, a3,…….,an.

Teorema:

Jika b suatu kelipatan bersama a1, a2, a3,…….,an maka [a1, a2,

a3,…….,an]│b. dengan kata lain, jika h KPK untuk a1, a2, a3,…….,an

yaitu h=[ a1, a2, a3,…….,an] maka 0, ± h, ± 2h, ± 3h, …. Merupakan

kelipatan kelipatan bersama a1, a2, a3,…….,an. Bilangan b tadi salah

satu dari kelipatan-kelipatan itu.

21

Perhatikan penjelasan berikut:

Misalkan a dan b bilangan bulat tidak nol.

Kelipatan perekutuan terkecil (KPK – least common multiples atau

lcm) dari a dan b adalah bilangan bulat terbesar m sedemikian

hingga

1. a| m dan b | m.

2. Bila a| n dan b | n, maka n ≥ m

Dalam hal ini kita nyatakan bahwa KPK[a, b] = m.

Contoh:

KPK [5,4]= 20

KPK [7, 6] =42

KPK [15, 12] = 60

Penggunaan Algoritma Euclid merupakan salah satu alternatif

metode dalam menemukan FPB, kelemahan metode ini bahwa hanya

dapat diberlakukan untuk dua bilangan saja.

Algoritma ini tidak dapat menentukan KPK tetapi dengan bantuan

Algoritma ini FPB yang sudah ditemukan dapat digunakan untuk

membantu kita dalam menentukan KPK dengan menggunakan

teorema berikut:

Teorema:

Untuk dua bilangan bulat positif sebarang a dan b, berlaku

hubungan

[a,b](a,b) = a.b

atau dengan kata lain hasil perkalian antara KPK dan FPB sama

dengan hasil perkalian kedua bilangan itu.

22

Teorema ini dapat dinyatakan ke dalam bentuk yang berbeda yaitu:

ba

baba

,,

Atau dengan kata lain, KPK adalah hasil bagi antara perkalian dua

bilangan a dan b dengan FPB nya.

Contoh

Kita dapat menentukan KPK dengan menggunakan teorema di atas

yaitu:

KPK dari 66 dan 50

Misalkan

a = 66 dan b = 50

a·b = (66) (50) = 3300

(a,b) = 2

ba

baba

,,

1650

2

3300

50,66

506650,66

Catatan: [a,b] artinya KPK dari a dan b dan (a,b) artinya FPB dari

a dan b

K. Aritmetika Modulo

Misalkan a adalah bilangan bulat dan m adalah bilangan bulat > 0.

Operasi a mod m (dibaca “a modulo m”) memberikan sisa jika a

dibagi dengan m.

23

Notasi: a mod m = r sedemikian sehingga a = mq + r, dengan 0 r <

m.

Bilangan m disebut modulus atau modulo, dan hasil aritmetika

modulo m terletak di dalam himpunan {0, 1, 2, …, m – 1}

(mengapa?).

Contoh 1.

Beberapa hasil operasi dengan operator modulo:

(i) 23 mod 5 = 3 (23 = 5 4 + 3)

(ii) 27 mod 3 = 0 (27 = 3 9 + 0)

(iii) 6 mod 8 = 6 (6 = 8 0 + 6)

(iv) 0 mod 12 = 0 (0 = 12 0 + 0)

(v) – 41 mod 9 = 4 (–41 = 9 (–5) + 4)

(vi) – 39 mod 13 = 0 (–39 = 13(–3) + 0)

Penjelasan untuk (v): Karena a negatif, bagi |a| dengan m

mendapatkan sisa r’. Maka a mod m = m – r’ bila r’ 0. Jadi |– 41|

mod 9 = 5, sehingga –41 mod 9 = 9 – 5 = 4.

L. Kongruen

Misalnya 38 mod 5 = 3 dan 13 mod 5 = 3, maka kita katakan 38 13

(mod 5) (baca: 38 kongruen dengan 13 dalam modulo 5).

Misalkan a dan b adalah bilangan bulat dan m adalah bilangan > 0,

maka a b (mod m) jika m habis membagi a – b.

Jika a tidak kongruen dengan b dalam modulus m, maka ditulis a / b

(mod m) .

Contoh 1.

17 2 (mod 3) ( 3 habis membagi 17 – 2 = 15)

24

–7 15 (mod 11) (11 habis membagi –7 – 15 = –22)

12 / 2 (mod 7) (7 tidak habis membagi 12 – 2 = 10 )

–7 / 15 (mod 3) (3 tidak habis membagi –7 – 15 = –22)

Kekongruenan a b (mod m) dapat pula dituliskan dalam hubungan

a = b + km

(3)

yang dalam hal ini k adalah bilangan bulat.

Contoh 2.

17 2 (mod 3)dapat ditulis sebagai 17 = 2 + 5 3

–7 15 (mod 11) dapat ditulis sebagai –7 = 15 + (–2)11

Berdasarkan definisi aritmetika modulo, kita dapat menuliskan a mod

m = r sebagai

a r (mod m)

Contoh 3.

Beberapa hasil operasi dengan operator modulo berikut:

(i) 23 mod 5 = 3 dapat ditulis sebagai 23 3 (mod 5)

(ii) 27 mod 3 = 0 dapat ditulis sebagai 27 0 (mod 3)

(iii) 6 mod 8 = 6 dapat ditulis sebagai 6 6 (mod 8)

(iv) 0 mod 12 = 0 dapat ditulis sebagai 0 0 (mod 12)

25

(v) – 41 mod 9 = 4 dapat ditulis sebagai –41 4 (mod 9)

(vi) – 39 mod 13 = 0 dapat ditulis sebagai – 39 0 (mod 13)

Teorema 2. Misalkan m adalah bilangan bulat positif.

1. Jika a b (mod m) dan c adalah sembarang bilangan bulat maka

(i) (a + c) (b + c) (mod m)

(ii) ac bc (mod m)

(iii) ap b

p (mod m) untuk suatu bilangan bulat tak negatif p.

2. Jika a b (mod m) dan c d (mod m), maka

(i) (a + c) (b + d) (mod m)

(ii) ac bd (mod m)

Bukti (hanya untuk 1(ii) dan 2(i) saja):

1(ii) a b (mod m) berarti:

a = b + km

a – b = km

(a – b)c = ckm

ac = bc + Km

ac bc (mod m)

2(i) a b (mod m) a = b + k1m

c d (mod m) c = d + k2m +

(a + c) = (b + d) + (k1 + k2)m

(a + c) = (b + d) + km ( k = k1 + k2)

(a + c) = (b + d) (mod m)

26

Contoh 4.

Misalkan 17 2 (mod 3) dan 10 4 (mod 3), maka menurut Teorema

2,

17 + 5 = 2 + 5 (mod 3) 22 = 7 (mod 3)

17 . 5 = 5 2 (mod 3) 85 = 10 (mod 3)

17 + 10 = 2 + 4 (mod 3) 27 = 6 (mod 3)

17 . 10 = 2 4 (mod 3) 170 = 8 (mod 3)

Perhatikanlah bahwa Teorema 2 tidak memasukkan operasi

pembagian pada aritmetika modulo karena jika kedua ruas dibagi

dengan bilangan bulat, maka kekongruenan tidak selalu dipenuhi.

Misalnya:

(i) 10 4 (mod 3) dapat dibagi dengan 2 karena 10/2 = 5 dan 4/2

= 2, dan 5 2 (mod 3)

(ii) 14 8 (mod 6) tidak dapat dibagi dengan 2, karena 14/2 = 7

dan 8/2 = 4, tetapi 7 / 4 (mod 6).

M. Balikan Modulo (modulo invers)

Jika a dan m relatif prima dan m > 1, maka kita dapat menemukan

balikan (invers) dari a modulo m. Balikan dari a modulo m adalah

bilangan bulat a sedemikian sehingga

a a 1 (mod m)

27

Bukti: Dari definisi relatif prima diketahui bahwa FPB(a, m) = 1, dan

menurut persamaan (2) terdapat bilangan bulat p dan q sedemikian

sehingga

pa + qm = 1

yang mengimplikasikan bahwa

pa + qm 1 (mod m)

Karena qm 0 (mod m), maka

pa 1 (mod m)

Kekongruenan yang terakhir ini berarti bahwa p adalah balikan dari a

modulo m.

Pembuktian di atas juga menceritakan bahwa untuk mencari balikan

dari a modulo m, kita harus membuat kombinasi lanjar dari a dan m

sama dengan 1. Koefisien a dari kombinasi lanjar tersebut merupakan

balikan dari a modulo m.

Contoh 1.

Tentukan balikan dari 4 (mod 9), 17 (mod 7), dan 18 (mod 10).

Penyelesaian:

(a) Karena FPB(4, 9) = 1, maka balikan dari 4 (mod 9) ada. Dari

algoritma Euclidean diperoleh bahwa

9 = 2 4 + 1

Susun persamaan di atas menjadi

–2 4 + 1 9 = 1

Dari persamaan terakhir ini kita peroleh –2 adalah balikan dari 4

modulo 9. Periksalah bahwa

–2 4 1 (mod 9) (9 habis membagi –2 4 – 1 = –9)

(b) Karena FPB(17, 7) = 1, maka balikan dari 17 (mod 7) ada. Dari

algoritma Euclidean diperoleh rangkaian pembagian berikut:

28

17 = 2 7 + 3 (i)

7 = 2 3 + 1 (ii)

3 = 3 1 + 0 (iii) (yang berarti: FPB(17, 7) = 1) )

Susun (ii) menjadi:

1 = 7 – 2 3 (iv)

Susun (i) menjadi

3 = 17 – 2 7 (v)

Sulihkan (v) ke dalam (iv):

1 = 7 – 2 (17 – 2 7) = 1 7 – 2 17 + 4 7 = 5 7 – 2 17

atau

–2 17 + 5 7 = 1

Dari persamaan terakhir ini kita peroleh –2 adalah balikan dari

17 modulo 7.

–2 17 1 (mod 7) (7 habis membagi –2 17 – 1 = –35)

(c) Karena FPB(18, 10) = 2 1, maka balikan dari 18 (mod 10)

tidak ada.

N. Kekongruenan Lanjar

Kekongruenan lanjar adalah kongruen yang berbentuk

ax b (mod m)

dengan m adalah bilangan bulat positif, a dan b sembarang bilangan

bulat, dan x adalah peubah bilangan bulat.

Nilai-nilai x dicari sebagai berikut:

ax = b + km

yang dapat disusun menjadi

29

a

kmbx

dengan k adalah sembarang bilangan bulat. Cobakan untuk k = 0, 1,

2, … dan k = –1, –2, … yang menghasilkan x sebagai bilangan bulat.

Contoh 1.

Tentukan solusi: 4x 3 (mod 9) dan 2x 3 (mod 4)

Penyelesaian:

(i) 4x 3 (mod 9)

4

93

kx

k = 0 x = (3 + 0 9)/4 = 3/4 (bukan solusi)

k = 1 x = (3 + 1 9)/4 = 3

k = 2 x = (3 + 2 9)/4 = 21/4 (bukan solusi)

k = 3, k = 4 tidak menghasilkan solusi

k = 5 x = (3 + 5 9)/4 = 12

…

k = –1 x = (3 – 1 9)/4 = –6/4 (bukan solusi)

k = –2 x = (3 – 2 9)/4 = –15/4 (bukan solusi)

k = –3 x = (3 – 3 9)/4 = –6

…

k = –6 x = (3 – 6 9)/4 = –15

…

Nilai-nilai x yang memenuhi: 3, 12, … dan –6, –15, …

(ii) 2x 3 (mod 4)

30

2

43

kx

Karena 4k genap dan 3 ganjil maka penjumlahannya menghasilkan

ganjil, sehingga hasil penjumlahan tersebut jika dibagi dengan 2 tidak

menghasilkan bilangan bulat. Dengan kata lain, tidak ada nilai-nilai x

yang memenuhi 2x 3 (mod 5).

O. Chinese Remainder Problem

Pada abad pertama, seorang matematikawan China yang bernama

Sun Tse mengajukan pertanyaan sebagai berikut:

Tentukan sebuah bilangan bulat yang bila dibagi dengan 5 menyisakan

3, bila dibagi 7 menyisakan 5, dan bila dibagi 11 menyisakan 7.

Pertanyaan Sun Tse dapat dirumuskan kedalam sistem kongruen lanjar:

x 3 (mod 5)

x 5 (mod 7)

x 7 (mod 11)

TEOREMA 5.6. (Chinese Remainder Theorem) Misalkan m1, m2,

…, mn adalah bilangan bulat positif sedemikian sehingga FPB(mi, mj)

= 1 untuk i j. Maka sistem kongruen lanjar

x ak (mod mk)

mempunyai sebuah solusi unik modulo m = m1 m2 … mn.

31

Contoh 1

Tentukan solusi dari pertanyaan Sun Tse di atas.

Penyelesaian:

Menurut persamaan (5.6), kongruen pertama, x 3 (mod 5),

memberikan x = 3 + 5k1 untuk beberapa nilai k. Sulihkan ini ke dalam

kongruen kedua menjadi 3 + 5k1 5 (mod 7), dari sini kita peroleh k1

6 (mod 7), atau k1 = 6 + 7k2 untuk beberapa nilai k2. Jadi kita

mendapatkan x = 3 + 5k1 = 3 + 5(6 + 7k2) = 33 + 35k2 yang mana

memenuhi dua kongruen pertama. Jika x memenuhi kongruen yang

ketiga, kita harus mempunyai 33 + 35k2 7 (mod 11), yang

mengakibatkan k2 9 (mod 11) atau k2 = 9 + 11k3. Sulihkan k2 ini ke

dalam kongruen yang ketiga menghasilkan x = 33 + 35(9 + 11k3)

348 + 385k3 (mod 11). Dengan demikian, x 348 (mod 385) yang

memenuhi ketiga konruen tersebut. Dengan kata lain, 348 adalah

solusi unik modulo 385. Catatlah bahwa 385 = 5 7 11.

Solusi unik ini mudah dibuktikan sebagai berikut. Solusi tersebut

modulo m = m1 m2 m3 = 5 7 11 = 5 77 = 11 35. Karena 77 3

1 (mod 5), 55 6 1 (mod 7), dan 35 6 1 (mod 11), solusi unik

dari sistem kongruen tersebut adalah

x 3 77 3 + 5 55 6 + 7 35 6 (mod 385)

3813 (mod 385) 348 (mod 385)

P. Bilangan Prima (Basit)

Defenisi:

Sebuah bilangan bulat P > 1 dinamakan bilangan Prima (P prima)

jika tidak ada bilangan d pembagi p, yang memenuhi 1<d<p.

32

Defenisi ini di tingkat SD disederhanakan menjadi

Bilangan Prima adalah bilangan yang hanya dapat dibagi 1 dan

dengan bilangan itu sendiri.

Bilangan yang bukan prima di sebut bilangan komposit.

Teorema:

Tiap bilangan bulat n > 1 dapat dinyatakan sebagai hasil kali

bilangan-bilangan prima

Contoh: 23 adalah bilangan prima karena ia hanya habis dibagi oleh 1

dan 23.

Karena bilangan prima harus lebih besar dari 1, maka barisan

bilangan prima dimulai dari 2, yaitu 2, 3, 5, 7, 11, 13, …. Seluruh

bilangan prima adalah bilangan ganjil, kecuali 2 yang merupakan

bilangan genap.

Bilangan selain prima disebut bilangan komposit (composite).

Misalnya 20 adalah bilangan komposit karena 20 dapat dibagi oleh 2,

4, 5, dan 10, selain 1 dan 20 sendiri.

Teorema (The Fundamental Theorem of Arithmetic). Setiap

bilangan bulat positif yang lebih besar atau sama dengan 2 dapat

dinyatakan sebagai perkalian satu atau lebih bilangan prima.

Contoh 1.

9 = 3 3 (2 buah faktor prima)

100 = 2 2 5 5 (4 buah faktor prima)

13 = 13 (atau 1 13) (1 buah faktor

prima)

33

Untuk menguji apakah n merupakan bilangan prima atau komposit,

kita cukup membagi n dengan sejumlah bilangan prima, mulai dari 2,

3, … , bilangan prima n. Jika n habis dibagi dengan salah satu dari

bilangan prima tersebut, maka n adalah bilangan komposit, tetapi jika

n tidak habis dibagi oleh semua bilangan prima tersebut, maka n

adalah bilangan prima.

Contoh 2.

Tunjukkan apakah (i) 171 dan (ii) 199 merupakan bilangan prima atau

komposit.

Penyelesaian:

(i) 171 = 13.077. Bilangan prima yang 171 adalah 2, 3, 5, 7, 11,

13. Karena 171 habis dibagi 3, maka 171 adalah bilangan

komposit.

(ii) 199 = 14.107. Bilangan prima yang 199 adalah 2, 3, 5, 7, 11,

13. Karena 199 tidak habis dibagi 2, 3, 5, 7, 11, dan 13, maka 199

adalah bilangan prima.

Q. Teorema Fermat

Terdapat metode lain yang dapat digunakan untuk menguji

keprimaan suatu bilangan bulat, yang terkenal dengan Teorema

Fermat. Fermat (dibaca “Fair-ma”) adalah seorang

matematikawan Perancis pada tahun 1640.

Teorema 4 (Teorema Fermat). Jika p adalah bilangan prima dan a

adalah bilangan bulat yang tidak habis dibagi dengan p, yaitu

FPB(a, p) = 1, maka

ap–1

1 (mod p)

34

Contoh 1.

Kita akan menguji apakah 17 dan 21 bilangan prima atau bukan. Di sini

kita mengambil nilai a = 2 karena FPB(17, 2) = 1 dan FPB(21, 2) = 1.

Untuk 17,

217–1

= 65536 1 (mod 17)

Karena 17 tidak membagi 65536 – 1 = 65535 (65535 17 = 3855).

Untuk 21,

221–1

=1048576 \ 1 (mod 21)

karena 21 tidak habis membagi 1048576 – 1 = 1048575.

Kelemahan Teorema Fermat: terdapat bilangan komposit n

sedemikian sehingga 2n–1

1 (mod n). Bilangan bulat seperti itu

disebut bilangan prima semu (pseudoprimes).

Misalnya komposit 341 (yaitu 341 = 11 31) adalah bilangan prima

semu karena menurut teorema Fermat,

2340

1 (mod 341)

Untunglah bilangan prima semu relatif jarang terdapat.

Contoh 2.

Periksalah bahwa (i) 316

1 (mod 17) dan (ii) 186 1 (mod 49).

Penyelesaian:

(i) Dengan mengetahui bahwa kongruen 33 10 (mod 17),

kuadratkan kongruen tersebut menghasilkan

36 100 –2 (mod 17)

Kuadratkan lagi untuk menghasilkan

312

4 (mod 17)

Dengan demikian, 316

312

33 3 4 10 3 120 1 (mod

17)

35

(ii) Caranya sama seperti penyelesaian (i) di atas:

182 324 30 (mod 49)

184 900 18 (mod 49)

186 18

4 18

2 18 30 540 1 (mod 49)

R. Fungsi Euler

Fungsi Euler medefinisikan (n) untuk n 1 yang menyatakan jumlah

bilangan bulat positif < n yang relatif prima dengan n.

Contoh 1

Tentukan (20).

Penyelesaian:

Bilangan bulat positif yang lebih kecil dari 20 adalah 1 sampai 19. Di

antara bilangan-bilangan tersebut, terdapat (20) = 8 buah yang relatif

prima dengan 20, yaitu 1, 3, 7, 9, 11, 13, 17, 19.

Untuk n = 1, 2, …, 10, fungsi Euler adalah

(1) = 0 (6) = 2

(2) = 1 (7) = 6

(3) = 2 (8) = 4

(4) = 2 (9) = 6

(5) = 4 (10) = 4

Jika n prima, maka setiap bilangan bulat yang lebih kecil dari n

relatif prima terhadap n. Dengan kata lain, (n) = n – 1 hanya

jika n prima.

Contoh 2.

(3) = 2, (5) = 4, (7) = 6, (11) = 10, (13) = 12, …

Teorema.

36

Jika n = pq adalah bilangan komposit dengan p dan q prima, maka

(n) = (p) (q) = (p – 1)(q – 1).

Contoh 3

Tentukan (21).

Penyelesaian:

Karena 21 = 7 3, (21) = (7) (3) = 6 2 = 12 buah bilangan bulat

yang relatif prima terhadap 21, yaitu 1, 2, 4, 5, 8, 10, 11, 13, 14, 17,

19, 20.

Teorema

Jika p bilangan prima dan k > 0, maka (pk) = p

k – p

k-1 = p

k-1(p – 1) .

Contoh 4

Tentukan (16).

Penyelesaian:

Karena (16) = (24) = 2

4 – 2

3 = 16 – 8 = 8, maka ada delapan buah

bilangan bulat yang relatif prima terhadap 16, yaitu 1, 3, 5, 7, 9, 11,

13.

Teorema 7 (Euler’s generalization of Fermat theorem). Jika FPB(a,

n) = 1, maka

a(n)

mod n = 1 (atau a(n)

1 (mod n) )

S. Latihan-latihan Soal

1. Buktikan 2 + 4 + 6 + . . . + 2n = n (1 + n)

2. Buktikan bahwa n2 ≤ 2

n , untuk setiap bilangan asli n ≥ 4

3. Gunakan Algoritma Euclid untuk menghasilkan bilangan bulat x dan

y yang memenuhi:

a. FPB(312,178) = 312x + 178y

37

b. FPB (866, 654) = 866x + 654y

4. Gunakan teorema (a,b) [a,b] = a . b untuk menentukan:

a. KPK [36,48],

b. KPK [227,143]

5. Gunakan teorema (a,b) [a,b] = a . b untuk menentukan:

a. KPK [32,48],

b. KPK [235,105]

6. Buktikan teorema

Untuk dua bilangan bulat positif sebarang a dan b, berlaku (a,b) [a,b]

= a . b

7. Hitunglah hasil pembagian modulo berikut:

a. 42 Modulo 8

b. -34 Modulo 11

8. Tunjukkan apakah bilangan berikut adalah bilangan prima atau

komposit:

a. 223

b. 377

9. Tunjukkan bahwa:

310

= 1 (modulo 11)

10. Fungsi Euler mendefinisikan (n) untuk n 1 yang menyatakan jumlah bilangan bulat positif < n yang relatif prima dengan n

Tentukan:

a. (45)

b. (52)

c. (77)

11. Tentukan sebuah bilangan bulat yang bila dibagi dengan 3

menyisakan 1, bila dibagi 5 menyisakan 2, dan bila dibagi 7

menyisakan 3

Yang dirumuskan ke dalam sistem kongruen linear:

x 1 (mod 3)

x 2 (mod 5)

x 3 (mod 7)

38

T. TUGAS TERSTRUKTUR 1

Mata Kuliah : Matematika Diskrit

Prodi/Sem. : Pendidikan Matematika/VI (Enam)

Dosen Penguji : Nego Linuhung, M. Pd

Dikumpulkan : Pada Pertemuan Ke-2

1. Perhatikan bahwa:

1 = 12

1 + 3 = 4 = 22

1 + 3 + 5 = 9 = 32

1 + 3 + 5 + 7 = 16 = 42

Dengan mengikuti pola yang tampak, carilah :

a. 1 + 3 + 5 + . . . + 99

b. 1 + 3 + 5 + . . . + 1001

c. 1 + 3 + 5 + . . . + 5555

TUGAS TERSTRUKTUR 2





1. Buktikan (a,b) [a,b] = a . b

2. Tentukan KPK dari 168 dan 230

3. Tentukan FPB dari 180 dan 290

TUGAS TERSTRUKTUR 3





1. Beberapa hasil operasi dengan operator modulo:

(i) 23 mod 5 = . . .

(ii) 27 mod 3 = . . .

(iii) 6 mod 8 = . . .

(iv) 0 mod 12 = . . .

(v) – 41 mod 9 = . . .

2. Tentukan sebuah bilangan bulat yang bila dibagi dengan 5 menyisakan 3,

bila dibagi 7 menyisakan 5, dan bila dibagi 11 menyisakan 7.

39

TUGAS TERSTRUKTUR 4





1. Tunjukkan apakah (i) 173 dan (ii) 201 merupakan bilangan prima

atau komposit

2. Tentukan (20).

3. Tentukan (35)

DAFTAR PUSTAKA

Nuryadi . (2015). Menentukan Kelipatan Persekutuan Terkecil (KPK) dan

Faktor Persekutuan Terbesar (FPB) dengan Metode Ebik. Tersedia.

Online. diakses 3 Januari 2015

Sukirman, Teori Bilangan, Yogyakarta : FMIPA UNY. Tersedia. Online.

diakses 3 April 2015

Rinaldi Munir. Teori Bilangan (Number Theory). Bahan Kuliah IF2091

Struktur Diskrit. Tersedia. Online. diakses 3 April 2015

R. Rosnawati. Jurusan Pendidikan Matematika. FMIPA UNY. Tersedia.

Online. diakses 3 April 2015

teori bilangan -...

Documents