number of theory

Nama : Andrian R. Lalang

NIM : 1301033072

Semester : III

Mata Kuliah : Teori Bilangan

BAB I

BILANGAN BULAT

1. Tunjukkan bahwa – (p+q )=(−p )+(−q) untuk semua p ,q ϵ z

Penyelesaian: – (p+q )=(−p )+(−q )

(−1 ) p+(−1 )q= (−p )+(−q )Berdasarkan hukum distributif perkalian terhadap penjumlahan kita dapati

– (p+q )=(−p )+(−q)

2. Tunjukkan bahwa – (p .q )=p .−q untuk semua p ,q ϵ z

Penyelesaian: p (−q )+ pq=0

→ p (−q+q )=0

→ −( pq )+( pq )=0

→ 0=0

Sesuai dengan sifat kanselasi, −(pq)=p (−q )

3. Diketahui p ,q , r ϵ z , p<q∧r<0Buktikan: p+r<q+r

Penyelesaian:p<q (kedua ruas ditambah r, untuk setiap r<0 )Maka p+r<q+r

4. Diketahui p ,q , r ϵ z , p>q∧q>rTunjukkan: p>r

Penyelesaian:Karena p>q danq>r

Maka p−q>0danq−r>0

Sehingga ( p−q )+(q−r )>0 dioperasikan sehingga mendapatkan p>r

5. Jika a ,b , c ϵ z maka buktikan bahwa ac<bc Penyelesaian

Misalkan bahwa a<b dan c>0, maka menurut definisi 1.4, b – a>0. Selanjutnya, karena

b – a>0dan c>0maka menurut sifat dasar ketertutupan perkalian urutan bilangan bulat positif, r (b−a)>0. Menurut sifat distributif, r (b−a)=rb−ra , dengan demikian

r (b−a)>0 berakibat rb−ra>0 sehingga r (b−a)>0, menurut definisi 1.4, ra<rb, dan menurut sifat komutatif perkalian, ar<br.Maka terbukti bahwa ac<bc

6. Buktikan bahwa tidak ada bilangan bulat positif kurang dari 1 Penyelesaian

Untuk membuktikan tidak ada bilangan bulat positif yang kurang dari 1, maka kita menggunakan metode kontradiksi.Pertama kita asumsikan bahwa ada bilangan bulat positif kurang dari 1. Selanjutnya akan dibuktikan bahwa pernyataan tersebut salah. Karena asumsi bahwa ada bilanhgan bulat kurang dari 1, maka 0 merupakan bilangan bulat positif. Namun, sesuai definisinya, bilangan bulat positif merupakan bilangan bulat yang lebih besar dari nol (a>0) sehingga asumsi sebelumnya salah dan dapat disimpulkan bahwa 1 merupakan bilangan bulat positif terkecil.

7. Buktikan bahwa √2 adalah suatu bilangan irasional Penyelesaian:

Untuk membuktikan bahwa √2 adalah bilangan irasional, maka kita menggunakan pembuktian melalui kontradiksi.

Kita asumsikan bahwa √2 adalah bilangan rasional, sehingga bisa

dinyatakan sebagai perbandingan bilangan bulat ab

dalam pecahan yang paling

sederhana. Tetapi jika ab=√2 maka a2=2b2. Ini berarti a2 adalah bilangan genap.

Karena kuadrat dari bilangan ganjil tidak mungkin genap, maka a adalah bilangan

genap. Karena ab

adalah pecahan paling sederhana, maka b pastilah ganjil sebab

pecahan genapgenap

masih bisa disederhanakan. Namun karena a adalah bilangan

genap (anggap 2 r=¿ a2=4 r2) adalah kelipatan 4, dan b2 adalah bilangan kelipatan 2.

Hal ini berarti b juga merupakan bilangan genap, dan ini merupakan kontradiksi terhadap kesimpulan sebelumnya bahwa b pastilah ganjil. Karena asumsi awal bahwa √2 adalah rasional mengakibatkan terjadinya kontradiksi, asumsi tersebut pastilah salah dan ingkarannya bahwa √2 adalah bilangan irasional merupakan pernyataan yang benar.

BAB II

INDUKSI MATEMATIKA

Untuk soal no 1 & 2 buktikan dengan induksi matematika

1.

∑k=1

n1

k (k+1)= 1

1.2+ 1

2.3+…+ 1

n (n+1)= nn+1

Penyelesaian:

S(n) : ∑k=1

n1

k (k+1)= nn+1

S(1) benar sebab untuk n = 1:

∑k=1

n1

k (k+1)=∑k=1

11

k (k+1)=1

2 dan

nn+1

= 11+1

=12

Misalkan S(k) benar , yaitu untuk n = k ;

∑k=1

k1

k (k+1)= 1

1.2+ 1

2.3+….+ 1

k (k+1)= kk+1

Harus dibuktikan bahwa S(k + 1) benar , yaitu:

∑k=1

k +11

k (k+1)= 1

1.2+ 1

2.3+….+ 1

k (k+1)+ 1k+1(k+2)

= k+1k+2

∑k=1

k +11

k (k+1)= 1

1.2+ 1

2.3+….+ 1

k (k+1)+ 1k+1(k+2)

= kk+1

+ 1(k+1 ) (k+2 )

kk+1

= k (k+2 )+1

(k+1 ) (k+2 )

= k2+2k+1

(k+1 ) (k+2 )

= (k+1 ) (k+1 )(k+1 ) (k+2 )

= k+1k+2

Jadi : S(n ) benar untuk sebarang n ϵ Z

2.

∑t=1

r

t 2=12+22+32+…+r2=r (r+1 )(2r+1)

6untuk setiapn ϵ Z+¿ ¿

Penyelesaian:

S(n) = ∑t=1

n

t 2=n (n+1 )(2n+1) /6

S (1) benar sebab untuk n = 1:

∑t=1

n

t 2=∑t=1

1

t 2=12=1dan 16n (n+1 ) (2n+1 )=1

6.1.2 .3

Misalkan S(k) benar, yaitu untuk n =k

∑t=1

k

t 2=12+22+32+…+k2=16k (k+1)(2k+1)

Harus dibuktikan S(k+1) benar , yaitu

∑t=1

k +1

t 2=12+22+32+…+k2+(k+1)2=16(k+1)(k+2)(2k+3)

∑t=1

k +1

t 2=12+22+32+…+k2+(k+1 )2=16k (k+1 ) (2k+1 )+(k+1)2

16

k (k+1)(2k+1)

= (k + 1) {16k (2k+1 )+(k+1)}

= 16

( k+1 ) {k (2k+1 )+6 (k+1 ) }

= 16k ( k+1 )+(2k 2+k+6k+6)

=16

( k+1 )(2k2+7k+6)

= 16

( k+1 ) ( k+2 )(2k+3)

Jadi : S(n) benar untuk sebarang nϵ Z+¿ ¿

3. Carilah

∑s=1

3

∏t=1

4

st

Penyelesaian:

∑s=1

3

s (1 .2.3 .4 )

¿∑s=1

3

24 s=24 .1+24 .2+24 .3

¿144

BAB III

KETERBAGIAN

1. Buktikan: jika a ,b , c z , a∨bdana∨c, makaa∨b+c Penyelesaian:

Gunakan definisi 3.1Karena a∨b, makab=xa untuk suatu x Z

Karena a∨c, makac= ya untuk suatuy Z

b=xa dan c= ya, maka b+c=xa+ ya=( x+ y)a

Jadi: a∨b+c

2. Nyatakan q dalam bentuk q=rp+s ,0 s< p, jika :

a. q=79 dan p=8q=203 dan p=13

q=−110 dan p=7

q=−156 danp=8

Penyelesaian: 79=9.8+7 203=15.13+8 −110=(−16).7+2

−156=(−20) .8+4

3. Buktikan ketunggalan dari r dan s pada teorema algoritma pembagian Penyelesaian:

Jika p ,qZ danp>0, maka ada bilangan-bilangan r , s Z yang masing-masing tunggal sehinggaq=rp+s dengan0≤s< p. Untuk membuktikan ketunggalan r dan s digunakan bukti tidak langsung.

Misalkan r dan s masing-masing tidak tunggal, yaitu ada r1 , r2 , s1 , s2Z sedemikian hingga:

q=r1 p+s1 , 0 s1< p

q=r2 p+s2 , 0 s2< p

dengan r1≠r2 dan s, s1≠ s2

Misalkan s1>s2, maka dari:

r1 p+s1=r2 p+s2

diperoleh:

s1−s2=p (r2 –r1)

berarti p∨s1−s2

Karena 0 s< p dan 0 s2< p, maka – p<s1−s2< p, sehingga:

1. Jika 0<s1−s2< p, maka p∨s1−s2. tidak mungkin 0<s1−s2< p Jika – p<s1−s2<0, maka 0<s2−s1< p, sehingga p∨s2−s1

Jadi: ¿ s1−s2 . Tidak mungkin – p<s1−s2<0

2. Jika s1−s2=0, makap∨s1−s2

Dari 1, 2, dan 3 dapat ditentukan bahwa tidak mungkin 0 < s1-s2 < p, dan tidak mungkin – p<s1−s2<0.

Jadi s1−s2=0, berarti s1=s2

s1=s2 dan s1−s2=p (r2−r1), maka p (r2−r 1)=0 Karena

p>0 dan p (r2−r 1)=0, maka r2−r1=0, atau r1=r2

4. Diketahui: t=(a4a5a3a2a1a0 ) dan 7∨tTunjukkan bahwa 7∨(a0+3a1+2a2)– (a3+3a4+2a5)

Penyelesaian:

t=(a5a4a3a2a1a0 ) ¿a5105+a4 104+a3103+a2102+a110+a0

t dapat dinyatakan sebagai:

t ¿a0+a110+a2 102+a3 103+a4104+a5105

¿a0+a1 (7+3 )+a2 (98+2 )+a3 (1001−1 )+a4 (10003−3 )+a5(100002−2)

t=(a0+3a1+2a2)– (a3+3a4+2a5)+7 (a1+14 a2+143a3+1429a4+14286a5)

Karena 7∨t dan 7∨7¿, maka sesuai teorema 3.9 , t∨(a0+3a1+2a2)– (a3+3a4+2a5)5. Buktikan:3∨n3−n untuk setiap n Z

Penyelesaian:Menurut teorema 3.10 (algoritma pembagian), setiap bilangan bulat n dapat dinyatakan sebagai n = 3p, n = 3p + 1, atau n = 3p + 2

- Untuk n = 3p, dapat ditentukan

n3−n=n (n2−1 )¿n (n+1 ) (n−1 ) ¿3 p (3 p+1 )(3 p−1)

Jadi, 3∨n3−n - Untuk n = 3p + 1, dapat ditentukan

n3−n=n (n2−1 ) ¿n (n+1 ) (n−1 )¿ (3 p+1 ) (3 p+1+1 ) (3 p+1−1 ) ¿3 p (3 p+1 )(3 p+2)

Jadi, 3∨n3−n- Untuk n = 3p + 2, dapat ditentukan

n3−n=n (n2−1 ) ¿n (n+1 ) (n−1 )

¿ (3 p+2 ) (3 p+2+1 ) (3 p+2−1 ) ¿ (3 p+1 ) (3 p+2 )(3 p+3)

Jadi, 3∨n3−nDengan demikian 3∨n3−n untuk setiap n Z

6. Nyatakan ¿dalam lambang bilangan basis 7 dan basis 5

Penyelesaian:

475=7.67+6 475=5.95+067=7.9+4 95=5.19+09=7.1+2 19=5.3+41=7.0+1 3=5.0+3¿ ¿

BAB IV

FPB DAN KPK

1. Nyatakan (2345)10 dalam notasi lambang bilangan

a. Basis 7

b. Basis 8

Penyelesaian:a. 2345=7.335+0

335=7.47+6

47=7.6+5

6=7.0+6

(2345)10=(6560)7

b. 2345=8.293+1293=8.36+5

36=8.4+4

4=8.0+4

(2345)10=(4451)8

2. Diketahui p ,qZ dan ( p ,q )=1

Carilah semua kemugkinan nilai d=¿)

Penyelesaian:

d=( p+q , p−q), maka d │ p+q dan d │ p−q, sehingga

d │(p+q) – (p−q) , atau d │2 p dan d │2q

Dengan demikian d adalah factor persekutuan dari 2p dan 2q, berarti

d │(2 p ,2q), atau d │2( p ,q).

Karena ( p ,q )=1 dan d │2( p ,q), maka d │2, berarti d=1atau d=2

3. Tunjukkan bahwa (3 t+2) dan (5 t+3) adalah relative prima, t {0 ,1 ,2 ,3 ,…}

Penyelesaian:

Untuk (3 t+2)

Subtitusikan masing-masing nilai t ke (3 t+2)

Jika t=0 maka(3 t+2 )=(3.0+2 )=2

Jika t=1 maka (3 t+2 )=(3.1+2 )=5

Jika t=2 maka (3 t+2 )=(3.2+2 )=8

Jika t=3maka (3 t+2 )=(3.3+2 )=11

Dan seterusnya

Untuk (5 t+3)

Jika t=0 maka(5 t+3 )=(5.0+3 )=3

Jika t=1 maka(5 t+3 )=(5.1+3 )=8

Jika t=2 maka (5 t+3 )=(5.2+3 )=13

Jika t=3maka (5 t+3 )=(5.5+3 )=18

Dan seterusnya

(3 t+2) dan (5 t+3) dikatakan relatif prima jika PBB (3 t+2), (5 t+3 )=1

2 dan 3 relatif prima karena PBB dari (2,3)=1




Sehingga terbukti bahwa (3 t+2) dan (5 t+3) adalah relative prima karena memiliki

pembagi persekutuan terbesar (PBB)=1

4. Carilah m dan n jika :

a. 67815m+21480n=(67815,21480)

b. 30745m+17446n=(30745,17446)

Penyelesaian:

a. 67815=3.21480+3375

21480=6 .3375+1230

3375=2.1230+915

1230=1.915+315

915=2 .315+285

315=1.285+30

285=9 .30+15

30=2.15+0, maka (67815,21480 )=15

r0=1

r1=0

- r2=r0−k 1r1

¿1−0

¿1

- r3=r1−k2 r2

¿0−6

¿−6

- r 4=r2−k3 r3

¿1−2 (−6 )

¿13

- r5=r3−k 4 r4

¿−6−13

¿−19

- r6=r4−k5 r5

¿13— (−19)2

¿51

- r7=r5−k 6r 6

¿−19−51

¿−70

- r8=r6−k7r 7

¿51−9 (−70 )

¿681

l0=0

l1=1

- l2=l0−k1l1

¿0−3

¿−3

- l3=l1−k2l2

¿1−6 (−3 )

¿19

- l4=l2−k3 l3

¿−3−2 (19 )

¿−¿41

- l5=l3−k4 l4

¿19−1 (−41 )

¿60

- l6=l4−k5 l5

¿−41−2 (60 )

¿−161

- l7=l5−k6 l6

¿60−1 (−161 )

¿221

- l8=l6−k7 l7

¿−161−9 (221 )

¿−2150

Jadi, (67815,21480 )=(681 ) 67815+(−2150 ) 21480

¿15, maka nilai m dan n adalah 681 dan -2150

b. 30475=1.17446+13299

17446=1.13299+4147

13299=3. 4147+858

4147=4 .858+715

858=1 .715+143

715=5 .143+0, maka (30745,17446 )=143

r0=1

r1=0

- r2=r0−k 1r1

¿1−0

¿1

- r3=r1−k2 r2

¿0−1

¿−1

- r 4=r2−k3 r3

¿1−(−3 )

¿4

- r5=r3−k 4 r4

¿−1−16

¿−17

- r6=r4−k5 r5

¿4— (−17)

¿21

l0=0

l1=1

- l2=l0−k1l1

¿0−1

¿−1

- l3=l1−k2l2

¿1−(−1)

¿2

- l4=l2−k3 l3

¿−1−6

¿−¿7

- l5=l3−k4 l4

¿2− (−28 )

¿30

- l6=l4−k5 l5

¿−7−30

¿−37

Jadi, (30745,17446 )=(21 )30745+ (−37 ) 17446

¿143, maka nilai m dan n adalah 21 dan -37

5. Buktikan : jika (x , y )=1 dan z (x+ y), maka (x , z )=( y , z )=1

Penyelesaian:

Misalkan d=(x , z ) , maka d │x dan d │z

d │z dan z│ x+ y, maka d │x+ y ; d │x+ y dan d │x, maka d │ y

d │x dan d │ y , maka d adalah factor persekutuan dari x dan y, sehinggad │(x , y ).

Karena d │(x , y ) dan (x , y )=1, maka d │1. Jadi (x , z )=1

6. Carilah (x2 ,108) jika diketahui (x ,18)=6

Penyelesaian:

(x ,18¿=6, maka ( x6 ,3)=1

Sehingga ( x2

36,3)=1,

Akibatnya 36( x2

36,3)=36

Dengan demikian (x2 ,108 )=36

BAB V

KONSEP DASAR KONGRUENSI

1. Diketahui p, q, m adalah bilangan-bilangan bulat dan m>0 sedemikian hingga p≡q (modm)

Buktikan : (p,m) = (q,m)

Penyelesaian p≡q (modm) , maka p –q=tmuntuk suatu bilangan bulat t.

Menurut definisi 2.3, ( p ,m)│ p dan ( p ,m)│m. Dari ( p ,m)│m, berdasarkan

teorema 2.1, ( p ,m)│tm. Selanjutnya, dari ( p ,m)│ p dan ( p ,m)│tm, berdasarkan

teorema 2.4, ( p ,m)│ p – tm. Karena p –q=tm, atau q=p – tm, maka ( p ,m)│q.

( p ,m)│m dan ( p ,m)│q, maka (p,m) merupakan faktor persekutuan m dan q, dan

sesuai teorema 2.17, ( p ,m)│(q ,m). Dengan jalan yang sama dapat ditunjukkan

bahwa (q ,m)│( p ,m) . Dari ( p ,m)│(q ,m) dan (q ,m)│( p ,m) ,( p ,m)>0, dan

(q ,m)>0, sesuai teorema 2.7, ( p ,m)=(q ,m).

2. Buktikan!

a. Jika p adalah suatu bilangan genap, maka p2≡0 (mod 4)

b. Jika p adalah suatu bilangan ganjil, maka p2≡1 (mod 4)

Penyelesaiana. Sesuai definisi 2.2, jika p merupakan suatu bilangan genap, maka p dapat

dinyatakan sebagai p=2t untuk suatu bilangan bulat t, dengan demikian

p2=4 t 2. Akibatnya, sesuai definisi 2.1, 4 │ p2 , atau 4 │ p2−0 , dan

berdasarkan definisi 3.1, p2≡0(mod 4) .

b. Sesuai definisi 2.2, jika p merupakan suatu bilangan ganjil, maka p dapat

dinyatakan sebagai p=2t+¿1 untuk suatu bilangan bulat t, dengan

demikian dapat dicari p2=4 t+4 t+1, atau p2=4 t (t+1 )+1 , atau

p2−1=4 t (t+1). Akibatnya, sesuai definisi 2.1, 4 │ p2−1, dan berdasarkan

definisi 3.1,p2≡1(mod 4).3. Buktikan jika p adalah suatu bilangan ganjil, maka p2≡1(mod 8)

Penyelesaian:

Sesuai definisi 2.2, jika p merupakan suatu bilangan ganjil, maka p dapat

dinyatakan sebagai p=2t+1 untuk suatu bilangan bulat t, dengan demikian

dapat dicari p2=4 t 2+4 t+1, atau p2=4 t (t+1)+1. Jika t adalah suatu bilangan

genap, sesuai definisi 2.2, t=2 r untuk suatu bilangan bulat r, sehingga

p2=8 r (2r+1)+1, ataup2−1=8 r (2 r+1). Akibatnya, sesuai definisi 2.1, 8│ p2−1

, dan berdasarkan pada definisi 3.1p2≡1(mod 8).

4. Carilah sisa positif terkecil dari 1 !+2 !+…+100!

a. Modulo 2

b. Modulo 12

Penyelesaian:

a. n !=1.2.3…n, berarti

2 !=1.2=2≡0(mod 2),

3 !=1.2.3=2.3≡0(mod 2) ,

n !=1.2.3…n=2.1 .3…n≡0(mod 2).

Dengan demikian dapat dicari bahwa

1 !+2 !+…+n! ≡1+0(mod 2)+0 (mod 2)+…+0(mod 2)≡0(mod 2)

b. n !=1.2.3 .4…n≡0(mod12) jika n4

akibatnya dapat ditentukan bahwa

1 !+2 !+…+100!≡1!+2!+3 !+0+0+…+0 (mod 12)≡9(mod 12)

5. Tunjukkan bahwa jika n adalah suatu bilangan genap positif, maka:

1+2+3+…+(n+1)≡0 (modn)

Bagaimana jika n adalah suatu bilangan ganjil positif ?

Penyelesaian:

1+2+…+(n+1)=(n−1)n

2.

Jika n adalah suatu bilangan ganjil, maka n –1 adalah suatu bilangan genap,

sehingga (n−1)

2 adalah suatu bilangan bulat, dengan demikian

n│1+2+…+(n+1)atau 1+2+…+(n+1)≡0(modn).

Jika n adalah suatu bilangan genap, maka n=2 r untuk suatu bilangan bulat r,

dengan demikian (n−1)

2=(n−1)r, berarti n tidak membagi (n – 1)rkarena

(n ,n−1)=1 dan r<n. Jadi 1+2+…+(n+1)tidak kongruen dengan 0 modulu n

jika n adalah suatu bilangan genap

6. Dengan menggunakan induksi matematika, tunjukkan bahwa 4n≡1+3n(mod 9)

Jika n adalah suatu bilangan bulat positif.

Penyelesaian:

- Misalkan n=1

4=4=1+3.≡1+3.1(mod 9)

Benar

- Kita asumsikan bahwa n=k adalah benar

4k≡1+3k (mod 9)

Anggaplah bahwa 4n≡1+3n(mod 9), harus dibuktikan

4n+1≡1+3 (n+1 ) (mod 9 )

4=4.4≡4 (1+3n ) (mod 9 )

≡4+12n (mod 9 )

≡4+3n (mod9)

number of theory

Education