5

4

3

2

1

pendidikan

Bunga Dara Sangadji

(201013500)

Desy Wulandari

(201013500704)

Neneng Fitriyanah

(201013500738)

Wijy Suryani

(201013500725)

Teori bilangan adalah cabang

dari matematika murni yang

mempelajari sifat-sifat bilangan

bulat dan mengandung berbagai

masalah terbuka yang dapat mudah

dimengerti sekalipun bukan oleh ahli

matematika.

Bukti dengan

Induksi

Keterbagian

Kongruensi Zn

Faktorisasi

TunggalAlogoritma

EuclidFungsi Bilangan

Teoritik

Aksioma untuk

Zn

Dalam teori

bilangan

itu, ada...

“Algoritma

pembagian”

“Keterbagian

elementer”

“Identitas

Aljabar”

Keterbagian

3.

Kongruensi Zn

“Kongruensi”

“Persamaan

Kongruensi”

“Uji

Keterbagian”

Apa saja

kongruensi

Zn

itu?

3.

Faktorisasi Tunggal

Bilangan Prima &

Faktorisasi

Teorema Fermat &

Teorema Euler

KPK & FPB

Algoritma Euclid

Sistem

Kongruensi

Linear

Beberapa aksioma dasar untuk Z:

1. Jika , maka (dikatakan

tertutup terhadap operasi penjumlahan,

pengurangan, dan perkalian)

2. Jika maka tidak ada sedemikian

sehingga

3. Jika dan maka atau

4. Hukum eksponen: Untuk dan

berlaku:

Aturan-aturan diatas berlaku untuk semua

jika

abbaba ,,ba,

ba,

a x

1axa

,,mn

1ba 1ba1ab

Rba,

nnn baab)(mnmn aaa

nmmn aa )(

5. Sifat ketaksamaan: Untuk berlaku:d

(a)Transitif: Jika dan maka

(b) Jika maka

(c) Jika dan maka

(d) Jika dan maka

(e)Taksonomi: Diberikan dan , hanya

berlaku salah satu dari:

6. Sifat terurut baik untuk : setiap himpunan

bagian tak kosong dari memuat suatu elemen

terkecil atau minimal. Suatu elemen

terkecildari suatu himpunan bagian adalah

suatu elemen dimana untuk setiap

Rcba ,,

ba cb ca

ba cbca

ba c0 bcac

ba 0c acbc

a b

,ba ,ca ab

S SS0Ss

7.Prinsip iduksi matematis: diambil

sebagai suatu pernyataan menyangkut

variabel bilangan asli Diambil adalah

suatu bilangan asli. adalah benar

untuk semua bilangan asli jika

kedua pernyataan ini berlaku:

(a) benar untuk

(b) Jika benar untuk maka

benar untuk

2. Bukti dengan Induksi

Jika maka

Disini digunakan prinsip induksi matematis

(a) Diambil adalah pernyataan . Untuk

diambil Secara sederhana dapat

dituliskan:

dan

(b)Sekarang jika maka menjadi

pernyataan yang adalah salah. Tetapi

jika adalah pernyataan atau

yang adalah benar. Jadi benar untuk

5n nn 52

nn 52 0n

nnP n 52:)( 50n

4n )(nP

5.5252532

)(nP

5n )(nP

.5n

3.1. Sifat Keterbagian Elementer n|n (sifat refleksif)

d|n dan n|m → d|m (sifat transitif)

d|n dan d|m → d|an + bm untuk setiap bilangan

bulat a dan b

(sifat linier)

d|n → ad|an untuk a ≠ 0 (sifat perkalian)

ad |an dan a ≠ 0 → d|n (sifat penghapusan)

1|n (1 membagi sembarang bilangan)

n|1 → n = ±1 (hanya 1 dan -1 yang merupakan

pembagi dari 1)

d|0 (sembarang nilai membagi 0)

0|n → n = 0 (nol hanya membagi nol)

d, n adalah positif dan d|n → d n (sifat

perbandingan)

d|n dan d|(n+m) → d|m

Pernyataan d|n dapat dibaca seperti berikut

ini :

d membagi n

d adalah pembagi dari n

d adalah suatu faktor dari n

n adalah kelipatan dari d

Contoh : 2|6, dibaca :

2 membagi 6

2 adalah pembagi dari 6

2 adalah suatu factor dari 6

6 adalah kelipatan dari 2

3.2. Algoritma PembagianTeorema 1 : Untuk sembarang bilangan

bulat a dan d, dimana d ≠ 0. Pasti ada

bilangan bulat q dan r yang memenuhi a =

qd+r dimana 0r < |d|

Secara Matematis : Untuk a,d € Z, dimana d ≠

0. Pasti ada q,r € Z yang memenuhi a = qd +

r dimana 0r < |d|

a disebut dividend (bilangan yang dibagi)

d disebut divisor (bilangan

pembagi/faktor)

q disebut quotient (hasil bagi)

r disebut remainder (sisa bagi)

Teorema 2 : dinyatakan habis

membagi jika dan hanya jika.

Sebaliknya, dinyatakan tidak habis

membagi jika dan hanya jika.

Secara Matematis:

sebaliknya

Contoh 1 :

„ 2 | 6 , dibaca 2 habis membagi 6

„ -9 | 36 , dibaca -9 habis membagi

36

„ 25| -100 , dibaca 25 habis membagi

-100

0| rad

0| rad

Teorema 3 : Untuk bilangan bulat dan .

Jika habis membagi dan habis

membagi , maka habis membagi

Secara matematis : Untuk Jika

dan maka

Teorema 4 : Untuk bilangan bulat

dan . Jika habis membagi dan habis

membagi , maka habis membagi

Secara matematis : Untuk jika

dan

ba, c

a b b c

cba ,, ba | cb |

ca |

a c

mba ,, n

c a c b

c nbma

nmba ,,, ac | bc |

)(| nbmac

Dalam algoritma

pembagian perhatikan bahwa sisa

bagi/remainder (r) BUKAN hal yang sama

dengan fungsi pada ilmu komputasi.

Memang ada hubungannya, tetapi kedua

hal ini adalah hal yang berbeda. Serupa

dengan algoritma pembagian, dikatakan

habis membagi jika dan hanya jika

Contoh 1 :

„ 6 = 3 . 2 + 0

„ 36 = -4 . -9 + 0

„ -100 = -4 . 25 + 0

Contoh 2 :

14 = 4 . 3 + 2

-53 = -7 . 8 + 3

37 = -4 . -9 + 1

rqda

),mod( da

d

a 0),mod( da

3.3. Identitas Aljabar

Pada bagian ini diberikan beberapa

contoh di mana penyelesaiannya

tergantung pada penggunaan beberapa

identitas aljabar elementer.Contoh :

Tentukan bilangan prima berbentuk n3 - 1,

untuk bilangan bulat n > 1!

Penyelesaian : n3 - 1 (n - 1) (n2 + n + 1) Jika

pernyataan tersebut merupakan bilangan

prima, karena (n2 + n + 1) > 1, pasti dipunyai n ‟

1 = 1, yang berarti n = 2. Jadi bilangan prima

yang dimaksud adalah 7.

4.1. Kongruensi

Misalnya 28 mod 5 = 3 dan 18 mod 5

= 3, maka kita katakan 28 18 (mod 5)

(baca: 28

kongruen dengan 18 dalam

modulo 5).

Misalkan a dan b adalah

bilangan bulat dan madalah 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).

Definisi : ditentukan p, q, m

adalah bilangan-bilangan bulat dan m

≠ 0. Pp disebut kongruen dengan q

modulo m, ditulis p ≡ q (mod m), jika

dan hanya jika m ∣ p ‟ q

Contoh :

„ 22 2 (mod 5) ( 5 habis membagi 22 ‟ 2 =

20)

„ ‟6 14 (mod 10) (10 habis membagi ‟6 ‟ 14 =

‟20)

Kekongruenan a b (mod m) dapat

pula dituliskan dalam

hubungan a = b + km dengan k adalah

bilangan bulat.

Contoh :

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

5 3

„ ‟7 15 (mod 11) dapat ditulis sebagai ‟7 = 15 +

(‟2)11

a) Sifat Kongruensi

m adalah bilangan bulat positif.

Kongruensi modulo m memenuhi sifat-sifat

berikut:

• Sifat refleksif

Jika p adalah suatu bilangan bulat, maka p ≡ p

(mod m)

• Sifat simetris

Jika p dan q adalah bilangan-bilangan bulat

sehingga p ≡ q (mod m), maka q ≡ p (mod m)

• Sifat transitif

Jika p, q dan r adalah bilangan-bilangan

bulat sehingga p ≡ q (mod m) dan q ≡ r (mod

b) Teorema

Misalkan m adalah bilangan bulat

positif.

Jika a b (mod m) dan c adalah sembarang

bilangan bulat maka:

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

2) ac bc (mod m)

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

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

2) ac bd (mod m)

4.4. Sisa Lengkap

Suatu himpunan x1; x2; :::; x dinamakan

sistem sisa lengkap (complete residue

system) modulo n jika untuk setiap bilangan

bulat y terdapat secara tepat satu indeks j

sedemikian sehingga y = xj (mod n).

contoh :

Diambil n = 3 sehingga dipunyai Z3 = f0; 1;

2g. Elemen 0 menyatakan semua semua

bilangan bulat yang dapat dibagi oleh 3,

sedangkan 1 dan 2 berturut-turut

menyatakan semua bilangan bulat yang

mempunyai sisa 1 dan 2 ketika dibagi oleh 3.

Dari dan , dinotasikan dengan Dicatat bahwa jika

dan maka

Sebagai contoh: (68,-8) = 2, (1998,1999) = 1.

Jika , maka dan dikatakan prima relative

(relatively prime) atau koprima (coprime).

Jika keduanya tidak nol, bilangan bulat positif

terkecil yang merupakan kelipatan dari dan dinamakan

kelipatan persekutuan terkecil.

Jika: dan maka

ba,a b

ca | cb | cba |],[

a b ),( ba ad |

bd | ),(| bad

1),( ba a b

( Teorema Bachet-Bezout)

faktor persekutuan terbesar ( FPB), yaitu terdapat bilangan

bulat dimana

Bukti: Dimisalkan . Berdasarkan

Algoritma pembagian, dapat dicari bilangan bulat dengan

sedemikian sehingga

Karena itu:

Jika , maka lebih kecil dari pada elemen terkecil

di

yx,byaxba ),(

},;0{ yxbyaxf

rq, dr0rdqa

byqxbyaxqdqr )1()(

Jika r

0r fr d f

( Lemma Euclid)

Jika dan maka

Bukti: Untuk berdasarkan Teorema Bachet-

Bezout, terdapat bilangan bulat dimana

(Teorema) : Jika maka

Bukti : Berdasarkan Teorema Bachet-Bezout, terdapat

bilangan bulat karena itu diperoleh

dimana adalah bilangan-bilangan bulat.

Disimpulkan bahwa

bca | 1),( ba ca |

1),( ba

yx, 1byax

dba ),( 1),(d

b

d

a

yx, 1)()( yd

bx

d

a

d

b

d

a,

1),(d

b

d

a

Teorema: Jika adalah suatu bilangan positif, maka:

Bukti : Diambil d1 dan d2 Akan di buktikan

bahwa d1 | cd2 dan cd2 | d1. Karena itu terdapat suatu

bilangan bulat sedemikian sehingga :

Lemma untuk bilangan-bilangan bulat tak nol a,b,c berlaku

Bukti : karena membagi dan membagi

sehingga disimpulkan :

c ),(),( baccbca

),( cbca ),( ba

)),(,(),( cbaabca

)),(,( cbaa cba ),( cba ),( bc)),(,(),( cbaabca

s byaxsd 2

yaitu suatu bilangan bulat positif lebih besar dari satu.

Contoh:

n adalah suatu bilangan bulat positif. Buktikan bahwa 32n+1

dapat dibagi oleh 2, tetapi tidak dapat dibagi oleh 4.

Bukti : jelas bahwa 32n adalah ganjil dan 32n+1 adalah genap.

Dicatat bahwa 32n = (32)2n-1 =92n-1 = (8+1)2n-1

mempunyai rumus binomial:

Bilangan PRIMA

Adalah cara memperoleh faktor persekutuan

terbesar (FPB) dengan menghindari pemfaktoran

dua bilangan bulat positif.

Dapat dinyatakan sebagai suatu kombinasi linier

dari dan Berdasarkan Teorema Bachet-Bezout,

disimpulkan bahwa adalah FPB dari dan . Jadi,

suku sisa tak nol berakhir yang dihasilkan oleh

algoritma Euclid adalah

Selanjutnya, FPB dari dua bilangan bulat boleh

dinyatakan sebagai suatu kombinasi linier dari

dua bilangan bulat tersebut dengan menggunakan

metode subsitusi balik.

Algoritma Euclid

a b

),( ba

(a) Diambil a = 84 dan b = 60, maka:

Penyelesaian:

84 = 1.60 + 24 24 = 84+(-1).60

60 = 2.24 + 12 12 = 60+(-2).24

24 = 1.12 12 =(84.60)

Selanjutnya dikerjakan secara mundur untuk

mendapatkan

12 = 60+(-2).24

12 = 60+(-2).(84+60.(-1)

12 = (-2).84+3.60

Jadi, (84.60) = 12 = (-2).84 + 3.60

(b) Duplikasi Algoritma euclid:

446 = 2.206 + 34 206 = 6.36 + 2 32 = 2.17

Karena (206,446) = 2 dan 2|40, maka terdapat

penyelesaian-penyelesaian bilangan bulat.

Selanjutnya disubstitusi balik untuk memperoleh

2 =206-6.34 = 206-6.(446-206) = 13.206-6.446

Sekarang karena 40 = 20.2, maka dapat

dituliskan:

40 = 20. (13.206-6.446) 260.260-120.446

Jadi penyelesaiannya adalah x = 260 dan y = -120

Diambil a=84 dan b=60 maka:

Penyelesaian:

84 = 1 . 60 + 24 24 = 84 + (-1) . 60

60 = 2 . 24 + 12 12 = 60 + (-2) . 24

24 = 1 . 12 12 = (84,60)

Selanjutnya dikerjakan secara mundur untuk mendapatkan

12 = 60 + (-2) . 24

12 = 60 + (-2) . (84 + 60 . (-1))

12 = (-2) . 84 + 3 . 60

Jadi, (84,60) = 12 = (-2) . 84 + 3 . 60

Suatu pernyataan yang meminta penyelesain-penyelesain

bilangan bulat dinamakan persamaan diophantine.

Berdasarkan Teorema Bachet-Bezout, diperhatikan bahwa

persamaa diophantine linier

Mempunyai suatu penyelesain bilangan bulat jika dan hanya

jika Algoritma euclid merupakan suatu cara yang efisien

untuk mencari suatu penyelesaian bagi persamaan tersebut.

Sebagai contohnya adalah:

Adalah

cbyax

cba |),(

272190 yx

29,11 yx

Suatu bilangan rill yaitu dimana terdapat diantara dua

bilangan bulat sehingga . Dimana adalah bilangan

bulat terbesar yang lebih kecil atau sama dengan

dinamakan adalah floor dari dinotasikan dengan .

Sedangkan adalah bilangan bulat terkecil yang lebih

besar atau sama dengan x, dinamakan n adalah ceiling dari xdinotasikan dengan .

Contoh soal:

dan

dan

x x1nxn n

x nn

TERIMA KASIH