4 0 110 KB
7.2 Jumlah dan Banyaknya Pembagi Definisi: Fungsi jumlah pembagi, dilambangkan dengan σ , didefinisikan dengan aturan σ (n) sama dengan jumlah semua pembagi yang positif dari n. Dalam Tabel 7.1, kita berikan σ (n) untuk 1 ≤n ≤ 12. Nilai σ (n) untuk 1 ≤n ≤ 100 diberikan pada Tabel 2 Lampiran E. (Nilai-nilai ini juga dapat dihitung menggunakan Maple atau Matematika.) n
1
2
3
4
5
6
7
8
9
10
11
12
σ (n)
1
3
4
7
6
12
8
15
13
18
12
28
Tabel 7.1 Jumlah pembagi untuk 1 ≤n ≤ 12 Definisi: Fungsi banyak pembagi, ditunjukkan dengan τ , didefinisikan dengan aturan τ (n) sama dengan banyaknya semua pembagi yang positif dari n. Dalam Tabel 7.2, kita berikan τ (n) untuk 1 ≤n ≤ 12. Nilai τ (n) untuk 1 ≤n ≤ 100 diberikan pada Tabel 2 Lampiran E. (Nilai-nilai ini juga dapat dihitung menggunakan Maple atau Matematika.) Perhatikan bahwa kita dapat menyatakan σ (n) dan τ (n) dalam notasi penjumlahan. Mudah untuk dimengerti bahwa σ ( n )=∑ d dan τ ( n )=∑ 1. d∨n
d∨n
Untuk membuktikan bahwa σ dan τ multiplikatif, kita gunakan teorema berikut. Teorema 7.8 Jika f adalah suatu fungsi multiplikatif, maka fungsi penjumlahan dari F didefinisikan dengan : F ( n )=∑ f ( d) juga merupakan fungsi multiplikatif. d ∨n
Sebelum membuktikan teorema diatas, kita ilustrasikan ide dibalik pembuktian tersebut dengan contoh berikut. Misalkan f suatu fungsi multiplikatif, dan F ( n )=∑ f ( d). Kita tunjukkan bahwa d ∨n
F ( 60 )=F(4) F(15). Setiap pembagi dari 60 dapat dinyatakan sebagai perkalian pembagi dari 4 dan pembagi dari 15 dengan cara berikut:
1=1 ∙ 1, 2=2 ∙ 1, 3=1∙ 3 , 4=4 ∙1 , 5=1 ∙5 , 6=2∙ 3 , 10=2 ∙5 ,12=4 ∙ 3 ,15=1 ∙15 , 20=4 ∙ 5 ,30=2 ∙15 , 60=4 ∙ 15 (dalam setiap perkalian, faktor pertama adalah pembagi dari 4, dan yang kedua adalah pembagi dari 15). Oleh karena itu, n
1
2
3
4
5
6
7
8
9
10
11
12
τ (n)
1
2
2
3
2
4
2
4
3
4
2
6
Tabel 7.2 Banyaknya pembagi untuk 1 ≤n ≤ 12 F ( 60 )= ∑ f (d ) d∨60
¿ f ( 1 ) + f (2 )+ f ( 3 ) +f ( 4 ) + f ( 5 )+ f ( 6 ) + f ( 10 )+ f ( 12 )+ f ( 15 ) + f ( 20 )
+ f (30 )+ f (60) ¿ f ( 1 ∙1 ) + f ( 2∙ 1 )+ f ( 1∙ 3 ) + f ( 4 ∙ 1 )+ f ( 1∙ 5 ) + f ( 2∙ 3 ) +f ( 2 ∙5 )+ f ( 4 ∙ 3)
+ f (1 ∙ 15 ) +f ( 4 ∙5 )+ f ( 2∙ 15 ) + f (4 ∙ 15) ¿f¿
+ f ( 4 ) f (3)+ f ¿ ¿ ( f ( 1 ) + f ( 2 )+ f ( 4 ) ) (f ( 1 ) + f (3 )+ f ( 5 ) + f ( 15 )) ¿ F ( 4 ) F(5). Sekarang kita buktikan Teorema 7.8 dengan menggunakan ide yang diilustrasi oleh contoh. Bukti. Untuk menunjukkan bahwa F adalah suatu fungsi multiplikatif, harus ditunjukkan bahwa m dan n adalah bilangan bulat positif yang relative prima, maka F ( mn )=F ( m ) F ( n ). Jadi mari kita asumsikan bahwa (m , n)=1. Kita peroleh F ( mn )= ∑ f (d) . d∨mn
Berdasarkan Lemma 3.7, karena ( m , n )=1, setiap pembagi dari mn dapat ditulis secara unik sebagai perkalian dari pembagi yang relatif prima d 1 dari m dan d 2 dari n, dan setiap pasangan pembagi d 1 dari m dan d 2 dari n sesuai dengan suatu pembagi d=d 1 d 2 dari mn. Karenanya, kita bisa menulis F ( mn )= ∑ f (d 1 d 2) d1∨m d2∨n
Karena f multiplikatif, dan ( d 1 , d 2 )=1, maka: F ( mn )= ∑ f ¿ ¿ d 1∨m d 2∨n
¿ ∑ f ( d 1) ∑ f (d 2) d1∨m
d2∨n
¿ F ( m ) F (n). Sekarang kita bisa menggunakan Teorema 7.8 untuk menunjukkan bahwa σ dan τ multiplikatif. Akibat 7.8.1 Fungsi jumlah pembagi σ dan fungsi banyaknya pembagi τ adalah fungsi-fungsi multiplikatif. Bukti: Misalkan f ( n )=n dan g ( n )=1. Kedua f dang adalah multiplikatif. Berdasarkan Teorema 7.8, kita temukan bahwa σ ( n )=∑ f ( d ) dan τ ( n )=∑ g ( d ) adalah multiplikatif. d∨n
d∨n
Sekarang kita tahu bahwa σ dan τ adalah multiplikatif, kita dapat memperoleh rumus untuk nilainya berdasarkan faktorisasi prima. Pertama, kita menemukan rumus untuk σ (n) dan τ (n) ketika n adalah pangkat dari suatu bilangan prima. Lemma 7.1 Jika p adalah suatu bilangan prima dan a adalah bilangan bulat positif. Maka
pa +1−1 a 2 a ( ) σ p =1+ p+ p +…+ p = p−1
dan τ ( pa ) =a+1. Bukti. Pembagi-pembagi pa adalah 1 , p , p2 , … , pa−1 , p a. Mengakibatkan, pa tepat mempunyai a+1 pembagi, dengan demikian τ ( pa ) =a+1. Selanjutnya, karena deret 1+ p+ p2 +…+ pa −1 + pa merupakan deret geometri dengan suku pertama 1 dan pembanding p, maka dapat ditentukan pa +1−1 a 2 a−1 a ( ) bahwa : σ p =1+ p+ p +…+ p + p = . p−1 Contoh 7.8. Ketika kita menerapkan Lemma 7.1 dengan p=5 dan a=3, kita peroleh bahwa 5 4−1 3 2 3 ( ) σ 5 =1+5+5 +5 = =156 dan τ ( 53 ) =1+3=4 . 5−1
Lemma 7.1 dan Akibat 7.8.1 mengarah ke formula berikut. Teorema 7.9. Jika n adalah bilangan bulat positif yang mempunyai faktorisasi prima n= pa1 p2a … pas . Sehingga 1
s
p1a +1−1 p2a +1−1 p a +1−1 s paj +1−1 ∙ ∙⋯∙ s =∏ p 1−1 p 2−1 p s−1 p j−1 j=1 1
σ ( n )=
2
2
s
j
dan s
τ ( n )=( a1 +1 ) ( a 2+1 ) ⋯ ( a s+1 ) =∏ ( a j+ 1 ) . j=1
Bukti. a a a a a a Karena σ dan τ adalah fungsi multiplikatif, sehingga σ ( n )=σ ( p1 p2 ⋯ ps ) =σ ( p 1 ) σ ( p2 ) ⋯ σ ( ps ) 1
2
s
1
2
s
a a a a a a a a dan τ ( n )=τ ( p1 p2 ⋯ ps ) =τ ( p 1 ) τ ( p2 ) ⋯ τ ( ps ). Masukkan nilai-nilai untuk σ ( p i ) dan τ ( p i ) yang 1
2
s
1
2
s
i
ditemukan di Lemma 7.1, sehingga kita mendapatkan formula yang diinginkan. Contoh 7.9. Gunakan Teorema 7.9, kita peroleh
i
24−1 53−1 3 2 σ ( 200 ) =σ ( 2 5 ) = ∙ =15 ∙ 31=465 , 2−1 5−1 τ ( 200 ) =τ ( 23 5 2) =( 3+1 ) ( 2+ 1 )=12 Dengan cara yang sama kita peroleh 25−1 33−1 52−1 4 2 ( ) ( ) σ 720 =σ 2 ∙3 ∙ 5 = ∙ ∙ =31∙ 13 ∙ 6=2418 2−1 3−1 5−1 τ ( 720 )=τ ( 24 ∙3 2 ∙ 5 )= ( 4+1 ) ( 2+1 ) (1+1 ) =30
7.3 Bilangan Sempurna dan Bilangan Prima Mersenne Definisi: Jika n adalah bilangan bulat positif dan σ ( n )=2 n, maka n disebut bilangan sempurna. Contoh 7.10. Karena σ ( 6 )=1+2+3+6=12, kita peroleh bahwa 6 sempurna. Kita juga memperoleh σ (28)=1+2+4 +7+1 4+ 28=56, sehingga 28 adalah bilangan sempurna lainnya. Teorema 7.10. Bilangan bulat positif n adalah bilangan sempurna genap jika dan hanya jika n=2m−1 (2m−1), di mana n adalah bilangan bulat sehingga m ≥2 dan 2m −1 adalah bilangan prima. Bukti. Pertama-tama, kita tunjukkan bahwa jika n=2m−1 ( 2m−1 ), di mana 2m −1 adalah prima, maka n adalah sempurna. Karena 2m −1 ganjil, kita peroleh ( 2m −1 , 2m−1 ) =1. Karena σ adalah fungsi multiplikasi, maka σ ( n )=σ ( 2m−1 ) σ ( 2m −1 ). Lemma 7.1 memberi tahu kita bahwa σ ( 2m −1 ) =2m−1 dan σ ( 2m −1 )=2m , karena kita mengasumsikan bahwa 2m −1 adalah prima. Akibatnya, σ ( n )=( 2m−1 ) 2m =2 n, menunjukkan bahwa n adalah bilangan sempurna. Untuk menunjukkan bahwa kebalikannya benar, misalkan n menjadi bilangan sempurna. Tulis n=2s t , di mana s dan t adalah bilangan bulat positif dan t ganjil. Karena ( 2 s , t )=1, kita peroleh dari Lemma 7.1 bahwa (7.1)
σ ( n )=σ ( 2s t )=σ ( 2 s ) σ ( t )= ( 2s+1 −1 ) σ (t ).
Karena n sempurna, kami peroleh (7.2)
σ ( n )=2 n=2 s+1 t ,
Gabungkan (7.1) dan (7.2) menunjukkan bahwa (7.3)
( 2 s+1−1 ) σ ( t )=2s +1 t .
Karena ( 2 s+1 ,2 s+1−1 ) =1, berdasarkan Lemma 3.4 kita peroleh 2s +1∨σ ( t ). Oleh karena itu, ada bilangan bulat q sehingga σ ( t )=2s +1 q. Masukkan pernyataan ini untuk σ (t ) ke dalam (7.3) diperoleh
( 2 s+1−1 ) 2s +1 q=2 s+1 t . dan, oleh karena itu,
( 2 s+1−1 ) q=t .
(7.4) Sehingga, q∨t dan q ≠ t.
Ketika kita menambahkan q di kedua sisi (7.4), kita temukan bahwa t+ q=( 2s +1−1 ) q+q=2 s+1 q=σ ( t ) .
(7.5)
Kami akan menunjukkan bahwa q=1. Perhatikan bahwa jika q ≠ 1, maka setidaknya ada tiga pembagi positif yang berbeda, yaitu, 1, q, dan t . Ini berarti bahwa σ ( t ) ≥ t+ q+1, yang bertentangan dengan (7.5). Oleh karena itu, q=1 dan, berdasarkan (7.4), kita simpulkan bahwa t=2s +1−1. Juga, dari (7.5), kita peroleh σ ( t )=t +1, sehingga t harus prima, karena satu-satunya pembagi positifnya adalah 1 dant. Oleh karena itu, n=2s ( 2s +1−1 ), di mana 2s +1−1 adalah prima. Menurut Teorema 7.10, kita lihat bahwa untuk menemukan bilangan sempurna genap, kita harus menemukan bilangan prima dari persamaan 2m −1. Dalam pencarian bilangan prima dari persamaan ini, pertama-tama kita tunjukkan bahwa m harus prima. Teorema 7.11. Jika m adalah bilangan bulat positif dan 2m −1 adalah bilangan prima, maka m harus merupakan bilangan prima. Bukti: Asumsikan bahwa m bukan bilangan prima, sehingga m=ab, di mana 1 1. Oleh karena itu, ( p , q−1 )= p, karena satu-satunya kemungkinan lain, yaitu, ( p , q−1 )=1, akan menunjukkan kebenaran dari (7,6) bahwa ( 2 p −1, 2q−1−1 ) =1. Oleh karena itu p∨(q−1) dan. oleh karena itu, ada bilangan bulat positif m sehingga q−1=mp. Karena q ganjil, maka m harus genap, sehingga m=2 k, di mana k adalah bilangan bulat positif. Oleh karena itu, q=mp+1=2kp +1. Karena setiap pembagi M p adalah perkalian pembagi utama M p, setiap pembagi utama M p adalah dari 2 kp+1, dan hasil kali bilangan dari persamaan ini juga dari persamaan tersebut, berikut hasilnya.