AKAR PRIMITIF DAN INDEKS10.1 Order Bilangan Bulat PositifMisalkan m adalah bilangan bulat positif dan a adalah bilangan bulat positif lainnya sehingga . Maka, menurut Teorema Euler, ada eksponen e sehingga , yaitu, . Secara umum, tidak perlu menjadi terkecil seperti eksponen. Dengan prinsip pengurutan yang baik, selalu ada setidaknya bilangan eksponen positif.Sebagai contoh, mari kita menghitung sisa-sisa pangkat dari setiap sisa positif dari a modulo dan mencari yang terkecil seperti eksponen disetiap kasus. Seperti yang terlihat pada tabel dibawah ini.

Eksponen e positif terkecil sehingga untuk setiap sisa positif adalah angka yang dilingkari dalam tabel diatas, yaitu, , dan untuk setiap dan . e disebut order modulo , sebuah konsep yang diperkenalkan oleh Gauss .Order Bilangan Bulat positifMisalkan m dan a bilangan bulat positif sehingga . Maka, terdapat eksponen positif sehingga yang merupakan order dari modulo . Hal ini dinotasikan dengan . Contoh 10.1 Hitunglah dan .Solusi : Pertama, perhatikan bahwa . Untuk mengevaluasi setiap order, kita menghitung sedikitnya sisa dari pangkat dari dan modulo sampai mencapai sisa . , , Dengan demikian, adalah eksponen positif sehingga , sehingga . Untuk mencari , perhatikan bahwa : ) Dengan demikian , .Jadi, untuk menghitung , kita harus menghitung modulo untuk setiap bilangan bulat positif .

Teorema 10.1 Misalkan a adalah sebuah bilangan bulat positif sehingga dan . Kemudian jika dan hanya jika .BUKTI : Misalkan . Menurut algoritma pembagian, ada bilangan bulat dan sehingga , dimana . Kemudian,

, Tetapi, , sehingga , di mana . Karena adalah bilangan bulat positif sehingga dan , anggap . Dengan demikian, dan karenanya . Sebaliknya, misalkan . Kemudian untuk beberapa bilangan bulat positif . Oleh karena itu , Teorema ini memiliki konsekuensi yang sangat berguna dalam menghitung .Akibat 10.1 Misalkan adalah bilangan bulat positif sehingga . Kemudian . Secara khusus, jika p adalah prima dan , makaBUKTI : Menurut teorema Euler, . Oleh karena itu, menurut Teorema 10.1, . Kasus khusus nya adalah ketika . Jadi, untuk menghitung , kita tidak perlu melihat semua pangkat positif dari yang , tetapi hanya perlu mempertimbangkan pangkat-pangkat positif dari , di mana .Contoh 10.2 Hitunglah .Solusi: Pertama, perhatikan bahwa . Faktor-faktor positif d adalah , dan , sehingga hanya ini nilai yang mungkin dari . Kemudian, cari modulo untuk setiap sampai sisanya menjadi : , tetapi Dengan demikian, dapat disimpulkan bahwa.Akibat 10.2 Misalkan . Maka jika dan hanya jika BUKTI: Misalkan dan . Ketika . Jadi, menurut konsekuensi 4.6, ada modulo m. Oleh karena itu, Artinya , .Jadi, menurut Teorema 10.1, , maka, . Sebaliknya, misalkan , di mana . Maka untuk suatu bilangan bulat . Oleh karena itu, Contoh 10.3 Dari Contoh 10.2, kita peroleh . Anda dapat periksa bahwa ), di mana . Tetapi, , ketika .Teorema 10.2 Misalkan dan k sembarang bilangan bulat positif. Maka .BUKTI : Misalkan dan . Kemudian dan , dimana dan bilangan bulat positif sehingga . Ketika,

menurut Teorema 10.1 , .Karena , , sehingga . Dengan demikian, dan karenanya, . Jadi, . Tetapi , sehingga .Dengan demikian, dan . Oleh karena itu, , sehingga:

Contoh 10.4 Dalam Contoh 10.2, kita peroleh bahwa . Oleh karena itu, menurut Teorema 10.2, . Untuk mengkonfirmasi hal ini, perhatikan bahwa: Jadi, , seperti yang diperoleh dengan menggunakan teorema 10.2.Akibat 10.3 Misalkan dan sembarang bilangan bulat positif. Maka jika dan hanya jika BUKTI : Menurut teorema 10.2, . Hal ini sama dengan jika dan hanya jika .Contoh : Dari contoh sebelumnya, kita peroleh bahwa . Maka, , karena Akar PrimitifMisalkan adalah bilangan bulat positif sehingga . Maka adalah akar primitif modulo jika . Contoh 10.6 Tunjukkan bahwa adalah akar primitif modulo !Solusi : Karena , itu sudah cukup untuk menunjukkan bahwa dan jika . Karena , kita menghitung modulo : Dengan demikian, dan karenanya adalah akar primitif modulo .Akar Primitif Modulo Bilangan Fermat Prima 2 merupakan akar primitif modulo bilangan fermat prima .Contoh 10.7 Tunjukkan bahwa bukan akar primitif modulo sebarang bilangan fermat prima , dimana .BUKTI: Kita ketahui bahwa :

Maka, , karena Dengan demikian, bukan akar primitif modulo, untuk Teorema 10.3 Jika adalah akar primitif modulo , maka setidaknya sisa-sisa dari modulo adalah permutasi dari bilangan bulat positif dan relatif prima terhadap .BUKTI: Akan dibuktikan relatif prima dengan dan tidak ada dua dari mereka kongruen modulo. Untuk , menurut akibat 3.2, untuk setiap k bilangan bulat positif. Untuk menunjukkan bahwa tidak ada dua dari pangkat pertama dari adalah kongruen modulo m, anggap bahwa , di mana , . Asumsikan lebih lanjut bahwa . Kemudian, berdasarkan Akibat 10.2, . Tapi , jadi . Dengan demikian , tidak ada dua dari pangkat yang kongruen modulo . Dengan demikian, setidaknya sisa dari modulo adalah penyusunan kembali bilangan bulat positif dan relatif prima terhadap .Contoh 10.8 Misalkan . Terdapat bilangan bulat positif dan relatif prima terhadap . Mereka adalah . Dan adalah akar primitif modulo . Yang pertama, pangkat dari yaitu . Setidaknya, sisa modulo dari keenam pangkat dari tersebut masing-masing adalah . Dengan penyusunan kembali, maka sisa sisanya adalah .Akibat 10.4 Jika mempunyai akar primitif, maka ia memiliki akar primitif. Secara khusus, jika adalah sebuah bilangan prima , maka ia mempunyai akar akar primitif.BUKTI : Misalkan menjadi akar primitif modulo . Maka, menurut Teorema 10.3, setidaknya, sisa dari modulo adalah berbeda dan relatif prima terhadap . Berdasarkan akibat 10.3, jika dan hanya jika , yaitu, adalah akar primitif modulo jika dan hanya jika . Tetapi, terdapat bilangan bulat positif dan relatif prima terhadap . Dengan demikian, memiliki akar primitif. Contoh 10.10 Tentukan akar primitif kongruen modulo .Solusi : Berdasarkan trial and error , kita dapatkan bahwa adalah akar primitif modulo . Oleh karena itu , berdasarkan akibat 10.5, memiliki akar primitif , di mana . Dengan demikian, modulo , yaitu, dalam pengurutan dari kecil sampai terbesar.10.2Menguji Bilangan Prima

Kita dapat menggunakan konsep order bilangan bulat untuk menguji bilangan prima. Teorme Lucas ditemukan pada tahun 1876, melakukan satu pengujian yang didasarkan pada fakta bahwa bilangan bulat positif adalah bilangan prima jika dan hanya jika

Teorema 10.4 (Lucas 'Teorema) Misalkan n bilangan bulat positif. Jika ada bilangan bulat positif sehingga dan untuk semua faktor prima dari , maka adalah prima.

Bukti : Misalkan , dari , menurut Teorema 10.1, Akan ditunjukkan bahwa , sehingga diasumsikan bahwa Karena , untuk beberapa bilangan bulat . Misalkan menjadi faktor utama dari . Kemudian:

yang merupakan kontradiksi. Jadi , sehingga , karena . Dengan demikian, adalah prima.Contoh 10.11 Dengan menggunakan teorema Lucas ', tunjukkan bahwa adalah prima.

Solusi: Kita harus memilih untuk menunjukkan bahwa memenuhi kondisi uji. Pertama, perhatikan bahwa :

Karena , faktor prima dari adalah .Ketika ,

Ketika

Ketika

Dengan demikian, untuk semua faktor prima dari . Oleh karena itu, dengan menggunakan teorema Lucas ', adalah prima.

Akibat 10.5 Misalkan bilangan bulat positif ganjil. Jika ada bilangan bulat positif sehingga (mod ) dan untuk semua faktor prima ganjil dari , maka adalah bilangan prima.

BUKTI: Karenasehingga ketika atau adalah setiap faktor utama . Dengan demikian , kedua kondisi ini sesuai dengan teorema Lucas ', maka adalah bilangan primaContoh 10.12Dengan menggunakan Akibat 10.5 , tunjukkan bahwa adalah prima .

Solusi : Kita akan menggunakan . Karena = 1212 = 22 3 101 , faktor prima adalah dan . Perhatikan bahwa

Ketika

Ketika

Dengan demikian , dalam kedua kasus , , sehingga 1213 adalah prima.10.3 Akar Primitif untuk Bilangan PrimaBerdasarkan konsekuensi 10.4, kita temukan bahwa jika suatu bilangan positif memiliki akar primitif, maka ia memiliki akar primitif. Contohnya, 8 tidak memiliki akar primitive. Perhatikan bahwa . Agar bilangan bulat positif a menjadi akar primitif modulo 8, maka dan a harus ganjil. Jadi . Kemudian . Jadi . Akibatnya, , oleh karena itu a bukan akar primitif.Terdapat ciri-ciri jenis bilangan bulat positif yang memiliki akar primitif. Pertama, akan ditunjukkan bahwa setiap bilangan prima memiliki akar primitif. Untuk itu, kita perlu mengetahui dasarnya dengan menggunakan kongruensi polinomial. Setiap merupakan polinomial dengan koefisien integral. Suatu bilangan bulat adalah sebuah solusi dari jika . Jelas, jika , maka juga solusi modulo m.Contoh 10.13 Tentukan apakah kongruen polinomial!Solusi: Fungsi tersebut memiliki dua solusi kongruen modulo13, yaitu 4 dan 10: Tetapi kongruensi tidak mempunyai solusi.

Teorema 10.5 (Teorema Lagrange ) Misalkan merupakan sebuah polinomial berderajat dengan koefiesien integralnya, dimana . Kemudian kongruesi memiliki paling banyak solusi kongruen modulo .

BUKTI : Ketika , , dimana . Karena , kongruensi memiliki solusi unik, berdasarkan konsekuensi 4.6. Jadi, ketika , mempunyai paling banyak 1 solusi. Teorema ini berlaku ketika . Kemudian, anggap itu benar untuk polinomial derajat Misalkan i merupakan polinomial derajat , dimana . Jika tidak memiliki solusi, maka berikut hasilnya.Jadi kita asumsikan bahwa ia memiliki setidaknya 1 solusi , dimana . Misalkan menjadi hasil bagi dan (bilangan bulat) merupakan sisanya ketika dibagi dengan , dimana adalah polinomial derajat dengan koefisien integral. (Berikut ini berdasarkan Teorema Sisa). Maka, diperoleh Oleh karena itu,dimana derajat . Misalkan merupakan solusi kongruen lainnya dari dimana . Kemudian Karena ini berarti Dengan demikian setiap solusi dari berbeda dari , merupakan solusi dari Jelas, bahwa setiap solusi dari juga solusi dari Karena derajat menggunakan hipotesis induktif, mempunyai solusi , sehingga paling banyak solusi solusi.Jadi, dengan induksi, Teorema ini berlaku untuk setiap polinomial berderajat .Contoh: Polinomial berderajat 2 dan kongruen mempunyai paling banyak 2 solusi dari modulo 13.

Teorema 10.6 Jika adalah bilangan prima dan , maka memiliki tepat solusi kongruen modulo .BUKTI: Berdasarkan Teorema Fermat, memiliki tepatsolusi modulo , yaitu 1 sampai . Karena ,= ( ) (+ ++ + 1 ) = ( ) di mana = + + + + 1 adalah polinomial derajat , berdasarkan Teorema Lagrange memiliki paling banyak solusi kongruen . Oleh karena itu, memiliki setidaknya (= solusi kongruen. Menurut Teorema Lagrange, 0 ( ) memiliki paling banyak solusi kongruen. Dengan demikian, ia memiliki solusi kongruen persis modulo.Contoh 10.14 Cari solusi yang kongruen dengan 0 ( mod 13 )!

Solusi: Karena dan kongruensi menyatakan atau . Kekongruenan menghasilkan . Karena , atau . Fungsi tersebut tidak memiliki solusi kongruen lainnya. Dengan demikian, kekongruenan yang diberikan memiliki tepat tiga solusi kongruen, yaitu 1, 3 , dan 9. Teorema Lagrange dapat ditulis dalam bentuk berikut : Misalkan merupakan sebuah polinomial berderajat dengan koefiesien integralnya. Apabila kongruesi memiliki lebih dari solusi kongruen, maka untuk setiap .

Akibat 10.7 (Teorema Wilson) Jika adalah prima, maka

BUKTI: Misalkan . Jelas, adalah polinomial berderajat dengan koefisien integral. Menurut teorema Fermat, memiliki solusi kongruen. Masing-masing juga merupakan solusi dari . Oleh karena itu, memiliki solusi kongruen. Sehingga, setiap koefisien dari harus kongruen dengan 0 modulo . Secara khusus, istilah harus kongruen dengan 0 modulo . Tetapi, (-1) Oleh karena itu, ,yaitu .Jika , maka jika adalah ganjil, maka .Dengan demikian di kedua kasus, diperoleh Contoh 10.15 Misalkan dan . Misalkan menunjukkan banyaknya sisa kongruen dari order d . Hitung dan untuk setiap , dan !Solusi : Karena atau anyaknya dari sisa kongruen dari order , sisa kongruen dari order , dan tercantum pada tabel berikut.Dari tabel, diperoleh bahwa, Teorema 10.6 Misalkan bilangan prima dan faktor positif utama dari . Maka, terdapat persis kongruen bilangan bulat modulo .BUKTI : Untuk setiap faktor positif dari , misalkan menunjukkan banyaknya sisa positif modulo oleh order . Karena ada sisa positif dan masing-masing memiliki suatu order yang unik, sisa positif dari order d agar membentuk partisi dari himpunan sisa positif. Oleh karena itu, Tapi, menurut Teorema 8.6, Oleh karena itu, Selanjutnya, akan ditunjukkan bahwa untuk setiap . Untuk tujuan ini, harus dipertimbangkan dua kasus.Kasus 1 Misalkan . Kemudian, jelas , , sehingga ).Kasus 2 Misalkan . Kemudian harus ada suatu bilangan bulat dari order modulo . Oleh karena itu, menurut akibat 10.3, bilangan bulat : kongruen modulo . Selain itu, masing-masing solusi dari , karena , dimana . Karena itu, menurut Akibat 10.6, ini merupakan solusi kongruen dari kongruensi dan ordp | berdasarkan Teorema 10.1.Tapi, berdasarkan Akibat 10.3, = jika dan hanya jika . Karena ada bilangan bulat positif dan relatif prima terhadap , maka terdapat tepat ) sisa dari modulo yang memiliki order . Oleh karena itu Dengan demikian, dalam kedua kasus, . Jadi, haruslah untuk semua . Dengan kata lain , ada persis bilangan bulat kongruen ( atau sisa ) dari order modulo p.Contoh 10.16 Tentukan banyaknya bilangan bulat kongruen order modulo , di mana .Solusi : Karena , atau. Misalkan menunjukkan banyaknya sisa kongruen dari order modulo . Kemudian, Karena , berarti ada empat akar primitif modulo 13.

Akibat 10.8 Setiap bilangan prima memiliki akar primitif kongruen

BUKTI : Karena , menurut Teorema 10.6, ada bilangan bulat kongruen dari order modulo . Masing-masing dari mereka, menurut definisi, adalah akar primitif. Oleh karena itu , ada akar primitif modulo . Fakta bahwa setiap bilangan prima memiliki akar primitif ditemukan oleh Euler pada tahun 1773. Dia bahkan membuat sebuah daftar akar primitif modulo bilangan prima 37 .10.4 Bilangan Komposit Dengan Akar Primitif Pada pembahasan yang lalu, telah ditetapkan bahwa setiap bilangan prima mempunyai suatu akar primitif, faktanya, ia mempunyai akar primitif Didalam contoh 10.9, kita menemukan bahwa 54= 2.33 mempunyai (enam) akar primitif tidak kongruen. Untuk menunjukkannya, kita mulai dengan menunjukkan bahwa mempunyai suatu akar primitif. Contoh 10.17 Diketahui bahwa adalah satu-satunya akar primitif modulo . Ini juga suatu akar primitive modulo ; untuk . Dengan demikian, adalah akar primitif modulo dan . Demikian juga, adalah suatu akar primitif modulo dan.

Akibat 10.1 Misalkan akar primitif modulo dari suatu bilangan ganjil prima . Kemudian .

BUKTI : Misalkan . Asumsikan bahwa. Kemudian ). Kita mempunyai

Hasil ini yaitu, Ini adalah suatu kontradiksi. Karena adalah suatu akar primitif. Sehingga ,

Contoh 10.18. Diketahui adalah akar primitif modulo 7. Periksa bahwa .Bukti :Perhatikan bahwa Oleh karena itu, .

Teorema 10.7 Jika adalah suatu akar primitif modulo suatu bilangan prima, kemudian juga atau adalah suatu akar primitif modulo .

BUKTI : Karena adalah suatu akar primitif modulo , Misalkan . Kemudian , jadi tetapi Oleh karena itu, . Karena , jadi . Kemudian untuk setiap bilangan bulat Oleh karena itu, , jadi . Dengan demikian, atau sehingga atau .

Kasus 1Misalkan . Kemudian maka adalah suatu akar primitif modulo .Kasus 2Misalkan . Kita akan menunjukkan bahwa adalah suatu akar primitif modulo . Ketika , juga suatu akar primitif modulo . Dimana atau . Tetapi, menurut Lemma 10.1, . Jadi . Maka, adalah suatu akar primitif modulo .Teorema ini menunjukkan bahwa kuadrat dari setiap bilangan prima ganjil mempunyai suatu akar primitif.

Contoh 10.19 Ingat kembali Contoh 10.17 bahwa adalah suatu akar primitif modulo dari dan . Dalam Contoh 10.18, kita menemukan bahwa adalah suatu akar primitif modulo . Walaupun bukan suatu akar primitif modulo , adalah suatu akar primitif modulo .Dapat ditunjukkan bahwa tiap-tiap dari suatu bilangan prima ganjil mempunyai suatu akar primitif. Kita tahu bahwa benar untuk dan . Maka kita akan menunjukkan lagi bahwa benar untuk.

Akibat 10.2 Misalkan suatu akar primitif modulo suatu bilangan prima ganjil . Dimana ). Kemudian untuk tiap-tiap bilangan bulat .. BUKTI : Ketika ,

berdasarkan hipotesis. Kemudian, pernyataan ini adalah benar untuk . Asumsikan adalah benar untuk sebarang bilangan bulat

Karena, . Maka,menurut teorema Eulers,

Kemudian Maka, untuk beberapa bilangan bulat, dengan Sekarang ambil pangkat ke dari kedua persamaan diatas Ketika , maka

Dengan demikian, menurut induksi, pernyataan diatas benar untuk setiap bilangan bulat .

Teorema 10.8 Setiap perpangkatan dari suatu bilangan prima ganjil mempunyai akar primitif, dimana .

BUKTI : Misalkan suatu akar primitif modulo. Jika akar primitif modulo , maka . Jika bukan akar primitif modulo , maka menurut Teorema 10.7, adalah akar primitif modulo , dimana dan . Didalam kedua kasus, adalah akar primitif sehingga . (Catatan : jika akar primitif modulo , sehingga . Menurut Lemma 10.2Untuk setiap bilangan bulat .Kita akan menunjukkan adalah akar primitif modulo , bahwa . Diasumsikan bahwa. Then dimana . Ketika , dengan .Misalkan untuk bilangan bulat . Dimana , yaitu . Jadi , dimana dan . Jika maka,

Yang mana merupaka kontradiksi. Oleh karena itu, dan . Dengan demikian, akar primitif modulo untuk .

Akibat 10.3 Kuadrat dari setiap bilangan bulat ganjil adalah kongruen dari modulo .

BUKTI : Misalkan bilangan bulat ganjil, misalnya untuk setiap bilangan bulat . Maka . Karena , jadi, Teorema 10.9 Bilangan bulat tidak mempunyai akar primitif jika .

BUKTI : Misalkan mempunyai suatu akar primitif. Maka . Tetapi, karena , maka adalah ganjil. Menurut Lemma 10.4, Akibatnya, , yang merupakan kontradiksi. Maka, tidak mempunyai akar primitif untuk .

Suatu bilangan bulat positiftidak memiliki suatu akar primitif , jika bilangan tersebut membagi dua bilangan prima ganjil berbeda, atau jika dapat ditulis dalam bentuk dimana dan p adalah bilangan prima ganjil.

Akibat 10.5 Bilangan bulat ab tidak memiliki akar primitif jika dan BUKTI : Misalkan mempunyai suatu akar primitif . Kemudian dan Karena . Misalkan . Karena , keduanya and menurut Teorema 8.5, maka . Karena dan ,= adalah bilangan bulat.Tetapi , jadi Karena and , [Catatan : ] Dengan cara yang sama, . Dimana, , yang mana merupakan suatu kontradiksi. Karena adalah suatu akar primitif modulo dan , maka tidak mempunyai akar primitif. Sebagai contoh, tidak punya akar primitif, karena , diman dan . Dimana , tidak mempunyai akar primitif.

TEOREMA 10.10 Suatu bilangan bulat positif tidak mempunyai akar primitif jika mempunyai dua factor bilangan prima ganjil yang berbeda, atau jika berbentuk , di mana adalah suatu bilangan prima ganjil dan .

BUKTI : Suatu bilangan bulat positif mempunyai dua faktor bilangan prima ganjil berbeda dan . Kemudian, menurut Lemma 10.5, dantidak mempunyai akar primitif. Pada sisi lain, misalkan , di mana dan adalah suatu bilangan prima ganjil. Menurut Lemma 10.5 dengan dan , tidak mempunyai suatu akar primitif.Contoh 10.21. bilangan bulat tidak memiliki akar primitive, karena bilangan tersebut membagi dua bilangan prima ganjil berbeda.

Teorema 10.11 Bilangan bulat , di mana adalah suatu bilangan prima ganjil, mempunyai suatu akar primitif.BUKTI :Misalkan suatu akar primitif modulo . Maka

Kasus 1 : Misalkan adalah bilangan ganjil. ( Kita akan menunjukkan bahwa adalah suatu akar primitif modulo ). Karena , ( 10.3 )karena adalah bilangan ganjil, jadi ( 10.4 )Oleh karena itu, menurut kongruensi (10.3) dan (10.4),, yaitu Misalkan . Maka, , Dengan demikian, dan jelas merupakan kontradiksi. Sehingga dan adalah akar primitif modulo .

Kasus 2 : Misalkan adalah bilangan genap. Maka, adalah bilangan ganjil, jadi

Selain itu, karena , . yaitu, . Sama seperti pada kasus 1, adalah akar primitif modulo. Dengan demikian, adalah akar primitif.

Teorema 10.12 Bilangan bulat positif yang memiliki akar primitif adalah dan , dimana adalah bilangan prima ganjil dan adalah bilangan bulat positif.

10.5 Indeks Aljabar Konsep indeks yang analog dengan logaritma diperkenalkan oleh Gauss di Disquisitiones Arithmeticae nya. Seperti yang akan kita pelajari, konsep indeks sangat berguna untuk memecahkan kongruensi tertentu dan sisa-sisa komputasi.

Misalkan merupakan akar primitif modulo bilangan bulat positif . Misalkan bilangan bulat positif 18 dan relatif prima untuk itu. Kemudian(mod 18) untuk beberapa bilangan bulat positif , di mana . Sebagai contoh, jika = 13, maka = 4 maka 13 54 (mod 18 ). Oleh karena itu , kita mengatakan bahwa 4 adalah indeks dari 13 ke basis 5 modulo 18 dan membuat definisi sebagai berikut.

Indeks

Misalkan bilangan bulat positif dengan akar primitif, dan bilangan bulat positif sehingga . Kemudian bilangan bulat positif sehingga disebut indeks ke basis modulo . Hal ini dilambangkan dengan atau . Perhatikan bahwa .Contoh 10.23 Bilangan bulat adalah akar primitif modulo . Akan ditunjukkan bahwa:

Akibatnya,ind5 5 = 1ind5 7 = 2ind5 17 = 3ind5 13 = 4ind5 11 = 5ind5 1 = 6Misalkan, kita ambil akar primitif modulo yang berbeda, misalnya . Sehingga,

Akibatnya,ind11 5 = 5ind11 7 = 4ind11 17 = 3ind11 13 = 2ind11 11 = 1ind11 1 = 6

Perhatikan bahwa, secara umum, ind5 ind11. Misalnya, 2 = ind5 7 ind11 7 =4. Akibatnya, nilai ind tergantung pada akar primitif (dan modulus ).

Ditunjukkan dari definisi bahwa, seperti dalam kasus logaritma, ind adalah bilangan positif eksponen. Perhatikan bahwa, dan bahwa ind adalah bilangan positif eksponen terkecil, di mana .

Misalkan Untuk melihat bagaimana ind dan ind yang terkait, mari kita anggap bahwa adalah akar primitif modulo . Kemudian ind ( mod ) dan ind ( mod ). Karena ( mod ), ind ind Kemudian, menurut Corollary 10.2, ind = ind . Dengan demikian, ( mod ) jika dan hanya jika ind = ind . Sebagai contoh , Ingat dari Contoh 10.23 bahwa ind513 = 4. Karena , ind5 67 = 4. Dengan demikian, ind5 13 = ind5 67.

Properti ind (mod ) mengingatkan kita pada properti logaritma, logb = untuk setiap basis dan setiap bilangan real positif . Demikian pula, properti ind= indjika dan hanya jika mengingatkan kita pada properti logaritmik lainnya yaitu logb= logb jika dan hanya jika =. Indeks mematuhi tiga sifat tambahan, analog dengan sifat properti logaritma, yaitu sebagai berikut :

Mereka disajikan dalam teorema berikut.

Teorema 10.13 Misalkan bilangan bulat positif dengan akar primitif, dan dan merupakan bilangan bulat positif relatif prima terhadap . Maka :

BUKTI :

1.) Ketika adalah akar primitif modulo adalah bilangan bulat positif terkecil ketika. Akibatnya, ind1 =

2.) Berdasarkan definisi, (mod) dan . Oleh karena itu,

Sekali lagi, menurut definisi .Dengan demikian,

Oleh karena itu, berdasarkan Corollary 10.2, .

3.) berdasarkan definisi, . Tetapi

Dengan demikian,

Contoh 10.24 Periksa bagian (2) dan (3) dari Teorema 10.13 dengan =5, =18, =11, =13, dan =7.Solusi :Dari contoh 10.23, ind511=5 dan ind513=4.1.) ind511 + ind513 = 5 + 4 3 (mod 6).

[Catatan: ]. Dengan komputasi secara langsung,

ind5(11 13 ) = ind517 = 3

ind5 11 + ind513 ( mod 6 )

2. ) 7 ind511 = 7 5 5 ( mod 6 )

Dengan komputasi secara langsung, ind5 (117) = ind5 11 5 ( mod 6 )

Dengan demikian, 5 (117) 7 ind5 11 ( mod 6 ).

Indeks sangat digunakan dalam memecahkan kongruensi dari bentuk dan ,dimana.

Contoh 10.26 Selesaikan kongruensi Solusi :Catatan : 2 adalah akar primitif modulo 13. Sehingga, dapat dibuat dalam tabel di bawah ini :

Kita mempunyai . Kalikan ind2 pada kedua ruas :

Menurut Teorema 10.13, didapatkan

Berdasarkan tabel di atas, maka didapatkan :

KESIMPULANDari penjelasan di atas, dapat disimpulkan bahwa : Misalkan dan bilangan bulat positif sehingga . Maka, terdapat eksponen positif sehingga yang merupakan order dari modulo , untuk setiap bilangan bulat positif .

Misalkan a adalah sebuah bilangan bulat positif sehingga dan . Kemudian jika dan hanya jika e | n . Jika a adalah bilangan bulat positif sehingga . Kemudian . Secara khusus, jika p adalah prima dan , maka Untuk menghitung , kita tidak perlu melihat semua pangkat positif dari yang , tetapi hanya perlu mempertimbangkan pangkat-pangkat positif dari , di mana .

Misalkan dan k sembarang bilangan bulat positif. Maka . Jika dan k sembarang bilangan bulat positif. Maka jika dan hanya jika Jika adalah akar primitif modulo , maka setidaknya sisa-sisa dari modulo adalah permutasi dari bilangan bulat positif dan relatif prima terhadap m. Setiap bilangan prima memiliki akar primtif. Akar primitif suatu bilangan bulat positif tidak unik.

Teorema Lucas. Misalkan bilangan bulat positif. Jika ada bilangan bulat positif bahwa (mod n) dan (mod n) untuk semua faktor prima dari , maka adalah prima.

Misalkan bilangan bulat positif yang aneh. Jika ada bilangan bulat positif sehingga (mod ) dan (mod ) untuk semua faktor prima ganjil dari , maka adalah bilangan prima. (Teorema Lagrange ) Misalkan merupakan sebuah polinomial berderajat dengan koefiesien integralnya, dimana . Kemudian kongruesi memiliki paling banyak solusi kongruen modulo . Jika adalah bilangan prima dan , maka memiliki tepat solusi kongruen modulo . Teorema Wilson. Jika adalah prima, maka Misalkan bilangan prima dan faktor positif utama dari . Maka, terdapat persis kongruen bilangan bulat modulo . Setiap bilangan prima memiliki akar primitif kongruen. Jika adalah suatu akar primitif modulo suatu bilangan ganjil prima , kemudian juga atau adalah suatu akar primitif modulo . Setiap dari suatu bilangan prima ganjil mempunyai akar primitif, dimana . Bilangan bulat tidak mempunyai akar primitif jika . Kuadrat dari setiap bilangan bulat ganjil adalah kongruen dengan modulo . Bilangan bulat tidak memiliki akar primitif jika dan Suatu bilangan bulat positif tidak mempunyai akar primitif jika mempunyai dua factor bilangan prima ganjil yang berbeda, atau jika berbentuk di mana adalah suatu bilangan prima ganjil dan . Bilangan bulat , di mana adalah suatu bilangan prima ganjil, mempunyai suatu akar primitif. Bilangan bulat yang memiliki akar primitif adalah , dimana adalah bilangan prima ganjil dan adalah bilangan bulat positif.

Misalkan bilangan bulat positif dengan akar primitif , dan dan bilangan bulat positif relatif prima terhadap . Kemudian :

27