ristia apriana (teori bilangan)

7/25/2019 Ristia Apriana (Teori Bilangan)

1/63

TEORI BILANGANRISTIA APRIANA

SEKOLAH TINGGI KEGURUAN DAN ILMUPENDIDIKAN

TAHUN AJARAN 2013/2014


2/63

INDUKSI MATEMATIK

Tujuan UmumMemahami metode pembuktian dengan induksi matematik dan terampil

menerapkannya.

Tujuan KhususDiharapkan mahasiswa dapat:1. Menuliskan algoritma pembuktian dengan induksi matematik.2. Menentukan basis untuk induksi dalam suatu pembuktian.3. Menentukan langkah induksi dalam pembuktian.4. Terampil menggunakan langkah-langkah pembuktian dengan induksi mat

1.1Pembuktian dengan Induksi Matematik Salah satu metode pembuktian yang absah dalam matematika adalah nduksMetode ini digunakan untuk memberikan teorema-teorema yang berlaku pada bSebagai !ontoh "ika ada bentuk kesamaan sebagai berikut:

#1$21

.....4321 +=+++++ nnn

%pakah penyataan tersebut selalau benar untuk setiap bilangan asli n&

'ara pembuktian kesamaan tersebut dapat dilakukan dengan memandang ruas kideret aritmatika sebagai berikut:

(ada ruas kiri : 1 ) 2 ) 3 ) 4) . . . ) nSuku pertama $a# : **.+eda $b# : . . . . .,umlah n suku pertama $Sn# [ ]bnan #1$22

1 +

[ ]#.....1$.....221 + nn

[ ]1221 + nn

[ ]121 +nn

$Sama dengan ruas kanan#

arena ruas kiri sama dengan ruas kanan/ maka kesamaan tersebut terbukti benaSelain !ara tersebut/ pembuktian dapat dilakukan dengan bukti 0ormal yaitu denmatematik.


3/63

angkah-langkah pembuktian dengan induksi matematik adalah:1. Memisalkan suatu kesamaan yang diketahui sebagai suatu pernyataan ata

p$n# yang akan dibuktikan kebenarannya untuk setiap bilangan n.2. emudian lan"utkan dengan:

angkah i: Tu"ukkan pernyataan tersebut benar untuk n 1 atau p$1# angkah ii: Dimisalkan bahwa p$n# benar/ tun"ukkan bahwa p$n)1# b

,ika langkah i dan ii benar/ dapat disimpulkan p$n# benar untuk setiap bilang

(ada pembuktian dengan induksi matematik/ langkah i disebut basis $dasar# insuksi dan langkah ii disebut langkah indukti0/ yaitu suatu bentuk implikasi " benar maka p$n)1# benar untuk setiap bilangan asli n .

Contoh 1:+uktikan dengan induksi matematik bahwa:

#1$21

.....4321 +=+++++ nnn

+erlaku untuk setiap bilangan asli n.

Bukti:

Dimisalkan p$n# : #1$21

.....4321 +=+++++ nnn

i. ntuk n 1/ p$n# adalah 1 #11$121 +

1 1 ** (benar)

ii. Dimisalkan p$n# benar. Selan"utnya tun"ukkan bahwa p$n)1#/ yaitu#2#$1$

21

#1$...321 ++=++++++ nnnn benar

5al ini ditun"ukkan sebagai berikut:

#......$#2#$1$21

#2$21

#1$

#121

#$1$

#1$#1$21

#1$#...4321$#1$...321

benar nn

nn

nn

nnn

nnnn

++=

++=

++=

+++=

+++++++=++++++


4/63

arena i dan ii benar/ maka terbukti p$n# benar.atau

#1$21

.....4321 +=+++++ nnn benar untuk setiap bilangan asli n.

Contoh :+uktikan dengan induksi matematik bahwa:

1#1$1

.....43

132

121

1+

=+

++

+

+ n

nnn

+erlaku untuk setiap bilangan asli n.

Bukti:

Dimisalkan p$n# : 1#1$1

.....43

132

121

1+

=+

++

+

+ n

nnn

i. ntuk n 1/ p$n# adalah11

1

21

1

+

=

21

21 = ** $benar#

ii. Dimisalkan p$n# benar. Selan"utnya akan ditun"ukkan bahwa p$n)1# b

21

#2#$1$

12

#2#$1$1#2$

#2#$1$1

1#2#$1$1

#1$1

.....43

132

121

1

2

++

=

++++

=

++++

=

+++

+=

+++

+++

+

+

nn

nn

nn

nnnn

nnnn

nnnn

ni menun"ukkan bahwa p$n)1# benar.arena i dan ii benar/ maka terbukti p$n# benar

atau

1#1$1

.....43

132

121

1+

=+

++

+

+ n

nnn benar untuk setiap bilangan asli n.

Contoh !:+uktikanlah dengan menggunakan induksi matematik bahwa:


5/63

1 ) 2 ) 4 ) . . . )2n-1 2n 6 1+erlaku untuk setiap bilangan asli n.

Bukti:

Contoh ":+uktikan untuk setiap bilangan asli n/ 7n 6 2n selalu terbagi habis oleh 8.

Bukti:Dimisalkan p$n# : 7n 6 2n selalu terbagi habis oleh 8.

i. ($1# adalah 71 6 21 terbagi habis oleh lima,adi p$1# benar.

ii. Dimisalkan p$n# benar. Selan"utnya tun"ukkan bahwa p $n)1# benar.

5al ini ditun"ukkan sebagai berikut:7n)1 6 2n)1 7n . 71 6 2n . 21

7n . 7 6 7 . 2n ) 7 . 2n 6 2n . 2

7 .$7n

6 2n

# ) 2n

$7 6 2# 7 .$7n 6 2n# ) 2n . 8Menurut asumsi/ $7n 6 2n# habis dibagi 8/ maka 7 .$7n 6 2n# "uga terbagi habis oleh 8/ dan n.8 "elas terbagi habis oleh 8.,adi 7n)1 6 2n)1 terbagi habis oleh 8 atau p$n)1# benar.

arena i dan ii benar/ maka terbukti p$n# benar atau 7n 6 2n selalu terbagi habis oleh 8/ untsetiap bilangan asli n.


6/63

Dari !ontoh di atas maka buktikanlah bahwa untuk setiap bilangan asli n berlaku11n 6 4n terbagi habis oleh 7

Bukti:

#atihan Soa$ 1%+uktikan dengan induksi matematika1. a. $am#n amn b. $ab#n an . bn !. 1n 12. 1 ) 2 ) 4 ) *..) 2n-1 2n 6 13. nn 2

121

.....91

41

21 =

4. 1 ) 3 ) 8 ) *.. ) $2n 6 1# n2

8. 2 ) 8 ) 9 ) *.. ) $3n 6 1# 2

#13$ +nn

. $2n . 2n 6 1# terbagi habis 3

1. Notasi SigmaSuatu !ara untuk menulis se!ara singkat dari bentuk pen"umlahan ialah denga

menggunakan notasi ; $sigma#.

Misalnya:= ++++=n

k

ni aaaaa1

321 .....

(ada ruas kiri di ba!a "umlah ai untuk i 1 sampai i n .+ilangan 1 sampai batas bawah/ dan n batas atas pen"umlahan.5impunan


7/63

=

+++++=n

k

ni1

...4321

'ontoh-!ontoh lain/ misalnya:1. 2222

1

2 ...321 nk n

k

++++==

2. =

++++=n

k

nk 1

#12$...831#12$

3. =

++++=n

i

ni1

2...:422

Si0at-si0at notasi sigma:1.

=

n

i

a1

diartikan a ) a ) a ) * ) n n . a

=

n

i

a1

n . a

2. ==

=n

j

n

ii aja

11

3. ==

=n

ii

n

ii baba

11

#$

4. ===+=+

n

i i

n

i i

n

i ii baba

111

#$$disebut "umlah monomial#

8. +

+==

= pn

pmii

n

mii paa

Contoh&'ontoh:1. >yatakan dengan notasi sigma dari ?1) ?2) ?3 ) ?4 )?8

,awab:Suku umumnya ?n batas bawah 1 dan batas atas 8,adi/ ?1 ) ?2 ) ?3 )?4 )?8

=

8

1ii x

2. >yatakan dengan notasi sigma dari 1 ) 3 ) 8 ) 7 ) @,awab :Di !ari bentuk umumnya:a1 1 2$1# 6 1a2 3 2$2# 6 1a3 8 2$3# 6 1a4 7 2$4# 6 1


8/63

a8 @ 2$8# 6 1suku umumnya an 2n 6 1/ batas bawah 1 dan batas atas 8.,adi/ 1 ) 3 ) 8 ) 7 ) @

=

8

1

#12$i

i

3. Tulislah= +8

1#23$

aa kedalam bentuk pen"umlahan biasa.

,awab:[ ] [ ] [ ] [ ] [ ]

.......

17141198

2#8$32#4$32#3$32#2$32#1$3#23$8

1

=

++++=

+++++++++=+=a

a

4. Tentukan hasil dari=

+n

a

a1

2 #1$

,awab:

=

+n

a

a1

2 #1$ 2 ) * ) * ) * ) * *..

Induksi Matematika da$am Notasi Sigma+entuk-bentuk kesamaan yang menggunakan notasi sigma/ dapat "uga dib

dengan induksi matematik/ seperti !ontoh-!ontoh berikut:1. +uktikan bahwa #3$

21

#23$ 21

nnk n

k

==

berlaku untuk setiap bilangan asli n.+ukti:(i) ($1# adalah #1.3$2

1#23$ 2

1

nk n

k

==

#13$21

213 =

1 1,adi p$1# benar

$ii# Dimisalkan p$n# benar untuk suatu bilangan asli n/ yaitu:#3$

21

#23$ 21

nnk n

k

==

Dan ditun"ukkan bahwa p$n ) 1# benar/ yaitu:[ ] #283$

21

#1$#1$321

#23$ 221

1

++=++=+

=

nnnnk n

k


9/63

5al ini ditun"ukkan sebagai berikut:

[ ]

#283$21

#2:3$21

#13$#3$2

1

2#1$3#23$#23$

2

2

21

1

1

1

++=

++=

+=++=

+

=

+

=

nn

nnn

nnnnk k

n

k

n

k

Dari $i# dan $ii# disimpulkan p$n# benar untuk setiap bilangan asli n.

'ontoh soal tersebut "uga dapat pula dibuktikan dengan menggunakan si0at-si0asebagai berikut:

#3$21

#433$21

2#1$21

3

23

23#23$

2

2

1

111

nn

nnn

nnn

nk

k k

n

k

n

k

n

k

n

k

=

+=

+=

=

=

=

===

#atihan Soa$ %


10/63

1. >yatakan "umlah berikut sebagai "umlah monominala.

=

n

iii ba

1

#83$

b. =

18

1

2 #83$k

k k

!. =

+n

k

k k 1

#12#$3$

d. =

n

k

k 1

2#32$

e. = =

+++1 1

2#1$#13$i

n

i

nn

2. Tulislah "umlah berikut ini dengan satu notasi sigmaa.

= =

+++n

k

n

k

k k 1 1

#23$#23$

b. = =

+n

k

n

k

k k k 1 1

22 #1$#4$

!. = =

++1A

8

7

2

22 #1$#2$n n

nnn

d. = =

++12

7

:

1

22 #3:12$a b

bba

e. = =

+++n

a

n

a

aa1 1

2 #32$#2$

3. Tulislah "umlah berikut ini dengan batas bawah bilangan 1.a. =

28

18k

k

b. =

+:

A

#3$n

n

!. =

12

1

23k

k

d. =

+4

2

2 #$n

nn

e. = +4

2

2

#1$i

i

4. +uktikana.

= = =

+=n

k

n

k

n

k

nk k k 1 1 1

22 44#12$


11/63

b. = = =

++=12

:

7

1

7

1

22 1781Ak k k

k k k

1.!. Teo(ema )inomia$

Tujuan Umum

Mahasiswa dapat memahami teorema +inomial dan si0at-si0at yang dituruteorema itu seerta trampil menggunakan si0at-si0at tersebut dalam mem!ahkan permasalahan yang terkait.

Tujuan Khusus

1. Menentukan koe0isien +inomial2. Menurunkan si0at-si0at koe0isien +inomial3. Menerapkan si0at-si0at koe0isien +inomial dalam meme!ahkan masalah y4. Terampil menggunakan si0at-si0at koe0isien +inomial dalam perhitungan

1. *akto(ia$

De+inisi dan notasi *akto(ia$

De+inisi 1.

nB 1.2.3.4. * $n 6 2# $n 6 1#.n

atau

nB n.$n 6 1#$n 6 2# * 3. 2.1

dan

AB 1

Dari de0inisi di atas maka:

3B 3.2.1

4B 4.3.2.1 *..


12/63

$n 6 1#B $n 6 1#$n 6 2#$n 6 3# * 3.2.1 maka nB n.$n 6 1#B atau#B1$B

nn

. Pe(mutasia. De+inisi dan Notasi Pe(mutasi(ermutasi dari sekumpulan unsure adalah penyusunan unsur-unsur itu dengmemperhatikan urutannya.Notasi Pe(mutasi+anyaknya permutasi dari n unsur diambil r dinyatakan dengan notasin( r atau nr P atau ($n/ r# atau (n/r

b. ,umus Pe(mutasi(ermutasi dari n unsur diambil r unsure adalah penyusunan r unsure yang dn unsure yang diketahui.

ota sedeiakan r kotak untuk menempatkan unsur-unsur tersebut

otak 1 2 3 4 ke 6 r

otak ke-1 dapat disi dengan n !ara/ kotak ke-2 dapat diisi dengan $n 6 1# !aunsur sudah menempati kotak ke-1. otak ke-3 dapat diisi dengan $n 6 2# !arseterusnya. ,ika proses ini dilan"utkan untuk kotak ke-r yang terakhir dapat diis$n 6 $r 6 1## !ara $n 6 r ) 1# !ara

ntuk r n/ maka n( n ***********************n( n ***********************n( n ***********************

ita tin"au lagi rumusn( r n$n 6 1#$n 6 2# * $n 6 r ) 1#,ika ruas kanan dikalikan dengan #B$

#B$r nr n

didapat:

n( r *******************************.n( r *******************************.n( r *******************************.

,adi n( r ******************.ntuk r n/ maka n( n ************.

(adahal n( n nB,adinB BA

B

#B$

B n

nn

n=

,adi:n( r n$n 6 1#$n 6 2# * $n 6 r ) 1#


13/63

Contoh Soa$:1. 5itunglah

a. 3( 3 ****************************** b. 9( 2 ******************************

2. Tentukan n "ikan( 2 12,awab:

!. Kombinasia. De+inisi dan Notasi Kombinasi

,ika ditentukan 3 buah huru0 a/ b/ ! maka permutasi dari 3 huru0 diamdua adalah ab/ ba/ b!/ !b/ a!/ dan !a. banyaknya permutasi ini adalah3( 2

:#B23$

B3 =

ombinasi dari permutasi sekumpulan unsur adalah penyusunan unsitu dengan tidak memperhatikan urutannya. Dari !ontoh di atas kombinasihuru0 a/ b/ ! dengan setiap pengambilan 2 adalah: ab/ b!/ a!.

+anyaknya kombinasi dari 3 unsur dengan setiap pengambilan 2 dindengan notasi3( 2 atau 32C atau '$3/ 2# atau '( )32 .

+erikut ini akan kita lihat apakah ada hubungan antara kombinasi dan permTampak disini untuk setiap kombinasi 2 udiperoleh 2B (ermutasi 2 permutasi. ,ik banyaknya kombinasi 3/ maka banyaknya permutasi adalah 3.2B

+anyaknya permutasi banyaknya kombkali 2B

3( 2 ' ( )32 .2B atau ' ( )32 3( 2C 2B

ombinasi (ermutasi

ab ab/ ba b! b!/ !b

a! a!/ !a' ( ) 332 = 3( 2


14/63

Dari !ontoh di atas dapat disimpulkan sebagai berikut1. ombinasi dari n unsur berbeda dengan setiap pengambilan r unsur $r n

susunan yang terdiri dari n unsur yang berbeda yang diambil dari n unsur tidak memperhatikan urutan-urutannya.

2. +anyaknya kombinasi dari n unsur dengan setiap pengambilan r unsur dindengan notasin' r atau ' $n/ r# atau ' ( )nr

b. ,umus Kombinasi+anyaknya kombinasi dari n unsure dengan setiap pengambilan r unsur

=

nr

nC

r n$B

B

belum lengkap

Bukti:,ika dari n unsur yang diketahui dibuat kombinasi dari r unsure/ maka ten' r kombinsi yang berbeda.Dari setiap kombinasi tersebut/ yang terdiri dari r unsur/ akan memberik permutasi.,adi/n( r n' r ErB ataun' r Br

P r n

arenan( r #B$Br n

n

/ maka ' ( )n

r #B$BB

r nr

n

,adi darin' r kombinasi akan diperolehn' r ErB permutasi yang berbeda. (adahal dunsur dengan sekali pengambilan r unsur diperolehn( r permutasi.

Contoh Soa$.

1. 5itunglah )@:C

***************************

2. Dengan beberapa !ara suatu panitia terdiri atas 3 orang dipilih dari @ oran,awab:


15/63

". )inomia$ Ne-ton

(erhatikan ekspensi $perluasan# dari $a ) b#n berikut

$a ) b#A 1

$a ) b#1 a ) b

$a ) b#2 a2 ) 2ab ) b2

$a ) b#3 a3 ) 3a2 b ) 3ab2 ) b3

$a ) b#4 a4 ) 4a3 b ) a2 b2 ) 4ab3 ) b4

$a ) b#8 a8 ) 8a4 b ) 1Aa3 b2 ) 1Aa2 b3 ) 8ab4 ) b8

*********************************.

oe0isien-koe0isien dari perluasan $a ) b#n di atas dapat disusun dalam suatu segitiga (a berikut:

1

1 1

1 2 1

1 3 3 1

1 * * * *1 * * * * 1

* * * * * * *


16/63

oe0isien +inomial

Segitiga (as!al mempunyai si0at-si0at sebagai berikut:

1. Tiap baris berawal dan berakhir dengan 1.

2. Tiap bilangan lainnya adalah "umlah kedua bilangan di kiri dan kanan ata3. oe0isien-koe0isien binomial tersebut dapat ditulis dengan menggunakankombinasi sebagai berikut.

( )AA

( )1A ( )11

( )2A ( )21 ( )22

( )3A ( )31 ( )...... ( )......( )...... ( )...... ( )...... ( )...... ( )......

Contoh Soa$:

1. Fkspansikan $a ) b#,awab:


17/63

2. 'arilah empat suku pertama dari perluasan $2? 6 y#9,awab:

3. Tentukan suku kelima dalam ekspansi( )1A2 y x ,awab:

4. Tentukan suku yang memuat y dari ekspansi $3?y2 6 G2#7,awab:


18/63

. Teo(ema&teo(emaTeo(ema 1.

,ika n suatu bilangan asli/ maka menurut rumus kombinasi berlaku( ) ( ) ( ) ( ) ( ) nnnnnnn 2...321A =++++++ahwa:Si0at-si0at dasar lainnya dari koe0isien +inomial diberikan berikut ini.

( )B#B$

Bk k n

nnn

= dan ( )n k n #B$B

Bk nk

n

Sehingga diperoleh

Teo(ema .( ) ( )n k nnk =

Teorema ini sering disebut si0at simetrik dari koe0isien +inomial.'ontoh 1:( )

B3B8B9

B3#B39$B99

3 == dan ( ) B8B3

B9B8#B89$

B998 =

=

,adi ( ) ( ) .....9893 ==

Teo(ema !.,ika n dan k bilangan-bilangan asli dan n H k/ maka( ) ( ) ( )111 += nk nk nk

Bukti:


19/63

Contoh:

( ) ( ) .....21@1A1A

21A9 =

== sedangkan

( ( ( ( ..................................@1@2@7@9 =+=+

,adi( ) ....................1A9 =

dan ( ) ......................................1A2 =

Teo(ema ".,ika n/ m/ k bilangan-bilangan asli dan n H k H m/ maka( )( ) ( )( )mn mk nmk mnk =

Bukti:

+uatlah !ontoh yang melibatkan bilangan untuk memper"elas Teorema 4.

Teo(ema .,ika n dan k bilangan-bilangan asli dengan n I k/ maka) )1= n k nnk nk

Bukti:


20/63

+uatlah !ontoh yang melibatkan bilangan untuk memper"elas Teorema 8.

Teo(ema /.( ) ( ) ( ) ( ) ( ) ( ) nnnk nk nnnn x x x x x ++++++=+ ......1 221A+erlaku untuk setiap bilangan asli n.

Bukti: (gunakan induksi matematik)

SISTEM )I#AN0AN )U#AT

%nggota-anggota dari


21/63

De+inisi !. Sistem bilangan bulat terdiri atas himpunan +


22/63

3 ? $8 ) 2# ************. ***.$-2# ? $8 ) $- ## **************** ***

&. Sifat distributif kanan perkalian terhadap penjumlahan$a ) b# ? ! $a ? b# ) $b ? !#Contoh:$$-9# ) 8# ? 3 ******************. ***..$7 ) $-2## ? $-4# ****************** ***

'. ntuk setiap a ada dengan tunggal elemen * dalam B sehingga a + * , * + a , a *disebut elemen identitas penjumlahan.

10. ntuk setiap a ada dengan tunggal elemen 1 dan B sehingga a x 1 , 1 x a , a. 1disebut elemen identitas perkalian .

Penjum$ahan )i$angan&)i$angan )u$at

Misalkan ! adalah bilangan bulat yang menyatakan $-a# ) $-b#/ yaitu:

! $-a# ) $-b#

! ) b $$-a# ) $-b## ) b

! ) b $-a# ) $$-b# ) b#! ) b $-a# ) A

$!) b# ) a $-a# ) a

$! ) b# ) a A

! ) $b ) a# A

! ) $a ) b# A

$! ) $a ) b## ) $-$a ) b## -$a ) b#

! ) $$a ) b# ) $-$a ) b### -$a ) b#

! ) A -$a ) b#


23/63

! -$a ) b#

karena ! $-a# ) $-b# maka $-a# ) $-b# -$a ) b#

"adi/ "ika a dan b bilangan-bilangan bulat positi0/ maka $-a# ) $-b# - $a ) b#

Menurut de0inisi urutan bilangan-bilangan !a!ah/ a K b berarti ada bilangan aslisedemikian hingga a ) ! b/ dan menurut de0inisi pengurangan bilangan-bilang! b sama artinya dengan b 6 a !. ,adi a ) $-b# a ) $-$a ) !##

a ) $$-a# ) $-!##

$a ) $-a## ) $-!#

A ) $-!#

$-!# karena ! b 6a/ maka

a ) $-b# - $b 6a#

,adi/ "ika a dan b bilangan-bilangan bulat positi0 dengan a K b/ maka a ) $-b#

Contoh 1:

,ika a dan b bilangan-bilangan !a!ah dengan b K a/ buktikan bahwa a ) $-b# a

Bukti:

Pengu(angan )i$angan )u$at

De+inisi ": ,ika a/ b dan k bilangan-bilangan bulat/ maka a 6 b k "ika dan hany b ) k.

-pakah pengurangan bilangan bulat memiliki sifat tertutup


24/63

Menurut de0inisi pengurangan a 6 b k "ika dan hanya "ika a b ) k

a ) $-b# $b ) k# ) $-b#

$k ) b# ) $-b#

k ) $b# ) $-b#

k ) A

a ) $-b# k

k a ) $-b# ini menun"ukkan bahwa ada bilangan bulat k sedemikian hingga a

Selan"utnya akan diperlihatkan bahwa bilangan bulat k $yang sama denga

itu tunggal. %ndaikan ada bilangan bulat n dengan n L k sedemikian hingga a arena a b ) k maka b ) n b ) k . "ika kedua ruas kesamaan terakhir masing-ditambah $-b# dan dengan si0at asosiati0 pen"umlahan dan inJers pen"umlahandiperoleh bahwa n k yang bertentangan dengan pengandaian. ,adi bilangan butertentu dengan tunggal sehingga a b ) k.

Dengan demikian terbuktilah bahwa pengurangan bilangan-bilangan bulatsi0at tertutup. ,adi a 6 b k a ) $-b#.

Contoh :

+uktikanlah bahwa a 6 $-b# a ) b

Bukti:


25/63

Contoh !:

+uktikanlah bahwa a 6 $b 6 !# $a ) !# 6 b

Bukti:

Contoh ":

+uktikanlah bahwa $a 6 b# 6 $-!# $a ) !# 6 b

Bukti:


26/63

Contoh :

+uktikanlah bahwa a 6 b $a 6 !# 6 $b 6 !#

Bukti:

Pe(ka$ian dan Pembagian )i$angan&bi$angan )u$at

Sebelum kita membi!arakan lebih lan"ut tentang si0at perkalian dan pemb bilangan bulat/ terlebih dahulu kita akan membuktikan suatu si0at yang telah disi0at ke-1A.

Si0at kanselasi dari pen"umlahan,ika a/ b dan ! bilangan-bilangan bulat dan a ) ! b ) !Maka a b

+ukti:a ) ! b ) !

$a ) !# ) $-!# $b ) !# ) $-!#a ) $! ) $-!## b ) $! ) $-!##

a ) A b ) A a b

Contoh /:Misalkan a dan b adalah bilangan-bilangan !a!ah/ sehingga a bilangan bulat pos bilangan bulat negati0. %kan diperlihatkan bahwa $a#$-b# -$ab#

angkah 1. a ? $b ) $-b## a ? A Aangkah 2. a ? $b ) $-b## $a ? b# ) $a ? $-b##angkah 3. $a ? b# ) $a ?$-b## A


27/63

angkah 4. $a ? b# ) $-$a ? b## Aangkah 8. $a ? b# ) $a ? $-b## $a ? b# ) $-$a ? b##angkah . a ?$-b# -$a ? b#

Mengingat bahwa perkalian bilangan-bilangan bulat bersi0at komutati0/ a? a dan a ? $-b# -$a ? b# maka $-b# ? a -$a ? b# -$b ? a#. begitu pula "ika$-b# -$A ? b# -A A dan $-b# ? A -$A ? b# -A A.

Contoh :+uktikan bahwa $-a# ? $-b# a ? b

Bukti:

Contoh 2:+uktikan bahwa $-a#$b ) $-!## a! 6 ab.

Bukti:

Pembagian )i$angan )u$atDe+inisi . ,ika a/ b dan ! bilangan-bilangan bulat dengan b L A/ maka a : b ! hanya "ika a b!.


28/63

5asil bagi bilangan-bilangan bulat $a : b# ada $yaitu suatu bilangan bulat#hanya "ika a kelipatan dari b. sehingga untuk setiap bilangan bulat a dan b/ hasitidak selalu ada $merupakan bilangan bulat#. leh karena itu pembagian bilang bulat tidak mempunyai si0at tertutup.

Membagi bahwa $-a#$b# $a#$-b# -$ab#/ maka:1. 6$ab# : a $-b#2. 6$ab# : b $-a#3. 6$ab# : $-a# b4. 6$ab# : $-b# a

Demikian pula karena $-a#$-b# ab/ maka8. ab : $-a# $-b#

. ab : $-b# $-a#

Mengingat de0inisi 8/ yaitu a : b ! "ika dan hanya "ika a b! yang sama ara b ? $a : b# atau a $a : b# ? b/ maka dari pernyataan-pernyataan 1 sampai diturunkan rumus-rumus de0inisi pembagian bilangan-bilangan bulat sebagai b

1. $$-a# : b# ? $b# $-a#2. $a : $-b## ? b $-a#3. $$-a# : b# ? $-b# a4. $a : $-b## ? $-b# a8. $$-a : $-b## ? b a

. $$-a# : $-b## ? $-b# $-a#

Contoh 3:+uktikanlah bahwa $p : $-N## : $-r# p : $N ? r#

Bukti:alimat yang akan dibuktikan yaitu/ p sebagai terbagi

$N ? r# sebagai pembagi


29/63

p

Contoh 14:+uktikanlah bahwa $a 6 b# : $-!# $b : !# 6 $a : !#

Bukti:alimat yang akan dibuktikan yaitu/ $a 6 b# sebagai terbagi$-!# sebagai pembagi


30/63

rutan bilangan-bilangan bulat ini akan tampak "elas pada garis bilangan brikut

-8 -4 -3 -2 -1 A 1 2 3 4 8

(ada garis bilangan a K b ditun"ukkan bahwa titik yang menyatakan a bersebelah kiri dari titik yang menyatakan b. misalkan $-4# K $-1#/ terlihat pada gitu bahwa titik yang menyatakan $-4# berada di sebelah kiri dari titik yang men

%pabila a/ b/ ! dan d bilangan-bilangan bulat/ maka1. a b maka a ) ! b ) !2. a b maka a ? ! b ? !3. a b dan a ! maka a ) ! b ) d4. a ) ! b ) ! maka a b8. a ? ! b ? ! dengan ! A maka a b

Si+at 1.,ika a/ b dan ! bilangan-bilangan bulat/ maka a K b "ika dan hanya "ika a )

Bukti:$i# dibuktikan "ika a K b maka a ) ! K b ) !

a K b berarti ada bilangan bulat positi0 k sedemikian hinggaa ) k b$a ) k# ) ! b ) !a ) $k ) !# b ) !a ) $! ) k# b ) !$a ) !# ) k b ) ! a ) ! K b ) !

$ii# dibuktikan "ika a ) ! K b ) ! maka a K ba ) ! K b ) ! berarti ada bilangan bulat positi0 p sedemikian hingga$a ) !# ) p b ) !a ) $! ) p# b ) !a ) $p ) !# b ) !$a ) p# ) ! b ) !


31/63

Si+at .,ika a dan b bilangan-bilangan bulat dan ! bilangan bulat positi0 serta a K b m

b ? !. Bukti:

Si+at !.,ika a dan b bilangan-bilangan bulat dan ! bilangan bulat positi0 serta a ? ! K

a K b Bukti:

Si+at ".,ika a dan b bilangan-bilangan bulat dan ! bilangan bulat negatiJe serta a K b.

H b ? !. Bukti:


32/63

Si+at .,ika a dan b bilangan-bilangan bulat dan ! bilnagan bulat negatiJe serta a ? ! H

maka a K b. Bukti:

#atihan Soa$%+uktikanlah pernyataan berikut dan dapat dilakukan dengan menun"ukkan !onto

1. ,ika a/ b dan ! bilangan-bilangan bulat dan a K b maka a ? ! K b ? !.2. ,ika a dan b bilangan-bilangan bulat/ ! bilangan bulat positi0 merupakan 0

bersama dari a dan b/ dan a H b maka a : ! H b : !.3. ,ika a/ b dan ! bilangan-bilangan bulat dengan a ? $-!# K b ? $-!# maka a 4. ,ika a/ b dan ! bilangan-bilangan bulat yang tak nol/ a dan b masing-masin

0aktor dari a dan a K b maka ! : a K ! : b.8. ,ika a dan b bilangan-bilangan bulat/ ! bilangan bulat negatiJe dan a H b m

6 $ b ? !# K A.. ,ika a/ b dan ! bilangan-bilangan bulat dan a K b maka $-a# ? ! K $-b# ? !

7. ,ika a/ b/ ! dan d bilangan-bilangan dengan bulat dengan a K b dan ! K d m b ? d.

9. ,ika a/ b/ ! dan d bilangan-bilangan bulat dengan a H b dan ! K d maka a )


33/63

KETE,)A0IAN

De+inisi 1: bilangan bulat a membagi habis bilangan bulat b/ $ditulis aQb# "ika d "ika ada bilangan bulat k sehingga b ak.

Contoh: 1Q14 karena 2k 12 sehingga k 7

-12 dapat dibagi oleh 4/ karena -12 4$-3#

3R1A karena tidak ada bilangan bulat k sehingga 3k 1A

stilah-istilah lain yang mempunyai arti sama dengan aQb adalah:

- a ialah 0aktor b- a ialah pembagi b- b ialah kelipatan a

Teo(ema 1 : "ika aQb dan bQ! maka aQ!.

Bukti:


34/63

Teo(ema : "ika aQb dan aQ! maka aQ$b ) !#

Bukti:

Teo(ema !: "ika aQb maka aQ!b untuk bilangan bulat ! sembarang

Bukti:

Teo(ema ": "ika aQb dan aQ! maka aQ$bm ) !m# untuk sembarang bilangan-bil bulat m dan n.

Bukti:

Teo(ema : "ika aQb dan bQa maka a b atau a -b Bukti:


35/63

Teo(ema /: "ika aQb dengan a dan bilangan-bilangan bulat posti0/ maka a K b.

Bukti:

aQb berarti ada bilangan bulat k sehingga b ak

karena a H A dan b H A maka k H A

"ika k 1 berarti a 6 b dan "ika k H 1 maka b H a

"adi a b.

#atihan Soa$%

1. ,ika aQb dan !Qd maka a!Qbd. +uktikanB2. Tun"ukkan bahwa "ika a H b maka a R b suatu pernyataan yang salah.3. +uktikan bahwa "ika dQa dan dQb maka dQ$a 6 b#


36/63

*AKT5, PE,SEKUTUAN TE,)ESA, 6*P)7

De+inisi 1: ,ika a/ b sebarang maka d dikatakan pembagi persekutuan dari a d "ika dQa

dan dQb.De+inisi : ,ika a atau b bilangan-bilangan bulat yang tidak nol/ d adalah 0a!tor persekutuan terbesar

dari a dan b ditulis $a/ b# "ika dan hanya "ika d 0aktor persekutuan dar! 0aktor persekutuan a dan b maka ! d.

Dari de0inisi 1 dan 2 dapat dinyatakan sebagai berikut:d $a/ b# "ika dan hanya "ika $i# dQa dan dQb

$menyatakan bahwa d adalah 0aktor persekutuan dari $ii# !Qa dan !Qb maka ! d $menyatakan bahwa d adalah 0a!tor persekutuan terbe

Contoh 1:(embagi positi0 dari -12 adalah 1/ 2/ 3/ 4/ / 12. (embagi positi0 dari 3A adal

/ 1A/ 18/ 3A. (embagi persekutuan dari -12 dan 3A adalah 1/ 2/ 3/ . (+ $-(+ $-8/ 8# 8/ (+ $9/ 17# 1/ (+ $-9/ -3 # 4.

Teorema 7: ,ika $a/ b# d maka $a:d/ b:d# 1+ukti:Misal: $a:d/ b:d# ! U ! 1Sehingga harus ditun"ukkan ! 1 dan ! I 1$i# ! I 1 karena ! adalah (+ maka sudah pasti ! I 1$ii# ! 1

$a:d/ b:d# ! maka !Q$a:d# !Q$b:d#!Q$a:d# berarti !k a:d

a $!k# d a $!d# k

!Q$b:d# berarti !k b:d


37/63

b $!k# d b $!d# k

karena $i# dan $ii# dapat disimpulkan bahwa $!d# adalah 0aktor perekrutan dari a damaka $!d# d. arena d bilangan bulat positi0 maka ! 1 TE,)UKTI

Contoh :(+ $3A/ 78# *..

3A 78 ,adi (+ $3A/ 78# adalah$3A:18/ 78:18# $2/ 8# 1

Teo(ema 2: untuk bilangan-bilangan bulat positi0 a dan b ada tepat satu pa bilangan-

bilangan bulat N dan r sehingga b Na ) r dengan A r K a.

Contoh !:a 21/ b 78 maka N 3/ r 12karena 78 321 ) 12terlihat bahwa $78/ 21# 3 dan $21/ 12# 3

Teo(ema 3: ,ika b Na ) r maka $b/ a# $a/ r# Bukti:

$b/ a# d U dQa dan dQb U dQ$b 6 Na# U dQr U d pembagi persekutuanr.! pembagi persekutuan dari a dan r U !Qa dan !Qr U !Q$Na ) r# U !Qa U ! pembagi persekutuan dari a dan b U ! d U $b/ a# $a/ r#

Contoh ":5itunglah $878 / 4483# **87 7 4483 E1 ) 13144483 1314 E 3 ) 8111314 811 E 2 ) 2@2811 2@2 E 1 ) 21@2@2 21@ E1 ) 7321@ ! E 3 ) A,adi (+ $87 7/ 4483# 73


38/63

Teo(ema 14: ,ika $a/ b# d maka bilangan bulat ? dan y sehingga a? ) by Contoh :Ditentukan a 247 dan b 2@@. Dengan algoritma pembagian berkali-kal

2@@ 247 E1 ) 82

247 82 E4 ) 3@ 82 3@ E 1 ) 13 3@ 13 E 3

Menurut teorema 1A maka ada bilangan-bilangan bulat ? dan y sedemikian h13 82 - 3@E1 82E4 ) 3@

82 E 8 6 247 $2@@ 6 247#8 6 247

13 2@@ E 8 6 247 E

,adi/ ? - dan y 8 agar 13 247? ) 2@@yTeo(ema 11: ,ika dQab dan $d/ a# 1 maka dQb Bukti:$d/ a# 1 maka ada ? dan y sehingga d? ) ay 1,ika kedua ruas dari persamaan ini dikalikan b/ maka b$d?# ) b$ay# bd$b?# ) $ab#y bkarena dQab U dQ$ab#y dank arena dQd$b?# U dQb TE,)UKTI

Teo(ema 1 : ,ika !Qa dan !Qb dengan $a/ b# d maka !Qd Bukti:$a/ b# d U d a? ) by

arena !Qa maka !Qa?/ karena !Qb U !Qby(ada persamaan d a? ) by/ !Qa? dan !Qby U !Qd TE,)UKTI

#atihan Soa$%1. 5itunglah

a. (+ $314/ 18@# b. (+ $1AA@/ 4AA1#2. +uktikan bahwa !Qab dan $!/ a# d maka !Qbd.


39/63

KE#IPATAN PE,SEKUTUAN TE,KECI# 6KPK7

De+inisi 1: +ilangan-bilangan bulat a1/ a2/ a3/ */ an masing-masing tidak nol memilikikelipatan

persekutuan b/ "ika aiQb untuk setiap 1/ 2/ 3/ */ n.

De+inisi : %pabila a1/ a2/ a3/ */ an adalah bilangan-bilangan bulat yang tidak nol/ mkelipatan

persekutuan terke!il $ ( # dari bilangan bulat positi0 terke!il di antkelipatan-

kelipatan persekutuan a1/ a2/ a3/ */an.

Teo(ema 1!: ,ika b suatu kelipatan persekutuan dari a1/ a2/ a3/ */ an maka Oa1/ a2/ a3/ */anPQb.

Bukti:Misalkan Oa1/ a2/ a3/ */ anP hMaka akan di tun"ukkan bawha hQb.%ndaikan hQb/ maka ada N dan r sehingga b hN ) r dengan A K r K h.

arena b suatu kelipatan persekutuan a1/ a2/ a3/ */ an maka aiQb untuk setiap 1/ 2/ 3/ *n.h Oa1/ a2/ a3/ */ anP maka aiQh untuk setiap i 1/ 2/ 3/ */ ndari b hN ) r dengan A K r K h/ karena aiQb dan aiQr/ yaitu r kelipatan persekutuan dari 1/a2/ a3/ */ hal ini bertentangan dengan r K h/ karena h kelipatan persekutuan terke pengandaian tersebut salah berarti hQb yaitu r kelipatan persekutuan dari a1/ a2/ a3/ */ an.hal ini bertentangan dengan r K h/ karena h kelipatan persekutan terke!il/ maka tersebut salah/ berarti hQb yaitu Oa1/ a2/ a3/ */ anPQb.

Teo(ema 1": ,ika m H A maka Oma/ mbP mOa/ bP Bukti:Misal: Oa/ bP d maka aQd dan bQd $semua dikalikan dengan m/ dimana m ,adi/ dapat dikatakan dm adalah kelipatan persekutuan dari am dan bm. Maka Odapat dikatkan kelipatannya m/ sehingga Oma/ mbP mOa/ bP

Contoh1:


40/63

O2E3/ 2E8P 2O3/ 8PO / 1AP 2O18P

Teo(ema 1 : ,ika a dan b bilangan- bilangan bulat positi0 maka Oa/ bP$a/b# ab

Bukti:$a/ b# 1 maka Oa/ bP abMisal: $a/ b# d U $a:d/ b:d# 1Maka di peroleh Oa:d/ b:dP $a:d/ b:d#

arena Oa:d/ b:dPE1 $a:d/ b:d#Oa:d/ b:dP$a:d/ b:d# $a:d/ b:d# $semua dikalikan dengan d2/ dimana d bilangan bulat#,adi/ Oa/ bP $a/ b# abContoh :$ / -1A# 2

elipatan persekutuan dan -1A */ - A/ -3A/ A/ 3A/ A/ *O / -1AP 3AO / -1AP$ / -1A# 3AE2 A

#atihan Soa$%1. 5itunglah O12 / 12AP2. +erikan satu !ontoh yang seperti teorema 18.


41/63

KEK5N0,UENAN

Tujuan umum:

Mahasiswa dapat memahami konsep kekongruenan dan si0at-si0at smenerapkannya untuk meme!ahkan masalah dalam mata kuliah ini dan dalamsehari-hari. Selain itu/ mahasiswa dapat memahami dan menyelesaikan pekongserta meme!ahkan soal-soal terapan yang berkaitan dengan pekongruenan.

Tujuan khusus

1. Menuliskan konsep kekongruenan2. Membuktikan beberapa si0at kekongruenan3. Menentukan banyaknya solusi pekongruenan linear 4. Menyelesaikan pekongruenan linear 8. Menyelesaikan persamaan linear Diophantus

. Menyelesaikan sistem pekongruenan linear

Mate(i

)i$angan )u$at Modu$o M

onsep keterbagian dan si0at-si0atnya pada himpunan bilangan bulat dlebih dalam lagi dengan menggunakan konsep kekongruenan. ekongruenan!ara lain untuk menelaah keterbagian pada himpunan bilangan bulat. Suatu keadalah suatu pernyataan tentang keterbagian.

Definisi 1

,ika m suatu bilangan bulat positi0 membagi a 6 b maka dikatakan a terhadap b modulo m dan ditulis a V b $mod m#.

Pemahaman definisi:%ndaikan diketahui a 13/ b 8. +erdasarkan de0inisi terebut dapat dinyataka ***********************************

***********************************


42/63

,ika m tidak membagi a 6 b maka dikatakan a tidak kongruen terhadap bdan ditulis a L b $mod m#.

Pemahaman definisi:

%ndaikan diketahui a 13/ b 3/ m 7. +erdasarkan de0inisi tersebut dapa bahwa: ************************************

************************************

,ika m H A dan mQ$a 6 b# maka ada suatu bilangan bulat k sehingga a 6 b V m

Dengan demikian aQb dapat dinyatakan sebagai a 6 b mk/ atau beda antmerupakan kelipatan m/ atau a b ) mk/ yaitu a sama dengan b ditambah kelipa

Pemahaman:

%ndaikan diketahui a 12/ b 2/ m 8/ berdasarkan pen"elasan di atas dapa bahwa:

************************************

Demikian "uga "ika diketahui a 2 dan b 12/ maka aQb atau 2Q12 dapasebagai 2 - 12Ek $untuk k -2#.

ita telah melihat bahwa "ika m H A dan a bilangan bulat maka a dapat dinyata

a mN ) r dengan A r K m. $%lgoritma pembagian#

ini berarti bahwa a 6 r mN/ yaitu a V r $mod m#. karena A r K m maka adauntuk r yaitu A/ 1/ 2/ . . ./ m 6 1.

,adi tiap bilangan bulat akan kongruen modulo m terhadap salah satu dari mkhususnya "ika mQa maka a V A $mod m#.


43/63

Definisi 2

(ada a V r $mod m#/ r disebut sebagai residu a modulo m.

Sedangkan himpunan bilangan bulat A/ 1/ 2/ 3/ . . ./ m 6 1/ yaitu


44/63

2. Tun"ukkan apakah


45/63

b. A/ 48 ,awab: ************************...

!. 2/ @@ ,awab: ************************...

d. -1/ 9 ,awab: ************************...e. -@/ 8 ,awab: ************************...

0. -1/ @@ ,awab: **********************...........3. ntuk bilangan bulat m positi0 yang manakah agar setiap pernyataan beri

benar&a. 27 V 8 $mod m# ,awab: m ********************...

b. 1AAA V 1 $mod m# ,awab: m ********************...

!. 1331 V A $mod m# ,awab: m *********************4. Tun"ukkan bahwa:

a. ,ika a adalah bilangan bulat genap/ maka a2 V A $mod 4#,awab:

b. ,ika b adalah bilangan bulat gan"il/ maka b2 V 1 $mod 4#,awab:

8. 'arilah residu nonnegati0 terke!il yang kongruen modulo 13 untuk bilanga berikut.a. 22 ,awab: r adalah ************************. b. 1AA ,awab: r adalah ************************.

!. 1AA1 ,awab: r adalah *************************

d. -1 ,awab: r adalah ************************.

e. -1AA ,awab: r adalah ************************..

0. -1AAA ,awab: r adalah ************************..


46/63

Teo(ema Kekong(uenan

ekongruenan modulo suatu bilangan bulat positi0 m sebetulnya menand bilangan bulat a dengan suatu bilangan bulat lain yaitu b. karena suatu pemadasuatu relasi/ bahkan ia suatu relasi ekiJalen/ seperti halnya relasi kesamaan. Sudisebut relasi ekiJalen atas suatu himpunan bilangan % "ika untuk a/ b dan ! un berlaku:

1. Si0at re0leksi0/ a a/ suatu bilangan a memiliki relasi terhadap bil sendiri.

2. Si0at simetris/ a b "ika dan hanya "ika b a. 3. Si0at transiti0/ a b dan b ! berakibat a !. 4. ekongruenan modulo suatu bilangan bulat positi0 m adalah suatu rela

pada himpunan bilangan bulat.Teo(ema 1

ntuk bilangan bulat sebarang a dan b/ a V b $mod m# "ika dan hanya "ika a dsisa yang sama "ika dibagi m.

+ukti:

(andang a V b $mod m#.

ni berarti a b ) km/ dengan k bilangan bulat.Menurut algoritma pembagian/ b Nm ) r dengan A r K m.Maka a b ) km $Nm ) r# ) km $N ) k# m ) r

ni berarti a seperti b/ memiliki sisa r/ "ika dibagi m.%ndaikan a N1m ) r dan b N2m ) r dengan r yang sama A r K m.Maka a 6 b $N1 6 N2#mXang berarti mQa 6 b. ini berarti a V b $mod m#

+uatlah !ontoh yang melibatkan bilangan untuk memper"elas teorema 1.


47/63

Teo(ema ekongruenan sebagai relasi ekiJalen.ntuk m bilangan bulat positi0 dan a/ b dan ! bilangan bulat berlaku:

1. a V a $mod m#

2. a V b $mod m# "ika dan hanya "ika b V a $mod m#3. "ika a V b $mod m# dan b V ! $mod m# maka a V ! $mod m#+ukti 6 bukti:1. +uktikan a V a $mod m#

+ukti:

2. +uktikan a V b $mod m# "uka dan hanya "ika b V a $mod m#+ukti:

3. +uktikan "ika a V b $mod m# dan b V ! $mod m# maka a V ! $mod m#+ukti:

ekongruenan modulo suatu bilangan bulat positi0/ dapat dikombinasikan denghampir sama seperti pada persamaan.

Teo(ema !

,ika a V b $mod m# dan ! V d $mod m# maka a ) ! V b ) d $mod m#


48/63

+ukti:


Teo(ema "

,ika a V b $mod m# dan ! V d $mod m# maka a? ) !y V b? ) dy $mod m#

+ukti:



49/63

Teo(ema

,ika a V b $mod m# dan ! V d $mod m# maka a! V bd $mod m#

+ukti:


Teo(ema /

,ika a V b $mod m# maka ka V kb $mod m# untuk k bilangan bulat sebarang.

+ukti:


50/63

+uatlah !ontoh yang melibatkan bilangan untuk memper"elas teorema .

#atihan :

1. residu terke!il modulo 9 dari 128 adalah**..2. periksalah apakah


51/63

Mate(i1. Kekongruenan mod 9

ekongruenan modulo @ dapat digunakan untuk memerikasa kebenaran per "umlah bilanganAbilangan bulat. ita mengetahui bahwa:

1A.AAA 6 1 @.@@@ @ k1 sehingga 1A.AAA V 1 $mod @#1.AAA 6 1 @@@ @ k2 sehingga 1AAA V 1 $mod @#1AA 6 1 @@ @ k3 sehingga 1AA V 1 $mod @#

Selan"utnya akan ditun"ukkan bahwa setiap bilangan bulat kongruen modulo "umlah angka-angkanya.

Contoh:9234 V $9AAA ) 2AA ) 3A ) 4# $mod @# V $9$1AAA# ) 2$1AA# ) 3$1A# ) 4# $mod @#

V9$1# ) 2$1# ) 3$1# ) 4 $mod @# V 17 $mod @#Selan"utnya dengan !ara yang sama17 V 1A ) 7 $mod @# V 1 ) 7 $mod @# V 9 $mod @#,adi 9.234 V 9 $mod @#

Teorema 11An V 1 $mod @# untuk n A/ 1/ 2/ 3/ . . . .

Bukti:1An 6 1 @@@*@ $n angka semuanya @# terbagi oleh @,adi 1An V 1 $mod @#

Teorema 2Setiap bilangan bulat kongruean modulo @ dengan "umlah angka-angkanya.

Bukti:

%mbil sembarang bilangan bulat n dan angka-angkanya se!ara berurutan an dk dk 6 1dk 6 2 . . . d2 d1 dA dann dk1Ak ) dk 6 11Ak- 1 ) dk 6 21Ak 6 2 ) . . . ) d21A2 ) d11A ) dAmenurut teorema 11An V 1 $mod @# untuk n A/ 1/ 2/ 3/ . . .Sehingga


52/63

n dk$1# ) dk 6 1$1# ) dk 6 2$1# ) . . . ) d2$1# ) d1$1# ) dA $mod @#,adi bilangan bulat n kongruen modulo @ dengan "umlah angka-angkanya.(erhatikan sekarang/ misalkan a ) b !

Maka tentukanlah a ) b V ! $mod @#

,ika a V m $mod @#/ b V n $mod @# dan ! V p $mod @#Maka dari a ) b V ! $mod @#Dapat disimpulkan bahwa m ) n V p $mod @#

(rinsip-prinsip dapat digunakan untuk memeriksa kebenaran suatu pen"umlahan pengurangan bilangan-bilangan bulat.

Menguji Penjum$ahanContoh:

(eriksalah kebenaran pen"umlahan berikut ini dengan prinsip di atas.249 ) 324 ) 72 1244,awab:

,adi/ 249 ) 324) 72 V

V

V . . . . . $i#

Sedangkan/ 1244 V


53/63

V

V

V V . . . . . $ii#

Dari kekongruenan $i# dan $ii# berarti 249 ) 324 ) 72 1.244 $benar#

#atihan Pemahaman:Masing-masing memuat pen"umlahan tiga bilangan dengan digit berbeda. aku penge!ekan dengan konsep modulo @.

Menguji Pe(ka$ian,ika a V b $mod @# dan ! V d $mod @# maka a! V bd $mod @#(rinsip ini dapat digunakan untuk memeriksa kebenaran suatu perkalian.

Contoh:+enarkah 94 ? 429 38.@8 &,awab:94 V429 VMaka 94 ? 429 V

V V . . . . . $i#

Sedangkan/ 38.@82 V 3 ) @ ) 8 ) 2 24 V $mod @# . . . . . $ii#

Dari $i# dan $ii# dapat disimpulkan bahwa 94 ? 429 38.@82 $+F>%W#.

#atihan Pemahaman:

Masing-masing memuat perkalian dua bilangan dengan digit berbeda $minimalakukan penge!ekan dengan konsep modulo @.

Contoh:+enarkah 1A ) 11 3A

ita mengetahui bahwa 1A ) 11 V 3 $mod @#3A V 3 $mod@#


54/63

Menurut !ara pemeriksaan di atas 1A ) 11 3A benar/ tetapi kita mengetahui ba 3A salah.

Selain itu kekongruenan modulo @ dapat digunakan untuk mengu"i keterbagian

bilangan bulat oleh @.Suatu bilangan terbagi oleh @ bila dan hanya bila sisa pembagian itu nol.n V a $mod @# bila dan hanya bila n dan a masing-masing mempunyai sisa yandibagi @.,adi/ "ika n V a $mod @# maka n terbagi oleh @/ bila dan hanya bila a terbagi on kongruen modulo @ dengan "umlah angka-angkanya.,adi suatu bilangan terbagi oleh @ bila dan hanya bila "umlah angka-angkanya @.

Contoh:1. 7. 897 V 7 ) 8 ) 9 ) 7 V @ $mod @#

arena @Q@ maka @Q78972. 47. 23 V 4 ) 7 ) ) 2 ) 3 V22 V 4 $mod@#

arena @ R 4 maka @R 47.723

#atihan Pemahaman:Masing-masing membuat !ontoh dua bilangan dengan 8 dan digit yang dapat

tidak dapat dibagi @. -pakah bilangan yang terbagi !leh ' akan tebagi juga !leh

Misalkan @Qn dan 3Q@ dengan si0at transiti0 diperoleh 3Qn. karena n t bila dan hanya bila angka-angkanta terbagi oleh @/ maka n terbagi oleh 3hanya bila "umlah angkanya terbagi oleh 3.

Contoh:1. 12.48 V 1 ) 2 ) 4 ) 8 ) V 19 V @ $mod @#

arena 3Q@ maka 3Q12.482. 42. 41 V 4 ) 2 ) ) 4 ) 1 V 17 V 9 $mod @#arena 3 R 9 maka 3 R 42. 41

2. Bilangan terbagi 2, 4 atau 8 Bagaimana menguji bilangan terbagi !leh 2 " atau &


55/63

+ilangan terbagi oleh 2/ bila bilangan itu genap.'oba buktikan pernyataan itu dengan menggunakan kekongruenan mod 2.

Bukti:%mbil n/ bilangan yang dinyatakan oleh n ak ak 6 1 . . . a1 aA dengan A ai K @ untuk 1/

3*n ak ak 6 1 . . . a1 aA ak1Ak ) ak 6 1 1Ak 6 1 ) . . . ) a2 1A2 ) a 1A ) aAterlihat bahwa suku-suku ruas kanan pada persamaan ini terbagi oleh 2 ke!ulai aA.%pabila n terbagi oleh 2/ maka aA pun terbagi oleh 2.aAadalah angka terakhir dari bilangan n. "adi suatu bilangan terbagi oleh 2 bila dan hanya bila angka terakhirnya terbagi

-pakah 1* 2 1* 1*" masing/masing terbagi !leh "+agaimana mengu"i suatu bilangan terbagi oleh 4.

Misalkan n ak ak -1. . . a2 a1 aA ataun ak 1Ak ) ak 6 1 1Ak 6 1 ) . . . ) a2 1AA ) $a11A ) aA#setiap suku pada ruas kanan dari persamaan itu/ ke!uali dua suku terakhir/ yaitu11A dan aA terbagi oleh 4.,adi n terbagi oleh 4 bila dan hanya bila $a11A ) aA# terbagi oleh 4.

Sehingga dapat disimpulkan:Suatu bilangan terbagi oleh 4 bila dan hanya bila bilangan yang ditanyakan olehterakhir dari bilangan itu terbagi oleh 4.

Contoh:8.132.21 terbagi oleh 4/ sebab 1 $dua angka terakhir # terbagi oleh 4.

Dengan !ara yang mirip dengan keterbagian oleh 4/ maka berikut aturan keterba bilangan oleh 9.Suatu bilangan terbagi oleh 9 bila dan hanya bila bilangan yang dinyatakan olehterakhir dari bilangan itu terbagi oleh 9.

Contoh:17.28 terbagi oleh 9 karena 28 @tiga angka terakhir# terbagi oleh 9.

!. )i$angan te(bagi o$eh / dan 11 Bagaimanakah menguji bilangan terbagi !leh $

2Qn dan 3Qn bila dan hanya bila Qn. +uktikanlah pernyataan itu.


56/63

'oba selesaikan dengan kekongruenan modulo 7.

#ATI8AN%+enar atau salahkah pernyataan berikut iniB ,ika benar/ buktikan dan tun"ukkansalah berikan alas an atau !ontoh kontranya.

1. ,ika angka terakhir dari bilangan n adalah 4/ maka n2 V $mod 1A#

2. Selisih pangkat tiga dari dua bilangan berurutan selalu tidak terbagi oleh 3

3. Sisa 2n

dibagi oleh 7 adalah salah satu di antara 1/ 2/ atau 4 utnuk setiap bil bulat positi0 n.

4. 234.8 7.7 8.432 terbagi oleh 11

8. 97 .843.212. 79 terbagi oleh 11

. Sisa 417 dibagi 7 adalah

7. %pabila n bilangan gan"il/ maka n2 V 1 $mod 9#

9. ,ika suatu bilangan terbagi oleh 3/ maka bilangan itu terbagi oleh @.@. ,ika suatu bilangan terbagi oleh 12 maka bilangan itu terbagi oleh 2 dan

4 sehingga bilangan itu terbagi oleh 9

1A.31418 ? @2 8 2.@1A. @3.@@8


57/63

PE,K5N0,UENAN #INEA,

Tujuan UmumMahasiswa dapat menyelesaikan perkongruenan linear serta meme!ahkan

terapan yang berkaitan dengan perkongruenan.

Tujuan KhususDiharapkan mahasiswa dapat:

1. Menentukan banyaknya solusi perkongruenan linear.2. Menyelesaikan perkongruenan linear.3. Menyelesaikan persamaan linear Diophantus.4. Men!irikan ada tidaknya solusi suatu pekongruenan linear.8. Menyelesaikan system perkongruenan linear.

Pe(samaan #inea( Dio9hantus(ersamaan linear diophantus yaitu persamaan linear yang berbentuk a? ) by !/ b/ ! bilangan bulat.


58/63

Pen e$esaian Pe(samaan #inea( Dio9hantus(ersamaan a? ) by ! berarti a? V ! $mod b#

atau by V ! $mod a#dari bentuk tersebut/ menun"ukkan bahwa persamaan linear dalam bentuk a? ) b

diselesaikan dengan perkongruenan.Contoh 1:

Tentukan himpunan penyelesaian dari @? ) 1 y 38

Penyelesaian:

@? ) 1 y 38

+erarti

>ilai y disubstitusikan pada @? ) 1 y 38

Memberikan

5impunan penyelesaian dari @? ) 1 y 38 adalah:


59/63

Sehingga $-8/8# merupakan penyelesaian @? ) 1 y 38.

+erdasarkan uraian di atas terlihat bahwa apabila $?A/ yA# suatu penyelesaian persamaanlinear Diphantus a? ) by !/ maka solusi lainnya adalah $?A ) bt/ yA 6 at# untuk stiap bilangan bulat t.

So$usi Pe(samaan #inea( Di9hantus

(ersaman linear Diphantus a? ) by ! dengan a/ b L A/

1. Mempunyai solusi "ika $a/ b# Q!2. Tidak mempunyai solusi "ika $a/ b# R !

ngat !ara menentukan (+ dua bilangan.

Dapat dilakukan dengan berbagai !ara/ di antaranya:

1. (ohon 0aktor 2. %lgoritma pembagian

Coba$ah bebe(a9a soa$ be(ikut:

Tentukan (+ nya:

a. $3A/ 1A8# b. $29/ 12# !. $2/ 7# d. $247/ 2@@# e. $87 7/ 4483#

Contoh :

1. Tentukan solusi dari persamaan linear Diophantus2? ) 4y 8 Penyelesaian:

arena $2/ 4# 2 dan 2 R 8 maka persamaan linear tersebut tidak mempunya(en"elasan:

248 t

x

=

%ndaikan y t/ maka


60/63

ntuk setiap bilangan bulat t/ maka $8 6 4t# merupakan bilangan gan"il.Sehingga

248 t

x

= bukan merupakan bilangan bulat.

2. Tentukan solusi dari persamaan linear Diophantus7? ) 18y 81/ dengan ? dan y bulat positi0.(enyelesaian:

arena $7/ 18# 1 maka persamaan linear tersebut mempunyai solusi.

Substitusi:

arena ? bulat positi0 dan t !a!ah/ maka ? 3 yaitu untuk t A sehingga y ,adi ? 3 dan y 2.3. Tentukan solusi dari persamaan linear Diophantus

2? ) y 2A(enyelesaian:

arena $2/ # 2 dan 2Q2A maka persamaan linear tersebut mempunyai sol(en"elasan:2? ) y 2A


61/63

Substitusi :

5impunan penyelesaian dari persamaan 2? ) y 2A adalah*************...................

Pe(kong(uenan #inea(

(engkongruenan linear adalah kalimat terbuka yang menggunakan relasi kekoContoh !:

3? V 4 $mod 8#?2 ) 3? 6 3 V A $mod 31#

(engkongruenan yang Jariabelnya berpangkatan paling tinggi satu disebut pengkongruenan linear.+entuk umum pengkongruenan linear adalah:

a? V b $mod m# memiliki penyelesaian "ika dan hanya "ika ada bilangayang memenuhi persamaan: a? b ) km

Misalkan r memnuhi pengkongruenan linear a? V b $mod m# berarti ar V b $m

Maka setiap bilangan bulat

$r ) m#/ $r ) 2m#/ $r ) 3m#/ */ $r 6 m#/ $r 6 2m#/ $r 6 3m# memenuhi pengkontersebut.

Sebab:

a$r ) km# ar b $mod m# untuk setiap bilangan bulat k/ diantara himpu bulat $r ) km#/ dengan k 1/ 2/ 3/ 4/ */ -1/ -2/ -3#/ ada tepat satu dan hanydengan A s m/ sebab suatu bilangan bulat mesti terletak di antara dua kyang berurutan. ,adi "ika r memenuhi a? V b $mod m#/ dan km r $k ) suatu bilangan bulat k/ maka A $r 6 km# m. "adi s r 6 km suatu bilan

(ernyataan tersebut menun"ukkan s adalah residu terke!il modulo m yang memn perkongruenan a? V b $mod m#. selan"utnya/ s disebut solusi dari pengkongru


62/63

Contoh ":

Tentukan penyelesaian dari 2? V 4 $mod 7# Penyelesaian: >ilai ? yang memnuhi : */ -1@/ -12/ -8/ 2/ @/ 1 / *Wesidu terke!il $yang kurang dari 7# dari modulo 7 yang memenuhi adalah 2.,adi penyelesaian 2? V 4 $mod 7# adalah ? 2.

So$usi 9e(kong(uenan a; < b 6mod m7

(ada persamaan a? b/ dengan a I A memiliki satu solusi. Sedangkan solusi ben

$mod m# dapat berupasatu solusi, banyak solusi dan tidak banyak solusi

#atihan soa$%

Tentukan solusi dari soal-soal berikut:

1. 3? V $mod 7#2. 2? V 1 $mod 4#3. 2? V 4 $mod #


63/63

ristia apriana (teori bilangan)

Documents