Modul perkuliahan

Teorema 4.2

Jika (a,m) = 1 maka kongruensi linear ax b (mod m) mempunyai selesaian x = a ^(m)-1b, dimana (m) adalah banyaknya residu didalam sistem residu modulo m tereduksi.

Bukti.

Menurut teorem Euler jika (a,m) = 1 maka a ^(m)-1 = 1.

ax b (mod m)

a. a ^(m)-1 .x b a ^(m)-1 (mod m)

a ^(m) b a ^(m)-1 (mod m)

Karena a ^(m) 1 (mod m) dan a ^(m) x b a ^(m)-1 (mod m)

Maka 1.x b a ^(m)-1 (mod m)

x b a ^(m)-1 (mod m)

x a ^(m)-1 b (mod m)

Contoh

1. Selesaikan 5x 3 (mod 13)

Jawab

Karena (5,13) = 1

Maka kongruensi linear 5x 3 (mod 13) mempunyai selesaian

x 3.5 ^{(13) –1} (mod 13)

3.5 ^{12 –1} (mod 13)

3.(5² )⁵.5 (mod 13)

3.(-1)⁵ 5 (mod 13), karena 5² -1 (mod 13)

11 (mod 13)
4.2 Kongruensi Simultan

Sering kita dituntut secara simultan untuk menentukan selesaian yang memenuhi sejumlah kongruensi. Hal ini berarti dari beberapa kongruensi linear yang akan ditentukan selesaiannya dan memenuhi masing-masing kongruensi linear pembentuknya.

Contoh

1. 
   Diberikan dua kongruensi (kongruensi simultan)
   

x 3 (mod 8)

x 7 (mod 10)

Karena x 3 (mod 8), maka x = 3 + 8t (t Z).

Selanjutnya x = 3 + 8t disubstitusikan ke x 7 (mod 10), maka diperoleh

3 + 8t 7 (mod 10) dan didapat

8t 7-3 (mod 10)

8t 4 (mod 10)

Karena (8,10) = 2 dan 2 │4 atau 2 │7-3, maka kongruensi 8t 4 (mod 10) mempunyai dua selesaian bilangan bulat modulo 10 yaitu

8t 4 (mod 10)

4t 2 (mod 5)

t 3 (mod 5)

Jadi t 3 (mod 5) atau t 8 (mod 10)

Dari t 3 (mod 5) atau t = 3 + 5r (r Z) dan t 8 (mod 10) atau x = 3 + 8t

Selanjutnya dapat dicari nilai x sebagai berikut:

x = 3 + 8t

= 3 + 8(3+5r)

= 3 + 24 + 40r

= 27 + 40r atau x 27 (mod 40) atau x 27 (mod [8,10])

1. 
   Diberikan kongruensi simultan
   

x 15 (mod 51)

x 7 (mod 42)

Selesaian

Karena (51,42) = 3 dan 15 / 7 (mod 3) atau 3 ┼ 15 –7 , maka kongruensi simultan di atas tidak mempunyai selesaian.

1. Teorema 4.3

Kongruensi simultan

x a (mod m)

x b (mod n)

dapat diselesaikan jika

a b (mod (m,n)) dana memiliki selesaian tunggal

x x_o (mod [m,n])

Bukti

Diketahui

x a (mod m)

x b (mod n)

Kongruensi pertama x a (mod m) → x = a + mk, k Z.

Kongruensi kedua harus memenuhi a + mk b (mod n) atau mk b-a (mod n)

Menurut teorema sebelumnya mk b-a (mod n) dapat diselesaikan jika

d │b-a, d = (m,n) atau dengan kata lain kondisi kongruensi a b (mod (m,n)) harus dipenuhi.

d = (m,n) → d │ m dan d │m.

Jika d│ m dan d │m maka , , Z.

, , Z dan mk b-a (mod n) mengakibatkan

( mod )

Dari teorema sebelumnya jika d = (m,n) maka ( , ) = 1

Jika ( , ) = 1 dan ( mod ), maka

( mod ) mempunyai 1 selesaian.

Misalkan selesaian yang dimaksud adalah k = k_o sehingga selesaian kongruensi adalah

k k_o (mod ) atau k = k_o + r, r Z.

Karena x = a = mk dan k = k_o + r, maka

x = a + mk

= a + m (k_o + r)

= ( a + m k_o + r)

= ( a + m k_o ) + [m,n].r ; sebab [m,n](m,n) = m.n

= x_o + [m,n]r, sebab x_o = ( a + m k_o )

= x_o (mod [m,n])

4.3 Teorema Sisa China

Dalil 4.4

Jika m₁, m₂, m₃, ... , m_r Z+, dan (m_i,m_j) = 1 untuk i j,

maka kongruensi simultan :

x a₁ ( mod m₁)

x a₂ ( mod m₂)

x a₃ ( mod m₃)

.........................

.........................

x a_r ( mod m_r)

Mempunyai selesaian persekutuan yang tunggal :

x a_jb_j (mod [m₁,m₂,m₃,...,m_r]

Bukti

Misal m = m₁, m₂, m₃, ... , m_r

Karena ( j = 1,2,3, ... , r) adalah bilangan bulat yang tidak memuat m_j, serta (m_i,m_j) =1 untuk i j maka = 1.

Menurut dalil jika = 1, maka kongruensi linear 1 (mod m_j) mempunyai 1 selesaian. Karena masih memuat m_i, maka untuk i j

berlaku 0 (mod m_j).

Dengan memilih t = a_jb_j , maka

t = + + ... + + ... +

Dalam modulo m_i (i=1,2,3,..., r) t dapat dinyatakan dengan

t ( + + ... + + ... + ) (mod m_i)

t (mod m_i) + (mod m_i) + ... + (mod m_i) + ... + ) (mod m_i)

Karena 1 (mod m_j) dan untuk i j berlaku 0 (mod m_j) maka diperoleh:

0 (mod mi) untuk i = 1,2,3,..., r. sehingga

0 (mod mi) untuk i = 1,2,3,..., r.

Jadi t 0 (mod m_i) + 0 (mod m_i) + ...+ a_i (mod m_i) + ... + 0 (mod m_i)

t a_i (mod m_i).

Karena i = 1,2,3, ... , r maka

t a₁ (mod m₁)

t a₂ (mod m₂)

t a₃ (mod m₃)

......................

t a_r (mod m_r).

Hal ini berarti memenuhi semua kongruensi x a_i (mod m_i). Dengan kata lain t merupakan selesaian persekutuan dari semua kongruensi linear simultan tersebut.

Contoh

1. Tentukan selesaian kongruensi simultan linear berikut:

x 5 (mod 8)

x 3 (mod 7)

x 4 (mod 9)
Jawab

Diketahui a₁ = 5, a₂ = 3, a₃ = 4 dan m₁ = 8, m₂ = 7, m₃ = 9.

Sehingga m = 8.7.9 = 504

(m₁,m₂) = 1, (m₁,m₃) = 1, (m₂,m₃) = 1.

Jadi kongruensi linear simultan memenuhi syarat untuk diselesaikan dengan teorema sisa China

1 (mod m₁) b₁ 1 (mod 8)

67 b₁ 1 (mod 8)

b₁ 7

Dengan cara yang sama diperoleh b₂ = 4 dan b₃ = 5

Jadi x = a_jb_j

x = 63.7.5 + 72.4.3 + 56.5.4

= 4186

x 4186 (mod [8.7.9])

x 157 (mod 504)

2. Tentukan selesaian kongruensi

19x 1 (mod 140)

Jawab

Karena 140 = 4.5.7 , maka kongruensi dapat dipilah menjadi kongruensi simultan yaitu

19x 1 (mod 4)

19x 1 (mod 5)

19x 1 (mod 7)

Selanjutnya dapat disederhanakan menjadi

x 3 (mod 4)

x 4 (mod 5)

x 3 (mod 7)

Dengan cara seperti contoh 1 di atas diperoleh

x = 899

x 899 (mod 140)

x 59 (mod 140)

2. 4.4 Soal-soal

1. 
   Tentukan selesaian kongruensi linear di bawah ini
   
2. 
   3x 2 (mod 5)
   
3. 
   7x 4 (mod 25)
   
4. 
   12x 2 (mod 8)
   
5. 
   6x 9 (mod 15)
   
6. 
   36x 8 (mod 102)
   
7. 
   8x 12 (mod 20)
   
8. 
   144x 216 (mod 360)
   
9. 
   Tentukan selesaian kongruensi simultan berikut ini.
   
10. 
    12 x 3 (mod 15)
    

10 x 14 (mod 8)

1. 
   x 5 (mod 11)
   

x 3 (mod 23)

3. Selesaiakan kongruensi linear dengan metode my_o + b = ax

↔ x_o = :

1. 
   353x 19 ( mod 400)
   
2. 
   49x 5000 ( mod 999)
   
3. 
   589x 209 ( mod 817)
   

4. Selesaikan kongruensi linear simulat berikut dengan teorema sisa China.

a. x 1 (mod 3)

x 1 (mod 5)

x 1 (mod 7)

2. 
   x 2 (mod 3)
   

x 3 (mod 5)

x 5 (mod 2)

2. 
   x 1 (mod 4)
   

x 0 (mod 3)

x 5 (mod 7)

2. 
   x 1 (mod 3)
   

x 2 (mod 4)

x 3 (mod 5)

e. 23x 17 (mod 180)
BAB V

KEPRIMAAN
Definisi 5.1

Misal p adalah suatu bilangan bulat positip lebih dari 1 yang hanya mempunyai pembagi 1 dan p, maka p disebut bilangan prima. Jika suatu bilangan bulat q lebih dari 1 dan bukan bilangan prima maka q disebut bilangan komposit.

Contoh

1. 
   2, 3, dan 5 adalah bilangan prima karena:
   
2. 
   2 hanya mempunyai pembagi 1 dan 2
   
3. 
   3 hanya mempunyai pembagi 1 dan 3
   
4. 
   5 hanya mempunyai pembagi 1 dan 5
   
5. 
   4, 6, dan 15 adalah bilangan-bilangan komposit karena:
   
6. 
   Pembagi 4 adalah 1, 2, dan 4 (tidak hanya 1 dan 4)
   
7. 
   Pembagi 6 juga bukan hanya 1 dan 6
   
8. 
   Pembagi 15 juga bukan hanya 1 dan 15.
   
9. 
   Didalam sejarah matematika terdapat beberapa “rumus” untuk menentukan bilangan prima. Rumus-rumus tersebut menggambarkan adanya usaha para ilmuwan matematika untuk mencari bilangan prima.
   
10. 
    Erastosthenes, seorang ahli matematika Yunani telah membuat klasifikasi bilangan pada tahun 300 SM yang dikenal dengan istilah saringan Erastosthenes (the sieve Erastosthenes). Adapun proses menentukan bilangan prima 100 adalah sebagai berikut:
    
11. 
    Bilangan 1 dicoret
    
12. 
    Bilangan 2 diberi tanda dan semua kelipatannya dicoret
    
13. 
    Bilangan 3 diberi tanda dan semua kelipatannya dicoret
    
14. 
    Bilangan 5 diberi tanda dan semua kelipatannya dicoret
    
15. 
    Demikian seterusnya untuk kelipatan-kelipatan bilangan prima berikutnya sehingga diperoleh bilangan-bilangan 2, 3, 5, 7, 11, 13, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, dan 97
    

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

51 52 53 54 55 56 57 58 59 60

61 62 63 64 65 66 67 68 69 70

71 72 73 74 75 76 77 78 79 80

81 82 83 84 85 86 87 88 89 90

91 92 93 94 95 96 97 98 99 100

1. 
   Rumus yang lain pernah muncul untuk menentukan bilangan prima dan rumus tersebut dinyatakan dengan f(n) = n² – n + 41.
   

Dengan pengecekan secara tabel diperoleh bilangan prima sebagai berikut

Nf(n)nf(n)nf(n)NF(n)141111512146131971243121732250332103334713197235473310974531422324593341163561152522564135123167116281266913613017831731327743371373897183472879738144791131938329853391523101312142130911401601

Jika diteruskan untuk n = 41 diperoleh f(n) 1681. Ternyata 1681 habis dibagi 1, 41, dan 1681. Maka 1681 bukan bilangan prima. Sehingga rumus tersebut di atas gagal untuk menentukan bilangan prima karena tidak berlaku untuk setiap n.

1. 
   Terdapat rumus lain untuk menentukan bilangan prima yaitu
   

f(n) = n² – 79 + 1601.

Teryata rumus ini gagal untuk n = 81 karena

f(81) = 81² -79.81 + 1601

= 1763

= 41.43 (bukan prima)

1. 
   Rumus lain adalah
   

f(n) = 2 + 1

Rumus ini juga gagal untuk menentukan bilangan prima karena untuk

n = 5 diperoleh

f(5) = 4194967297 (habis dibagi 641)

Rumus ini dikenal dengan rumus Fermat

1. 
   Salah satu bilangan prima besar yang pernah diketahui adalah
   

2¹¹²¹³ – 1

Peristiwa ini ditemukan di University of Illinois pada tahun 1913. Karena menjadi kebanggaan pada waktu itu maka monumentalnya menjadi gambar dari salah satu perangko di Amerika Serikat.

2¹¹²¹³ - 1

Bilangan di atas mempunyai 3376 angka

1. 
   Pada tahun 1971, bilangan 2¹⁹⁹³⁷ – 1 diketahui sebagai bilangan prima yang terdiri dari 6002 angka.
   

Dalil 5.1

Jika p adalah bilangan prima dan p │ ab, maka p │a, atau p │ b

Bukti:

Anggaplah p ┼ a, karena p adalah suatu bilangan prima, maka p hanya mempunyai factor 1 dan p sehingga (a,p) = 1

Menurut dalil sebelumnya p │ ab dan (a,p) = 1 berakibat p │ b.

Dengan cara yang sama, jika dianggap p ┼ b maka dapat dibuktikan bahwa p │a.

Dalil 5.2

Jika p adalah bilangan prima dan p │a₁ a₂ a₃ … a_n, maka paling sedikit membagi

satu faktor a_i (1 i n ).

Bukti:

Karena p │a₁ a₂ a₃ … a_n, maka p │a₁ (a₂ a₃ … a_n,).

Menurut dalil sebelumnya maka p │a₁ atau p │a₂ a₃ … a_n,

Jika p │a₁ maka terbukti p paling sedikit membagi satu faktor a_i

Jika p ┼ a₁, maka p │a₁ (a₂ a₃ … a_n,) atau p │a₂ (a₃ … a_n,). Hal ini berarti

p │a₂ atau p │a₃ … a_n,. Demikian seterusnya diperoleh p │a_n-1 a_n

Sehingga p membagi paling sedikit membagi satu faktor a_i.

Dalil 5.3 (Teorema Dasar Aritmatika)

Jika n adalah sebarang bilangan bulat positip lebih dari 1, maka n dapat dinyatakan secara tunggal sebagai hasil kali faktor-faktor prima.

Bukti

Misal n Z⁺ dan n > 1, maka n adalah suatu bilangan prima atau n suatu bilangan komposit.

Jika n adalah prima, maka terbukti n mempunyai faktor prima n.

Jika n bilangan komposit, maka terdapat bilangan-bilangan bulat n₁, n₂ dengan (11,n₂1n₂.

Jika n₁ dan n₂ keduanya bilangan prima maka terbukti n mempunyai faktor prima.

Dalah hal yang lain ada bilangan bulat n₁, n₂, n₃ dengan (11,n₂,n₃1. n₂. n₃.

Demikian seterusnya sehingga diperoleh n = n₁. n₂. n₃. … .n_k dengan syarat

(11,n₂,n₃, … ,n_k

dan n₁, n₂, n₃, n₄, … ,n_k adalah bilangan prima.

Untuk menunjukkan ketunggalan faktor prima, dimisalkan pemafktorannya tidak prima (bukti negasi) yaitu:

n = p₁, p₂, p₃, p₄, … ,p_k dan

n = q,, q₂, q₃, q₄, … ,q_m dengan p_i dan q_i adalah bilangan prima.

p₁ │n berati p₁ │ q₁, q₂, q₃, q₄, … ,q_k

Karena p_i adalah bilangan prima, maka menurut dalil sebelumnya berlaku p₁ │ q_i

untuk beberapa i. Selanjutnya karena qi juga suatu bilangan prima yaitu bilangan yang faktornya 1 dan q_i, maka jelaslah bahwa p₁ = q_i.

n = p₁, p₂, p₃, p₄, … ,p_k dan n = q,, q₂, q₃, q₄, … ,q_m

hal ini berarti n = p₁, p₂, p₃, p₄, … ,p_k = q,, q₂, q₃, q₄, … ,q_m

Misal tempat qi di qi maka p₁ = q₁ sehingga diperoleh

p₂, p₃, p₄, … ,p_k = q₂, q₃, q₄, … ,q_m

Jika proses sama dilakukan maka diperolah

p₂ = q₂, p₃ = q₃, p₄ = q₄ dan seterusnya.

Jika k < m, diperolah

1 = q_k+1q_k+2 ... q_m.

Hal ini tidak mungkin terjadi, sebab tidak ada bilangan-bilangan prima yang hasil kalinya 1 sehingga terjadi hal yang bertentangan (kontradiksi).

Jika k > m juga deemikian. Berdasarkan hal tersebut haruslah k = m yaitu pemfaktorannya adalah tunggal.

Dalil 5.4

Terdapat tak hingga banyaknya bilangan prima

Bukti

Anggaplah banyaknya bilangan prima adalah hingga yaitu p₁, p₂, p₃, p₄, … ,p_k

selanjutnya p₁, p₂, p₃, p₄, … ,p_k+1

Maka ada dua kemungkinan nilai dari n

1. 
   Jika N adalah suatu bilangan komposit, maka menurut dalil sebelumnya N dapat dinyatakan sebagai hasil kali faktor-faktor prima. Faktor-faktor prima ini terdapat dalam p₁, p₂, p₃, p₄, … ,p_k. Misal pi adalah faktor prima dari N, maka
   

p_i │n atau p_i │ p₁, p₂, p₃, p₄, … ,p_k maka dan p_i │1. Hal ini terjadi kontradiksi.

Jadi banyaknya bilangan prima adalah tak hingga.

1. 
   Jika N adalah suatu bilangan prima, maka
   

N = pj (j = 1,2,3, ... ,k)

N │N berarti pj │ (p₁, p₂, p₃, p₄, … ,p_k ) + 1

pj │ p₁, p₂, p₃, p₄, … ,p_k dan pj │ (p₁, p₂, p₃, p₄, … ,p_k ) + 1

Maka pj │1. Hal ini terjadi kontradiksi.

Jadi banyaknya bilangan prima adalah tak hingga.

Selanjutnya dalil-dalil yang berkaitan dengan keprimaan dapat digunakan untuk menentukan faktor-faktor persekutuan terbesar dari dua bilangan dengan lebih sederhana.

Contoh.

1. Carilah (24,80)

Jawab

24 = 2 (12) = 2(2.6) = 2 (2.2.3)

= 2³.3

80 = 2 (40) = 2 (2.20) = 2 (2.2.10) = 2(2.2.2.5)

= 2⁴.10

Karena (24,80) tidak dapat memuat faktor 2 lebih dari 3, maka (24,80) = 2³ = 8

2. Carilah (2700,9000)

Jawab

2700 = 2³.3³.5²

9000 = 2³.3².5³

Karena (2700,9000) tidak dapat mempunyai faktor 2 lebih dari 2 kali, faktor 3

lebih dari dua kali, faktor 5 lebih dari dua kali maka

(2700,9000) = 2².3².5² = 900.

3. Carilah (54,72,84).

Jawab

Dengan cara yang sama diperoleh

(54,72) = 2.3² = 18

(72,84) = 2².3 = 12

Sehingga (54,72,84) = (18,12) = 6

Soal-soal

1. Carilah banyaknya bilangan-bilangan:

a. antara 50 dan 500 yang habis dibagi 3

b. antara 75 dan 750 yang habis dibagi 7

c. antara 100 dan 1000 yang habis dibagi 3 dan 5

d. antara 100 dan 2000 yang habis dibagi 3 dan 4

e. antara 100 dan 1000 yang habis dibagi 3,4, dan 5.

2. Tunjukkan bahwa

a. Perkalian tiga bilangan bulat yang berurutan habis dibagi 6.

b. Perkalian empat bilangan bulan berurutan habis dibagi 24.
3. Carilah

a. (60,75) b. (107,91) c. (18,78,144) d. (180,125)

e. (629,357) f. (44239,140299) g. (5321,544)

4. Carilah

a. [12,15] b. [9,21], c.[2,5,11] d. [3,4,6] e.[4,5,9]

5. Carilah (n,n+1) dan [n,n+1] untuk sebarang n bilangan bulat.

DAFTAR PUSTAKA

Dale Varberg., Edwin J. Purcell. 2001. Kalkulus (Edisi VII). Batam: Interaksara

David M.Burton. 1980. Elementary Number Theory (Revised Printing). London: Allyn and Bacon, Inc.
David S. Dummit. 1991. Abstrcat Algebra. New York: Prentice-Hall International, Inc.
Dwi Purnomo, 1997. Kumpulan Makalah Ilmu Bilangan (Tidak Dipublikasikan). Malang : PPS IKIP Malang.
____________, 1998. Pengantar Teori Bilangan. Malang : FPMIPA IKIP Budi Utomo Malang.
Evawati Alisah , 1997. Ciri-Ciri Habis Dibagi (Makalah Tidak Dipublikasikan). Malang: PPS IKIP Malang.
Gatot Muhsetyo, 1994. Dasar-dasar Teori Bilangan. Malang : IKIP Malang.
Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery. 1991. An Introduction to the Theory of Numbers. New York: John Wiley & Sons Inc.
M. Coesamin. 1997. Keprimaan (Makalah Tidak Dipublikasikan). Malang: PPS IKIP Malang.
Robert G. Bartle. 1992. Introduction to Real Analysis. New York: John Wiley & SonsInc.
Seymour Lipschutz. 1984. Teori Himpunan (terjemahan Pantur Silaban). Seri Buku Schaum Teori dan Soal-soal. Jakarta: Erlangga.
Usfandi Haryaka, 1997. Keterbagian (Makalah Tidak Dipublikasikan). Malang: PPS IKIP Malang.