AKAR PRIMITIF Ririn [PDF]

Citation preview

AKAR PRIMITIF Misalkan a adalah bilangan bulat positif sehingga (a,m) = 1. Maka a adalah akar primitif φ (m). modulo m jika ord α m



=



Dengan kata lain, suatu bilangan bulat positif m dikatakan memiliki akar primitif a, apabila a ≡ 1 ( mod m ), dan ak ≠ 1 (mod m), untuk semua bilangan bulat positif k < ∅ (m) . ∅ (m)



Setiap bilangan prima mesti mempunyai akar primitif. Sedangkan untuk bilangan bulat positif n yang prima belum tentu mempunyai akar primitif. Misalnya : Akar-akar primitif dari 9 adalah 2 dan 5 karena ∅(9) = 6 dan orde-orde dari 2 dan 5 modulo 9 masing-masing adalah 6. 2 2 Tetapi 8 tidak mempunyai akar primitif, sebab ∅(8) = 4 dan 3 ≡ 1 (mod 8), 5 ≡ 1



(mod 8) dan 7



2



≡1 (mod 8).



Berikut ini teorema yang berkenaan dengan bilangan bulat positif yang mempunyai akarakar primitive. Teorema 6.13 Misalkan (a,m) = 1 dan



c1 , c2



,…,



c ϕ (m)



adalah bilangan-bilanganbulat positif yang



kurang dari m dan saling prima dengan m. apabila a adalah akar primitif dari m maka



(m) c ,c ϕ¿ berturut-turut kongruen modulo m dengan suatu permutasi dari 1 2 , … , 1 2 ¿ a ,a ,…,a c ϕ (m)



.



Bukti Karena (a,m) = 1 maka setiap perpangkatan bulat positif dari a juga saling prima dengan m, yaitu



(m) c ϕ¿ masing-masing saling prima dengan m. karena c 1 , c 2 , … , ϕ (m) 1 2 ¿ a ,a ,…,a adalah bilangan-bilangan bulat positif yang kurang dari m dan saling prima dengan m maka untuk membuktikan teorema tersebut cukup menunjukan bahwa tak ada dua suku dari



(m) ϕ¿ yang konguen modulo m. a1 , a2 , … , a¿ Misalkan : i



a ≡a



j



(mod m) untuk 0 ¿ j ≤ ϕ(m)



i− j



≡1(modul m)



a



Karena a ialah akar primitive dari m, berarti orde a (mod m) adalah ϕ (m) dan karena 0 ≤i− j ≤ ϕ( m) maka kekongruenan terakhir itu hanya mungkin apabila i-j = 0 sehingga i=j. hal



(m) ¿ ini berarti bahwa tidak ada dua suku dari 1 ϕ yang kongruen modulo m. 2 a , a , … , a¿



Contoh : Akar primitive dari 9 adalah 2 dan ϕ ( 9 )=6 maka 21 = 2 (mod 9), 22 = 4 (mod 9), 3



2



4



2



= 8 (mod 9), = 7 (mod 9),



25 = 5 (mod 9),



6



2



= 1 (mod 9),



Perhatikan bahwa himpunan residu sederhana modulo 9 adalah {1,2,4,5,7,8} Elemen – elemen himpunan ini berturut-turut kongruen modulo 9 dengan elemen-elemen 6 1 2 5 4 3 himpunan { 2 ,2 , 2 , 2 ,2 ,2 }.



5 Maka akar primitive yang lain dari 9 adalah 2 ≡ 5 (mod 9). Jadi akar-akar primitive dari 9



adalah 2 dan 5.



Teorema 6.14 Apabila bilangan positif m mempunyai akar primitive maka banyaknya akar primitive dari m adalah ϕ ( ϕ (m)) Bukti Misalkan akar primitive dari m adalah a makan menurut teorema 6.13, akar-akar primitive yang



(m) ϕ¿ ak lain dapat dicari dari himpunan 1 2 ¿ } , yaitu {a , a , … , a



dengan 1 ≤ k ≤ ϕ(m) yang



berorde ϕ (m). Hal ini diperoleh apabila (k, ϕ (m)) = 1. Banyaknya bilangan bulat positif k, dengan 1 ≤ k ≤ ϕ(m) yang memenuhi (k, ϕ (m)¿ adalah ϕ ( ϕ ( m )) . Jadi banyaknya akar primitive dari m adalah ϕ ( ϕ ( m )) .



Contoh : Sebuah akar primitive dari 17 adalah 3 sebeb orde 3 (mod 17) adalah 16, yaitu ϕ ( 17 ) . Akar3 5 7 9 11 12 15 akar primitive dari 17 lainnya adalah 3 ,3 , 3 , 3 ,3 ,3 , 3 (ingat eksponen-eksponen



tersebut saling prima dengan 16) yang berturut-turut kongruen modulo 17 dengan 10,5,11,14,7,12,6. Jadi banyaknya akar primitive dari 17 adalah 8, dan ϕ ( ϕ ( 17 ) ) = ϕ ( 16 ) = 8.