الجذر الأولي modulo n

في نظرية الأعداد ، يُقال عن العدد 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 ] وقد} أثبت ذلك لأول مرة كارل فريدريش غاوس . ^{[ 4 ]} عرّف غاوس الجذور الأولية في المادة 57 من كتابه "Disquisitiones Arithmeticae " (1801)، حيث نسب صياغة المصطلح إلى ليونارد أويلر . وفي المادة 56، ذكر أن يوهان هاينريش لامبرت وأويلر كانا على دراية بها، لكنه كان أول من برهن بدقة على وجود الجذور الأولية لعدد أولي n . في الواقع، يحتوي كتاب "Disquisitiones " على برهانين: البرهان الوارد في المادة 54 هو برهان وجود غير بنائي ، بينما البرهان الوارد في المادة 55 هو برهان بنائي .

ويمكن وصف ذلك بشكل مكافئ بأن g جذر أولي بتردد n إذا وفقط إذا كان g مولدًا لمجموعة الضرب للأعداد الصحيحة بتردد n . وبالتالي، توجد الجذور الأولية إذا وفقط إذا كانت هذه المجموعة مجموعة دورية . 

إذا كان g جذرًا بدائيًا modulo n و g ^k ≡ a (mod n )  ، فإن القيمة k تسمى الدليل أو اللوغاريتم المنفصل لـ a للأساس g modulo n .

العدد 3 هو جذر أولي بتردد  7 ^{[ 5 ]} لأن $${\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}}}$$ تشمل البواقي 3، 2، 6، 4، 5، 1 كل فئة تطابق أولية نسبياً مع 7. وتكرر القوى الأعلى نفس النمط بشكل دوري .

يُعطى عدد فئات التطابق الأولية نسبيًا للمعامل n بواسطة دالة أويلر φ المطبقة على n . في هذه الحالة، φ (7) = 6. بالنسبة للمعامل الأولي n ، تكون هذه الدورة دائمًا مساوية لـ n − 1 ، ولكن هذا لا ينطبق على n المركب .

إذا كان n عددًا صحيحًا موجبًا، فإن الأعداد الصحيحة من 1 إلى n − 1 التي هي أولية فيما بينها مع n (أو بصورة مكافئة، فئات التطابق الأولية فيما بينها مع n ) تُشكل زمرة ، مع الضرب بتردد n كعملية؛ ويُرمز لها بـ${\displaystyle \mathbb {Z} _{n}^{\times }}$وتُسمى هذه المجموعة مجموعة الوحدات بتردد n ، أو مجموعة الفئات الأولية بتردد n . وكما هو موضح في مقال المجموعة الضربية للأعداد الصحيحة بتردد n ، فإن هذه المجموعة الضربية${\displaystyle \mathbb {Z} _{n}^{\times }}$تكون المجموعة دورية إذا وفقط إذا كان n يساوي 2 أو 4 أو p k أو 2<sup> p k حيث p k  هو قوة لعدد أولي فردي . [ 6 ] [ 2 ] [ 7 ] عندما (وفقط عندما) تكون هذه المجموعة${\displaystyle \mathbb {Z} _{n}^{\times }}$إذا كانت المجموعة دورية، يُطلق على مولد هذه المجموعة الدورية اسم الجذر الأولي modulo n [ 8 ] (أو بتعبير أدق الجذر الأولي للوحدة modulo n ، مع التأكيد على دوره كحل أساسي لمعادلات جذور الوحدة متعددة الحدود X m).-1 في الحلقة${\displaystyle \mathbb {Z} _{n}}$أو ببساطة عنصر بدائي من${\displaystyle \mathbb {Z} _{n}^{\times }}$.

متى${\displaystyle \mathbb {Z} _{n}^{\times }}$إذا كان العدد غير دوري، فإن هذه العناصر الأولية بتردد n غير موجودة. بدلاً من ذلك، لكل مكون أولي من n جذوره الأولية الفرعية الخاصة به (انظر 15 في الأمثلة أدناه).

لأي قيمة لـ n (سواء كان ذلك أم لا)${\displaystyle \mathbb {Z} _{n}^{\times }}$(دوري)، ترتيب${\displaystyle \mathbb {Z} _{n}^{\times }}$يُعطى بواسطة دالة أويلر φ ( n ) (المتتالية A000010 في OEIS ) . وتنص نظرية أويلر على أن φ ^{( n )} ≡ 1 (mod n ) لكل عدد أولي نسبيًا a مع n ^؛ ويُسمى أصغر قوة لـ a التي تُطابق 1 بتردد n بالرتبة الضربية لـ a بتردد n . على وجه الخصوص، لكي يكون a جذرًا أوليًا بتردد n ، يجب أن تكون φ ( n ) أصغر قوة لـ a تُحقق a ^x ≡ 1 (mod n ) .

على سبيل المثال، إذا كان n = 14 فإن عناصر${\displaystyle \mathbb {Z} }$^{تمثل φ(14} ₎ فئات التطابق {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} }$^X ₁₅ هي فئات التطابق {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 ]}

هذه هي الأرقام${\displaystyle n}$مع${\displaystyle \varphi (n)=\lambda (n),}$كما تم الاحتفاظ بها في التسلسل A033948 في OEIS .

يسرد الجدول التالي الجذور الأولية بتردد n حتى${\displaystyle n=31}$:

⁠${\displaystyle n}$⁠	الجذور الأولية modulo${\displaystyle n}$⁠	طلب${\displaystyle \varphi (n),}$( (التسلسل A000010 في OEIS ) )	الأس${\displaystyle \lambda (n),}$( (التسلسل A002322 في OEIS ) )
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 modulo 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}$هو جذر أولي modulo العدد الأولي${\displaystyle p}$، ثم${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$.

تنص فرضية أرتين حول الجذور الأولية على أن العدد الصحيح a الذي ليس مربعًا كاملاً ولا -1 هو جذر أولي modulo عدد لا نهائي من الأعداد الأولية .

لا توجد صيغة عامة بسيطة معروفة لحساب الجذور الأولية بتردد n . ^{[ أ ] [ ب ]} ومع ذلك، توجد طرق لتحديد الجذر الأولي أسرع من مجرد تجربة جميع الاحتمالات. إذا كان الترتيب الضربي (أسه ) لعدد m بتردد n يساوي${\displaystyle \varphi (n)}$(ترتيب${\displaystyle \mathbb {Z} }$إذا كان m جذرًا ^أوليًا بترددn _، فإن رتبته الضربيةهي1.${\displaystyle \varphi (n)=\lambda (n)~.}$يمكننا استخدام هذا لاختبار المرشح m لمعرفة ما إذا كان بدائيًا.

ل${\displaystyle n>1}$أولاً، احسب${\displaystyle \varphi (n)~.}$ثم حدد العوامل الأولية المختلفة لـ${\displaystyle \varphi (n)}$لنفترض أن _p1 ، ...، pk _. وأخيرًا، احسب

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

باستخدام خوارزمية سريعة للأس المعياري مثل الأس بالتربيع . العدد g الذي تكون جميع نتائج k الخاصة به مختلفة عن 1 هو جذر أولي.

عدد الجذور الأولية modulo n ، إن وجدت، يساوي ^{[ 12 ]}

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

بما أن المجموعة الدورية التي تحتوي على r عنصرًا، بشكل عام، تمتلك${\displaystyle \varphi (r)}$مولدات كهربائية.

بالنسبة للعدد الأولي n ، فإن هذا يساوي${\displaystyle \varphi (n-1)}$و منذ ذلك الحين${\displaystyle n/\varphi (n-1)\in O(\log \log n)}$تُعدّ المولدات شائعة جدًا بين {2، ...، n − 1}، وبالتالي من السهل نسبيًا إيجاد مولد واحد. ^{[ 13 ]}

إذا كان g جذرًا أوليًا بتردد p ، فإن g يكون أيضًا جذرًا أوليًا بتردد جميع القوى p ^k إلا إذا كان g ^{p −1} ≡ 1 (mod p ² )؛ في هذه الحالة، يكون g + p كذلك. ^{[ 14 ]}

إذا كان g جذرًا أوليًا modulo p ^k ، فإن g هو أيضًا جذر أولي modulo جميع القوى الأصغر لـ p .

إذا كان g جذرًا أوليًا modulo p ^k ، فإن إما g أو g + p ^k (أيهما فردي) يكون جذرًا أوليًا modulo 2 p ^k . ^{[ 14 ]}

إن إيجاد الجذور الأولية modulo p يعادل أيضًا إيجاد جذور متعددة الحدود الدائرية ( p − 1) modulo p .

يكون الجذر الأولي الأصغر g _p modulo p (في النطاق 1، 2، ...، p − 1) صغيرًا بشكل عام.

يُستخدم الجذر الأولي بتردد n بشكل شائع في مولدات الأرقام شبه العشوائية ^{[ 19 ]} وعلم التشفير ، بما في ذلك مخطط تبادل المفاتيح ديفي-هيلمان . وقد استندت مُشتِّتات الصوت إلى مفاهيم نظرية الأعداد مثل الجذور الأولية والبواقي التربيعية . ^{[ 20 ] [ 21 ]}

• أور، أويستين (1988). نظرية الأعداد وتاريخها . دوفر. ص 284-302 . ISBN  978-0-486-65620-5..

• وايسشتاين، إريك دبليو. "الجذر الأولي" . عالم الرياضيات .
• هولت. "البقايا التربيعية والجذور الأولية" . الرياضيات. جامعة ميشيغان التقنية.
• "حاسبة الجذور الأولية" . BlueTulip .