Teori Bilangan

Yang dimaksud dengan teori bilangan dalam Matematika Diskrit adalah teori mengenai bilangan bulat dan sifat-sifatnya, dimana bilangan yang dimakudkan adalah bilangan integer/bilangan bulat. Bilangan bulat adalah bilangan yang tidak mempunyai pecahan desimal, sebagai contoh disebutkan 1, 4, 7, 2010, -88 merupakan sekumpulan bilangan bulat/integer. Sedangkan lawan dari bilangan bulat/integer adalah bilangan riil, yaitu bilangan yang memiliki titik desimal, sebagai contoh 9.0, 26.5, 0.25.
Pada bagian ini akan dijelaskan prinsip-prinsip teori bilangan, meliputi :

• Keterbagian (divisibility)
• Pembagi persekutuan terbesar (greatest common divisors/gcd)
• Kelipatan persekutuan terkecil (least common multiples/lcm), dan
• Aritmetika modular (modular arithmetics)

untuk lebih jelasnya, silahkan klik link dibawah ini saja
link ppt nya
link doc nya
Balikan Modulo (modulo invers)
Teorema 3. 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  sedemikian sehingga
a º 1 (mod m)
Contoh :
Tentukan balikan dari 17 (mod 7), dan 18 (mod 10).
Penyelesaian:

• Dari algoritma Euclidean diperoleh  rangkaian pembagian berikut:

17 = 2 × 7 + 3   (i)
7 =  2 × 3 + 1    (ii)
3 = 3 × 1 + 0     (iii)       (yang berarti: PBB(17, 7) = 1) )
Karena PBB(17, 7) = 1, maka balikan dari 17 (mod 7) ada.
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)

• Karena PBB(18, 10) = 2 ¹ 1, maka balikan dari 18 (mod 10) tidak ada.

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 4. (Chinese Remainder Theorem) Misalkan m₁, m₂, …, m_n adalah bilangan bulat positif sedemikian sehingga PBB(m_i, m_j) = 1 untuk i ¹ j. Maka sistem kongruen lanjar
x º a_k (mod m_k) à k = 1, 2, 3, …
mempunyai sebuah solusi unik modulo m = m₁ × m₂ × … × m_n.

Contoh :
Tentukan solusi  dari pertanyaan Sun Tse di atas.
x º 3 (mod 5)
x º 5 (mod 7)
x º 7 (mod 11)
Penyelesaian:
Menurut persamaan diatas, kongruen pertama,
x º 3 (mod 5), à x = 3 + 5k₁ untuk beberapa nilai k.
Sulihkan ini ke dalam kongruen kedua menjadi,
x º 5 (mod 7), à 3 + 5k₁ º 5 (mod 7)
à k₁ º 6 (mod 7)
à k₁ = 6 + 7k₂ , untuk beberapa nilai k₂.
Jadi kita mendapatkan
x = 3 + 5k₁
= 3 + 5(6 + 7k₂)
= 33 + 35k₂
yang mana memenuhi dua kongruen pertama. Jika x memenuhi kongruen yang ketiga, maka :
x º 7 (mod 11)            à 33 + 35k₂ º 7 (mod 11)
k₂ º 9 (mod 11)
k₂ = 9 + 11k₃.
Sulihkan k₂ ini ke dalam kongruen yang ketiga menghasilkan :
x = 33 + 35k₂
= 33 + 35(9 + 11k₃)
º 348 + 385k₃ (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.
m = m₁ × m₂ × m₃
= 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)
Bilangan Prima
Bilangan bulat positif p (p > 1) disebut bilangan prima jika pembaginya hanya 1 dan p. 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.
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 :
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)
Untuk menguji apakah n merupakan bilangan prima atau komposit, kita cukup membagi n dengan sejumlah bilangan prima, mulai dari 2, 3, … , bilangan prima £ Ön.

• Bilangan Komposit           à n habis dibagi dengan salah satu dari bilangan prima.
• Bilangan Prima                  à n tidak habis dibagi oleh semua bilangan prima.

Contoh :
Tunjukkan apakah 171 dan 199 merupakan bilangan prima atau komposit.
Penyelesaian:

• Ö171 = 13.077.

Bilangan prima yang £ Ö171 adalah 2, 3, 5, 7, 11, 13.
Karena 171 habis dibagi 3, maka 171 adalah bilangan komposit.

• Ö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.
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 5 (Teorema Fermat). Jika p adalah bilangan prima dan a adalah bilangan bulat  yang tidak habis dibagi dengan p,  yaitu PBB(a, p) = 1, maka
a^p–1 º 1 (mod p)
Contoh :
Kita akan menguji apakah 17 dan 21 bilangan prima atau bukan. Di sini kita mengambil nilai a = 2 karena PBB(17, 2) = 1 dan PBB(21, 2) = 1.
Untuk 17,
2^17–1 = 65536 º 1 (mod 17)     à Bilangan Prima
karena 17 habis membagi 65536 – 1 = 65535    (6553517 = 3855).
Untuk 21,
2^21–1 =1048576 º\ 1 (mod 21)             à Bilangan Komposit
karena 21 tidak habis membagi 1048576 – 1 = 1048575.

Pseudoprimes / Bilangan Prima Semu
Kelemahan Teorema Fermat: terdapat bilangan komposit n sedemikian sehingga
2^n–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,  2³⁴⁰ º 1 (mod 341)
Contoh :
Periksalah bahwa 3¹⁶ º 1 (mod 17) dan 18⁶ º 1 (mod 49).
Penyelesaian:

• Dengan mengetahui bahwa kongruen 3³ º 10 (mod 17), kuadratkan kongruen tersebut menghasilkan

3¹ º 3 º 3  (mod 17)
3³ º 27 º 10  (mod 17)
…
Kuadratkan lagi untuk menghasilkan
3¹² º 4 (mod 17)
Dengan demikian, 3¹⁶ º 3¹² × 3³ × 3 º 4 × 10 × 3 º 120 º 1 (mod 17)

• Caranya sama seperti penyelesaian (i) di atas:

18² º 324 º 30 (mod 49)
18⁴ º 900 º 18 (mod 49)
18⁶ º 18⁴ × 18² º 18 × 30 º 540 º 1 (mod 49)