عدد أولي

لم يعتبر معظم اليونانيين الأوائل العدد 1 عددًا، ^{[ 35 ] [ 36 ]} لذا لم يتمكنوا من اعتباره عددًا أوليًا. كما اعتبر بعض العلماء في التراث اليوناني والروماني اللاحق، بمن فيهم نيكوماخوس ، ويامبليخوس ، وبوثيوس ، وكاسيودوروس ، الأعداد الأولية تقسيمًا للأعداد الفردية، لذا لم يعتبروها عددًا أوليًا .${\displaystyle 2}$ليس أوليًا أيضًا. ومع ذلك، اعتبر إقليدس ومعظم علماء الرياضيات اليونانيين الآخرين ⁠${\displaystyle 2}$كعدد أولي. اتبع علماء الرياضيات المسلمون في العصور الوسطى إلى حد كبير رأي الإغريق في اعتبار العدد 1 ليس عددًا. ^{[ 35 ]} وبحلول العصور الوسطى وعصر النهضة، بدأ علماء الرياضيات في التعامل مع العدد 1 كعدد، وبحلول القرن السابع عشر، أدرجه بعضهم كأول عدد أولي. ^{[ 37 ]} في منتصف القرن الثامن عشر، ذكر كريستيان غولدباخ العدد 1 كعدد أولي في مراسلاته مع ليونارد أويلر ؛ ^{[ 38 ]} ومع ذلك، لم يعتبر أويلر نفسه العدد 1 عددًا أوليًا. ^{[ 39 ]} كان العديد من علماء الرياضيات في القرن التاسع عشر لا يزالون يعتبرون العدد 1 عددًا أوليًا، ^{[ 40 ]} وقدأدرج ديريك نورمان ليمر العدد 1 في قائمته للأعداد الأولية التي تقل عن عشرة ملايين والتي نُشرت عام 1914. ^{[ 41 ]} واستمر نشر قوائم الأعداد الأولية التي تتضمن العدد 1 حتى عام 1956. ^{[ 42 ] [ 43 ]} ومع ذلك، بحلول أوائل القرن العشرين، بدأ علماء الرياضيات يتفقون على أنه لا ينبغي إدراج العدد 1 كعدد أولي، بل في فئة خاصة به كـ" وحدة ". ^{[ 40 ]}

لو اعتُبر العدد 1 عددًا أوليًا، لكان من الضروري إعادة صياغة العديد من العبارات المتعلقة بالأعداد الأولية بطريقة غير سلسة. على سبيل المثال، كان لا بد من إعادة صياغة النظرية الأساسية للحساب بدلالة تحليل الأعداد إلى عواملها الأولية الأكبر من 1، لأن كل عدد سيكون له عدة تحليلات تحتوي على أي عدد من نسخ العدد  1. ^{[ 40 ] [ 44 ]} وبالمثل، لن تعمل غربال إراتوستينس بشكل صحيح إذا تعامل مع العدد 1 كعدد أولي، لأنه سيستبعد جميع مضاعفات العدد 1 (أي جميع الأعداد الأخرى) ولن يُخرج سوى العدد  1. ^{[ 43 ]} كما أن بعض الخصائص التقنية الأخرى للأعداد الأولية لا تنطبق على العدد 1: على سبيل المثال، تختلف صيغ دالة أويلر أو دالة مجموع القواسم للأعداد الأولية عنها للعدد  1. ^{[ 45 ]}

كتابة عدد على شكل حاصل ضرب أعداد أولية يُسمى تحليل العدد إلى عوامله الأولية . ^{[ 46 ]} على سبيل المثال:

${\displaystyle {\begin{aligned}50&=2\times 5\times 5\\&=2\times 5^{2}.\end{aligned}}}$

تُسمى الحدود الموجودة في حاصل الضرب بالعوامل الأولية . قد يظهر العامل الأولي نفسه أكثر من مرة؛ في هذا المثال، يوجد نسختان من العامل الأولي.${\displaystyle 5.}$عندما يتكرر عدد أولي عدة مرات، يمكن استخدام الأسس لتجميع نسخ متعددة من نفس العدد الأولي: على سبيل المثال، في الطريقة الثانية لكتابة الناتج أعلاه،${\displaystyle 5^{2}}$يشير إلى مربع أو قوة ثانية لـ${\displaystyle 5}$[ ⁴⁶ ]^​​

تكمن الأهمية المحورية للأعداد الأولية في نظرية الأعداد والرياضيات عمومًا في النظرية الأساسية للحساب . ^{[ 47 ]} تنص هذه النظرية على أن كل عدد صحيح أكبر من 1 يمكن كتابته كحاصل ضرب عدد أولي واحد أو أكثر. والأهم من ذلك، أن هذا الناتج فريد من نوعه، بمعنى أن أي تحليلين للعدد نفسه إلى عوامله الأولية سيحتويان على العدد نفسه من نسخ الأعداد الأولية نفسها، على الرغم من اختلاف ترتيبها. ^{[ 48 ]} لذا، على الرغم من وجود طرق عديدة لإيجاد تحليل باستخدام خوارزمية تحليل الأعداد الصحيحة ، إلا أنها جميعًا تُنتج النتيجة نفسها. وبالتالي، يمكن اعتبار الأعداد الأولية "اللبنات الأساسية" للأعداد الطبيعية. ^{[ 49 ]}

تعتمد بعض البراهين على تفرد التحليل إلى عوامل أولية على مبرهنة إقليدس : إذا ⁠${\displaystyle p}$هو عدد أولي و${\displaystyle p}$يقسم المنتج${\displaystyle ab}$من الأعداد الصحيحة${\displaystyle a}$و​${\displaystyle b,}$ثم​${\displaystyle p}$يقسم​​${\displaystyle a}$أو​​${\displaystyle p}$يقسم​​${\displaystyle b}$( أو كلاهما). ^{[ 50 ]} على العكس من ذلك، إذا كان الرقم${\displaystyle p}$إذا كان للعدد خاصية أنه عند قسمة ناتج ما، فإنه يقسم دائمًا عاملًا واحدًا على الأقل من عوامل الناتج، فإن${\displaystyle p}$يجب أن يكون عددًا أوليًا. ^{[ 51 ]}

يوجد عدد لا نهائي من الأعداد الأولية. بعبارة أخرى، المتتالية

${\displaystyle 2,3,5,7,11,13,...}$

لا تنتهي الأعداد الأولية. تُعرف هذه المقولة بنظرية إقليدس تكريمًا للرياضي اليوناني القديم إقليدس ، إذ يُنسب إليه أول برهان معروف لها. وهناك العديد من البراهين الأخرى المعروفة على لانهائية الأعداد الأولية، بما في ذلك البرهان التحليلي لأويلر ، وبرهان غولدباخ القائم على أعداد فيرما ، ^{[ 52 ] وبرهان} فورستنبرغ باستخدام الطوبولوجيا العامة ، ^{[ 53 ]} وبرهان كومر بالتناقض . ^{[ 54 ] [ 55} ]

يُظهر برهان إقليدس أن كل قائمة منتهية من الأعداد الأولية غير مكتملة. ^{[ 56 ]} الفكرة الأساسية هي ضرب الأعداد الأولية في أي قائمة معطاة وجمعها${\displaystyle 1.}$إذا كانت القائمة تتكون من الأعداد الأولية${\displaystyle p_{1},p_{2},\ldots ,p_{n},}$وهذا يعطي الرقم

${\displaystyle N=1+p_{1}\cdot p_{2}\cdots p_{n}.}$

بحسب النظرية الأساسية للحساب ،${\displaystyle N}$له تحليل إلى عوامل أولية

${\displaystyle N=p'_{1}\cdot p'_{2}\cdots p'_{m}}$

مع عامل أولي واحد أو أكثر .${\displaystyle N}$يقبل القسمة بالتساوي على كل من هذه العوامل ، ولكن${\displaystyle N}$يكون باقي قسمة العدد على أي من الأعداد الأولية في القائمة المعطاة مساوياً للواحد، لذا لا يوجد أي عامل أولي للعدد${\displaystyle N}$يمكن أن يكون العدد ⁠ ضمن القائمة المعطاة. ولأنه لا توجد قائمة منتهية بجميع الأعداد الأولية، فلا بد أن يكون هناك عدد لا نهائي من الأعداد الأولية.

تُسمى الأعداد الناتجة عن إضافة واحد إلى حاصل ضرب أصغر الأعداد الأولية بأعداد إقليدس . ^{[ 57 ]} أول خمسة منها أعداد أولية، أما السادس،

${\displaystyle 1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,}$

هو عدد مركب.

لا توجد صيغة فعّالة معروفة للأعداد الأولية. على سبيل المثال، لا توجد معادلة متعددة الحدود غير ثابتة ، حتى في عدة متغيرات، تأخذ قيمًا أولية فقط. ^{[ 58 ]} مع ذلك، توجد العديد من التعبيرات التي تُشفّر جميع الأعداد الأولية، أو الأعداد الأولية فقط. إحدى الصيغ الممكنة مبنية على نظرية ويلسون، وتُنتج العدد 2 مرات عديدة، وجميع الأعداد الأولية الأخرى مرة واحدة فقط. ^{[ 59 ]} كما توجد مجموعة من المعادلات الديوفانتية في تسعة متغيرات ومعامل واحد، تتميز بالخاصية التالية: يكون المعامل أوليًا إذا وفقط إذا كان لنظام المعادلات الناتج حلٌّ ضمن مجموعة الأعداد الطبيعية. يمكن استخدام هذه الخاصية للحصول على صيغة واحدة تتميز بأن جميع قيمها الموجبة أولية. ^{[ 58 ]}

ومن الأمثلة الأخرى على الصيغ المولدة للأعداد الأولية نظرية ميلز ونظرية رايت . وتؤكد هذه الصيغ وجود ثوابت حقيقية.${\displaystyle A>1}$و${\displaystyle \mu }$بحيث

${\displaystyle \left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor }$

أولية لأي عدد طبيعي${\displaystyle n}$في الصيغة الأولى، وأي عدد من الأسس في الصيغة الثانية. ^{[ 60 ]} هنا${\displaystyle \lfloor {}\cdot {}\rfloor }$يمثل دالة الجزء الصحيح ، وهو أكبر عدد صحيح أصغر من أو يساوي العدد المطلوب. ومع ذلك، لا تُعد هذه الدوال مفيدة لتوليد الأعداد الأولية، إذ يجب توليد الأعداد الأولية أولاً لحساب قيمها .${\displaystyle A}$أو​${\displaystyle \mu .}$^{[ 58 ]}

طُرحت العديد من التخمينات المتعلقة بالأعداد الأولية. ورغم بساطة صياغتها، إلا أن العديد من هذه التخمينات صمدت أمام البراهين لعقود: فجميع مسائل لاندو الأربع من عام 1912 لا تزال دون حل. ^{[ 61 ]} إحداها تخمين غولدباخ ، الذي ينص على أن كل عدد زوجي ⁠${\displaystyle n}$أكبر من​${\displaystyle 2}$يمكن كتابة ⁠ كمجموع عددين أوليين. ^{[ 62 ]} اعتبارًا من عام 2014تم التحقق من هذه الفرضية لجميع الأرقام حتى${\displaystyle n=4\cdot 10^{18}.}$^{[ 63 ]} تم إثبات عبارات أضعف من هذه؛ على سبيل المثال،نظرية فينوغرادوفعلى أنه يمكن كتابة أي عدد فردي كبير بما فيه الكفاية على أنه مجموع ثلاثة أعداد أولية. ^{[ 64 ]} وتنص نظرية تشينعلى أنه يمكن التعبير عن أي عدد زوجي كبير بما فيه الكفاية على أنه مجموع عدد أولي وعددشبه أولي(ناتج ضرب عددين أوليين). ^{[ 65 ]} كذلك، يمكن كتابة أي عدد زوجي أكبر من 10 على أنه مجموع ستة أعداد أولية. ^{[ 66 ]} يُطلق على فرع نظرية الأعداد الذي يدرس هذه المسائل اسمنظرية الأعداد الجمعية. ^{[ 67 ]}

نوع آخر من المسائل يتعلق بالفجوات الأولية ، أي الفروقات بين الأعداد الأولية المتتالية. ويمكن إثبات وجود فجوات أولية كبيرة كيفما شاء المرء بملاحظة أن المتتالية${\displaystyle n!+2,n!+3,\dots ,n!+n}$يتكون من${\displaystyle n-1}$الأعداد المركبة، لأي عدد طبيعي${\displaystyle n.}$^{[ 68 ]} مع ذلك، تظهر فجوات الأعداد الأولية الكبيرة في وقت أبكر بكثير مما يُظهره هذا الاستدلال. ^{[ 69 ]} على سبيل المثال، تقع أول فجوة بين الأعداد الأولية بطول 8 بين العددين الأوليين 89 و97، ^{[ 70 ]} وهي أصغر بكثير من${\displaystyle 8!=40320.}$يُفترض وجود عدد لا نهائي من الأعداد الأولية التوأم ، أي أزواج من الأعداد الأولية التي يكون الفرق بينها 2؛ وهذا ما يُعرف بفرضية الأعداد الأولية التوأم . وتنص فرضية بولينياك بشكل أعم على أنه لكل عدد صحيح موجب${\displaystyle k,}$يوجد عدد لا نهائي من أزواج الأعداد الأولية المتتالية التي تختلف بمقدار${\displaystyle 2k.}$^{تشير كل من} حدسية أندريكا ^{[ 71 ]} ،وحدسية بروكارد ^{[ 71 ]} ،وحدسية ليجندر ^{[ 72 ]} ،وحدسيةأوبيرمان ^{[ 73 ] إلى أن} أكبر الفجوات بين الأعداد الأولية من 1إلى${\displaystyle n}$ينبغي أن يكون على الأكثر تقريبًا${\displaystyle {\sqrt {n}},}$وهي نتيجة معروفة أنها تتبع فرضية ريمان، بينما تحدد فرضية كرامر الأقوى بكثير أكبر حجم للفجوة عند ⁠${\displaystyle O((\log n)^{2})}$[ ⁷¹ ]يمكن تعميم الفجوات الأولية ^{لتشمل الأعداد} الأولية${\displaystyle k}$تُعرف هذه الأنماط باسم " المجموعات"، وهي أنماط في الفروق بين أكثر من عددين أوليين. وتُعدّ لانهائيتها وكثافتها موضوعحدسية هاردي-ليتلوود الأولى، والتي يمكن تبريرها بالقاعدةالاستدلالية القائلةبأن الأعداد الأولية تتصرف بشكل مشابه لتسلسل عشوائي من الأعداد بكثافة معطاة بنظرية الأعداد الأولية. ^{[ 74 ]}

يعتمد برهان أويلر على وجود عدد لا نهائي من الأعداد الأولية على مجموع مقلوبات الأعداد الأولية.

${\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}.}$

أثبت أويلر أنه لأي عدد حقيقي اختياري${\displaystyle x}$يوجد عدد أولي${\displaystyle p}$والتي يكون هذا المجموع فيها أكبر من${\displaystyle x}$[ ^{77 ]} هذا يدل على وجود عدد لا نهائي من الأعداد الأولية، لأنه لو كان عدد الأعداد الأولية محدودًا ،لكان المجموع سيصل إلى قيمته القصوى عند أكبر عدد أولي بدلاً من أن ينمو متجاوزًا كل عدد أولي ^. ${\displaystyle x}$. يُوصف معدل نمو هذا المجموع بدقة أكبر بواسطة نظرية ميرتنز الثانية . ^{[ 78 ]} وللمقارنة، فإن المجموع

${\displaystyle {\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}}$

لا ينمو إلى ما لا نهاية كما${\displaystyle n}$يؤول إلى اللانهاية (انظر مسألة بازل ). وبهذا المعنى، تظهر الأعداد الأولية أكثر من مربعات الأعداد الطبيعية، على الرغم من أن كلتا المجموعتين لانهائيتان. ^{[ 79 ]} تنص نظرية برون على أن مجموع مقلوبات الأعداد الأولية التوأم ،

${\displaystyle \left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots ,}$

هي محدودة. وبسبب نظرية برون، لا يمكن استخدام طريقة أويلر لحل تخمين الأعداد الأولية التوأم ، الذي ينص على وجود عدد لا نهائي من الأعداد الأولية التوأم. ^{[ 79 ]}

دالة عد الأعداد الأولية${\displaystyle \pi (n)}$يُعرَّف بأنه عدد الأعداد الأولية التي لا تزيد عن${\displaystyle n}$[ ^{80 ] على} سبيل المثال ،${\displaystyle \pi (11)=5}$بما أن هناك خمسة أعداد أولية أصغر من أو تساوي 11، فإن طرقًا مثل خوارزمية مايسل-ليمر يمكنها حساب القيم الدقيقة لـ${\displaystyle \pi (n)}$أسرع من إمكانية سرد كل عدد أولي حتى${\displaystyle n}$[ ^{81 ]} تنصنظرية الأعداد الأولية ^على أن${\displaystyle \pi (n)}$يقترب من${\displaystyle n/\log n}$، والذي يُشار إليه بـ

${\displaystyle \pi (n)\sim {\frac {n}{\log n}},}$

ويعني ذلك أن نسبة${\displaystyle \pi (n)}$يقترب الكسر الموجود في الطرف الأيمن من 1 عندما${\displaystyle n}$يتزايد إلى ما لا نهاية. ^{[ 82 ]} وهذا يعني أن احتمال أن يكون عدد مختار عشوائيًا أقل من${\displaystyle n}$العدد الأولي يتناسب عكسيًا (تقريبًا) مع عدد الأرقام فيه ${\displaystyle n}$[ ⁸³ ] وهذا ^{يعني أيضاً} أن${\displaystyle n}$العدد الأولي رقم n يتناسب مع${\displaystyle n\log n}$^{[ 84 ]} وبالتالي فإن متوسط ​​حجم الفجوة الأولية يتناسب مع⁠${\displaystyle \log n}$[ ⁶⁹ ] تقدير أكثر ^{دقة لـ}${\displaystyle \pi (n)}$يتم إعطاؤها بواسطة التكامل اللوغاريتمي للإزاحة ^{[ 82 ]}

${\displaystyle \pi (n)\sim \operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\log t}}.}$

المتتابعة الحسابية هي سلسلة أعداد منتهية أو غير منتهية بحيث يكون الفرق بين كل عددين متتاليين فيها متساوياً. ^{[ 85 ]} يُسمى هذا الفرق معيار المتتابعة. ^{[ 86 ]} على سبيل المثال،

${\displaystyle 3,12,21,30,39,...,}$

هي متتالية حسابية لانهائية بمعامل 9. في المتتالية الحسابية، يكون لجميع الأعداد نفس الباقي عند قسمتها على المعامل؛ في هذا المثال، الباقي هو 3. ولأن كلاً من المعامل 9 والباقي 3 من مضاعفات 3، فإن كل عنصر في المتتالية هو أيضًا من مضاعفات 3. لذلك، تحتوي هذه المتتالية على عدد أولي واحد فقط، وهو 3 نفسه. بشكل عام، المتتالية اللانهائية

${\displaystyle a,a+q,a+2q,a+3q,\dots }$

لا يمكن أن يكون للعدد أكثر من عدد أولي واحد إلا إذا كان باقي قسمته${\displaystyle a}$ومعامل المرونة​${\displaystyle q}$تكون الأعداد الأولية نسبياً. إذا كانت الأعداد الأولية نسبياً، فإن نظرية ديريشليه حول المتتابعات الحسابية تنص على أن المتتابعة تحتوي على عدد لا نهائي من الأعداد الأولية. ^{[ 87 ]}

الأعداد الأولية في المتتابعات الحسابية بتردد 9. يُظهر كل صف من الشريط الأفقي الرفيع إحدى المتتابعات التسع الممكنة بتردد 9، مع تمييز الأعداد الأولية باللون الأحمر. تحتوي متتابعات الأعداد التي ترددها 0 أو 3 أو 6 بتردد 9 على عدد أولي واحد على الأكثر (العدد 3)؛ أما متتابعات الأعداد المتبقية التي ترددها 1 أو 2 أو 4 أو 5 أو 7 أو 8 بتردد 9، فتحتوي على عدد لا نهائي من الأعداد الأولية، مع تقارب عدد الأعداد الأولية في كل متتابعة.

تُبيّن نظرية غرين -تاو وجود متتابعات حسابية منتهية طويلة كيفما كانت، تتكون فقط من أعداد أولية. ^{[ 34 ] [ 88 ]}

أشار أويلر إلى أن الدالة

${\displaystyle n^{2}-n+41}$

ينتج أعدادًا أولية لـ${\displaystyle 1\leq n\leq 40}$على الرغم من ظهور الأعداد المركبة ضمن قيمها اللاحقة. ^{[ 89 ] [ 90 ]} وقد أدى البحث عن تفسير لهذه الظاهرة إلى نظرية الأعداد الجبرية العميقة لأعداد هيجنر ومسألة عدد الفئات . ^{[ 91 ]} تتنبأ حدسية هاردي-ليتلوود F بكثافة الأعداد الأولية بين قيم كثيرات الحدود التربيعية ذات المعاملات الصحيحة بدلالة التكامل اللوغاريتمي ومعاملات كثيرة الحدود. لم يُثبت حتى الآن أن أي كثيرة حدود تربيعية تأخذ عددًا لا نهائيًا من القيم الأولية. ^{[ 92 ]}

يُرتب حلزون أولام ^{[ 93 ]} الأعداد الطبيعية في شبكة ثنائية الأبعاد، حلزونية الشكل في مربعات متحدة المركز تحيط بنقطة الأصل مع تمييز الأعداد الأولية. بصريًا، تبدو الأعداد الأولية وكأنها تتجمع على أقطار معينة دون غيرها، مما يشير إلى أن بعض كثيرات الحدود التربيعية تأخذ قيمًا أولية أكثر من غيرها. ^{[ 92 ]}

افترض عالم الرياضيات الروسي فيكتور بونياكوفسكي في عام 1857 أن أي متعددة حدود ذات متغير واحد${\displaystyle f(x)}$باستخدام معاملات صحيحة، سينتج عدد لا نهائي من الأعداد الأولية في المتتالية${\displaystyle f(1),f(2),f(3),\dots }$يجب أن تستوفي متعددة الحدود الشروط التالية: أن يكون معاملها الرئيسي موجبًا، وأن تكون غير قابلة للاختزال على الأعداد النسبية، وألا يكون لقيمة هذه المتتالية أي عامل مشترك أكبر من 1. وقد عُممت هذه الفرضية بواسطة فرضية H لعالم الرياضيات البولندي أندريه شينزل ، ثم وُسعت لاحقًا لتشمل متعددات الحدود متعددة المتغيرات في فرضية ديكسون ، ثم في فرضية باتمان-هورن . ^{[ 94 ]}

تُعدّ فرضية ريمان واحدة من أشهر المسائل غير المحلولة في الرياضيات، ويعود تاريخها إلى عام 1859، وهي إحدى مسائل جائزة الألفية ، والتي تسأل عن مكان أصفار دالة زيتا لريمان .${\displaystyle \zeta (s)}$توجد هذه الدالة. وهي دالة تحليلية على الأعداد المركبة . ^{[ 95 ]} بالنسبة للأعداد المركبة${\displaystyle s}$بجزء حقيقي أكبر من واحد، فإنها تساوي مجموعًا لانهائيًا على جميع الأعداد الصحيحة، وحاصل ضرب لانهائي على الأعداد الأولية. $${\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}.}$$ تُسمى هذه المساواة بين المجموع والضرب، التي اكتشفها أويلر، بضرب أويلر . ^{[ 96 ]} يمكن اشتقاق ضرب أويلر من النظرية الأساسية للحساب، ويُظهر العلاقة الوثيقة بين دالة زيتا والأعداد الأولية. ^{[ 97 ]} ويؤدي ذلك إلى برهان آخر على وجود عدد لا نهائي من الأعداد الأولية: فلو كان عددها محدودًا فقط، لكانت مساواة المجموع والضرب صحيحة أيضًا عند ⁠${\displaystyle s=1}$لكن المجموع سيتباعد (إنها متسلسلة توافقية ).${\displaystyle 1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots }$) بينما سيكون الناتج محدودًا، وهو تناقض. ^{[ 98 ]}

تنص فرضية ريمان على أن أصفار دالة زيتا إما أعداد زوجية سالبة، أو أعداد مركبة جزءها الحقيقي يساوي 1/2. ^{[ 99 ]} استند البرهان الأصلي لنظرية الأعداد الأولية إلى صيغة ضعيفة من هذه الفرضية، وهي أنه لا توجد أصفار جزءها الحقيقي يساوي 1، ^{[ 100 ] [ 101 ]} على الرغم من وجود براهين أخرى أبسط. ^{[ 102 ]} يمكن التعبير عن دالة عد الأعداد الأولية بصيغة ريمان الصريحة كمجموع، حيث يأتي كل حد من أحد أصفار دالة زيتا؛ الحد الرئيسي لهذا المجموع هو التكامل اللوغاريتمي، وتتسبب الحدود المتبقية في تذبذب المجموع أعلى وأسفل الحد الرئيسي. ^{[ 103 ]} وبهذا المعنى، تتحكم الأصفار في مدى انتظام توزيع الأعداد الأولية. إذا كانت فرضية ريمان صحيحة، فستكون هذه التقلبات صغيرة، وسيظل التوزيع التقاربي للأعداد الأولية الذي تنص عليه نظرية الأعداد الأولية ساريًا على فترات أقصر بكثير (طولها حوالي الجذر التربيعي لـ ⁠${\displaystyle x}$للفترات القريبة من رقم معين${\displaystyle x}$) . ^{[ 101 ]}

يُعدّل الحساب النمطي الحساب المعتاد باستخدام الأرقام فقط .${\displaystyle \{0,1,2,\dots ,n-1\}}$، بالنسبة لعدد طبيعي${\displaystyle n}$يُسمى هذا العدد بالمعامل. ويمكن تمثيل أي عدد طبيعي آخر في هذا النظام عن طريق استبداله بباقي قسمته على${\displaystyle n}$[ 104 ^{] تُحسب المجاميع والفروق والضربات المعيارية بإجراء نفس عملية} الإحلال بالباقي على نتيجة الجمع أو الفرق أو الضرب المعتاد للأعداد الصحيحة. ^{[ 105 ] تساوي} الأعداد الصحيحة يقابله التطابق في الحساب المعياري :${\displaystyle x}$و​​${\displaystyle y}$متطابقة (مكتوبة)${\displaystyle x\equiv y}$mod ⁠${\displaystyle n}$) عندما يكون لهما نفس الباقي بعد القسمة على${\displaystyle n}$[ 106 ^] في هذا النظام العددي، يكون القسمة على جميع الأعداد غير الصفرية ممكناً فقط إذا كان المعامل عدداً أولياً. على سبيل المثال، إذا كان المعامل هو العدد الأولي 7، فإن القسمة على ^{3 ممكنة} :${\displaystyle 2/3\equiv 3{\bmod {7}}}$لأن التخلص من المقامات بضرب كلا الطرفين في 3 يعطي الصيغة الصحيحة .${\displaystyle 2\equiv 9{\bmod {7}}}$ومع ذلك، مع معامل مركب يساوي 6، فإن القسمة على 3 مستحيلة. لا يوجد حل صحيح لـ${\displaystyle 2/3\equiv x{\bmod {6}}}$يؤدي التخلص من المقامات بضرب عدد في 3 إلى جعل الطرف الأيسر يساوي 2، بينما يصبح الطرف الأيمن إما 0 أو 3. في مصطلحات الجبر المجرد ، تعني القدرة على إجراء القسمة أن الحساب النمطي بتردد عدد أولي يُشكل حقلاً ، أو تحديداً حقلاً منتهياً ، بينما تُعطي المعاملات الأخرى حلقة فقط ، وليس حقلاً. ^{[ 107 ]}

يمكن صياغة العديد من النظريات المتعلقة بالأعداد الأولية باستخدام الحساب النمطي. على سبيل المثال، تنص نظرية فيرما الصغرى على أنه إذا${\displaystyle a\not \equiv 0}$(تعديل ⁠${\displaystyle p}$ثم​${\displaystyle a^{p-1}\equiv 1}$(تعديل ⁠${\displaystyle p}$[ 108 ^{] بجمع} هذا ^على جميع خيارات${\displaystyle a}$يعطي المعادلة

${\displaystyle \sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}},}$

صالحة في أي وقت${\displaystyle p}$العدد ⁠ أولي. تنص تخمينات جيوجا على أن هذه المعادلة هي أيضًا شرط كافٍ لـ ⁠${\displaystyle p}$أن يكون عددًا أوليًا. ^{[ 109 ]} تنص نظرية ويلسون على أن العدد الصحيح${\displaystyle p>1}$يكون عدد المضروب أوليًا إذا وفقط إذا كان عدد المضروب أوليًا${\displaystyle (p-1)!}$متطابق مع${\displaystyle -1}$mod ⁠${\displaystyle p}$بالنسبة للعدد المركب ${\displaystyle n=r\cdot s}$هذا غير صحيح، لأن أحد عوامله يقسم كلاً من n و${\displaystyle (n-1)!}$وهكذا​${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$مستحيل. ^{[ 110 ]}

الـ​${\displaystyle p}$-adic order${\displaystyle \nu _{p}(n)}$عدد صحيح${\displaystyle n}$⁠ هو عدد نسخ ⁠${\displaystyle p}$في التحليل إلى العوامل الأولية لـ${\displaystyle n}$. يمكن توسيع المفهوم نفسه من الأعداد الصحيحة إلى الأعداد النسبية عن طريق تعريف ⁠${\displaystyle p}$الرتبة -adic للكسر${\displaystyle m/n}$أن يكون${\displaystyle \nu _{p}(m)-\nu _{p}(n)}$. الـ​${\displaystyle p}$القيمة المطلقة -adic${\displaystyle |q|_{p}}$من أي عدد نسبي${\displaystyle q}$ثم يتم تعريفها على النحو التالي${\displaystyle \vert q\vert _{p}=p^{-\nu _{p}(q)}}$ضرب عدد صحيح في قيمته${\displaystyle p}$تلغي القيمة المطلقة -adic عوامل ⁠${\displaystyle p}$في تحليله إلى عوامله الأولية ، لا يتبقى سوى الأعداد الأولية الأخرى. وكما يمكن قياس المسافة بين عددين حقيقيين بالقيمة المطلقة لفرقهما، يمكن قياس المسافة بين عددين نسبيين بـ${\displaystyle p}$المسافة الأدية ، الـ${\displaystyle p}$القيمة المطلقة للفرق بينهما. وفقًا لهذا التعريف للمسافة، يكون عددان متقاربين (أي أن المسافة بينهما صغيرة) عندما يكون الفرق بينهما قابلاً للقسمة على قوة عالية من .${\displaystyle p}$بنفس الطريقة التي يمكن بها تكوين الأعداد الحقيقية من الأعداد النسبية ومسافاتها، عن طريق إضافة قيم حدية إضافية لتكوين حقل كامل ، فإن الأعداد النسبية مع${\displaystyle p}$يمكن تمديد المسافة -adic إلى مجال كامل مختلف ،${\displaystyle p}$الأعداد -adic . ^{[ 111 ] [ 112 ]}

يمكن تعميم هذه الصورة للترتيب والقيمة المطلقة والحقل الكامل المشتق منهما لتشمل حقول الأعداد الجبرية وتقييماتها (بعض التطبيقات من المجموعة الضربية للحقل إلى مجموعة جمعية مرتبة كليًا ، وتُسمى أيضًا بالترتيبات)، والقيم المطلقة (بعض التطبيقات الضربية من الحقل إلى الأعداد الحقيقية، وتُسمى أيضًا بالمعايير )، ^{[ 111 ]} والمواضع (امتدادات للحقول الكاملة حيث يكون الحقل المعطى مجموعة كثيفة ، وتُسمى أيضًا بالإكمالات). ^{[ 113 ]} على سبيل المثال، يُعد الامتداد من الأعداد النسبية إلى الأعداد الحقيقية موضعًا تكون فيه المسافة بين الأعداد هي القيمة المطلقة المعتادة لفرقها. سيكون التطبيق المقابل لمجموعة جمعية هو لوغاريتم القيمة المطلقة، على الرغم من أن هذا لا يفي بجميع متطلبات التقييم. وفقًا لنظرية أوستروفسكي ، وحتى مفهوم طبيعي للتكافؤ، فإن الأعداد الحقيقية و${\displaystyle p}$الأعداد -أدية ، برتبها وقيمها المطلقة، هي القيم المطلقة والمواقع الوحيدة في مجموعة الأعداد النسبية. ^{[ 111 ]} يسمح مبدأ المحلي -العالمي بحل بعض المسائل المتعلقة بالأعداد النسبية عن طريق تجميع الحلول من كل موقع من مواقعها، مما يؤكد مجددًا أهمية الأعداد الأولية في نظرية الأعداد. ^{[ 114 ]}

الحلقة التبديلية هي بنية جبرية تُعرَّف فيها عمليات الجمع والطرح والضرب. الأعداد الصحيحة هي حلقة، وقد عُمِّمت الأعداد الأولية في الأعداد الصحيحة إلى حلقات بطريقتين مختلفتين: العناصر الأولية والعناصر غير القابلة للاختزال . العنصر ⁠${\displaystyle p}$من حلقة​${\displaystyle R}$يُطلق على العدد الأولي اسم العدد الأولي إذا كان غير صفري، وليس له معكوس ضربي (أي أنه ليس عددًا محايدًا )، ويحقق الشرط التالي: كلما كان${\displaystyle p}$يقسم الناتج${\displaystyle xy}$من عنصرين من ⁠${\displaystyle R}$كما أنه يقسم واحداً على الأقل من${\displaystyle x}$أو​​${\displaystyle y}$العنصر غير قابل للاختزال إذا لم يكن عنصرًا محايدًا ولا ناتج ضرب عنصرين آخرين غير محايدين. في حلقة الأعداد الصحيحة، تشكل العناصر الأولية وغير القابلة للاختزال نفس المجموعة.

${\displaystyle \{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,.}$

في أي حلقة، تكون جميع العناصر الأولية غير قابلة للاختزال. لا يصح العكس بشكل عام، ولكنه يصح بالنسبة لمجالات التحليل الفريدة . ^{[ 115 ]}

تظل النظرية الأساسية للحساب سارية (بحكم تعريفها) في مجالات التحليل الفريدة. ومن أمثلة هذه المجالات الأعداد الصحيحة الغاوسية .${\displaystyle \mathbb {Z} [i]}$، حلقة الأعداد المركبة من الشكل${\displaystyle a+bi}$أين​${\displaystyle i}$يرمز إلى الوحدة التخيلية و${\displaystyle a}$و​​${\displaystyle b}$الأعداد الصحيحة هي أعداد صحيحة اختيارية. تُعرف عناصرها الأولية بالأعداد الأولية الغاوسية . ليس كل عدد أولي بين الأعداد الصحيحة يبقى أوليًا في الأعداد الغاوسية؛ على سبيل المثال، يمكن كتابة العدد 2 كحاصل ضرب عددين أوليين غاوسيين.${\displaystyle 1+i}$و​${\displaystyle 1-i}$الأعداد الأولية النسبية (العناصر الأولية في الأعداد الصحيحة) التي تُطابق 3 بتردد 4 هي أعداد أولية غاوسية، بينما الأعداد الأولية النسبية التي تُطابق 1 بتردد 4 ليست كذلك. ^{[ 116 ]} هذه نتيجة لنظرية فيرما حول مجموع مربعين ، والتي تنص على أن العدد الأولي الفردي${\displaystyle p}$يمكن التعبير عن ⁠ كمجموع مربعين، ⁠${\displaystyle p=x^{2}+y^{2}}$وبالتالي يمكن تحليلها إلى عواملها الأولية .${\displaystyle p=(x+iy)(x-iy)}$، بالضبط متى${\displaystyle p}$⁠ هو 1 mod 4. ^{[ 117 ]}

ليست كل حلقة مجال تحليل فريد. على سبيل المثال، في حلقة الأعداد${\displaystyle a+b{\sqrt {-5}}}$(للأعداد الصحيحة )${\displaystyle a}$و​​${\displaystyle b}$) العدد${\displaystyle 21}$له تحليلان${\displaystyle 21=3\cdot 7=(1+2{\sqrt {-5}})(1-2{\sqrt {-5}})}$حيث لا يمكن اختزال أي من العوامل الأربعة أكثر من ذلك، لذا لا يوجد تحليل وحيد لها. ولتوسيع نطاق التحليل الوحيد ليشمل فئة أكبر من الحلقات، يمكن استبدال مفهوم العدد بمفهوم المثالي ، وهو مجموعة جزئية من عناصر الحلقة تحتوي على جميع مجاميع أزواج عناصرها، وجميع نواتج ضرب عناصرها في عناصر الحلقة. تُعدّ المثاليّات الأولية ، التي تُعمّم العناصر الأولية بمعنى أن المثالي الرئيسي المُوَلَّد بواسطة عنصر أولي هو مثالي أولي، أداةً وموضوع دراسة مهمين في الجبر التبادلي ، ونظرية الأعداد الجبرية، والهندسة الجبرية . المثاليّات الأولية لحلقة الأعداد الصحيحة هي المثاليّات ...${\displaystyle (0)}$،​​${\displaystyle (2)}$،​​${\displaystyle (3)}$،​​${\displaystyle (5)}$،​​${\displaystyle (7)}$،​​${\displaystyle (11)}$... تُعمم النظرية الأساسية للحساب إلى نظرية لاسكر-نوثر ، التي تعبر ^عن كل مثالي في حلقة تبديلية نوثرية كتقاطع للمثاليات الأولية ، وهي التعميمات المناسبة لقوى الأعداد الأولية . [ ^{118 ]}

طيف الحلقة هو فضاء هندسي تمثل نقاطه المُثُل الأولية للحلقة. ^{[ 119 ]} تستفيد الهندسة الحسابية أيضًا من هذا المفهوم، وتوجد العديد من المفاهيم في كلٍ من الهندسة ونظرية الأعداد. على سبيل المثال، يُشابه تحليل المُثُل الأولية أو تفرعها عند رفعها إلى حقل امتداد ، وهي مسألة أساسية في نظرية الأعداد الجبرية، التفرع في الهندسة . بل يمكن لهذه المفاهيم أن تُساعد في مسائل نظرية الأعداد التي تُعنى بالأعداد الصحيحة فقط. على سبيل المثال، يمكن استخدام المُثُل الأولية في حلقة الأعداد الصحيحة لحقول الأعداد التربيعية في إثبات التبادلية التربيعية ، وهي عبارة تتعلق بوجود الجذور التربيعية بتردد الأعداد الأولية الصحيحة. ^{[ 120 ]} أدت المحاولات المبكرة لإثبات نظرية فيرما الأخيرة إلى تقديم كومر للأعداد الأولية المنتظمة ، وهي أعداد أولية صحيحة مرتبطة بفشل التحليل الفريد في الأعداد الصحيحة الدائرية . ^{[ 121 ]} تتناول نظرية كثافة تشيبوتاريف مسألة عدد الأعداد الأولية الصحيحة التي تُحلل إلى حاصل ضرب عدة مثاليات أولية في حقل عددي جبري ، والتي (عند تطبيقها على الأعداد الصحيحة الدائرية) تُعتبر نظرية ديريشليه حول الأعداد الأولية في المتتابعات الحسابية حالة خاصة منها. ^{[ 122 ]}

في نظرية الزمر المنتهية، تشير نظريات سيلو إلى أنه إذا كانت قوة لعدد أولي${\displaystyle p^{n}}$إذا قسمت قيمة رتبة مجموعة ما ، فإن المجموعة تحتوي على مجموعة جزئية من الرتبة ⁠${\displaystyle p^{n}}$بحسب نظرية لاغرانج ، فإن أي زمرة ذات رتبة أولية هي زمرة دورية ، وبحسب نظرية بيرنسايد، فإن أي زمرة تكون رتبتها قابلة للقسمة على عددين أوليين فقط تكون قابلة للحل . ^{[ 123 ]}

أبسط طريقة للتحقق من أولية عدد صحيح معين ⁠${\displaystyle n}$تُسمى هذه الطريقة بالقسمة التجريبية . تقسم هذه الطريقة${\displaystyle n}$⁠ لكل عدد صحيح من 2 حتى الجذر التربيعي لـ ⁠${\displaystyle n}$أي عدد صحيح من هذا القبيل يقسم${\displaystyle n}$يُؤسس بالتساوي​${\displaystyle n}$باعتباره عددًا مركبًا؛ وإلا فهو عدد أولي. لا داعي للتحقق من الأعداد الصحيحة الأكبر من الجذر التربيعي لأنه كلما${\displaystyle n=a\cdot b}$، أحد العاملين${\displaystyle a}$و​​${\displaystyle b}$أقل من أو يساوي الجذر التربيعي لـ${\displaystyle n}$. يتمثل أحد التحسينات الأخرى في التحقق من الأعداد الأولية فقط كعوامل في هذا النطاق. ^{[ 126 ]} على سبيل المثال، للتحقق مما إذا كان العدد 37 عددًا أوليًا، تقسمه هذه الطريقة على الأعداد الأولية في النطاق من 2 إلى${\displaystyle {\sqrt {37}}}$⁠ ، وهي 2 و 3 و 5. كل قسمة تنتج باقي قسمة غير صفري، لذا فإن 37 هو عدد أولي بالفعل.

على الرغم من سهولة وصف هذه الطريقة، إلا أنها غير عملية لاختبار أولية الأعداد الصحيحة الكبيرة، لأن عدد الاختبارات التي تُجريها يزداد أُسّيًا مع ازدياد عدد أرقام هذه الأعداد. ^{[ 127 ]} ومع ذلك، لا تزال القسمة التجريبية تُستخدم، بحد أدنى لحجم المقسوم عليه أقل من الجذر التربيعي، لاكتشاف الأعداد المركبة ذات العوامل الصغيرة بسرعة، قبل استخدام طرق أكثر تعقيدًا على الأعداد التي تجتاز هذا المعيار. ^{[ 128 ]}

قبل ظهور الحواسيب، كانت تُطبع عادةً جداول رياضية تُدرج جميع الأعداد الأولية أو تحليلاتها إلى عواملها الأولية حتى حدٍّ معين. ^{[ 129 ]} تُعرف أقدم طريقة معروفة لإنشاء قائمة بالأعداد الأولية باسم غربال إراتوستينس. ^{[ 130 ]} يُظهر الرسم المتحرك نسخة مُحسَّنة من هذه الطريقة. ^{[ 131 ]} وهناك طريقة غربلة أخرى أكثر كفاءة من الناحية التقاربية لنفس المسألة، وهي غربال أتكين . ^{[ 132 ]} في الرياضيات المتقدمة، تُطبَّق نظرية الغربال أساليب مماثلة على مسائل أخرى. ^{[ 133 ]}

بعض أسرع الاختبارات الحديثة لتحديد ما إذا كان رقم معين عشوائيًا${\displaystyle n}$تُعدّ خوارزميات تحديد أولية الأعداد خوارزميات احتمالية (أو مونت كارلو )، مما يعني أن لديها فرصة عشوائية ضئيلة لإنتاج إجابة خاطئة. ^{[ 134 ]} على سبيل المثال، اختبار سولوفاي-ستراسن لأولية عدد مُعطى .${\displaystyle p}$يختار رقمًا​${\displaystyle a}$بشكل عشوائي من 2 إلى${\displaystyle p-2}$ويستخدم الأسس المعيارية للتحقق مما إذا${\displaystyle a^{(p-1)/2}\pm 1}$يقبل القسمة على${\displaystyle p}$[ ^{د ]} إذاكان الأمر كذلك، فالإجابة نعم، وإلا فالإجابة لا ^. إذا${\displaystyle p}$إذا كان العدد أوليًا بالفعل، فسيجيب دائمًا بنعم، ولكن إذا${\displaystyle p}$إذا كان المتغير مركباً، فإن الإجابة تكون بنعم باحتمالية لا تتجاوز 1/2، ولا باحتمالية لا تقل عن 1/2. ^{[ 135 ]} إذا تكرر هذا الاختبار ...${\displaystyle n}$إذا تم اختبار نفس الرقم عدة مرات، فإن احتمال نجاح رقم مركب في كل مرة هو على الأكثر${\displaystyle 1/2^{n}}$ولأن هذا يتناقص أُسّيًا مع عدد الاختبارات، فإنه يوفر ثقة عالية (وإن لم تكن يقينًا) بأن العدد الذي يجتاز الاختبار المتكرر هو عدد أولي. من ناحية أخرى، إذا فشل الاختبار في أي وقت، فإن العدد يكون بالتأكيد عددًا مركبًا. ^{[ 136 ]} يُطلق على العدد المركب الذي يجتاز مثل هذا الاختبار اسم عدد شبه أولي . ^{[ 135 ]}

في المقابل، تضمن بعض الخوارزميات الأخرى صحة إجابتها دائمًا: إذ تُحدد الأعداد الأولية دائمًا على أنها أولية، والأعداد المركبة دائمًا على أنها مركبة. على سبيل المثال، ينطبق هذا على القسمة التجريبية. تشمل الخوارزميات ذات المخرجات المضمونة الصحة كلاً من الخوارزميات الحتمية (غير العشوائية)، مثل اختبار AKS للأعداد الأولية ^{[ 137 ]} ، وخوارزميات لاس فيغاس العشوائية حيث لا تؤثر الاختيارات العشوائية التي تُجريها الخوارزمية على إجابتها النهائية، مثل بعض أنواع إثبات أولية المنحنى الإهليلجي ^{[ 134 ]} . عندما تُثبت طريقة المنحنى الإهليلجي أن عددًا ما أولي، فإنها تُقدم شهادة أولية يُمكن التحقق منها بسرعة ^{[ 138 ]} . يُعد اختبار أولية المنحنى الإهليلجي الأسرع عمليًا بين اختبارات أولية الأعداد المضمونة الصحة، ولكنه يعتمد فقط على حجج استدلالية لتفسير سرعته بدلًا من البراهين الدقيقة. أثبت اختبار AKS للأعداد الأولية أنه يعمل في وقت متعدد الحدود ، ولكن بمعامل متعدد الحدود أعلى، مما يجعله أبطأ عمليًا من اختبار المنحنى الإهليلجي. ^{[ 139 ]} يمكن استخدام هذه الطرق لتوليد أعداد أولية عشوائية كبيرة، وذلك بتوليد أعداد عشوائية واختبارها حتى العثور على عدد أولي؛ عند القيام بذلك، يمكن لاختبار احتمالي أسرع استبعاد معظم الأعداد المركبة بسرعة قبل استخدام خوارزمية مضمونة الصحة للتحقق من أن الأعداد المتبقية أولية. ^{[ هـ ]}

يسرد الجدول التالي بعضًا من هذه الاختبارات. ويُعطى وقت تشغيلها بوحدة ⁠${\displaystyle n}$، الرقم المراد اختباره، وبالنسبة للخوارزميات الاحتمالية، الرقم ⁠${\displaystyle k}$من الاختبارات التي تم إجراؤها. علاوة على ذلك،${\displaystyle \varepsilon }$هو عدد موجب صغير بشكل تعسفي، وlog هو اللوغاريتم لأساس غير محدد. تعني صيغة Big O أنه يجب ضرب كل حد زمني بمعامل ثابت لتحويله من وحدات لا بُعدية إلى وحدات زمنية؛ يعتمد هذا المعامل على تفاصيل التنفيذ مثل نوع الحاسوب المستخدم لتشغيل الخوارزمية، ولكنه لا يعتمد على معلمات الإدخال .${\displaystyle n}$و​​${\displaystyle k}$⁠ .

امتحان	تم تطويره في	يكتب	مدة التشغيل	ملحوظات	مراجع
اختبار AKS الأولي	2002	حتمية	${\displaystyle O((\log n)^{6+\varepsilon })}$		[ 137 ] [ 140 ]
إثبات أولية المنحنى الإهليلجي	1986	لاس فيغاس	${\displaystyle O((\log n)^{4+\varepsilon })}$بشكل استدلالي		[ 139 ]
اختبار بايلي-PSW للأوليية	1980	مونت كارلو	${\displaystyle O((\log n)^{2+\varepsilon })}$		[ 141 ] [ 142 ]
اختبار ميلر-رابين للأولوية	1980	مونت كارلو	${\displaystyle O(k(\log n)^{2+\varepsilon })}$	احتمالية الخطأ${\displaystyle 4^{-k}}$	[ 143 ]
اختبار سولوفاي-ستراسين للبدائية	1977	مونت كارلو	${\displaystyle O(k(\log n)^{2+\varepsilon })}$	احتمالية الخطأ${\displaystyle 2^{-k}}$	[ 143 ]

بالإضافة إلى الاختبارات المذكورة سابقًا والتي تنطبق على أي عدد طبيعي، يمكن اختبار أولية بعض الأعداد ذات الصيغة الخاصة بسرعة أكبر. على سبيل المثال، يمكن لاختبار لوكاس-ليمر للأولية تحديد ما إذا كان عدد ميرسين (أقل بواحد من قوة العدد اثنين ) أوليًا، بشكل حتمي، في نفس الوقت الذي يستغرقه تكرار واحد لاختبار ميلر-رابين. ^{[ 144 ]} لهذا السبب، منذ عام 1992 ( حتى أكتوبر 2024) كان أكبر عدد أولي معروف دائمًا هو عدد ميرسين الأولي. ^{[ 145 ]} ويُفترض أن هناك عددًا لا نهائيًا من أعداد ميرسين الأولية. ^{[ 146 ]}

يُبيّن الجدول التالي أكبر الأعداد الأولية المعروفة من أنواع مختلفة. وقد تم اكتشاف بعض هذه الأعداد الأولية باستخدام الحوسبة الموزعة . في عام ٢٠٠٩، فاز مشروع البحث عن أعداد ميرسين الأولية على الإنترنت بجائزة قدرها ١٠٠,٠٠٠ دولار أمريكي لاكتشافه أول عدد أولي يحتوي على ١٠ ملايين رقم على الأقل. ^{[ ١٤٧ ]} كما تُقدّم مؤسسة الحدود الإلكترونية جوائز بقيمة ١٥٠,٠٠٠ دولار و٢٥٠,٠٠٠ دولار للأعداد الأولية التي تحتوي على ١٠٠ مليون رقم على الأقل ومليار رقم على الأقل، على التوالي. ^{[ ١٤٨ ]}

بفرض عدد صحيح مركب${\displaystyle n}$تُعرف مهمة إيجاد عامل أولي واحد (أو جميع العوامل الأولية) باسم تحليل العدد إلى عوامله الأولية .${\displaystyle n}$. إنها أصعب بكثير من اختبار أولية العدد، ^{[ 156 ]} وعلى الرغم من وجود العديد من خوارزميات التحليل إلى عوامل، إلا أنها أبطأ من أسرع طرق اختبار أولية العدد. يمكن استخدام القسمة التجريبية وخوارزمية بولارد رو لإيجاد عوامل صغيرة جدًا من ⁠${\displaystyle n}$[ 128 ^{] ويمكن أن يكون تحليل} المنحنى الإهليلجيفعالاً عندما${\displaystyle n}$يحتوي على عوامل متوسطة الحجم. ^{[ 157 ]} تشمل الطرق المناسبة للأعداد الكبيرة العشوائية التي لا تعتمد على حجم عواملها الغربال التربيعي وغربال حقل الأعداد العام . كما هو الحال مع اختبار أولية الأعداد، توجد أيضًا خوارزميات تحليل تتطلب أن يكون لمدخلاتها شكل خاص، بما في ذلك غربال حقل الأعداد الخاص . ^{[ 158 ]} اعتبارًا من ديسمبر 2019 أكبر عدد معروف تم تحليله بواسطة خوارزمية عامة الأغراض هو RSA-240 ، والذي يحتوي على 240 رقمًا عشريًا (795 بتًا) وهو ناتج ضرب عددين أوليين كبيرين. ^{[ 159 ]}

يمكن لخوارزمية شور تحليل أي عدد صحيح إلى عوامله الأولية في عدد كثير الحدود من الخطوات على حاسوب كمومي . ^{[ 160 ]} مع ذلك، لا تستطيع التقنية الحالية تشغيل هذه الخوارزمية إلا للأعداد الصغيرة جدًا. اعتبارًا من أكتوبر 2012 أكبر عدد تم تحليله بواسطة حاسوب كمي يعمل بخوارزمية شور هو 21. ^{[ 161 ]}

تعتمد العديد من خوارزميات التشفير بالمفتاح العام ، مثل RSA وتبادل مفاتيح ديفي -هيلمان ، على الأعداد الأولية الكبيرة (الأعداد الأولية ذات 2048 بت شائعة). ^{[ 162 ]} تعتمد RSA على افتراض أن عملية ضرب عددين (كبيرين) أسهل بكثير (أي أكثر كفاءة) .${\displaystyle x}$و​​${\displaystyle y}$بدلاً من حساب${\displaystyle x}$و​​${\displaystyle y}$( بافتراض أنهما عددان أوليان فيما بينهما ) إذا كان الناتج فقط${\displaystyle xy}$معروف. ^{[ 31 ]} يعتمد تبادل مفاتيح ديفي-هيلمان على وجود خوارزميات فعالة للأس المعياري (حساب ⁠${\displaystyle a^{b}{\bmod {c}}}$) ، بينما يُعتقد أن العملية العكسية ( اللوغاريتم المنفصل ) تمثل مشكلة صعبة. ^{[ 163 ]}

تُستخدم الأعداد الأولية بكثرة في جداول التجزئة . فعلى سبيل المثال، اعتمدت طريقة كارتر وويغمان الأصلية للتجزئة الشاملة على حساب دوال التجزئة عن طريق اختيار دوال خطية عشوائية بتردد أعداد أولية كبيرة. وقد عمم كارتر وويغمان هذه الطريقة إلى${\displaystyle k}$التجزئة المستقلة باستخدام كثيرات الحدود ذات الدرجة الأعلى، مع مراعاة الأعداد الأولية الكبيرة. ^{[ 164 ]} كما هو الحال في دالة التجزئة، تُستخدم الأعداد الأولية لحجم جدول التجزئة فيالتجزئة القائمة على التحقق التربيعيلضمان تغطية تسلسل التحقق للجدول بأكمله. ^{[ 165 ]}

تعتمد بعض طرق التحقق من المجموع الاختباري على رياضيات الأعداد الأولية. على سبيل المثال، تُعرَّف مجاميع التحقق المستخدمة في أرقام الكتاب المعياري الدولي (ISO) بأخذ باقي قسمة العدد على 11، وهو عدد أولي. ولأن 11 عدد أولي، يمكن لهذه الطريقة اكتشاف كل من أخطاء الرقم الواحد وتبديل الأرقام المتجاورة. ^{[ 166 ]} وتستخدم طريقة أخرى للتحقق من المجموع الاختباري، وهي أدلر-32 ، العمليات الحسابية بتردد 65521، وهو أكبر عدد أولي أقل من 11.${\displaystyle 2^{16}}$[ 167 ^] تُستخدم الأعداد الأولية أيضًا في مولدات الأرقام شبه العشوائية، ^{بما في} ذلك مولدات التوافق الخطي ^{[ 168 ]} ومولد ميرسين تويستر . ^{[ 169 ]}

أعداد فيرما الأولية هي أعداد أولية من الشكل

${\displaystyle F_{k}=2^{2^{k}}+1,}$

مع​${\displaystyle k}$عدد صحيح غير سالب . ^{[ 175 ]} سُميت هذه الأعداد نسبةً إلى بيير دي فيرما ، الذي افترض أن جميع هذه الأعداد أولية. الأعداد الخمسة الأولى من هذه الأعداد - 3، 5، 17، 257، و65537 - هي أعداد أولية، ^{[ 176 ]} ولكن${\displaystyle F_{5}}$هو عدد مركب ، وكذلك جميع أعداد فيرما الأخرى التي تم التحقق منها حتى عام 2017. ^{[ 177 ]} عدد منتظم${\displaystyle n}$يمكنشكل هندسي مكون من ستة أضلاع باستخدام المسطرة والفرجارإذا وفقط إذا كانت العوامل الأولية الفردية لـ${\displaystyle n}$( إن وجدت) هي أعداد فيرما الأولية المتميزة. ^{[ 176 ]} وبالمثل، فإن العدد المنتظم${\displaystyle n}$يمكن إنشاء شكل هندسي مكون من ثمانية أضلاع باستخدام المسطرة والفرجار ومنصف الزاوية إذا وفقط إذا كانت العوامل الأولية لـ${\displaystyle n}$هي أي عدد من نسخ العددين 2 أو 3 بالإضافة إلى مجموعة (قد تكون فارغة) منأعداد بيربونت الأولية، وهي أعداد أولية من الشكل ⁠${\displaystyle 2^{a}3^{b}+1}$[ ¹⁷⁸ ]^​​

من الممكن تقسيم أي مضلع محدب إلى${\displaystyle n}$المضلعات المحدبة الأصغر ذات المساحة والمحيط المتساويين، عندما${\displaystyle n}$يمثل قوة لعدد أولي ، ولكن هذا غير معروف بالنسبة للقيم الأخرى لـ${\displaystyle n}$[ ¹⁷⁹ ]^​​

بدءًا من أعمال هيو مونتغمري وفريمان دايسون في سبعينيات القرن الماضي، تكهن علماء الرياضيات والفيزياء بأن أصفار دالة زيتا لريمان مرتبطة بمستويات طاقة الأنظمة الكمومية . ^{[ 180 ] [ 181 ]} كما أن للأعداد الأولية أهمية بالغة في علم المعلومات الكمومية ، وذلك بفضل البنى الرياضية مثل القواعد غير المتحيزة المتبادلة والمقاييس المتناظرة ذات القيم الموجبة الكاملة معلوماتيًا . ^{[ 182 ] [ 183 ]}

تعتمد استراتيجية التطور التي تتبعها حشرات الزيز من جنس ماجيكيكادا على الأعداد الأولية. ^{[ 184 ]} تقضي هذه الحشرات معظم حياتها كيرقات تحت الأرض. ولا تتحول إلى خادرة ثم تخرج من جحورها إلا بعد 7 أو 13 أو 17 عامًا، وعندها تبدأ بالطيران والتكاثر، ثم تموت بعد بضعة أسابيع على الأكثر. ويفترض علماء الأحياء أن أطوال دورات التكاثر هذه، التي تعتمد على الأعداد الأولية، قد تطورت لمنع المفترسات من التزامن مع هذه الدورات. ^{[ 185 ] [ 186 ]} في المقابل، يُفترض أن الفترات الممتدة لعدة سنوات بين الإزهار في نباتات الخيزران هي أعداد سلسة ، لا تحتوي إلا على أعداد أولية صغيرة في تحليلاتها. ^{[ 187 ]}

أثرت الأعداد الأولية في العديد من الفنانين والكتاب. استخدم الملحن الفرنسي أوليفييه ميسيان الأعداد الأولية لابتكار موسيقى غير متناغمة من خلال "الظواهر الطبيعية". في أعمال مثل " ميلاد الرب" (1935) و "أربع دراسات إيقاعية" (1949-1950)، وظّف ميسيان في آنٍ واحدٍ ألحانًا ذات أطوال تُحددها أعداد أولية مختلفة لخلق إيقاعات غير متوقعة: تظهر الأعداد الأولية 41 و43 و47 و53 في الدراسة الثالثة، "أعداد إيقاعية". ووفقًا لميسيان، فإن هذه الطريقة في التأليف الموسيقي "مستوحاة من حركات الطبيعة، حركات حرة وغير متساوية المدة". ^{[ 188 ]}

في روايته الخيالية العلمية " كونتاكت" ، اقترح العالم كارل ساغان إمكانية استخدام التحليل إلى العوامل الأولية كوسيلة لإنشاء مستويات صور ثنائية الأبعاد في التواصل مع الكائنات الفضائية، وهي فكرة طورها بشكل غير رسمي مع عالم الفلك الأمريكي فرانك دريك عام 1975. ^{[ 189 ]} في رواية " الحادثة الغريبة للكلب في الليل" لمارك هادون ، يرتب الراوي أجزاء القصة وفقًا للأعداد الأولية المتتالية كوسيلة للتعبير عن الحالة الذهنية لشخصيتها الرئيسية، وهي مراهق موهوب رياضيًا مصاب بمتلازمة أسبرجر . ^{[ 190 ]} تُستخدم الأعداد الأولية كاستعارة للوحدة والعزلة في رواية باولو جيوردانو "عزلة الأعداد الأولية "، حيث تُصوَّر على أنها "غريبة" بين الأعداد الصحيحة. ^{[ 191 ]} يُقدِّم فيلم الإثارة "سنيكرز" (1992) طريقة خيالية لتحليل الأعداد الكبيرة بسرعة إلى عواملها الأولية، وبالتالي اختراق أنظمة تشفير الكمبيوتر. ^{[ 192 ] [ 193 ] [ 194 ]}