عدد أولي

"أولي" تحوّل إلى هنا. لمطالعة استخدامات أخرى، انظر أولي (توضيح).

Composite numbers can be arranged into rectangles but prime numbers cannot

العدد الأولي prime number، هو عدد صحيح طبيعي أكبر من 1، يقبل القسمة فقط على نفسه وعلى الواحد.

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

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

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

الأعداد الأولية الأصغر من 100 هي : 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.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 تاريخ الأعداد الأولية

The منخل إراتوستين is a simple, ancient algorithm for finding all prime numbers up to a specified integer. It is the predecessor to the modern Sieve of Atkin, which is faster but more complex. The eponymous Sieve of Eratosthenes was created in the 3rd century BC by Eratosthenes, an ancient Greek mathematician.

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

اهتم العلماء منذ القدم بهذه المسألة، وقد وضعت براهين كثيرة على أنّ عدد الأعداد الأولية غير منتهٍ.

من أقدم هذه البراهين البرهان الذي قدمه إقليدس Euclid في نحو300 قبل الميلاد، في المقالة التاسعة في كتابه الشهير «الأصول».

تسمى الأعداد التي تكتب على النحو قن = ق1، ق2 .... قن-1+1 حيث ق1 = 2 وينتج عن ذلك ق2= 3، … أعداد إقليدس.

وليست كلها أولية فالعدد ق5 مثلاً يساوي 1807 = ´13 ن139 هو عدد مؤلف.

 تعريفات

العدد الأولي هو عدد صحيح أكبر من الواحد، ليس له إلا قاسمان موجبان فقط، هما: الواحد والعدد نفسه.

يتضح من التعريف أن العدد 2 هو أصغر عدد أولي، وأنّه هو العدد الأولي الزوجي الوحيد.

الأعداد التالية مثلاً: 2، 3، 5، 13 … هي أعداد أولية.

إذا كان ن عدداً صحيحاً أكبر من الواحد و لم يكن أوّلياً فإنه يدعى عدداً مؤلفاً، أي إنّ كل عدد صحيح أكبر من الواحد هو إمّا عدد أولي، أو عدد مؤلف، والأعداد التالية 4 =2´2، ن91 = 7 ´ ن13 … هي أعداد مؤلفة.

يقال إنّ العددين الصحيحين ب وجـ أوليان نسبياً إذا كان القاسم المشترك الأعظم لهما = 1، أي إذا كان (ب، جـ) = 1، فالعددان (6، 25) مثلاً أوليان نسبياً.

 القواسم الأولية

المقالة الرئيسية: قائمة الأعداد الأولية

رسم يوضح أن الرقم 11 هو عدد أولي بينما الرقم 12 ليس عدد أولي.

دللت المبرهنة الأساسية في الرياضيات أن كل عدد صحيح موجب أكب رمن 1 يمكن أن يكتب كناتج لواحد أو أكثر من الأعداد الاولية بطريقة which is unique except possibly for the order of the prime factors. ويمكن أن يتكرر العدد الأولي لمرات متعددة. ومن ثم يمكن اعتبار الأعداد الأولية على أنها “الكتل البنائية الأساسية” للأعداد الطبيعية. على سبيل المثال، يمكن كتابة:

$23244=2^{2}\times 3\times 13\times 149$

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

• جميع الأعداد الأولية - عدا 2 و 5 - تنتهي ب 1 ، 3 ، 7 أو 9 لماذا ؟

لأن جميع الأعداد التي تنتهي ب(0، 2، 4، 6 أو 8) هي من مضاعفات الاثنين فليست بالتأكيد أوليّة، والأعداد التي تنتهي ب(0 أو 5) من مضاعفات الخمسة فليست أولية أيضاً.

• إذا كان لدينا عددان صحيحان أ و ب، ولدينا عدد ثالث ج، حيث ج عدد أولي. وكان حاصل ضرب العددين (أ × ب) يقبل القسمة على العدد ج، فإن "أ" أو "ب" يقبل القسمة على ج هذه الخاصية تعرف أيضا ً بمبرهنة إقليدس.

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

إنّ كل عدد صحيح ن أكبر من الواحد يمكن أن يُكتب جداءَ عددٍ منتهٍ من الأعداد الأولية، قد يكون بعضها مكرراً، ويتم ذلك بشكل وحيد، فيمكن مثلاً كتابة العدد 17640 على النحو 17640=2 3×3 2×5×7 2، وتسمى هذه العملية تحليل العدد إلى عوامله الأولية.

ينتج من المبرهنة الأساسية أنّ لكل عدد صحيح أكبر من الواحد، عاملاً أولياً واحداً على الأقل.

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

 مرشحة إراتوستينس

مرشحة إراتوستينس (230 ق.م)، هي قاعدة للحصول على الأعداد الأولية التي هي أصغر من عدد صحيح ما (ن)، ويتم ذلك كما يأتي:

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

فللحصول على الأعداد الأولية التي هي أصغر من مئة مثلاً تُشطَبُ مضاعفات الأعداد 2 و3 و5 و7 فقط، من جدول الأعداد من 2 إلى 100.

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

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

لقد بحث العلماء عن دساتير بسيطة تعطي أعداداً أولية فوضعت العبارة:

س2- س + 41، و وجد أنها تعطي أعداداً أولية من أجل قيم س من الصفر حتى العدد 40، لكنها تعطي عدداً مؤلفاً عندما تصبح س = 41.

حاول الرياضيون تطوير هذه العبارة والبحث عن حدوديات تحقق الغاية دون جدوى.

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

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

هناك أكثر من 15 اختبارا لمعرفة هل عدد معين أولي أم لا وهي:

• اختبار ليكاس - ليهمر
• ختبار فيرما المتربط بمبرهنة فيرما الصغرى.

 اختبار فيرما

وضع فيرما (1601ـ 1665م) الصيغة التي ظن بحدسه أنها تعطي أعداداً أولية فقط، وهي العبارة:

فن = 2 (2ن)+1 و ن £ 0 ولكنه أخطأ بحدسه هذا إذ أثبت أولر Euler في عام 1732 م ، أنّ ف5 عدد مؤلف ولم يستطع أحد حتى اليوم إيجاد عدد أولي بعد هذا العدد من أعداد فيرما.

مبرهنة فيرما الصغرى تبين أنه إذا كان 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 عدد غير أولي قطعيا.

 صيغة ميرسن

كما وضع ميرسن (1644) صيغة أخرى على النحو: م ل = 2ل - 1 حيث ل عدد أولي، ثم تبين أن العدد م = 23×89 عدد مؤلف.

استخدمت صيغة ميرسن لتعيين أكبر عدد أولي حُدِّد عام 1984، وهو العدد الذي يوافق القيمة ل=216091.

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

 صيغة گاوس

في عام 1793 وضع العالم گاوس المبرهنة الشهيرة التي تسمى مبرهنة الأعداد الأولية، وتنص على أنه إذا كان (س) هو عدد الأعداد الأولية التي لا تتجاوز قيمها العدد س فإن نسبة (س) إلى الدالة س/لع س تنتهي إلى الواحد عندما تنتهي قيمة س إلى مالانهاية، ولم تثبت صحة هذه المبرهنة إلا عام 1896 حين أثبتها العالمان بوسان C.J.V.Poussin وهادامار J.Hadamard كلٌ على انفراد.

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

 أهمية واستخدامات الأعداد الأولية

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 جوائز العثور على أعداد أولية

عرضت مؤسسة الحدود الإلكترونية جائزةمقدارها 100.000 دولار أمريكي لأول من يكتشف عدد أولي من ضمن 10 مليون عدد على الأقل. وعرضت المؤسسة أيضاً 150.000 دولار لاكتشاف العدد الأولي من ضمن 100 مليون عدد، و250.000 من ضمن بليون عدد. في عام 2000 قدمت جائزة مقدارها 50.000 دولار لاختيار عدد أولي من ضمن مليون عدد. ومن المتحمل أن تقدم جائزة 100.000 دولار إلى قسم الرياضيات في جامعة لوس أنجلس، كاليفورنيا ومشروع جي أي إم پي إس GIMPS لاكتشافهم 13 مليون عدد أولي في أغسطس 2008.[1][2]

عرضت RSA Factoring Challenge جوائز قيمتها أكثر من 200.000 دولار للعثور على أعداد أولية من أعداد نصف أولية مؤكدة عددها أكثر من 2048 بيت. بالرغم من ذلك، توقف التحدي في 2007 بعد منح عدد كبير من الجوائز الأصغر لاكتشاف الأعداد الأولية من ضمن أعداد نصف أولية أقل.

 طالع أيضاً

• Full cycle
• عدد گودل
• عدد هيلبرت
• Integer factorization
• Irreducible polynomial
• Logarithmic integral function
• أس أولي
• Primon gas
• Sphenic number
• قائمة الأعداد الأولية (list of special classes of prime numbers‎)

 المشاريع الحاسوبية الموزعة التي يبحث عن أعداد أولية

• GIMPS searches for أعداد مرسن الأولية.
• PrimeGrid searches for megaprimes.
• Seventeen or Bust searches for primes which can help prove that 78557 is the smallest Sierpinski number.
• Twin Prime Search searches for record twin primes
• Wieferich@Home searches for Wieferich primes.

 المصادر

• John Derbyshire, Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. Joseph Henry Press; 448 pages
• Wladyslaw Narkiewicz, The development of prime number theory. From Euclid to Hardy and Littlewood. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2000.
• H. Riesel, Prime Numbers and Computer Methods for Factorization, 2nd ed., Birkhäuser 1994.
• Marcus du Sautoy, The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics. HarperCollins; 352 pages. ISBN 0-06-621070-4. The Music of Primes website.
• Karl Sabbagh, The Riemann Hypothesis: The Greatest Unsolved Problem in Mathematics. Farrar, Straus and Giroux; 340 pages

 وصلات خارجية

Wikinews has related news:

Two largest known prime numbers discovered just two weeks apart, one qualifies for $100k prize

• Caldwell, Chris, The Prime Pages at primes.utm.edu.
• Prime Numbers at MathWorld
• MacTutor history of prime numbers
• The prime puzzles
• An English translation of Euclid's proof that there are infinitely many primes
• Number Spiral with prime patterns
• An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier
• EFF Cooperative Computing Awards
• Why a Number Is Prime by Enrique Zeleny, The Wolfram Demonstrations Project.

 Prime number generators & calculators

• Online Prime Number Generator and Checker - instantly checks and finds prime numbers up to 128 digits long (does NOT require Java or Javascript)
• Prime number calculator — Check prime number, and find next largest and next smallest prime numbers (requires Javascript).
• Fast Online primality test — Dario Alpern's personal site – Makes use of the Elliptic Curve Method (up to thousands digits numbers check!, requires Java)
• Prime Number Generator — Generates a given number of primes above a given start number.
• Primes from WIMS is an online prime generator.
• Huge database of prime numbers