8.2 Akar Primitif Untuk bilangan primaKarena akar primitif memainkan peran penting dalam banyak penyelidikan teoritis, masalah mengerahkan daya tarik alam yang menggambarkan semua bilangan bulat yang memiliki akar primitif. Kita akan, selama beberapa halaman berikutnya, membuktikan adanya akar primitif untuk semua bilangan prima. Sebelum melakukan hal ini, marilah kita singgah sebentar untuk membangun teorema berurusan dengan jumlah solusi dari kongruensi polinomial.Theorem 8-5 (lagrange). If p is a prime andf(x)=anxn+ an-1xn-1+.. +a1x+a0, an0(mod p)Adalah polinomial derajat n 1 dengan koefisien integral, maka kongruensi yangf(x) 0 (mod p)Memiliki paling banyak n solusi kongruen modulo p. Bukti: kita lanjutkan dengan induksi pada n, tingkat f (x). Jika n = 1, maka polinomial kami adalah dalam bentukf(x) = a1x + a0Karena FPB (a1, p) = 1, kita tahu dengan Teorema 4-7 bahwa kesesuaian a1x -a0 (mod p) memiliki keunikan solusi modulo p. Dengan demikian, teorema tersebut berlaku untuk n = 1.Sekarang asumsikan induktif bahwa teorema tersebut berlaku untuk polinomial derajat k-1 dan mempertimbangkan kasus di mana f (x) memiliki derajat k. baik f (x) 0 (mod p) tidak memiliki solusi (dan kita sudah selesai) atau memiliki setidaknya satu solusi, sebut saja. Jika f (x) dibagi dengan x-a, hasilnya adalahf(x) = (x-a)q(x)+rDi mana q (x) adalah polinomial derajat k-1 dengan koefisien integral dan r adalah bilangan bulat. Mengganti x = a, kita memperoleh0 f(a)=(a-a)q(a)+r=r(mod p)Dan f(x)(x-a)q(x)(mod p) Jika b adalah salah satu dari solusi kongruen dari f (x) 0 (mod p), maka0f(b)=(b-a)q(b)(mod p).Karena b - a 0 (mod p), ini berarti bahwa q (b) 0 (mod p); dengan kata lain, setiap solusi dari f (x) 0 (mod p) yang berbeda dari harus memenuhi q (x) 0 (mod p). dengan asumsi induksi kami, kecocokan terakhir dapat memiliki paling banyak k-1 solusi kongruen. Ini melengkapi langkah induksi dan bukti.Dari teorema ini, kita dapat lulus dengan mudah ke Akibat wajar. Jika p adalah bilangan prima dan | p - 1, maka kongruensi yangXd 1 0 (mod p)Telah tepat d solusi. bukti: Karena d | p - 1, kita memiliki p - 1 = dk untuk beberapa k. kemudianxp-1 -1 = (xd 1)f(x),Dimana polinomial f(x) = xd(k-1) + xd(k-2) + + xd +xd +1 memiliki koefisien integral dan derajat d (k-1) = p-1-d. oleh teorema lagrange, para f keselarasan (x) 0 (mod p) memiliki paling banyak p - 1 - d solusi. Kita juga tahu dari Teorema Fermat yang xp-1 1 0 (mod p) memiliki tepat p - 1 solusi kongruen; yaitu, thr bilangan bulat 1,2, ....., p-1Sekarang ada solusi x = a- xp-1 - 1 0 (mod p) yang bukan merupakan solusi dari f (x) 0 (mod p) harus memenuhi xd - 1 0 (mod p). untuk0 ap-1-1=(ad - 1)f(a)(mod p),Dengan pf, berarti (a) bahwa p | ad - 1 Oleh karena itu xd - 1 0 (mod p) harus memiliki minimal.P 1 (p 1 d) = dSolutions. Kongruensi terakhir ini dapat memiliki tidak lebih dari d solusi (Teorema lagrange itu masuk lagi), maka memiliki tepat d solusi Kami mengambil keuntungan langsung dari konsekuensi ini untuk membuktikan Teorema Wilson dalam wa berbeda y: diberi p prima, menentukan polinomial f (x) olehF(x) = (x-1)(x-2).(x-(p-1))-(xp-1-1) = ap-2xp-2+ ap-3xp-3++a1x+a0,Yang derajat p-2. Teorema Fermat menunjukkan bahwa p-1 bilangan bulat 1, 2, .... P-1 adalah solusi kongruen dari kongruensi yangf(x)0(mod p),Tapi ini bertentangan dengan Teorema Lagrange, kecualiap-2 ap-3a1a00 (mod p)berikut bahwa, untuk pilihan salah satu bilangan bulat x,(x-1)(x-2).(x-(p-1))-(xp-1-1)0 (mod p)Sekarang menggantikan x = 0 untuk mendapatkan(-1)(-2)(-(p-1))+1-1(mod p)Atau (-1)p-1(p-1)!+10 (mod p). baik p-1 bahkan atau p = 2, dalam hal -1 1 (mod p); pada setiap tingkat, kita mendapatkan(p-1)! -1(m0d p)Teorema Lagrange telah memberikan kita dengan wedge masuk. Kita sekarang dalam posisi untuk membuktikan bahwa, untuk setiap p prima, ada keluar bilangan bulat dengan pesanan yang sesuai untuk setiap pembagi dari p-1, menyatakan lebih tepatnya: