TEORI BILANGAN (akar primitif)

AKAR PRIMITIF SUATU BILANGAN

1 Orde Suatu Bilangan Bulat Modulo M

Dalam Teorema Euler telah dipelajari bahwa :

Jika (a,m) = 1 maka aϕm 1 (mod m)

Definisi 6.3

Misalkan suatu bilangan bulat m > 1 dan (a,m) = 1. Orde dari a modulo m adalah suatu bilangan bulat positif terkecil t, sehingga at1 (mod m)

Contoh:

Perhatikan residu-residu terkecil dari perpangkatan bulat positif a modulo 7, pada rimi berikut ini.

Tabel 6.1

a	a2	a3	a4	a5	a6
1	1	1	1	1	1
2	4	1	2	4	1
3	2	6	4	5	1
4	2	1	4	2	1
5	4	6	2	3	1
6	2	6	1	6	1

Pada rimi tampak bahwa :

Orde 1 (mod 7) adalah 1,

Orde 2 (mod 7) adalah 3, sebab 3 adalah bilangan bulat positif terkecil sedemikian hingga 231 (mod 7)

Orde 3 (mod 7) adalah 6

Orde 4 (mod 7) adalah 3

Orde 5 (mod 7) adalah 6 dan

Orde 6 (mod 7) adalah 2

Pada definisi 6.3 tersebut perlu ditekankan bahwa orde dari a (mod m) hanya ada, jika syarat (a,m) = 1 di penuhi. Sebab jika (a,m)  1, seperti telah diketahui bahwa pengkongruenan linier ax  1 (mod m) tidak mempunyai penyelesaian.

Pada contoh di atas tampak bahwa orde dari bilangan-bilangan bulat positif a modulo 7 selalu membagi ϕ(7) = 6, yaitu orde a mod 7 adalah 1,2,3,6 yang masing-masing membagi 6. Hal ini mengarahkan pada teorema berikut ini.

Teorema 6.10

Misalkan (a,m) = 1 dan orde a (mod m) adalah t maka ak 1 (mod m) jika hanya jika t|k.

Bukti:

() orde a (mod m) adalah t, berarti t adalah suatu bilangan bulat positif terkecil sedemikian hingga at1 (mod m)

Perhatikan k dan t, menurut algoritma pembagian maka ada bilangan-bilangan bulat q dan r sedemikian hingga k = qt + r dengan t

Sehingga:

ak = aqt + r = (at)qar

karena diketahui bahwa ak1 (mod m) maka:

ak         1 (mod m)

(at)qar   1 (mod m)

ar          1 (mod m), sebab at1 (mod m)

karena  t dan t adalah bilangan bulat positif terkecil sedemikian hingga at1 (mod m) 

maka r = 0.

Sehingga k = qt dan diperoleh t|k.

(⇐) karena t|k maka k = th untuk suatu bilangan bulat h.

karena at1 (mod m) maka (at)h1 (mod m), yaitu ak1 (mod m)

Menurut Teorema Euler, yaitu:Jika (a,m) = 1 maka aϕm 1 (mod m)

Apabila orde dari a (mod m) adalah t maka menurut teorema 1 dapat disimpulkan bahwa t|ϕm.

Contoh:

Perhatikan orde-orde dari bilangan-bilangan bulat positif mod 13 pada rimi berikut.

Tabel 6.2

Bilangan bulat	1	2	3	4	5	6	7	8	9	10	11	12
ordenya	1	12	3	6	4	12	12	4	3	6	12	2

Perhatikan pada rimi, orde dari bilangan-bilangan bulat positif yang merupakan residu terkecil mod 13 adalah pembagi dari ϕ (13).

Perhatikan pula bahwa:

3033 3639 (mod 13) dan

31 34 37 310 (mod 13)

Hal ini mengarahkan pada teorema berikut ini.

Teorema 6.11

Jika (a,m) = 1 dan orde a (mod m) adalah k maka ai aj (mod m) jika dan hanya jika I  j (mod k)

Bukti:

() misalkan ai aj (mod m) dengan I  j.

karena (a,m) = 1 maka diperoleh ai-j 1 (mod m).

Selanjutnya karena orde a (mod m) adalah k, menurut Teorema 6.10 maka k|(i-j)

Hal ini berarti I  j (mod k).

(⇐) karena I  j (mod k) maka I = j+tk untuk suatu bilangan bulat t.

orde a (mod m) adalah k berarti ak 1 (mod m).

sehingga:

ai           aj+tk (mod m)

aj (at)k (mod m)

ai           aj (mod m)

Memperhatikan Teorema ini karena orde a (mod m) adalah k, yaitu k adalah suatu bilangan bulat positif terkecil sedemikian hingga ak  1 (mod m)

Maka bilangan-bilangan bulat positif a, a2, a3, ..., ak tidak ada kongruen modulo m. Sebab, jika ai aj (mod m) dengan 1  i j k, maka menurut Teorema 6.11, i j (mod k) yang berarti I = j.

Jika diketahui bahwa orde a (mod m) adalah k, berapakah orde dari at (mod m)?

Misalkan (k,t) = d maka k = kid dan t = t1d dengan (k1,t1) = 1.

Maka:

=  =   1 (mod m)

Misalkan orde dari at (mod m) adalah r, menurut Teorema 6.10 maka r| k1 dan (at)r = atr1 (mod m)

Karena orde dari a (mod m) adalah k maka k|tr. Dengan kata lain k1 d|t1 dr atau k1|t1r. Dan karena (k1, t1) = 1 maka k1|r. Selanjutnya karena r|k1dan k1|r maka k1 = r sehingga k1 = r =  =

Teorema 6.12

Jika (a,m) = 1 dan orde a (mod m) adalah k maka orde dari at (mod m) dengan t  0 adalah k.

Pada Teorema 6.12 tersebut, jika (t,k) = 1 maka orde dari at(mod m) sama dengan orde a (mod m).

Sebaliknya jika orde a (mod m) adalah k dan orde dari at (mod m) adalah k pula maka dapat dibuktikan bahwa (t,k) = 1.

Misalkan (t,k) = d maka dan dan d adalah bilangan-bilangan bulat.

Orde a (mod m) adalah k maka:

ak  1 (mod m)

1 (mod m)

1 (mod m)

Karena orde dari at (mod m) adalah k maka k|.

Hal ini hanya mungkin, apabila d = 1. Jadi (t,k) = 1.

Perhatikan rimi sebelumnya, orde dari 2 (mod 13) adalah 12, sedangkan orde dari 22 dan 23 (mod 13) berturut-turut adalah 6 dan 4.

Sesuai Teorema 6.12, hal tersebut mudah diperiksa bahwa orde 22 (mod 13) adalah orde 2 (mod 13) adalah =  = 6, dan

Orde 23 (mod 13) adalah  = 4.

Mengingat akibat tersebut maka perpangkatan bulat positif dari 2 yang mempunyai orde 12 modulo 13 adalah 25, 27, dan 211.

Sedangkan 256 (mod 13), 2711 (mod 13) dan 2117 (mod 13).

Selanjutnya, 2, 6, 7, dan 11 masing-masing yang mempunyai orde 12 = ϕ(13) disebut akar-akar rimitivedari 13.

Definisi 6.4

Jika (a,m) = 1 dan orde dari a modulo m adalah(m) maka a dinamakan akar primitifdari m.

Dengan kata lain, bilangan bulat positif m mempunyai akar rimitive a, apabila 1 (mod m) Asalkan ak 1 (mod m), untuk semua bilangan bulat positif k .

Hal ini mudah untuk memeriksa bahwa 3 adalah akar-akar rimitive dari 7 karena (7) = 6 dan

31 3 (mod 7)

32  2 (mod 7)

33  6 (mod 7)

34  4 (mod 7)

35  5 (mod 7)

36 1 (mod 7)

​Apabila p suatu bilangan prima dan (a,p) = 1 maka pengkongruenan linier ax  1 (mod p) selalu mempunyai solusi. Mengingat teorema  Euler, ap-1 1 (mod p) maka solusinya adalah residu terkecil modulo p dari ap-2.

​Hal ini berarti setiap bilangan prima mesti mempunyai akar rimitive.Sedangkan untuk bilangan bulat positif n yang bukan prima belum tentu mempunyai akar rimitive.

Misalnya:

​Akar-akar rimitive dari 9 adalah 2 dan 5 karena (9) = 6 dan orde-orde dari 2 dan 5 modulo 9 masing-masing adalah 6.

Tetapi 8 tidak mempunyai akar rimitive, sebab (8) = 4 dan 32  1 (mod 8), 52  1 (mod 8) dan 72  1 (mod 8).

​Berikut ini suatu teorema yang berkenaan dengan bilangan bulat positif yang mempunyai akar-akar rimitive.

Teorema 6.13

Misalkan (a,m) = 1 dan c1,c2,…, adalah bilangan-bilangan bulat positif yang kurang dari m dan saling prima dengan m. apabila a adalah akar rimitive dari m maka , ,…, berturut-turut kongruen modulo m dengan suatu permutasi dari c1,c2,…, ,

Bukti:

Karena (a,m) = 1 maka setiap perpangkatan bulat positif dari a juga saling prima dengan m, yaitu , ,…, masing-masing saling prima dengan m. karena c1,c2,…, , adalah bilangan-bilangan bulat positif yang kurang dari m maka untuk membuktikan teorema tersebut cukup menunjukkan bahwa tak ada dua suku dari , ,…, yang kongruen modulo m.

Misalkan:

ai aj (mod m) untuk 0  j (m)

ai-j 1 (mod m)

Karena a ialah akar primitive dari m, berarti orde a (mod m) adalah  rimitive 0  I– j (m) sehingga I = j. hal ini berarti bahwa tidak ada dua suku dari , ,…, yang kongruen modulo m.

Contoh:

Akar rimitive dari 9 adalah 2 dan (9) = 6 maka

21 2 (mod 9)

22 4 (mod 9)

23 8 (mod 9)

24 7 (mod 9)

25 5 (mod 9)

26 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 himpunan

{26,21,22,25,24,23}

Memperhatikan himpunan terakhir ini dan menerapkan akibat teorema 6.12 maka akar rimitive yang lain dari 9 adalah 25 5 (mod 9). Jadi akar-akar rimitive dari 9 adalah 2 dan 5

Teorema 6.14

Apabilabilanganbulatpositif m mempunyaiakarprimitifmakabanyaknyaakarprimitifdari m adalah((m)).

Bukti:

Misalkan akar rimitive dari m adalah a maka menurut teorema 6.13, akar-akar rimitive yang lain dapat dicari dari himpunan {, ,…,}, yaitu ak dengan 1  k (m) yang berorder (m). hal ini diperoleh apabila (k,(m)) = 1.

Banyaknya bilangan bulat positif k, dengan 1  k (m) yang memenuhi (k,(m)) = 1 adalah ((m)).

Jadi banyaknya akar rimitive dari m adalah ((m)).

Contoh:

Sebuah akar rimitive dari 17 adalah 3 sebab orde 3 (mod 17) adalah 16, yaitu (17).Akar-akar rimitive dari 17 lainnya adalah 33,35,37,39,311,312,315 (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 rimitive dari 17 adalah 8, dan ((17)) = (16) = 8.

B. AkarPrimitif

Pertama, kita akan mempelajari keberadaan akar-akar rimitive untuk bilangan-bilangan prima. Kita memulai menunjukkan banyaknya solusi perkongruenan rimitive berikut.

Teorema 6.15

Jika p suatu bilangan prima dan f adalah suatu polynomial berderajat n maka perkongruenan f(x) = 0 (mod p) mempunyai sebanyak-banyaknya n solusi.

Bukti:

Misalkan rimitive f yang berderajat n adalah

F(x) = anxn + an-1xn-1 + … + a1x + a0dengan an 0 (mod p).

Teorema akan dibuktikan dengan induksi matematika pada n, yaitu derajat dari f(x).

Untuk n = 1 maka f(x) = a1x + a0 dengan an 0 (mod p)

a1x  -a0 (mod p)

karena a1p = 1 (mengapa ?) maka perkongruenan linier ini mempunyai tepat satu solusi. Jadi teorema benar untuk n = 1.

​Selanjutnya diasumsikan bahwa teorema benar untuk n = k – 1, yatu rimitive f berderajat (k – 1) mempunyai sebanyak-banyaknya (k – 1) solusi. Akan ditunjukkan bahwa untuk rimitive f berderajat k, f(x)  0 (mod p) mempunyai sebanyak-banyaknya k solusi.

​Untuk ini kita cukup menunjukkan bahwa f(x)  0 (mod p) tidak mempunyai solusi atau mempunyai satu solusi.

Jika f(x)  0 (mod p) tidak mempunyai solusi maka teorema terbukti.

​Selanjutnya, jika f(x)  0 (mod p) mempunyai sekurang-kurangnya satu solusi, misalnya a maka f(a)  0 (mod p) dan a adalah suatu residu terkecil modulo p.

jika f(x) dibagi dengan (x – a) maka diperoleh:

f(x) = (x – a) q(x) + r

suku banyak q(x) berderajat k – 1 dengan koefisien bulat dan r suatu bilangan bulat pula. Substitusi x = a, pada f(x)  0 (mod p) dan pada f(x) = (x – a) q(x) + r diperoleh:

0 f(a) = (a – a) q(a) + r (mod p)

r 0 (mod p)

sehingga f(x)  (x – a) q(x)(mod p)

misalkan b adalah penyelesaian lain dengan b  a (mod p) dari f(x)  0 (mod p) maka 0  f(b) = (b – a) q(b) (mod p)

karena p prima dan b – a  0 (mod p) maka q(b)  0 (mod p)

​hal ini dapat dikatakan bahwa suatu solusi dari f(x)  0 (mod p) yang berbeda dengan a merupakan penyelesaian dari q(x)  0 (mod p).

rimitive q(x) mempunyai sebanyak-banyaknya (k – 1) solusi sehingga f(x)  0 (mod p) tidak akan mempunyai lebih dari k solusi.

​Perlu dicatat di sini bahwa teorema 6.15 hanya benar, apabila modulonya suatu bilangan prima.Sebab, jika modulonya tidak prima maka teorema tidak benar. Misalnya x2+ x = 0 (mod p) mempunyai 4 solusi, yaitu 0,2,3 dan 5, meskipun ruas kiri dari pengkongruenan tersebut suatu polinom berderajat dua.

​Menurut teorema fermat, yaitu jika p prima dan (a,p) = 1 maka ap-1 1 (mod p). Ini benar perkongruenan xp-1 – 1  0mempunyai tepat (p – 1) solusi, yaitu:

1,2,3,…,p – 1

Misalkan bahwa d|(p – 1) maka,

xp-1– 1 = (xd – 1) (xp-1-d + xp-1-2d +…+ 1)

= (xd – 1) f(x)

Menurut teorema 6.15, f(x)  0 (mod p) mempunyai sebanyak-banyaknya (p-1-d) solusi. Misalkan x = a suatu solusi dari xp-1– 1  0 (mod p) yang bukan solusi dari f(x)  0 (mod p), maka a suatu solusi dari xd – 1  0 (mod p).

Sebab

1 ap-1 – 1  (ad – 1) f(a) (mod p)

Karena p prima dan p|f(a) maka p|(ad – 1).

Jadi xd – 1  0 (mod p) mempunyai sekurang-kurangnya p – 1 – (p – 1 – d) = d solusi.

Menurut teorema Lagrange xd–1  0 (mod p) mempunyai sebanyak-banyaknya d solusi. Jadi perkongruenan tersebut mempunyai tepat d solusi.

Uraian tersebut merupakan bukti dari teorema berikut ini:

Teorema 6.16

Jika p suatu bilangan prima dan d|p – 1 maka perkongruenan xd – 1  0 (mod p) mempunyai tepat d solusi.

Sekarang perhatikan bilangan prima 13 dan (13) = 12.

Dibentuk Ψ(d) = banyaknya bilangan bulat positif k yang kuang dari 13 dan berorde d dengan d|12.

Untuk modulo 13 ini,

1 berorde 1;

3 dan 9 masing-masing berorde 3;

4 dan 10 masing-masing berorde 6;

5 dan 8 masing-masing berorde 4;

2, 6, 7 dan 11 masing-masing berorde 12, dan 12 berorde 2.

Sehingga

1 + 1 + 2 + 2 + 2 + 4

Perhatikan juga bahwa :

Ψ(1)    =  1  =  ɸ(1)	Ψ(4)     =  2  =  ɸ(4)
Ψ(2)    =  1  =  ɸ(2)	Ψ(6)     =  2  =  ɸ(6)
Ψ(3)    =  2  =  ɸ(3)	Ψ(12)   =  4  =  ɸ(12)

Teorema 6.17

Jika p suatu bilangan prima dan d|p-1 maka ada tepat ɸ(d) bilangan bulat positif kurang dari p yang berorde d modulo p.

Bukti :

Dibentuk fungsi Ψ(d), yaitu banyaknya bilangan bulat positif yang kurang dari p yang berorde d modulo p.

Karen setiap bilangan bulat positif yang kurang dari p selalu berorde d dengan d|p-1 maka

Padahal kita telah mengetahui bahwa  maka kita harus menunjukkan bahwa Ψ(d)=ɸ      Ambil sebarang d, yaitu pembagi dari p-1 sedemikian hingga Ψ(d) > 0 maka ada suatu bilangan bulat positif a yang beorde d sehingga

Tidak ada dua suku yang kongruen modulo p dan masing-masing masing-masing memenuhi perkongruen

Sebab dengan 1 .

Menurut teorema 6.15, perkongruenan tersebut mempunyai tepat d solusi.

Selanjutnya,suatu bilangan bulat positif yang beorde d modulo p mesti kongruen modulo p dengan suatu bilangan dari  . Dan hanya sebanyal ɸ(d) dari perkongruenan a tersebut yang berorde d, yaitu aᵏ dengan (k, d) = 1.

​Jadi banyaknya bilangan bulat positif yang kurang dari p dab berorde d modulo p adalah ɸ(d). Sehingga Ψ(d) = ɸ(d).

Apabila pada teorema 6.16, d = p-1 maka diperoleh akibat teorema tersebut sebagai berikut:

Akibat: setiap bilangan prima p mempunyai sebanyak ɸ(p -1) akar rimitive

Contoh:

Tentukan akar-akar rimitive dari 31 dan tentukan pula bilangan-bilangan bulat positif yang kurang dari 31 yang berorde 6 modulo 31.

Jawab :

Banyaknya akar rimitive dari 31 adalah ɸ(ɸ(31)) =ɸ(30) = 8.

Karena banyak maka 2 bukan akar rimitive dari 31.

Kita mencoba memangkatkan 3 dengan eksponen yang tidak lebih dari 15 karena orde dari 3 mesti membagi ɸ(31) = 30 maka perhitungannya dilakukan sebagai berikut:

Karena  dan  maka orde dari 3 mesti lebih dari 15. Dan karena orde 3 mesti membagi ɸ(31) = 30 maka dapat ditarik kesimpulan bahwa orde dari 3 (mod 31) adalah 30.

Jadi 3 adalah akar rimitive dari 31.

Akar-akar rimitive dari 31 yang lain adalah  dengan (k, 30) = 1, yaitu

Yang berturutu-turut kongruen mod 31 dengan

17, 13, 24, 22, 12, 11 dan 21.

​Karena 3 adalah akar rimitive dari 31 maka setiap bilangan bulat positif yang kurang dari 31 dapat dinyatakan dalam bentuk  dengan 1 .

​Selanjutnya menurut teorema 6.12 maka orde dari adalah

Sehingga 3ᵏ yang berorde 6 apabila (k, 30) = 5, yaitu k = 5 atau k = 25. Jadi 3⁵dan  masing-masing berorde 6 (mod 31). Dengan perhitungan berikut ini dapat diketahui residu terkecilnya.

Banyaknya bilangan bulat positif yang kurang dari 31 dan berorde 6 adalah ɸ(6)=2, yaitu 6 dan 26. Akibat dari teorema 6.16 menyebutkan bahwa setiap bilangan prima p mempunyai sebanyak ɸ(p-1) akar rimitive. Apakah suatu bilangan komposit mempunyai akar rimitive?Akar-akar rimitive dari 9 adalah 2 dan 5, tetapi 8 tidak mempunyai akar rimitive.

Sekarang perhatikan bilangan komposit 2ᵏ dengan k

kita akan menunjukkan bahwa untuk sebarang bilangan ganjil a dengan (a, 2ᵏ) = 1,

maka

apabila kita berhasil menunjukkan kekongruenan tersebut maka dapat disimpulkan bahwa 2ᵏ tidak mempunyai akar rimitive.

Akan ditunjukkan dengan induksi matematik untuk setiap bilangan asli k

Jika k=3 maka diperoleh kekongruenan a²  yang benar untuk a = 1, 3, 5 dan 7, yaitu:

Jadi benar bahwa  tidak mempunyai akar rimitive.

Selanjutnya diasumsikan kekongruenan benar untuk suatu bilangan bulat k > 3, yaitu:

Kekongruenan ini ekuevalen dengan

m dengan m suatu bilangan bulat.

Jika kedua ruas dikuadratkan maka diperoleh:

Jadi kekongruenan juga benar untuk k + 1 sehingga kekongruenan benar untuk semua bilangan bulat k

Uraian diatas merupakan bukti dari teorema berikut ini.

Teorema 6.19

Jika bilangan-bilangan bulat m  2 dan n  2 dengan (m, n) I, maka m tidak mempunyai akar rimitive.

Misalkan (m), (n)] = h dan ((m), (n)) = d. Karena (m) dan(n) masing-masing bilangan genap (ingat teorema 6.5), maka d2. 

(a, m) = 1, menurut Teorema Euler   1 (mod m). Selanjutnya = a  = (  1 (mod m)

dengan cara yang sama dapat diperoleh bahwa  1 (mod n).

Karena (m, n) = 1,   (mod m) dan  1 (mod n), maka 1 (mod mn).

Lemma I.

Jika p suatu bilangan prima ganjil, maka ada suatu akar rimitive r dari p sedemikian hingga   1 (mod p²)

Lemma 2:

Misalkan p suatu bbilangan priima ganjil dan r suatu akar rimitive dari p sedemikian hingga   1 (mod p²), maka untuk setiap bilangan bulat positif k2, berlaku:

1 (mod )

Teorema 6.20

Jika p suatu bilangan prima ganjil dan bilangan bulat k1, maka  mempunyai akar rimitive.

Bukti:

Berdasarkan lemma di atas , kita dapat memilih suatu akar rimitive r dari p dan misalkan orde r (mod ) adalah n.

Teorema 6.21

Jika p suatu bilangan prima ganjil dan suatu bilangan bulat k1, maka 2 mempunyai akar rimitive.

Bukti:

Menurut Teorema 6.20,  mempunyai akar rimitive, misalnya r. Kita asumsikan bahwa r suatu bilangan ganjil, sebab jika r genap, maka r +  adalah suatu bilangan ganjil yang merupakan akar rimitive dari  pula. Maka (r, 2) =1. Misalkan orde dari r (mod 2) adalah n, maka n mesti membagi (2).

Dan karena  n. Karena orde di r (mod 2 adalah n, maka n |

Jadi n =  yang berarti bahwa r adalah akar rimitive dari 2.

Bilangan prima 5 mempunyai ((5)) = 2 akar rimitive, yaitu 2 dan 3. Karena:

25-1 16  1 (mod 25) dan 35-1  81  6  (mod 2/5).

Maka 2 dan 3 merupakan akar-akar rimitive dari 52.

Menurut teorema 6.20, 2 dan 3 juga merupakan akar-akar rimitive 5k dengan k  1. Sedangkan menurut teorema 6.21, 3 merupakan suatu akar rimitive dari semua bilangan berbentuk 2.5k dengan k  1.Tabel 6.3

Berikut ini suatu daftar akar rimitive terkecil

dari bilangan prima yang kurang dari 100

prima	Akar rimitive terkecil	prima	Akar rimitive terkecil
2	1	43	3
3	2	47	5
5	2	53	2
7	3	59	2
11	2	61	2
13	2	67	2
17	3	71	7
19	2	73	5
23	5	79	3
29	2	83	2
31	3	89	3
37	2	97	5
41	6	101	2