TEORI BILANGAN

“Teorema Sisa/Chinese Remainder Theorem"

DOSEN PEMBIMBING

Dr. Ni Nyoman Parwati, M.Pd.

Oleh:

Kelompok 11

Ketut Lia Ruwiyani. NIM. 2013011010

PROGRAM STUDI PENDIDIKAN MATEMATIKA

JURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS PENDIDIKAN GANESHA

SINGARAJA

2021
 KATA PENGANTAR

Puji syukur kami panjatkan kehadirat Tuhan Yang Maha Esa, karena berkat
rahmat dan hidayah-Nya, kami dapat menyelesaikan makalah ini dengan baik
dan tepat waktu. Makalah yang kami buat diharapkan dapat menjadi panduan
dalam mempelajari Teori Bilangan. Dalam proses pembuatan makalah ini kami
juga sangat banyak berterima kasih kepada semua pihak yang telah membantu
dan membimbing kami dalam pembuatan makalah ini. Tak lupa juga kami
mengucapkan terimakasih kepada :
1. Ibu Dr. Ni Nyoman Parwati, M.Pd. selaku pengampu mata kuliah Teori
Bilangan di Undiksha Singaraja.
2. Teman yang telah membantu kami dalam menyelesaikan Makalah tentang
Menyelesaikan Teorema Sisa/Chinese Remainder Theorem
Dalam pembuatan Makalah mengenai Menyelesaikan Perkongruenan Linier
ini masih banyak terdapat kekurangan, sehingga kami mengharapkan saran dan
kritik yang bersifat membangun demi kesempurnaan Makalah ini. Semoga
Makalah ini dapat bermanfaat dan menambah pengetahuan pembaca.

Singaraja, 30 Mei 2021

Penulis,

ii
 DAFTAR ISI

HALAMAN JUDUL.................................................................................................i
KATA PENGANTAR............................................................................................ii
DAFTAR ISI..........................................................................................................iii
BAB I PENDAHULUAN.......................................................................................1
1.1 Latar Belakang....................................................................................................1
1.2 Rumusan Masalah..............................................................................................2
1.3 Tujuan Penulisan................................................................................................2
BAB II PEMBAHASAN........................................................................................3
2.1 Teorema dan Pembuktian Teorema Sisa............................................................3
2.2 Cara – Cara Menyelesaikan Perkongruenan Linier............................................3
BAB III PENUTUP................................................................................................6
3.1 Kesimpulan.........................................................................................................6
3.2 Saran...................................................................................................................6
DAFTAR PUSTAKA.............................................................................................7

iii
 BAB I PENDAHULUAN

1.1 Latar Belakang

Matematika sebagai salah satu cabang keilmuan yang digunakan sebagai alat
bantu dalam menyelesaikan persoalan manusia. Dalam hubungannya dengan
berbagai ilmu pengetahuan, matematika berfungsi sebagai bahasa ilmu dengan
lingkup universal, sebab dengan menggunakan matematika dapat dilakukan
abstraksi dari kenyataan-kenyataan yang sangat rumit menjadi suatu model
sehingga dicapai ketajaman dalam memberikan deskripsi, mempermudah untuk
mengadakan klasifikasi dan kalkulasi (Roziana, 2008:1). Oleh karena itu dengan
semakin berkembangnya teknik-teknik penganalisaan maka peranan peralatan
matematis dalam menganalisa semakin bertambah penting.
Matematika sebagai Queen of Sciences mempunyai dua fungsi penting dalam
perkembangan keilmuan. Pertama, matematika berfungsi sebagai ilmu aplikasi,
artinya konsep-konsep matematika dapat di aplikasikan secara riil dalam bidang
ilmu-ilmu yang lain. Sebagai contoh dalam bidang Ekonomi, persamaan linier
digunakan dalam menentukan tingkat penawaran dan permintaan (Dumairy,
1999:40). Selain itu penganalisaan ekonomi sering dibutuhkan peralatan-
peralatan yang bersifat model-model matematis untuk memudahkan melihat
permasalahan đan penganalisaannya.
Kedua, matematika sebagai ilmu itu sendiri, artinya adanya keterkaitan
konsep antara suatu materi pembahasan tentang sistem persamaan linier (SPL)
dengan kongruensi modulo yang akhirnya terbentuk sistem kongruensi linier
(SKL) dengan modulo. Dewasa ini semakin banyak muncul penggunaan model
matematika maupun penalaran matematika sebagai alat bantu dalam
menyelesaikan permasalahan yang dihadapi dalam berbagai disiplin ilmu. Teori
bilangan merupakan salah satu cabang matematika yang penting dan banyak
manfaatnya karena teori-teorinya dapat diterapkan dalam kehidupan sehari-hari.
Selain itu teori bilangan juga merupakan salah satu dari beberapa cabang
matematika klasik yang sudah lama dipelajari dan dikembangkan oleh banyak
matematikawan. Pada awalnya teori bilangan dipelajari dan dikembangkan
sebagai kesenangan dan pemenuhan rasa ingin tahu belaka, tetapi saat ini
beberapa cabang dari teori bilangan telah mendapatkan tempat sebagai alat dari
teknologi modern, misalnya dalam konstruksi kriptografi. Kongruensi
merupakan bahasa teori bilangan karena pembahasan teori bilangan bertumpu
kongnuensi. Bahasa kongruensi ini diperkenalkan dan dikembangkan oleh Karl
Friedrich Gauss, matematisi paling terkenal dalam sejarah pada awal abad
sembilan belas, sehingga sering disebut sebagai Pangeran Matematisi (The
Prince of Mathematicians). Berbicara tentang kongruensi berarti tidak terlepas

1
 dari masalah keterbagian. Karena membahas konsep keterbagian dan sifat-
sifatnya merupakan pengkajian secara lebih dalam dengan menggunakan konsep
kongruensi. Sehingga kongruensi merupakan cara lain untuk mengkaji
keterbagian dalam himpunan bilangan bulat. Sedangkan untuk sistem kongruensi
linier merupakan suatu sistem yang terdiri lebih dari satu kongruensi dan
variabel dan mempunyai modulo yang sama. Salah satu pokok bahasan dalam
teori bilangan adalah menyelesaikan perkongkurenan linier. Pada makalah ini
akan dijabarkan bagaimana cara cara penyelesaikan perkongruenan linier.

1.2 Rumusan Masalah

Dari latar belakang diatas didapaat rumusan masalah sebagai berikut :
1. Bagaimana cara menyelesaikan perkongruenan linier ?
2. Apa saja cara acara yang bia diterapkan untuk menyelesaikan
perkongruenan linier?

1.3 Tujuan Penulisan

Dari rumusan masalah diatas didapatkan tujuan penulisan makalah sebagai
berikut :
1. Untuk mengetahui penyelesaian perkongruenan linier
2. Untuk mengetahui cara menyelesaikan perkongruenan linier

2
 BAB II PEMBAHASAN

2.1 Teorema dan Pembuktian Teorema Sisa

TEOREMA SISA
Ambil bilangan dinyatakan sebagai bilangan bulat positif yang relative prima
sepasang-sepasang, dan ambil bilangan bulat Maka pekongruenan (mod ), i = 1,
2, 3,….,r mempunyai solusi simultan (serentak/bersama) modulu
Cara lain menyatakan teorema ini adalah:
Sistem perkogruenan x ≡ (mod ), dengan ( ) = 1, bila mempunyai solusi simultan
modulu tidak relative prim sepaang-sepasang m, maka tidak mempuyai solusi
kongruen modulu
Bukti:
Misalkan m = = bilangan bulat Maka ada bilangan bulat sehingga Jelas bahwa
Didefenisikan sebagai berikut
didapat
(mod )
Karena itu adalah solusi simultan dari system perkongruenan semula. Jika
keduanya solusi simultan dari x ≡ (mod ) dengan I = 1, 2, 3, ….,r maka
Jika (, maka system

….. …. …. …. …. …..,

Memiliki solusi tunggal modulo m dengan m

Bukti :

Andaikan untuk () = 1
Karena () = 1 untuk Karena () = 1 perkongruenan

. Memiliki solusi untuk setiap I, dengan kata lain untuk setiap I terdapat
sedemikian sehingga

Asumsikan = . Kemudian untuk setiap i karena dan . Jadi, merupakan solusi

dari system

Andaikan dua solusi dari system tersebut maka

Dan Untuk setiap i. Kemudian karena ( atau Karena itu, solusinya tunggal
modulu m

3
2.2 Cara – Cara Menyelesaikan Perkongruenan Linier
Cara – cara meyelesaikan perkongruenan ax ≡b (mod m) apabila a , b dan m
bilangan – bilangan besar dapat menggunakan beberapa metode sebagi berikut :

1. Dengan mereduksi ax ≡b ( mod m ) menjadi my ≡−b ( mod a )

a x ≡ b ( mod m ) direduksi menjadi my ≡−b (mod a) perkongruenan ini
mempunyai modulo yang lebih kecil. Dengan mengulang proses ini
perkongruenan ax ≡b (mod m) yang mmiliki a,b dan m bilangan besar dapat
diselesaikan.
Bila Y 0 adalah solui dari my ≡−b(mod a) maka m y 0 + b kelipatan a0 katakana
ax0. Sehingga ax0 = my0
my 0+b
x0 =
a
dan ini merupakan solusi dari ax ≡b (mod m)
Hal ini dapat dijelaskan sebagai berikut.
Bila ax ≡b (mod m) ini berarti ax – b adalah kelipatan m, misalkam my
dengan y bilangan bulat, sehingga ax – b=my atau my – b=ax. Karena x
bilangan bulat, maka my+ b adalah kelipatan dari a. jadi my+ b=ax berarti
my ≡−b ( mod a ) .

Contoh
Selesaikan 7 x ≡ 1432(mod 5317)
Penyelesaian
7 x ≡ 1432(mod 5317) direduksi
5317 y ≡−1432 ( mod 7 )
5317=k .7+ 4
−1432=h.7+ 3
Sehingga
5317 ≡−1432(mod 7) menjadi
4 y ≡ 3 ( mod 7 )
y 0 ≡6 ( mod 7 )
5317.6=1432
Jadi x 0 = =4762(mod 5317)
7

2. Dari ax ≡b (mod m) bila m/2<a< m, maka ax ≡b ( mod m ) direduksi menjadi

( a−m ) x ≡b ( mod ) m .

4
 ax ≡b (mod m) menurut definisi dapat dinyatakan sebagai ax=mk+b .
Kurangi kedua ruas dengan mx diperoleh(a−m)x=m( k−x)b
Karena k dan x bilangan bulat, maka k −x juga bilangan bulat. Jadi, bentuk
(a−m)x=m(k−x)+ b setara dengan (a – m) x ≡ b ( mod m ) .

Contoh
Selesaikan 26 x ≡ 17(mod 33)
Penyelesaian
26 x ≡ 17(mod 33)
−7 x ≡ 17(mod 33)
7 x ≡−17 (mod 33)
7 x ≡ 49( mod 33)
7 x ≡ 7.7(mod 33)

Menurut teorema 5.5 (2), jika ax ≡ay ( mod m) dan ( a , m )=1 maka x ≡ y (mod m),
jadi diperoleh x ≡ 7(mod 33)

a b m
3. ax ≡b (mod m) direduksi menjadi
(a , m)
x≡
(a , m) (
mod
(a , m) ) dengan
(a , m) ǀ b
Bentuk ax ≡b (mod m) dapat dinyatakan sebagai ax-b=mk, bagi kedua ruas
dengan (a,m), diperoleh

ax−b m
= k
(a , m) (a , m)
ax−b b m
− = k
(a , m) (a , m) (a , m)
Setara dengan
a b m
(a , m)
x≡
(
(a , m)
mod
(a , m) )
b
Persamaan terakhir sahih karena (a , m) ǀ b, jadi bilangan bulat.
(a , m)
Contoh
Selesaikan1700 x ≡300 ( mod 2300 )
Penyelesaian
1700 x ≡300 ( mod 2300 ) direduksi menjadi

5
 1700 300 2300
(1700,2300)
x≡
(1700,2300)
mod
((1700,2300) )
17 x ≡ 3 ( mod 23 )
−6 x ≡ 3 ( mod 23 )
6 x ≡−3 ( mod 23 )
x 0 ≡11 (mod 23)

Jadi x ≡ 11+k .23 untuk k =0,1,2,3 , … 99

4. Bila (a , m)=1, maka ax ≡b (mod m) menjadi ¿ dengan d=(a , b).

Nyatakan ax ≡b (mod m) sebagai ax ≡mk +b. Kemudian, bagi kedua ruas
dengan (a,b) = d, diperoleh

a m b a k b
x= k + ⟺ x= m+
d d d d d d

Yang sama dnegan

a b
= (mod m)
d d

Contoh
Selesaikan 1700 x ≡300 ( mod 253 )
Penyelesaian
1700 x ≡300 ( mod 253 )
17 x ≡ 3 ( mod 253 )
Karena m bilangan besar, dilanjutkan dengan cara (1) sehingga
17 x ≡ 3 ( mod 253 ) direduksi menjadi
253 y ≡−3 ( mod 17 )
−2 y ≡−3 ( mod 17 )
2 y ≡−3 ( mod 17 )
y0 ≡10 (mod 17)
253.10+3
x 0≡ =149(mod 253)
17
BAB III PENUTUP

3.1 Kesimpulan

6
 1. Menyelesaikan perkongruenan linier dengan a,b dan m bilangan besar dapat
memanfaatkan berbagai teorema mengenai perkongruenn linier.
2. Cara – cara meyelesaikan perkongruenan ax ≡b (mod m) apabila a , b dan m
bilangan – bilangan besar dapat menggunakan beberapa metode sebagi
berikut:
1. Dengan mereduksi ax ≡b ( mod m ) menjadi my ≡−b ( mod a )
2. Dari ax ≡b ( mod m ) bila m/2<a< m, maka ax ≡b ( mod m ) direduksi menjadi
( a−m ) x ≡b ( mod ) m .
a b m
3. ax ≡b (mod m) direduksi menjadi
(a , m)
x≡
(
(a , m)
mod
(a , m))dengan

(a , m) ǀ b
4. Bila (a , m)=1, maka ax ≡b (mod m) menjadi ¿ dengan d=(a , b).

3.2 Saran
Dengan dibuatnya makalah ini, diharapkan pembaca dapat lebih mudah dalam
memahami materi yang berkaitan dengan penyelesaian perkongruenan linier.
Dalam penulisan makalah, penulis tentunya masih menyadari jika makalah
masih terdapat banyak kesalahan dan jauh dari kesempurnaan. Penulis akan
memperbaiki makalah dengan berpedoman pada banyak sumber serta kritik yang
membangun dari para pembaca.

DAFTAR PUSTAKA

7
Parwati, Ni Nyoman. 2014. Teori Bilangan. Yogyakarta: Graha Ilmu.