13 0 82 KB
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.