عدد أولي

العدد الأولي والعدد الأول^[1] هو عدد طبيعي أكبر قطعاً من 1، لا يقبل القسمة إلا على نفسه وعلى واحد فقط. يُدعى كل عدد طبيعي أكبر قطعاً من 1 وغير أولي عددا مؤلفا. على سبيل المثال، 5 هو عدد أولي لأنه لا يقبل القسمة إلا على 1 وعلى 5، بينما 6 هو عدد مؤلف لأنه قابل للقسمة على 1، وعلى 2 وعلى 3 وعلى 6. تقيم المبرهنة الأساسية في الحسابيات الدور المركزي للأعداد الأولية في نظرية الأعداد: كل عدد صحيح طبيعي أكبر قطعا من 1 يساوي جُداء (ضَرب) مجموعة وحيدة ما من الأعداد الأولية (بغض النظر عن ترتيب هؤلاء الأعداد داخل هذهِ المجموعة). فإن هذهِ المبرهنة تستلزم إقصاء 1 من لائحة الأعداد الأولية.

لأجل تحديد هل العدد أولي أم لا؟ توجد طريقة سهلة ولكنها بطيئة، تسمى القسمة المتكررة، وتتمثل في قسمة هذا العدد على الأعداد المحصورة بين 2 والجذر التربيعي للعدد المعين. توجد خوارزميات أخرى أكثر فعالية من القسمة، تستعمل في تحديد أولية الأعداد الكبيرة، وخصوصا عندما يتعلق الأمر بأعداد ذات شكل خاص كأعداد ميرسين الأولية. وفي 21 ديسمبر 2018، تألف أكبر عدد أولي تم الوصول إليه من 24,862,048 رقما.^[2]

مجموعة الأعداد الأولية مجموعة غير منتهية. وقد برهن على ذلك أقليدس في حوالي عام 300 قبل الميلاد. لا تعرف صيغة ما، جميع قيمها أعداد أولية. ولكن توزيع الأعداد الأولية يمكن أن يخضع للدرس وأن تقام حولهُ النظريات. إن أول مبرهنة تذهب في هذا الاتجاه هي مبرهنة الأعداد الأولية، والتي بُرهن عليها في نهاية القرن التاسع عشر والتي بموجبها الاحتمال أن يكون عدد طبيعي ما n، اختير بصفة عشوائية، أولياً، يتناسب عكسياً مع عدد الأرقام التي يحتوي عليها هذا العدد. وبتعبير آخر، يتناسب عكسياً مع اللوغارتم الطبيعي للعدد n.

خضعت الأعداد الأولية لبحوث عديدة، مع ذلك تظل الكثير من الأسئلة الأساسية مثل فرضية ريمان وحدسية غولدباخ التي تنص على أن أي عدد زوجي أكبر قطعاً من 2، يمكن أن يكتب على شكل مجموع عددين أوليين، وحدسية الأعداد الأولية التوأم والتي تنص على أن عدد الأزواج من الأعداد الأولية والتي يكون الفرق بينهما مساويا ل2 هو عدد غير منته، وهنالك مسائل غير محلولة حتى الآن بالرغم من مرور أكثر من قرن على طرحها. والسبب الأساسي يعود إلى عدم فهم العلماء لطريقة توزيع الأعداد الأولية، على عكس الأعداد الفردية أو الزوجية على سبيل المثال، وكانت هذه المعضلات سببا في تطورات كثيرة عرفتها نظرية الأعداد، التي اهتمت بالخصائص الجبرية والتحليلية للأعداد. وتستعمل الأعداد الأولية في عدة مجالات في تكنولوجيا المعلومات كالتشفير باستخدام المفتاح المعلن. حيث تعتمد أساساً هذهِ التقنية على خصائص معينة كصعوبة تعميل الأعداد الكبيرة إلى جداء أعداد أولية.

تعريف وأمثلة

يكون عدد طبيعي ما أوليا إذا كان أكبر قطعا من 1 وكان له قاسمان اثنان، 1 والعدد نفسه. الأعداد الطبيعية الأكبر قطعا من 1 والغير أولية قد تسمى أعداداً مركبةً أو مؤلفةً (لا ينبغي الخلط مع الأعداد المركبة والتي تسمى أيضا الأعداد العقدية).

من بين الأعداد الطبيعية المحصورة بين 1 و 6، الأعداد 2 و 3 و 5 أولية، بينما الأعداد 1 و 4 و 6 أعداد غير أولية. أُقصى الواحد من لائحة الأعداد الأولية. 2 عدد أولي لأن القاسمين الوحيدين له هما 1، 2 نفسه. 3 عدد أولي أيضا لأن القاسمين الوحيدين له هما 1، 3 نفسه. قسمة 3 على 2 تعطي باقيا مساويا ل 1. إذن، 3 أولي. 4 عدد غير أولي لأنه بالإضافة إلى 1 و 4 اللذان يقسمانه، 2 أيضا يقسمه:

4 = 2 · 2.

5 عدد أولي لأن 2 و 3 و 4 لا يقسمونه. 6 عدد غير أولي لأنه قابل للقسمة على 2 و 3.

6 = 3 · 2.

جميع الأعداد الأولية - عدا 2 و 5 - تنتهي ب 1 أو 3 أو 7 أو 9 لأن جميع الأعداد التي تنتهي ب 0 أو 2 أو 4 أو 6 أو 8 هي من مضاعفات العدد 2 (تسمى أعدادا زوجية) فليست بالتأكيد أولية، والأعداد التي تنتهي ب 5 هي من مضاعفات العدد 5 فليست أولية أيضاً.

الأعداد الأولية المائة والثمانية والستون الأولى والأصغر من 1000 هي :
2، 3، 5، 7، 11، 13، 17، 19، 23، 29، 31، 37، 41، 43، 47، 53، 59، 61، 67، 71، 73، 79، 83، 89، 97، 101، 103، 107، 109، 113، 127، 131، 137، 139، 149، 151، 157، 163، 167، 173، 179، 181، 191، 193، 197، 199، 211، 223 227، 229، 233، 239، 241، 251، 257، 263، 269، 271، 277، 281، 283، 293، 307، 311، 313، 317، 331، 337، 347، 349، 353، 359، 367، 373، 379، 383، 389، 397، 401، 409، 419، 421، 431، 433، 439، 443، 449، 457، 461، 463، 467، 479، 487، 491، 499، 503، 509، 521، 523، 541، 547، 557، 563، 569، 571، 577، 587، 593، 599، 601، 607، 613، 617، 619، 631، 641، 643، 647، 653، 659، 661، 673، 677، 683، 691، 701، 709، 719، 727، 733، 739، 743، 751، 757، 761، 769، 773، 787، 797، 809، 811، 821، 823، 827، 829، 839، 853، 857، 859، 863، 877، 881، 883، 887، 907، 911، 919، 929، 937، 941، 947، 953، 967، 971، 977، 983، 991، 997.

عادة ما يرمز لمجموعة الأعداد الأولية بالرمز P.

المبرهنة الأساسية في الحسابيات

تنبثق أهمية الأعداد الأولية في نظرية الأعداد وفي الرياضيات عموما من المبرهنة الأساسية في الحسابيات، والتي تنص على أن كل عدد صحيح موجب أكبر من 1، يمكن أن يكتب على شكل جداء أي (ضرب) لعدد أولي واحد أو مجموعة من الأعداد الأولية. هذه المجموعة وحيدة إذا غُض النظر إلى ترتيب الأعداد الأولية التي تُكونها. ونتيجة لذلك، هو أنه يمكن اعتبار الأعداد الأولية الأساس التي بنيت عليه الأعداد الطبيعية. على سبيل المثال،

23244	= 2 · 2 · 3 · 13 · 149
	= 2² · 3 · 13 · 149. حيث 2² يعني مربع 2 أو القوة الثانية ل 2.

أ, 3*7=21

كما في المثال السابق، قد يتكرر نفس العامل الأولي أكثر من مرة. تسمى عملية تحليل عدد n ما إلى جداء عومل أولية : $n = p 1 \cdot p 2 \cdot ... \cdot p t$ تحليل عدد صحيح إلى عوامل. يمكن إذن صياغة المبرهنة الأساسية في الحسابيات كما يلي:

تحليل عدد صحيح إلى عوامل وحيد إذا غُض النظر إلى ترتيب الأعداد الأولية في هذا التحليل. قد تختلف الخوارزميات لإيجاد هذا التحليل، ولكن النتيجة وحيدة ولا تتعلق بالخوارزمية المستعملة.

إذا كان p عددا أوليا وكان يقسم جداء a × b لعددين طبيعيين a و b، فإنه يقسم أحد حدي هذا الجداء، أي أنه يقسم a أو يقسم b. تسمى هاته الخاصية بموضوعة أقليدس. تستعمل في بعض البراهين على وحدة تحليل عدد صحيح إلى جداء أعداد أولية.

هل العدد 1 عدد أولي ؟

لم يعتبر معظم الإغريق العدد 1 على أنه عدد. ولهذا، لم يعتبروه أوليا. بينما في القرن التاسع عشر، اعتبره عدد من علماء الرياضيات أوليا. على سبيل المثال، اللائحة التي كونها ديريك نورمان ليهمر من الأعداد الأولية الأصغر من 10,006,721، والتي طبعت لآخر مرة في عام 1956، ابتدأت بالعدد 1. حتى القرن التاسع عشر، كان علماء الرياضيات يعتبرون 1 عددا أوليا، بما أن تعريف الأعداد الأولية كان آنذاك هو كل عدد لا يقبل القسمة إلا على 1 وعلى نفسه. ويقال أن عالم الرياضيات هنري ليون لوبيغ هو آخر عالم رياضيات اعتبر 1 أوليا. رغم أن الجزء الكبير من الأعمال في الرياضيات يبقى صحيحا إذا اعتُبر 1 عددا أوليا، ولكن المبرهنة الأساسية في الحسابيات لا تبقى صحيحة. على سبيل المثال، العدد 15 يمكن أن يُعمّل إلى 3×5 أو إلى 1×3×5. إذا كان 1 أوليا، هذان الشكلان الاثنان مختلفان عن بعضما البعض مما يجعل نص المبرهنة خاطئا. بالإضافة إلى ذلك، للأعداد الأولية مجموعة من الخصائص لا يملكها العدد 1. من بينها العلاقة التي تربط عددا ما بقيمة دالة مؤشر أويلر أو بدالة مجموع القواسم.

التاريخ

تشير بعض السجلات التاريخية القديمة إلى معرفة قدماء المصريين لمفهوم الأعداد الأولية: يأخذ التحليل إلى كسر مصري شكلا مختلفا عندما يُطَبق على أعداد أولية عن الشكل الذي يأخذه عندما يُطَبق على أعداد غير أولية.

مع ذلك يظل اليونانيون القدامى أول من أجرى دراسات جدية بشأنها. قام عالم الرياضيات اليوناني إراتوستينس بدراسة الأعداد الأولية، رغم أن أيٍ من مخطوطاته لم توجد، فقد أشار إليها علماء آخرون.

بعد الإغريق، لم يحدث الكثير فيما يتعلق بدراسة الأعداد الأولية حتى القرن السابع عشر. في عام 1640، نص بيير دي فيرما مبرهنة فيرما الصغرى بدون تقديم أي برهان عليها (بُرهن عليها فيما بعد من طرف لايبنتز وأويلر). حالة خاصة من مبرهنة فيرما قد تكون قد عرفت من طرف الصينيين من قبل. حدس فيرما أن جميع الأعداد الطبيعية على الشكل 2^2ⁿ + 1 (تسمى هذه الأعداد بأعداد فيرما) هي أعداد أولية وقد تحقق من ذلك إلى حدود n = 4 (أي 2¹⁶ + 1). ولكن عدد فيرما التالي (أي 2³² + 1) هو عدد مؤلف (واحد من قواسمه الأولية 641) كما اكتشف ذلك أويلر فيما بعد. بالإضافة إلى ذلك، حاليا لا يعرف عدد أولي ما يكتب على شكل أعداد فيرما. درس رجل الكنيسة الفرنسي مارين ميرسين الأعداد الأولية على الشكل 2^p − 1 حين يكون العدد p أوليا أيضا. سميت هذه الأعداد بأعداد ميرسن الأولية تكريما له.

احتوى عمل أويلر في نظرية الأعداد على مجموعة من النتائج تتعلق بالأعداد الأولية. برهن على أن المتسلسلة غير المنتهية 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + … هي متسلسلة متباعدة. في عام 1747، برهن على أن الأعداد المثالية الزوجية هي بالتحديد الأعداد الطبيعية اللائي يكتبن على الشكل (2^p−1(2^p − 1 حيث الحد الثاني من هذا الجداء هو عدد أولي لميرسن..

منذ عام 1951، كل الأعداد الأولية الكبيرة اللائي وُجدن، وُجدن بفضل الحاسوب. انظر إلى البحث الكبير عن أعداد ميرسين الأولية في الإنترنت.

عدد الأعداد الأولية

يوجد عدد غير منته من الأعداد الأولية تتوزع بشكل غير منتظم. وبتعبير آخر، المتسلسلة

2، 3، 5، 7، 11، 13،...

لا تنتهي أو لا تتوقف. تُدعى هذهِ المبرهنة مبرهنة أقليدس تكريما لعالم الرياضيات الإغريقي أقليدس بما أن أول برهان معروف لها يعود إليه. تُعرف حاليا براهين أخرى للا نهائية الأعداد الأولية منها برهان تحليلي من طرف أويلر، وبرهان غولدباخ المعتمد على أعداد فيرما، وبرهان فورشتنبرغ باستعمال الطوبولوجيا العامة وبرهان كومر الأنيق.

برهان أقليدس

برهان أقليدس يعتبر مجموعة منتهية ما S، من الأعداد الأولية. إن الفكرة الأساسية هي النظر إلى جداء جميع هذه الأعداد، أضيف إليه 1.

N = 1 + \prod_{p \in S} p .

عادة ما يعتقد خطأ أن برهان اقليدس يعتمد على طريقة البرهان بالخلف.

برهان أويلر التحليلي

يستعمل برهان أويلر مجموع مقلوبات الأعداد الأولية كما يلي :

S (p) = \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \dots + \frac{1}{p} .

هذه المتسلسلة تصير أكبر من أي عدد حقيقي معين عندما يصير p كبيرا بما فيه الكفاية. هذا يدل على أن هناك عددا غير منتهي من الأعداد الأولية. نمو (S(p، تعطيه مبرهنة ميرتنز الثانية. على سبيل المقارنة، المتسلسلة

\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \dots + \frac{1}{n^{2}} = \sum_{i = 1}^{n} \frac{1}{i^{2}}

لا تتباعد إلى ما لا نهاية له. هذا يدل على أن الأعداد الأولية أكثر كثافة من مربعات الأعداد الطبيعية. تنص مبرهنة برون على أن مجموع مقلوبات الأعداد الأولية التوأم.

(\frac{1}{3} + \frac{1}{5}) + (\frac{1}{5} + \frac{1}{7}) + (\frac{1}{11} + \frac{1}{13}) + \dots = \sum_{\begin{matrix} p prime, \\ p + 2 prime \end{matrix}} (\frac{1}{p} + \frac{1}{p + 2}),

هو عدد منته.

اختبار أولية عدد ما وتعميل الأعداد الطبيعية

هناك العديد من الاختبارات لمعرفة هل عدد معين ما أولي أم لا. أبسطها هي القسمة المتكررة. ولكن هاته الطريقة قليلة النفع والاستعمال وذلك لكونها شديدة البطئ.

عن طريق القسمة المتكررة

الطريقة الأكثر بساطة، والأكثر سهولة من حيث الفهم، من أجل تحديد أولية عدد ما تدعى القسمة المتكررة. تتمثل هذه الطريقة في قسمة العدد n على جميع الأعداد الصحيحة الأكبر من الواحد والأصغر من الجذر التربيعي ل n. إذا لم تنتج إحدى هذه القسمات باقيا، فإن العدد n ليس بالأولي. وهو أولي في غير ذلك. بالفعل، إذا كان n = a * b عددا مؤلفا (أي أن العددين الطبيعيين a و b يختلفان عن الواحد)، فإن على الأقل واحد من هذين العددين يكون أصغر من أو يساوي الجذر التربيعي ل n. على سبيل المثال، إذا توفر n = 37، فإن القسمة المتكررة تخص الأعداد الطبيعية 2 و 3 و 4 و 5 و 6. لا يقسم عدد من هذه الأعداد العددَ 37. إذن، فإن 37 عدد أولي. قد تُطور هذه العملية لكي تصير أكثر فعالية وسرعة. وذلك بالنظر إلى الأعداد الأصغر من الجذر التربيعي للعدد المراد تحديد أوليته، واللائي يكن في نفس الوقت أعدادا أولية. على سبيل المثال، بالنسبة للعدد 37، فإنه يكفي النظر إلى الأعداد 2 و 3 و 5. ولا ينبغي النظر إلى العددين 4 و 6 لأنهما عددان غير أوليين.

الغرابيل

كل خوارزمية تمكن من إيجاد جميع الأعداد الأولية الأصغر من عدد ما تسمى غربالا. أقدم مثال على ذلك غربال إراتوستينس لكنه لا يستعمل إلا في حالة الأعداد الصغيرة. غربال أتكين أحدث منه ولكنه أكثر منه تعقيدا ولهذا فهو أكثر منه سرعة. تستعمل نظرية الغرابيل طرقا مشابهة من أجل حلحلة معضلات أخرى.

اختبار أولية عدد ما مقابل البرهان على ذلك

الاختبارات العصرية لأولية عدد طبيعي ما يمكن أن تقسم إلى نوعين : الاختبارات الاحتمالية والاختبارات القطعية.

مبرهنة فيرما الصغرى تبين أنه إذا كان p عددا أوليا وa عددا أوليا مع p، إذن : $a^{p - 1} \equiv 1 (p)$

عكس المبرهنة خاطئ، مثلا 561=3×11×17 ليس عددا أوليا ومع ذلك بالنسبة لعدد a أولي مع 561، لدينا $a^{560} \equiv 1 (561)$

لكن يمكن مع ذلك كتابة:

إذا كان p غير أولي فإن $a^{p - 1}$ متوافق مع 1 بترديد p لقيمة ما a

الشيء الذي يمثل عكس احتمالي للمبرهنة.

برمجة التشفير PGP، تستعمل هذه الخاصية لمعرفة إذا كانت الأعداد العشوائية التي يختارها أعداد أولية. إذا كان: $1 \equiv 2^{x - 1} \equiv 3^{x - 1} \equiv 5^{x - 1} \equiv 7^{x - 1} (x)$ ، فهذا يعني أن x عدد أولي احتمالي.

إذا أعطت إحدى المعادلات قيمة مخالفة ل1، في هذه الحالة x عدد غير أولي قطعيا.

الاختبار	طُور عام	النوع	الوقت الضروري للاختبار	ملاحظات
اختبار أ.ك.أس لأولية عدد ما	2002	قطعي	((O(log^6+ε(n
برهان المنحنيات الإهليلجية على أولية عدد ما	1977	قطعي	O(log^5+ε(n)) heuristically
اختبار Baillie-PSW لأولية عدد ما	1980	احتمالي	O(log³ n)	لا يعرف مثال مضاد
اختبار ميلر-رابن لأولية عدد ما	1980	احتمالي	O(k · log^2+ε (n))	احتمال الخطأ 4^−k
اختبار سولوفاي-شتراسن لأولية عدد ما	1977	احتمالي	O(k · log³ n)	احتمال الخطأ 2^−k
اختبار فيرما لأولية عدد ما		احتمالي	O(k · log^2+ε (n))	يفشل عند عدد كارميكائيل

خوارزميات ذت أهداف خاصة وأكبر عدد أولي معروف

إنشاء خماسي منتظم للأضلع. 5 هو عدد أولي لفيرما.

بالإضافة إلى الاختبارات المشار إليها أعلاه، واللائي يمكن أن يُطبقن على أي عدد طبيعي، فإن هناك اختبارات أكثر قوة ودقة تطبق على أشكال خاصة من الأعداد. على سبيل المثال، اختبار لوكاس لأولية عدد ما يتطلب معرفة العوامل الأولية ل n - 1. بينما يتطلب اختبار لوكاس-ليهمر لأولية عدد ما معرفة العوامل الأولية ل n + 1.

تعميل الأعداد الصحيحة

ليكن n عددا مؤلفا ما (أي أنه عدد غير أولي). يسمى البحث عن أحد أو كل قواسم n الأولية تعميل n. التعميل باستعمال المنحنيات الإهليلجية هي خوارزمية تعتمد على حسابيات تقام على المنحنيات الإهليلجية.

التوزيع

عدد الأعداد الأولية الأصغر من عدد معين

خارطة تصف (π(n (لون أزرق)، (n / ln (n (لون أخضر) و(Li (n، التكامل اللغواريتمي المزاح (لون أحمر)

تعرف الدالة المعدة للأعداد الأولية (π(n بأنها عدد الأعداد الأولية الأصغر من n. مثال ذلك π(11) = 5، وذلك لوجود خمسة أعداد أولية أصغر من أو تساوي العدد 11. توجد خوارزمات شهيرة لحساب القيم الدقيقة ل (π(n أسرع من طريقة حسابها بشكل منفرد حتى n. يمكن إحصاء قيم قد تصل إلى π(10²⁰) بسرعة عالية ودقة بواسطة الحواسيب المعاصرة.

بالنسبة للقيم الكبيرة من n، والتي تتجاوز قدة الأجهزة الحديثة فإن مبرهنة الأعداد الأولية تعطينا تقديراً أولياً:(π(n تساوي تقريباً (n/ln(n. بعبارة أخرى، عندما تصبح n عدد كبيراً جداً فإن احتمالية أن يكون العدد الأولي أقل من n تتناسب عكسياً مع عدد الأرقام المكونة ل n.

المتتاليات الحسابية

المتتالية الحسابية هي مجموعة الأعداد الصحيحة الطبيعية التي تعطي نفس الباقي عندما تقسم على عدد معين q ما. على سبيل المثال،

3، 12، 21، 30، 39،...،

هي متتالية حسابية لأن باقي قسمة هؤلاء الأعداد على 9 يساوي دائما نفس العدد 3. جميع حدود هاته المتتالية، باستثناء 3، أعداد غير أولية بما أن

(1 + 9n + 3 = 3(3n

انظر مبرهنة غرين-تاون.

القيم الأولية لمتعددات الحدود من الدرجة الثانية

لاحظ أويلر أن الدالة

n^{2} + n + 41

تعطي أعدادا أولية بالنسبة ل n ≥ 0 و n <40. هذه الحقيقة أدت إلى نظرية جبرية للأعداد شديدة العمق، وبشكل خاص أعداد هيغنر.

مسائل لم تحل بعد

دالة زيتا وفرضية ريمان

دالة زيتا لريمان (ζ(s تعرف كمجموع غير منته :

ζ (s) = \sum_{n = 1}^{\infty} \frac{1}{n^{s}},

حيث s هو عدد عقدي جزءه الحقيقي أكبر قطعا من 1. يمكن البرهان على أن هذا المجموع يساوي الجداء التالي :

\prod_{p أولي} \frac{1}{1 - p^{- s}} .

حيث p عدد أولي.

هذه الصيغة تعني ارتباط دالة زيتا الشديد بالأعداد الأولية.

حدسيات أخرى

بالإضافة إلى فرضية ريمان، وضعت العديد من الحدسيات المتعلقة بالأعداد الأولية. عادة ما تكون صياغتها بسيطة وعادة ما تستعصي على البرهان لعقود. معضلات لاندو الأربع وضعت عام 1912 ولم تحلحل بعد. ومنها أيضا حدسية غولدباخ والتي تنص على أن كل عدد زوجي n أكبر قطعا من 2، يمكن كتابته على شكل مجموع عددين أوليين. حتى فبراير 2011، بقيت هاته الحدسية صحيحة بالنسبة لجميع الأعداد الأصغر من 2.10¹⁷. نصوص أضعف من نص هاته الحدسية لم تقاوم البرهان. على سبيل المثال، تنص مبرهنة فينوغرادوف على أن أي عدد طبيعي فردي، كبير فيما فيه الكفاية، يمكن أن يُكتب على شكل مجموع ثلاثة أعداد أولية. مبرهنة تشين تنص على أن أي عدد طبيعي زوجي، كبير فيما فيه الكفاية، يمكن أن يكتب على شكل مجموع عدد أولي وعدد نصف أولي.

من الحدسيات غير المحلحلة بعد ما يلي:

حدسية التوأمين الأولية

خصائص الأعداد الأولية

أي عدد أولي أكبر من 3 يكتب على شكل 6k+1 أو 6k-1 حيث k عدد طبيعي.
كل عدد صحيح n> 1 له قاسم أولي.
إذا كان n عدداً مؤلفاً (غير أولي) فإن له قاسم أولي p أصغر أو يساوي الجذر التربيعي ل n.
إذا كان الفرق بين عددين أوليين مساويا ل 2، فهذان العددان يسميان توأما أوليا. 5 و 7 من جهة و 11 و 13 من جهة ثانية، هما توأمان أوليان. (حدسية العددين الأوليين التوأم)

برمجة الأعداد الأولية

يمكن برمجة تطبيقات (دوال برمجية) تقوم بتحديد الأعداد الأولية عن طريق استخدام خورزمية القسمة المتكررة (المثال بلغة بايثون) :

def isPrime(num):
    if num>1:
        for count in range(2,int(num**(1/2))):
            if not(num%count):
                return False
                break
        return True
    else:
        return False
for count in range(0,100):
    if isPrime(count):
        print(count,end=",")
#in the screen : 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

في الجبر التجريدي

مفهوم العدد الأولي مهم جدا. ولهذا عمم بأشكال مختلفة في عدة مجالات من الرياضيات. بشكل عام، مفهوم أولي يعني كل ما هو غير قابل للتفكيك إلى أجزاء أخرى. على سبيل المثال، حقل أولي هو أصغر حقل ضمن حقل F ما، يحتوي على 0 وعلى 1.

الحسابيات بتردد عدد أولي والحقول المنتهية

تغير الحسابيات بتردد عدد n ما، الحسابيات بشكل عام باستعمالها للأعداد التالية فقط

{0, 1, 2, \dots, n - 1},

حيث n عدد طبيعي ثابت. يتم حساب المجاميع والفرق والجداءات بالشكل المعتاد، ولكنه كلما كانت النتيجة سلبية أو مساوية لعدد أكبر من، أو يساوي n، عوضت بباقي قسمتها على العدد n.

الأعداد التقاربية بتردد p

العناصر الأولية في الحلقات

نظرية الزمر

في نظرية الزمر المنتهية، تنص مبرهنة سيلاو على أنه إذا قسمت $p^{n}$ قوةٌ ما لعدد أولي ما، رتبةَ زمرة، فإن في هذه الزمرة زمرة جزئية رتبتها $p^{n}$ . تنص مبرهنة لاغرانج على أن كل زمرة رتبتها عدد أولي هي زمرة دائرية. وتنص مبرهنة بورنصايد على أن كل زمرة رتبتها قابلة للقسمة على عددين أوليين اثنين فقط (أي أنها عدد نصف أولي)، هي زمرة قابلة للحلحلة.

تطبيقات

لمدة طويلة، اعتُبرت نظرية الأعداد بشكل عام ودراسة الأعداد الأولية بشكل خاص، جزءا من الرياضيات البحتة، بدون أية تطبيقات باستثناء الاهتمام الذي يوليه عالم الرياضيات إلى هذه الدراسة. على سبيل المثال، العاملون في نظرية الأعداد من أمثال عالم الرياضيات البريطاني غودفري هارولد هاردي، كانو يفتخرون بعملهم في مجال ليس لديه تطبيقات عسكرية. ولكن هاته النظرة تحطمت في سبعينات القرن العشرين، حين أُعلن للعموم أن الأعداد الأولية قد تستعمل قاعدة لبناء خوارزميات التشفير باستخدام المفتاح المعلن. يستعمل الأعدادَ الأولية أيضا مولدات الأعداد شبه العشوائية.

التشفير باستخدام المفتاح المعلن

تستعمل الأعداد الأولية في ميدان المعلوميات وخاصة في علم التعمية. ومن أشهر التطبيقات التي تستعمل الأعداد الأولية خوارزمية آر إس إيه وتبادل مفتاح ديفي-هيلمان. تعتمد خوارزمية آر إس إيه أساسا على افتراض أن حساب جداء عددين صحيحين معلومين x و y أسهل بكثير من حساب x و y إذا كان جداؤهما xy فقط معروفا (مع افتراض أنها أوليين فيما بينهما). لمزيد من المعلومات راجع التشفير ومشكلة التفكيك إلى جداء عوامل أولية.

انظر أيضًا

مصادر

^ "عجى وعجو - موسوعات لسان نت للّغة العربية - Lisaan.net". lisaan.net (بen-US). Archived from the original on 2019-12-10. Retrieved 2018-04-04. {{استشهاد ويب}}: line feed character في |عنوان= في مكان 12 (help)صيانة الاستشهاد: لغة غير مدعومة (link)
^ البحث الكبير عن أعداد ميرسين الأولية في الإنترنت; http://www.mersenne.org/ نسخة محفوظة 03 أبريل 2018 على موقع واي باك مشين.

وصلات خارجية

في كومنز صور وملفات عن: عدد أولي

[1] "عجى وعجو - موسوعات لسان نت للّغة العربية - Lisaan.net". lisaan.net (بen-US). Archived from the original on 2019-12-10. Retrieved 2018-04-04. {{استشهاد ويب}}: line feed character في |عنوان= في مكان 12 (help)صيانة الاستشهاد: لغة غير مدعومة (link)

[2] البحث الكبير عن أعداد ميرسين الأولية في الإنترنت; http://www.mersenne.org/ نسخة محفوظة 03 أبريل 2018 على موقع واي باك مشين.

[1]

[2]

ع ن ت مواضيع علم التعمية
مصطلحات رئيسة	تعمية كتل • تعمية تيار بيانات متدفقة • سرية كاملة • تعمية بالمفتاح المتناظر • تعمية باستخدام المفتاح العام • توقيع رقمي
تعمية تقليدية	آلة تعمية • تعمية استبدال • شفرة قيصر • شفرة فيجينير • شفرة فيرنام • شفرة بلايفير • ألترا (تعمية) • آلة إنجما • عداد الدورات • حاسوب كلوسوس • آلة التعمية من النوع ب • جيد (محرك لعبة) • سحر
تعمية بالمفتاح المتناظر	لوحة المرة الواحدة • معيار التعمية المتقدم • 3DES • معيار تعمية البيانات • RC4
تعمية باستخدام المفتاح العام	خوارزمية آر إس إيه • شفرة رابين • توقيع رابين الرقمي • شفرة الجمل • توقيع الجمل الرقمي • DSA • شفرة بلوم وغولدفاسر • تعمية بالمنحنيات الإهليلجية
بروتوكول تعمية	تبادل مفتاح ديفي-هيلمان • برتوكول تحدي-جواب • برتوكول كيرباروس • برهان معرفة صفرية • برتوكول فييجة-فيات-شمير • نقل نَسَّاء • تشارك سر • بروتوكول طبقة المنافذ الآمنة • بروتوكول النقل الآمن
الاساسات النظرية	مولد الاعداد شبه العشوائية • دالة وحيدة الاتجاه • تبادلية وحيدة الاتجاه • بت صعب • عائلة دوال شبه عشوائية • دالة هاش تعميةية
مسائل رياضية: فك التعمية وخوارزميات	بحث شامل • تحليل ترددات • مسألة اللوغاريثم المتقطع • حساب المؤشرات • تحليل عدد صحيح إلى عوامل • الغربال التربيعي • خوارزمية rho لبوراد • غربال حقل الاعداد • خوارزمية ميلر رابين • تحليل شفرات تفاضلي • تحليل الشفرات الخطي
المصادقة والتحقق من الهوية	كلمة المرور • شفرة تصديق الرسالة • SHA • إم دي5 • MD4
مواضيع مصاحبة	عدد عشوائي • عدد أولي • زيادة (نظرية المعلومات) • مفتاح المكالمة • تعمية بإخفاء • تعمية كمومي • مبادئ كيرشوف • أمن المعلومات • تعمية مرئي • أليس وبوب (تعمية) • الطرف الموقع باستخدام المفتاح

ع ن ت مجموعات من الأعداد الصحيحة مُصنَّفة على أساس قابلية القسمة
نظرة عامة	تحليل عدد صحيح إلى عوامل قاسم Unitary divisor دالة القواسم عامل أولي المبرهنة الأساسية في الحسابيات Arithmetic number
Factorization forms	عدد أولي عدد غير أولي عدد نصف أولي Pronic Sphenic عدد صحيح خال من المربعات Powerful Perfect power Achilles Smooth عدد نظامي Rough Unusual
Constrained divisor sums	عدد مثالي Almost perfect Quasiperfect Multiply perfect Hemiperfect Hyperperfect Superperfect Unitary perfect Semiperfect Practical Erdős–Nicolas
With many divisors	عدد زائد Primitive abundant Highly abundant Superabundant Colossally abundant Highly composite Superior highly composite Weird
متتالية تجزيئية-related	عدد غير ملموس أعداد متحابة عدد أنيس Betrothed
Other sets	عدد ناقص Friendly Solitary Sublime Harmonic divisor Frugal Equidigital عدد مبذر

ع ن ت أصناف الأعداد الأولية
من حيث الصيغة	فيرما ( $2 2 n + 1$ ) ميرسين ( $2 p - 1$ ) عدد ميرسين المزدوج ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) عدد أولي عاملي Primorial ( $p n # \pm 1$ ) أقليدس( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 m \cdot3 n + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 m \pm 2 n \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Carol $(2 n - 1) 2 - 2$ Kynea $(2 n + 1) 2 - 2$ Leyland ( $x y + y x$ ) ثابت( $3\cdot2 n - 1$ ) Williams ( $(b -1)\cdot b n - 1$ ) Mills ( $خطأ في التعبير: علامة ترقيم لم نتعرف عليها «'».$ )
By integer sequence	فيبوناتشي لوكاس بيل Newman–Shanks–Williams بيرن تجزئة (نظرية الأعداد) عدد بيل رقم موتسكين
من حيث الخصائص	Wieferich (pair) Wall–Sun–Sun Wolstenholme عدد ويلسون الأولي محظوظ Fortunate عدد رامانجن الأولي Pillai عدد أولي نظامي Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient
أساس (رياضيات)-dependent	عدد سعيد Dihedral Palindromic Emirp Repunit $(10 n - 1)/9$ Permutable دائرية Truncatable Strobogrammatic Minimal Weakly Full reptend Unique Primeval Self Smarandache–Wellin Tetradic
من حيث الشكل	عددان أوليان توأم ( $p, p + 2$ ) Bi-twin chain ( $n - 1, n + 1, 2 n - 1, 2 n + 1, \dots$ ) Triplet ( $p, p + 2 or p + 4, p + 6$ ) Quadruplet ( $p, p + 2, p + 6, p + 8$ ) k−Tuple Cousin ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) عدد تشين الأولي Sophie Germain ( $p, 2 p + 1$ ) Cunningham ( $p, 2 p \pm 1, 4 p \pm 3, 8 p \pm 7, ...$ ) Safe ( $p, (p - 1)/2$ ) Arithmetic progression ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Balanced ( $consecutive p - n, p, p + n$ )
من حيث عدد الأرقام	Titanic (1,000+ digits) Gigantic (10,000+ digits) Mega (1,000,000+ digits) أكبر عدد أولي معروف
عدد مركب	عدد أيزنشتاين الأولي عدد صحيح غاوسي
عدد غير أولي	عدد شبه أولي كاتالان Elliptic أويلر أويلر–جاكوبي أعداد فيرما شبه الأولية فروبنيوس لوكاس سومر–لوكاس Strong عدد كارميكائيل Almost prime عدد نصف أولي Interprime Pernicious
Related topics	عدد أولي محتمل Industrial-grade prime عدد غير شرعي صيغة للأعداد الأولية فجوة أولية
الأعداد الأولية الستون الأولى	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
قائمة الأعداد الأولية

ع ن ت مواضيع رئيسية في نظرية الأعداد
النظرية الجبرية للأعداد • نظرية الأعداد التحليلية • نظرية الأعداد الهندسية • نظرية الأعداد الحاسوبية
أعداد • عدد طبيعي • عدد أولي • أعداد منطقة • عدد غير نسبي • عدد جبري • عدد متسام • حساب • حساب طوري • دوال حسابية
أشكال تربيعية • دوال-إل • معادلة ديفونتية • تقريب ديوفانتين • كسر مستمر
قائمة مواضيع نظرية الأعداد التخليقية • قائمة مواضيع نظرية الأعداد