عدد أولي

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

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

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

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

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

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

• if num>1:
• for count in range(2,int(num**(1/2))):
• if not(num%count):
• return False
• break

وفي هذا السياق، يمكن برمجة تطبيقات (دوال برمجية) تقوم بتحديد الأعداد الأولية عن طريق استخدام خورزمية القسمة المتكررة (المثال بلغة بايثون) :def isPrime(num):

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

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

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

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

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

التوزيع

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

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

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

برهان أقليدس

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

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

الغرابيل

وفي هذا السياق، مبرهنة فيرما الصغرى تبين أنه إذا كان p عددا أوليا وa عددا أوليا مع p، إذن :

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

علاوةً على ذلك، برمجة التشفير PGP، تستعمل هذه الخاصية لمعرفة إذا كانت الأعداد العشوائية التي يختارها أعداد أولية.

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

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

• إذا كان: ، فهذا يعني أن x عدد أولي احتمالي.
• إذا أعطت إحدى المعادلات قيمة مخالفة ل1، في هذه الحالة x عدد غير أولي قطعيا.
• خوارزميات ذت أهداف خاصة وأكبر عدد أولي معروف

• لكن يمكن مع ذلك كتابة:
• إذا كان p غير أولي فإن متوافق مع 1 بترديد p لقيمة ما a
• الشيء الذي يمثل عكس احتمالي للمبرهنة.

من جانب آخر، عكس المبرهنة خاطئ، مثلا 561=3×11×17 ليس عددا أوليا ومع ذلك بالنسبة لعدد a أولي مع 561، لدينا

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

التاريخ

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

وعلى صعيد آخر، درس رجل الكنيسة الفرنسي مارين ميرسين الأعداد الأولية على الشكل 2p − 1 حين يكون العدد p أوليا كذلك. سميت هذه الأعداد بأعداد ميرسن الأولية تكريما له.

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

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

من جهة ثانية، حدس فيرما أن جميع الأعداد الطبيعية على الشكل 22n + 1 (تسمى هذه الأعداد بأعداد فيرما) هي أعداد أولية وقد تحقق من ذلك إلى حدود n = 4 (أي 216 + 1). ولكن عدد فيرما التالي (أي 232 + 1) هو عدد مؤلف (واحد من قواسمه الأولية 641) كما اكتشف ذلك أويلر فيما بعد. علاوةً على ذلك، في الوقت الحالي لا يعرف عدد أولي ما يكتب على شكل أعداد فيرما.

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

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

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

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

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

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

return True

else:

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

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

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

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

تعريف وأمثلة

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

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

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

وفي هذا السياق، جميع الأعداد الأولية - عدا 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.

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

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

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

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

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

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

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

أ,

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

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

من جانب آخر، قد تُطور هذه العملية لكي تصير أكثر فعالية وسرعة. وذلك بالنظر إلى الأعداد الأصغر من الجذر التربيعي للعدد المراد تحديد أوليته، واللائي يكن في نفس الوقت أعدادا أولية. مثلًا، بالنسبة للعدد 37، فإنه يكفي النظر إلى الأعداد 2 و 3 و 5. ولا ينبغي النظر إلى العددين 4 و 6 لأنهما عددان غير أوليين.

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

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

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

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

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

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

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

إضافةً إلى ذلك، أي عدد أولي أكبر من 3 يكتب على شكل 6k+1 أو 6k-1 حيث k عدد طبيعي.

كل عدد صحيح n> 1 له قاسم أولي.

علاوةً على ذلك، إذا كان n عدداً مؤلفاً (غير أولي) فإن له قاسم أولي p أصغر أو يساوي الجذر التربيعي ل n.

وعلى صعيد آخر، إذا كان الفرق بين عددين أوليين مساويا ل 2، فهذان العددان يسميان توأما أوليا. 5 و 7 من جهة و 11 و 13 من جهة ثانية، هما توأمان أوليان. (حدسية العددين الأوليين التوأم)

نظرية الزمر

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

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

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

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

حدسيات أخرى

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

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

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

تطبيقات

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

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

وفي السياق ذاته، لمزيد من المعلومات راجع التشفير ومشكلة التفكيك إلى جداء عوامل أولية.

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

3*7=21

كذلك، كما في المثال السابق، قد يتكرر نفس العامل الأولي أكثر من مرة. تسمى عملية تحليل عدد n ما إلى جداء عومل أولية : تحليل عدد صحيح إلى عوامل. يمكن إذن صياغة المبرهنة الأساسية في الحسابيات كما يلي:

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

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

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

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

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

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

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

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

هو عدد منته.