ในทฤษฎีจำนวน จำนวนgเป็นรากปฐมภูมิมอดู  ล n ถ้า จำนวน a ทุกจำนวนที่ เป็น จำนวนเฉพาะสัมพัทธ์ กับn สมมูลกับกำลังของg มอดูล nในทางสัญลักษณ์gเป็นรากปฐมภูมิมอดู  ล n ถ้าสำหรับจำนวนเต็ม aทุกจำนวนที่เป็นจำนวนเฉพาะ สัมพัทธ์กับnจะมีจำนวนเต็มk บางจำนวน ที่ทำให้g ^k ≡ a (mod  n )

รากปฐมภูมิมีอยู่เฉพาะสำหรับจำนวนเต็มn บางจำนวน เท่านั้น โดยเฉพาะอย่างยิ่ง รากปฐมภูมิจะมีอยู่โมดูลัสnก็ต่อเมื่อnเป็น 4, p ^kหรือ2 p ^kสำหรับจำนวนเฉพาะคี่p บางตัว และk ≥ 0บาง ตัว ^{[ 1 ] [ 2 ] [ 3 ] สิ่งนี้ได้รับการพิสูจน์ครั้ง แรก} โดยCarl Friedrich Gauss [ ^{4 ]} Gauss นิยามรากปฐมภูมิในบทที่ 57 ของDisquisitiones Arithmeticae (1801) ของเขา โดยเขาให้เครดิตLeonhard Eulerว่าเป็นผู้บัญญัติศัพท์นี้ ในบทที่ 56 เขากล่าวว่าJohann Heinrich Lambertและ Euler รู้จักรากปฐมภูมิ แต่เขาเป็นคนแรกที่พิสูจน์อย่างเข้มงวดว่ารากปฐมภูมิมีอยู่สำหรับจำนวนเฉพาะnอันที่จริงDisquisitionesมีการพิสูจน์สองแบบ: แบบในบทที่ 54 เป็นการพิสูจน์การมีอยู่ แบบไม่สร้างสรรค์ ในขณะที่การพิสูจน์ในบทที่ 55 เป็นแบบ สร้างสรรค์

ลักษณะที่เทียบเท่ากันคือgเป็นรากปฐมภูมิมอดู  ล nก็ต่อเมื่อgเป็นตัวสร้างของกลุ่มการคูณของจำนวนเต็มมอดูลnเท่านั้น ดังนั้น รากปฐมภูมิจะมีอยู่ก็ต่อเมื่อกลุ่มนี้เป็นกลุ่มวัฏจักร

ถ้าgเป็นรากปฐมภูมิมอดูล nและg ^k ≡ a (mod  n )แล้ว ค่าkเรียกว่าดัชนีหรือลอการิทึมแบบไม่ต่อเนื่องของaเทียบกับฐานgมอดูล n

เลข 3 เป็นรากดั้งเดิมมอดูโล 7 ^{[ 5 ]}เนื่องจาก เศษเหลือ 3, 2, 6, 4, 5, 1 ครอบคลุมชั้นความสอดคล้อง กันแต่ละชั้น ซึ่งเป็นจำนวนเฉพาะสัมพัทธ์กับ 7 กำลังที่สูงกว่าจะทำซ้ำรูปแบบเดียวกันเป็น ระยะ$${\displaystyle {\begin{array}{rcrcrcrcrcr}3^{1}&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\end{array}}}$$

จำนวนชั้นความสอดคล้องกันที่เป็นจำนวนเฉพาะสัมพัทธ์กับโมดูลัสnจะได้รับจากฟังก์ชันโทเทียนต์ของออยเลอร์φที่ใช้กับnในกรณีนี้ นั่นคือφ (7) = 6สำหรับโมดูลัสจำนวนเฉพาะnคาบนี้จะเท่ากับn − 1 เสมอ แต่สิ่งนี้ไม่เป็นจริงสำหรับ โมดูลั ส จำนวนประกอบn

ถ้าnเป็นจำนวนเต็มบวก จำนวนเต็มตั้งแต่ 1 ถึงn − 1ที่เป็น จำนวน เฉพาะสัมพัทธ์กับn (หรือเทียบเท่ากับชั้นสมมูลที่ เป็นจำนวนเฉพาะ สัมพัทธ์กับn ) จะรวมกันเป็นกลุ่มโดยมีการคูณมอดูลnเป็นตัวดำเนินการ กลุ่มนี้เขียนแทนด้วยและเรียกว่ากลุ่มของหน่วยมอดูลnหรือ กลุ่มของชั้นดั้งเดิมมอดูลnดังที่อธิบายไว้ในบทความกลุ่มการคูณของจำนวนเต็มมอดู^ลnกลุ่มการคูณนี้เป็น กลุ่ม วัฏจักรก็ต่อเมื่อnเท่ากับ 2, 4, ^pk หรือ 2pk ^โดยที่ pk เป็นกำลังของจำนวนเฉพาะคี่^{[ 6 ] [ 2 ] [ 7 ]}เมื่อ (และเฉพาะเมื่อ) กลุ่มนี้เป็นวัฏจักรตัวสร้างของกลุ่มวัฏจักรนี้เรียกว่ารากปฐมภูมิโมดูลัส n ^{[ 8 ]} (หรือในภาษาที่สมบูรณ์กว่าคือรากปฐมภูมิของเอกภาพโมดูลัสnโดยเน้นบทบาทของมันในฐานะคำตอบพื้นฐานของรากของสมการพหุนามเอกภาพ X${\displaystyle \mathbb {Z} _{n}^{\times }}$${\displaystyle \mathbb {Z} _{n}^{\times }}$${\displaystyle \mathbb {Z} _{n}^{\times }}$^ม− 1 ในวงแหวน) หรือเป็นเพียงองค์ประกอบดั้งเดิมของ ${\displaystyle \mathbb {Z} _{n}}$${\displaystyle \mathbb {Z} _{n}^{\times }}$

เมื่อn ไม่เป็นวัฏจักร องค์ประกอบดั้งเดิมแบบ mod nดังกล่าวจะไม่มีอยู่จริง แต่แต่ละองค์ประกอบเฉพาะของnจะมีรากย่อยดั้งเดิมของตัวเอง (ดูข้อ 15ในตัวอย่างด้านล่าง) ${\displaystyle \mathbb {Z} _{n}^{\times }}$

สำหรับn ใดๆ (ไม่ว่าจะเป็นวัฏจักรหรือไม่) ลำดับของ a จะกำหนดโดยฟังก์ชันโทเทียนต์ของออยเลอร์φ ( n ) (ลำดับA000010ในOEIS ) จากนั้นทฤษฎีบทของออยเลอร์กล่าวว่าa ^{φ ( n )} ≡ 1 (mod n )สำหรับทุกaที่เป็นจำนวนเฉพาะ สัมพัทธ์กับ nกำลังต่ำสุดของaที่สอดคล้องกับ 1 มอดูลnเรียกว่าลำดับการคูณของaมอดูลnโดยเฉพาะอย่างยิ่ง สำหรับaที่จะเป็นรากปฐมภูมิ มอดูล n นั้น φ ( n )ต้องเป็นกำลังที่เล็กที่สุดของaที่สอดคล้องกับa ^x ≡ 1 ( mod n )${\displaystyle \mathbb {Z} _{n}^{\times }}$${\displaystyle \mathbb {Z} _{n}^{\times }}$

ตัวอย่างเช่น ถ้าn = 14แล้วองค์ประกอบของ${\displaystyle \mathbb {Z} }$^× _nคือชั้นความสอดคล้อง {1, 3, 5, 9, 11, 13}; มีφ (14) = 6ชั้น ต่อไปนี้คือตารางกำลังของพวกมันโมดูล 14:

xx, x 2 , x 3 , ... (mod 14) 1 : 1 3 : 3, 9, 13, 11, 5, 1 5 : 5, 11, 13, 9, 3, 1 9 : 9, 11, 1 11 : 11, 9, 1 13 : 13, 1 

อันดับของ 1 คือ 1 อันดับของ 3 และ 5 คือ 6 อันดับของ 9 และ 11 คือ 3 และอันดับของ 13 คือ 2 ดังนั้น 3 และ 5 จึงเป็นรากปฐมภูมิโมดูลัส 14

สำหรับตัวอย่างที่สอง ให้n = 15องค์ประกอบของ${\displaystyle \mathbb {Z} }$^× ₁₅คือคลาสความสอดคล้อง {1, 2, 4, 7, 8, 11, 13, 14}; มีφ (15) = 8คลาส

xx, x 2 , x 3 , ... (mod 15) 1 : 1 2 : 2, 4, 8, 1 4 : 4, 1 7 : 7, 4, 13, 1 8 : 8, 4, 2, 1 11 : 11, 1 13 : 13, 4, 7, 1 14 : 14, 1 

เนื่องจากไม่มีจำนวนใดที่มีอันดับเป็น 8 จึงไม่มีรากปฐมภูมิโมดูล 15 อันที่จริงλ (15) = 4โดยที่λคือฟังก์ชันคาร์ไมเคิล (ลำดับA002322ในOEIS )

จำนวนที่มีรากแรกเริ่มจะมีรูปแบบดังนี้ ${\displaystyle n}$

${\displaystyle n\in \{1,2,4,p^{k},2\cdot p^{k}\;\;|\;\;2<p{\text{ prime}};\;k\in \mathbb {N} \},}$

= {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}. ^{[ 9 ]}

นี่คือตัวเลขที่ถูกเก็บไว้ในลำดับA033948ในOEIS ด้วยเช่น กัน ${\displaystyle n}$${\displaystyle \varphi (n)=\lambda (n),}$

ตารางต่อไปนี้แสดงรายการรากปฐมภูมิโมดูลัสnจนถึง: ${\displaystyle n=31}$

⁠ ⁠${\displaystyle n}$	รากปฐมภูมิโมดูลัส⁠ ⁠${\displaystyle n}$	ลำดับ((ลำดับA000010ในOEIS )) ${\displaystyle \varphi (n),}$	เลขชี้กำลัง ((ลำดับA002322ในOEIS )) ${\displaystyle \lambda (n),}$
1	0	1	1
2	1	1	1
3	2	2	2
4	3	2	2
5	2, 3	4	4
6	5	2	2
7	3, 5	6	6
8		4	2
9	2, 5	6	6
10	3, 7	4	4
11	2, 6, 7, 8	10	10
12		4	2
13	2, 6, 7, 11	12	12
14	3, 5	6	6
15		8	4
16		8	4
17	3, 5, 6, 7, 10, 11, 12, 14	16	16
18	5, 11	6	6
19	2, 3, 10, 13, 14, 15	18	18
20		8	4
21		12	6
22	7, 13, 17, 19	10	10
23	5, 7, 10, 11, 14, 15, 17, 19, 20, 21	22	22
24		8	2
25	2, 3, 8, 12, 13, 17, 22, 23	20	20
26	7, 11, 15, 19	12	12
27	2, 5, 11, 14, 20, 23	18	18
28		12	6
29	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27	28	28
30		8	4
31	3, 11, 12, 13, 17, 21, 22, 24	30	30

เกาส์พิสูจน์^{[ 10 ]}ว่าสำหรับจำนวนเฉพาะp ใดๆ (ยกเว้นp = 3 เพียงตัวเดียว)ผลคูณของรากดั้งเดิมของจำนวนเฉพาะนั้นจะสอดคล้องกับ 1 มอดูล p

เขายังพิสูจน์^{[ 11 ]}ว่าสำหรับจำนวนเฉพาะp ใดๆ ผลรวมของรากดั้งเดิมของมันจะสอดคล้องกับμ ( p − 1) modulo pโดยที่μคือฟังก์ชันโมเบียส

ตัวอย่างเช่น,

p = 3	μ (2) = −1.	รากศัพท์ดั้งเดิมคือ 2
p = 5	μ (4) = 0.	รากศัพท์ดั้งเดิมคือ 2 และ 3
p = 7	μ (6) = 1.	รากศัพท์ดั้งเดิมคือ 3 และ 5
p = 31	μ (30) = −1.	รากศัพท์ดั้งเดิมคือ 3, 11, 12, 13, 17, 21, 22 และ 24

เช่น ผลคูณของรากปฐมภูมิหลังๆ คือและผลรวมของรากปฐมภูมิเหล่านั้นคือ ${\displaystyle 2^{6}\cdot 3^{4}\cdot 7\cdot 11^{2}\cdot 13\cdot 17=970377408\equiv 1{\pmod {31}}}$${\displaystyle 123\equiv -1\equiv \mu (31-1){\pmod {31}}}$

ถ้าเป็นรากปฐมภูมิมอดูโลของจำนวนเฉพาะ แล้ว${\displaystyle a}$${\displaystyle p}$${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$

ข้อสันนิษฐานของอาร์ตินเกี่ยวกับรากปฐมภูมิระบุว่า จำนวนเต็มa ที่กำหนด ซึ่งไม่ใช่ทั้งกำลังสองสมบูรณ์และไม่ใช่ −1 จะเป็นรากปฐมภูมิมอดูลของจำนวนเฉพาะอนันต์จำนวน

ไม่มีสูตรทั่วไปง่ายๆ ในการคำนวณรากปฐมภูมิโมดูลัสnที่เป็นที่รู้จัก^{[ a ] ​​[ b ]}อย่างไรก็ตาม มีวิธีการค้นหารากปฐมภูมิที่เร็วกว่าการลองใช้ตัวเลือกทั้งหมด หากลำดับการคูณ ( เลขชี้กำลัง ) ของจำนวนmโมดูลัสnเท่ากับ(ลำดับของ${\displaystyle \varphi (n)}$${\displaystyle \mathbb {Z} }$^× _nถ้าmเป็นรากปฐมภูมิ มอดู ล n แล้ว ลำดับการคูณของm ก็ คือn = n + ...${\displaystyle \varphi (n)=\lambda (n)~.}$

ขั้นแรก ให้คำนวณจากนั้นหาตัวประกอบเฉพาะ ต่างๆ ของเช่นp ₁ , ..., p _kสุดท้าย ให้คำนวณ ${\displaystyle n>1}$${\displaystyle \varphi (n)~.}$${\displaystyle \varphi (n)}$

${\displaystyle g^{\varphi (n)/p_{i}}{\bmod {n}}\qquad {\mbox{ for }}i=1,\ldots ,k}$

โดยใช้อัลกอริทึมที่รวดเร็วสำหรับการยกกำลังแบบโมดูลาร์เช่นการยกกำลังโดยการยกกำลังสองจำนวนgที่ ผลลัพธ์ k เหล่านี้ ทั้งหมดแตกต่างจาก 1 เรียกว่ารากปฐมภูมิ

จำนวนรากดั้งเดิมโมดูลัสnหากมีอยู่ จะเท่ากับ^{[ 12 ]}

${\displaystyle \varphi \left(\varphi (n)\right)}$

เนื่องจากโดยทั่วไปแล้ว กลุ่มวัฏจักรที่มี สมาชิก rตัวจะมีตัวสร้าง ${\displaystyle \varphi (r)}$

สำหรับจำนวนเฉพาะn ค่า นี้จะเท่ากับและเนื่องจากตัวสร้างนั้นพบได้ทั่วไปในกลุ่ม {2, ..., n −1} ดังนั้นจึงค่อนข้างง่ายที่จะหาตัวสร้างหนึ่งตัว^{[ 13 ]}${\displaystyle \varphi (n-1)}$${\displaystyle n/\varphi (n-1)\in O(\log \log n)}$

ถ้าgเป็นรากดั้งเดิมมอดูล pแล้วgก็เป็นรากดั้งเดิมมอดูลกำลังp ^k ทั้งหมดด้วย เว้นแต่g ^{p −1} ≡ 1 (mod p ² ); ในกรณีนั้นg + pก็เป็นรากดั้งเดิมเช่นกัน^{[ 14 ]}

ถ้าgเป็นรากปฐมภูมิมอดูโลp ^kแล้วgก็เป็นรากปฐมภูมิมอดูโลกำลังที่เล็กกว่าทั้งหมดของpด้วย

ถ้าgเป็นรากดั้งเดิมมอดูโลp ^kแล้วgหรือg + p ^k (อันไหนเป็นเลขคี่) จะเป็นรากดั้งเดิมมอดูโล2 p ^{k [ 14 ]}

การหารากปฐมภูมิโมดูลpยังเทียบเท่ากับการหารากของ พหุ นามไซโคลโทมิกลำดับ ที่ ( p − 1) โมดูลpด้วย

รากที่เล็กที่สุดg _p modulo p (ในช่วง 1, 2, ..., p − 1)โดยทั่วไปจะมีค่าเล็ก

เบอร์เจส (1962) พิสูจน์^{[ 15 ] [ 16 ]}ว่าสำหรับทุกε > 0 จะมีCเช่นนั้น${\displaystyle g_{p}\leq C\,p^{{\frac {1}{4}}+\varepsilon }.}$

กรอสส์วาลด์ (1981) พิสูจน์^{[ 15 ] [ 17 ]}ว่าถ้าแล้ว${\displaystyle p>e^{e^{24}}\approx 10^{11504079571}}$${\displaystyle g_{p}<p^{0.499}.}$

Shoup (1990, 1992) พิสูจน์^{[ 18 ]}โดยสมมติสมมติฐาน Riemann ทั่วไปว่าg _p = O(log ⁶ p )

Fridlander (1949) และ Salié (1950) พิสูจน์^{[ 15 ]}ว่ามีค่าคงที่บวกC เช่น นั้นสำหรับจำนวนเฉพาะอนันต์g _p > C log p

สามารถพิสูจน์ได้[ ^{15 ] ใน}ลักษณะพื้นฐานว่าสำหรับจำนวนเต็มบวกM ใดๆ จะมีจำนวนเฉพาะอนันต์ที่M < g _p < p − M

รากดั้งเดิมโมดูลัสnมักใช้ในเครื่องกำเนิดเลขสุ่มเทียม^{[ 19 ]}และการเข้ารหัสลับรวมถึงแผนการแลกเปลี่ยนคีย์ Diffie–Hellman ตัวกระจายเสียงมีพื้นฐานมาจากแนวคิดทางทฤษฎีจำนวน เช่น รากดั้งเดิมและเศษกำลังสอง^{[ 20 ] [ 21 ]}

• Ore, Oystein (1988). ทฤษฎีจำนวนและประวัติศาสตร์ของมัน . Dover. หน้า  284–302 . ISBN 978-0-486-65620-5..

• ไวส์สไตน์, เอริค ดับเบิลยู. "รากแรกเริ่ม" . MathWorld .
• โฮลท์. "เศษเหลือของสมการกำลังสองและรากแรกเริ่ม" . คณิตศาสตร์. มิชิแกนเทค.
• " เครื่องคำนวณรากศัพท์ดั้งเดิม" BlueTulip