Teori Bilangan (Akar Primitif)

AKAR PRIMITIF SUATU BILANGAN

A.  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 at 1 (mod m)

Contoh:

Perhatikan residu-residu terkecil dari perpangkatan bulat positif a modulo 7, pada tabel 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 tabel tampak bahwa :

Orde 1 (mod 7) adalah 1,

Orde 2 (mod 7) adalah 3, sebab 3 adalah bilangan bulat positif terkecil sedemikian hingga 2³ 1 (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 a^t 1 (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:

a^k = a^{qt + r} = (a^t)^qa^r

karena diketahui bahwa a^k 1 (mod m) maka:

a^k         1 (mod m)

(a^t)^qa^r   1 (mod m)

a^r          1 (mod m), sebab a^t 1 (mod m)

karena  t dan t adalah bilangan bulat positif terkecil sedemikian hingga a^t 1 (mod m) maka r = 0.

Sehingga k = qt dan diperoleh t|k.

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

karena a^t 1 (mod m) maka (a^t)^h 1 (mod m), yaitu a^k 1 (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 tabel 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 tabel, orde dari bilangan-bilangan bulat positif yang merupakan residu terkecil mod 13 adalah pembagi dari ϕ (13).

Perhatikan pula bahwa:

3⁰ 3³  3⁶ 3⁹ (mod 13) dan

3¹  3⁴  3⁷  3¹⁰ (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 aⁱ  a^j (mod m) dengan i  j.

karena (a,m) = 1 maka diperoleh a^i-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 a^k  1 (mod m).

sehingga:

aⁱ           a^j+tk (mod m)

             a^j (a^t)^k (mod m)

aⁱ           a^j (mod m)

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

Maka bilangan-bilangan bulat positif a, a², a³, ..., a^k tidak ada kongruen modulo m. Sebab, jika aⁱ  a^j (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 a^t (mod m)?

Misalkan (k,t) = d maka k = k_id dan t = t₁d dengan (k₁,t₁) = 1.

Maka:

=  =    1 (mod m)

Misalkan orde dari a^t (mod m) adalah r, menurut Teorema 6.10 maka r| k₁ dan (a^t)^r = a^tr 1 (mod m)

Karena orde dari a (mod m) adalah k maka k|tr. Dengan kata lain k₁ d|t₁ dr atau k₁|t₁r. Dan karena (k₁, t₁) = 1 maka k₁|r. Selanjutnya karena r|k₁dan k₁|r maka k₁ = r sehingga k₁ = 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 a^t (mod m) sama dengan orde a (mod m).

Sebaliknya jika orde a (mod m) adalah k dan orde dari a^t (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:

a^k  1 (mod m)

 1 (mod m)

 1 (mod m)

Karena orde dari a^t (mod m) adalah k maka k| .

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

Perhatikan tabel sebelumnya, orde dari 2 (mod 13) adalah 12, sedangkan orde dari 2² dan 2³ (mod 13) berturut-turut adalah 6 dan 4.

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

Orde 2³ (mod 13) adalah  = 4.

Mengingat akibat tersebut maka perpangkatan bulat positif dari 2 yang mempunyai orde 12 modulo 13 adalah 2⁵, 2⁷, dan 2¹¹.

Sedangkan 2⁵ 6 (mod 13), 2⁷ 11 (mod 13) dan 2¹¹ 7 (mod 13).

Selanjutnya, 2, 6, 7, dan 11 masing-masing yang mempunyai orde 12 = ϕ(13) disebut akar-akar primitif dari 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 primitif a, apabila

 1 (mod m)

Asalkan a^k  1 (mod m), untuk semua bilangan bulat positif k .

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

3¹  3 (mod 7)

3²  2 (mod 7)

3³  6 (mod 7)

3⁴  4 (mod 7)

3⁵  5 (mod 7)

3⁶  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, a^p-1  1 (mod p) maka solusinya adalah residu terkecil modulo p dari a^p-2.

            Hal ini berarti setiap bilangan prima mesti mempunyai akar primitif. Sedangkan untuk bilangan bulat positif n yang bukan 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.

            Tetapi 8 tidak mempunyai akar primitif, sebab (8) = 4 dan 3²  1 (mod 8), 5²  1 (mod 8) dan 7²  1 (mod 8).

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

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 primitif 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 c₁,c₂,…, ,  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:

aⁱ  a^j (mod m) untuk 0  j (m)

a^i-j  1 (mod m)

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

Contoh:

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

2¹  2 (mod 9)

2²  4 (mod 9)

2³  8 (mod 9)

2⁴  7 (mod 9)

2⁵  5 (mod 9)

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 himpunan

{2⁶,2¹,2²,2⁵,2⁴,2³}

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

Teorema 6.14

Apabilabilanganbulatpositif m mempunyaiakarprimitifmakabanyaknyaakarprimitifdari m adalah ( (m)).

Bukti:

            Misalkan akar primitif dari m adalah a maka menurut teorema 6.13, akar-akar primitif yang lain dapat dicari dari himpunan { ,  ,…, }, yaitu a^k 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 primitif dari m adalah ( (m)).

Contoh:

            Sebuah akar primitif dari 17 adalah 3 sebab orde 3 (mod 17) adalah 16, yaitu (17). Akar-akar primitif 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 primitif dari 17 adalah 8, dan ( (17)) = (16) = 8.

B. AkarPrimitif

            Pertama, kita akan mempelajari keberadaan akar-akar primitif untuk bilangan-bilangan prima. Kita memulai menunjukkan banyaknya solusi perkongruenan polinomial 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 polinomial f yang berderajat n adalah

            F(x) = a_nxⁿ + a_n-1x^n-1 + … + a₁x + a₀dengan a_n  0 (mod p).

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

            Untuk n = 1 maka f(x) = a₁x + a₀ dengan a_n  0 (mod p)

 a₁x  -a₀ (mod p)

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

            Selanunya diasumsikan bahwa teorema benar untuk n = k – 1, yatu polinomial f berderajat (k - 1) mempunyai sebanyak-banyaknya (k – 1) solusi.

            Akan ditunjukkan bahwa untuk polinomial 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).

polinomial 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 x²+ 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 a^p-1  1 (mod p). Ini benar perkongruenan x^p-1 – 1  0 mempunyai tepat (p – 1) solusi, yaitu:

1,2,3,…,p – 1

Misalkan bahwa d|(p – 1) maka,

x^p-1– 1 = (x^d – 1) (x^p-1-d + x^p-1-2d +…+ 1)

                                     = (x^d – 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 x^p-1 – 1  0 (mod p) yang bukan solusi dari f(x)  0 (mod p), maka a suatu solusi dari x^d – 1  0 (mod p).

Sebab

0  a^p-1 – 1  (a^d – 1) f(a) (mod p)

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

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

Menurut teorema Lagrange x^d - 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)=ɸ(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 primitif

Contoh:

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

Jawab :

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

Karena banyak maka 2 bukan akar primitif 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 primitif dari 31.

Akar-akar primitif 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 primitif 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 primitif. Apakah suatu bilangan komposit mempunyai akar primitif? Akar-akar primitif dari 9 adalah 2 dan 5, tetapi 8 tidak mempunyai akar primitif.

            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 primitif.

            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 primitif.

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.18

Untuk k , bilangan bulat  tidak mempunyai akar primitif.

Teorema berikut ini mempunyai spirit sama dengan teorema tersebut.

Teorema 6.19

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

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

                         h =    

 karena (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 primitif r dari p sedemikian hingga    1 (mod p²)

Lemma 2:

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

                         1 (mod )

Teorema 6.20

Jika p suatu bilangan prima ganjil dan bilangan bulat k 1, maka  mempunyai akar primitif.

           

Bukti:

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

Teorema 6.21

Jika p suatu bilangan prima ganjil dan suatu bilangan bulat k 1, maka 2  mempunyai akar primitif.

Bukti:

            Menurut Teorema 6.20,  mempunyai akar primitif, misalnya r. Kita asumsikan bahwa r suatu bilangan ganjil, sebab jika r genap, maka r +  adalah suatu bilangan ganjil yang merupakan akar primitif 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 primitif dari 2 .

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

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

Maka 2 dan 3 merupakan akar-akar primitif dari 5².

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

Tabel 6.3

Berikut ini suatu daftar akar primitif terkecil

dari bilangan prima yang kurang dari 100

prima	Akar primitif terkecil	prima	Akar primitif 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