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

تقديم موجز

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

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

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

أعداد ميرسين الأولية

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

لقد كان عدد من الرياضيين السابقين يعتقدون أن العدد من الصورة    يكون أوليا كلما كان n  عددا أوليا ، و لكن في 1536 أثبت ريجيوس ( Regius ) أن العدد : = 2047 = 23.89  ليس أوليا حيث أنه حاصل ضرب 23 × 89 ، و في عام 1603 تحقق كاتالدي (Cataldi) أن العددان  و     أوليان ، و استنتج كاتالدي و بشكل خاطئ أن العدد   يكون أوليا لكل : n = 23,29,31,37  ، حيث أثبت فيرمات في 1645 أن كاتالدي كان خاطئا بالنسبة للعددين n = 23,37 ، و أثبت أويلر في 1738 أن كاتالدي كان أيضا خاطئا بالنسبة للعدد  n = 29  ، و في وقت لاحق أثبت أويلر أن كاتالدي كان مصيبا بالنسبة للعدد n = 31 .

بمجيء الفرنسي مارين ميرسين (Marin Mersenne) 1588-1648 ، حيث وضع في مقدمة أحد كتبه أن العدد   يكون أوليا عندما :  n = 2,3,5,7,13,17,19,31,67,127,257  ، و أنه مركبا لكل الأعداد n < 257 الصحيحة ، و رغم أن هذا التخمين من ميرسين كان خاطئا إلا أن اسمه ظل ملتصقا بهذه الأعداد حيث سميت باسمه .

  تعريف : عندما يكون العدد أوليا فإنه يسمى بعدد ميرسين الأولي .

كان واضحا أنه ليس بإمكان ميرسين التحقق من كل هذه الأعداد ( n<257 ) لصعوبة ذلك في عصر ميرسين ، كذلك لم يكن بمقدور معاصريه التحق من موضوعته ، فبقيت كذلك إلى 100 سنة و ذلك عندما تحقق أويلر (Euler )  في 1750 من أن العدد التالي في قائمة ميرسين هو ، و بعد قرن آخر و في 1876 بين لوكاس ( Lucas )  أن العدد  كان أوليا ، و بعد سبع سنوات أثبت بيرفوستين (Pervouchine ) أن العدد  أوليا و هذا لم يذكره ميرسين ، كذلك أثبت باورس (Powers ) في بداية القرن القرن العشرين أن ميرسين أغفل أيضا العددان الأوليان   و   و بنهاية عام 1947 كانت سلسلة ميرسين للأعداد (n<258 ) قد اكتملت بشكلها الصحيح و هي :

(n = 2,3,5,7,13,17,19,31,61,89,107,127 ) ، أما بالنسبة لبقية أعداد ميرسين فقد تم اكتشافها مع ظهور الحاسب الحالي .

        ( أنظر : قائمة بأعداد ميرسين )

العدد التام ونظريات هامة

نظرا لوجود ارتباط بين الأعداد الأولية و الأعداد التامة فارتأيت توضيح مفهوم العدد التام قبل الدخول في النظريات و الإختبارات التي وضعها العلماء لفحص الأعداد و معرفة أوليتها .

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

أول عدد تام هو 6 حيث أن : 6 = 1 + 2 + 3

و العدد التام التالي هو :       28= 1+ 2 + 4 + 7 + 14

و العددان التامان التاليان هما : 496  و  8128  .

كانت هذه الأعداد الأربعة هي الأعداد التامة المعروفة حتى عصر المسيح ، و لو جئنا إلى هذه الأعداد لتحليلها فسوف نجد أنه بإمكاننا تحليلها كالتالي :  2.3 , 4.7 , 13.31 , 64.127  ،  فنلاحظ أن جميعها من الصورة    لكل ( n = 2,3,5,7 ) بالترتيب ، و في كل حالة  هو من أعداد ميرسين الأولية ، و هنا مربط اللغز بشأن علاقة الأعداد التامة بأعداد ميرسين الأولية .

و نستطيع مما سبق أن نثبت بسهولة النظريات التالية :

( البرهان )

نظرية 1 : يقال للعدد n أنه تاما إذا و فقط إذا كان على الصورة 2^k-1(2^k-1) ، و 2^k-1 عدد أولي

( البرهان )

نفرض أولا أن p = 2^k-1  عددا أوليا ، و n = 2^k-1(2^k-1)  . لإثبات أن العدد nتاما يجب أن نثبت أن : sigma(n)=2n  . (  انظر معنى sigma)

بما أن دالة السيجما ضربية (multiplicative ) ، و s(p) = p+1=2^k ، بالتالي نستطيع أن نعرف أن :  s(n) = s(2^k-1). s(p) = (2^k-1)2^k = 2n ،  و هذا يثبت أن n عدد تام .

و على الجانب الآخر ، لنفرض أن n  عددا تاما زوجيا ، و ليكن n = 2^k-1.mn  حيث m  عدد فردي ، k ³ 2. و بما أن دالة السيجما ضربية ، إذن :

s(2^k-1.m) = s(2^k-1). s(m)=2^k-1). s(m)  -------> (1)

، و بما أن n  عددا تاما ، فإنه أيضا نعرف أن :

s(n)=2n = 2^k.m                                   -------> (2)

من 1 ، 2  نستنتج أن :

2^k.m = (2^k-1). s(m)                            -------> (3)

أي إن 2^k-1  يقسم 2^k.m  و من هنا 2^k-1  يقسم m  ، أي إن : m = (2^k-1)M   ، و بتعويض هذا الأخير في المعادلة (3) ، و بقسمة الطرفين على 2^k-1  نحصل على 2^k.M=s(m)  .

بما أن كلا من m,M   هما قواسم لـ m  إذا من السهولة أن نعرف أن :

2^k.M=s(m)³ m+M = 2^k.M    ، و بالتالي :  s(m) = m+M .

و هذا يعني أن m  عدد أولي له عاملان فقط و هما نفسه m  و الواحد M  ، و هكذا يكون :

     m = 2^k-1  عددا أوليا .

         ( البرهان ) 

نظرية 2 : إذا كان العدد 2ⁿ-1   أولي فإن n   يكون أوليا أيضا .

( البرهان )

  نفرض أن r , s  عددان صحيحان موجبان ، بالتالي الحدودية x^rs-1 تساوي :

x^rs-1 = (x^s-1)(x^s(r-1) + x^s(r-2)+ ... + x^s + 1 )  ،

 أي إنه إذا كانت n مركبة ( و لتكن تساوي  r.s  بحيث 1 < s £ n  ) فإن 2ⁿ-1  تكون أيضا مركبة لأنها تقبل القسمة على 2^s-1  .

            نعود الآن للأعداد التامة حيث أنه لعلك لاحظت أيضا أن الأعداد التامة المذكورة و هي :

(6 , 28 , 496 , 8128 ) كلها تنتهي إما بالعدد 6 أو العدد 8 ، و هذا يمكن إثباته بسهولة ، و لكنها لا تنتهي بالكيفية المتغيرة (6 , 8 , 6 , 8 ,..  ) ، و لو كتبنا الأعداد التامة الأربعة السابقة بالنظام الثنائي فسنجد انها كالتالي :

110

11100

1111110000

111111100000

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

            عندما نريد النظر في أعداد ميرسن و التحقق من كونها أولية نبحث في العادة عن أي قواسم صغيرة  ، و النظرية التالية لفيرمات و أويلر مهمة جدا بهذا الخصوص و هي :

             ( البرهان باللغة الإنجليزية )

            أخيرا ، نقدم النظريات التالية لتمعن النظر فيها :

             ( البرهان باللغة الإنجليزية )

             ( البرهان باللغة الإنجليزية )

كيف تتم معرفة الأعداد الأولية

بعد استعراضنا للأعداد التامة و أهم النظريات التي تربط بينها و بين الأعداد الأولية ، يبقى السؤال الذي اخترناه لهذا الفصل بدون إجابة ، و هو : كيف يتم الكشف عن الأعداد الأولية ؟

و يجدر بنا هنا أن نشير إلى أن الأعداد الأولية يمكن أن نقسمها على قسمين الأعداد الأولية الصغيرة ( الأقل من 10000000000 ) و الأعداد الأولية الكبيرة .

الأعداد الأولية الصغيرة :

يمكن معرفة الأعداد الأولية الصغيرة بأحد طريقتين و هما :

أولا : غربال إيراتوستين (Sieve of Eratosthenes ):

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

              و تقول هذه الطريقة أنه لإيجاد جميع الأعداد الأولية الأصغر من n  اكتب في قائمة جميع هذه الأعداد الأصغر من n  ثم استبعد جميع  مضاعفات الأعداد الأولية بحيث تبدأ من مضاعفات 2 ثم 3 ثم 5 ثم 7 و هكذا فالأعداد المتبقية هي الأعداد الأولية و الجدول التالي يوضح مثال لغربال إيراتوستين المستخدم في الأعداد الأقل من 100 :

               و كيفية العمل في الجدول السابق هو بأن نبدأ بأول عدد و هو الواحد و يتم استبعاده مباشرة ، العدد الذي يليله هو 2 فيكون أول عدد أولي ثم نستبعد جميع مضاعفاته الموجودة بالجدول ، العدد التالي هو 3 فنختاره حيث أنه العدد الذي لم يحذف فيكون أول عدد أولي فردي ثم نحذف جميع مضاعفاته الغير محذوفة ، و نستمر بالمسير فنجد أن 4 محذوف أي إنه غير أولي ، و لكن الذي يليه و هو 5 غير محذوف فيكون العدد الأولي الثالث ثم نحذف جميع مضاعفاته الغير محذوفة ، و نستمر بهذه الطريقة بالنسبة للعدد 7 و 11 و هكذا حتى نكون قد استبعدنا جميع المضاعفات ليتبقى لدينا الأعداد الأولية الأقل من 100 ، و هي الأعداد الزرقاء في الجدول . 

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

ثانيا : طريقة القسمة ( trial division ) :

 تستخدم هذه الطريقة أيضا في الكشف عن الأعداد الأولية الصغيرة ، و هي أصعب من سابقتها ، و لكن باستطاعة طلاب المرحلة الثانوية إنجازها ، فلكي نفحص نعرف أن عددا ما n هل أولي ؟ فإننا نقسمه على جميع الأعداد الأولية الأقل من جذره التربيعي ، فعلى سبيل المثال لو أردنا أن نفحص أولية العدد 211 ، فإننا نحتاج لأن نقسمه على 2 ، 3 ، 5 ، 7 ، 11 ، 13 ، فإذا لم يقبل القسمة على أي منها فيكون العدد 211 أوليا و إلا فلا . و لا حاجة لنجرب قسمته على عدد أول أكثر من 13 لأن جذره التربيعي أقل من 15 ، و هذا يعني أن علينا أن نتوقف عن القسمة عندما نصل إلى جذره التربيعي التقريبي .

في الحقيقة قد تصبح هذه الطريقة صعبة عندما تكبر الأعداد فليس من السهل أن تستخدم الطريقة هذه بحذافيرها مع العدد 100000001 على سبيل المثال ، على الرغم أن هذا العدد لا يعتبر من الأعداد الكبيرة ، فلو جئنا إلى هذا العدد و أردنا أن نطبق طريقة القسمة عليه لمعرفة هل هو أولي أم لا ، فيجب علينا أن نبدأ مع الرقم 2 و نكرر ذلك حتى نصل إلى أحد قواسمه أو نتوقف عند العدد الأولي الأقل من جذره التربيعي مباشرة ، و إذا عرفنا أن  sqrt(100000001)@ 10000 و عدد الأعداد الأولية الأقل من 10000 حسب صيغة ليجاندر و هي :  p(n)=n/(log(n)-1.08366) هي :

            p(10000)=10000/(log(10000)-1.08366) @ 3428  ،  أي أنه علينا أن نقسم على 3428 عدد أولي تقريبا ، و لا يخفى أن في هذا صعوبة من حيث الوقت و الجهد ، لذلك استخدم الرياضيون و ابتكروا مهارات مختلفة و أدخلوا التحليل الرياضي فيها ، و لكن الحاسب الآلي سهل أمر هذه القسمة حيث كتبت برامج و خورازميات عديدة تنفذ القسمة آليا ، و باعتقادي أن من لديه معرفة بسيطة ببرنامج الإكسل الذي تصدره شركة مايكروسوفت ضمن مجموعة الأوفيس يستطيع اكتشاف أولية هذا الرقم باستخدام القسمة شريطة أن تكون لديه قائمة بكل الأعداد الأولية الأقل من 10000 و عددها بالدقة 1229 عددا .

           إذا كنت تريد معرفة الأعداد الأولية الأقل من 10000 ( انظر هنا )

الأعداد الأولية الكبيرة :

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

اختبار ليكاس- لهمر :

لكل p عدد أولي فردي ، عدد ميرسين يكون أوليا إذا و فقط  إذا كان يقسم  s(p-1) حيث S(n+1)=S(n)²-2  و S(1)=4   .

لقد مرت هذه النظرية بعدة مراحل حتى وصل إلى هذه الصورة حيث كانت بدايتها مع مبرهنة فيرمات الصغيرة ، و الخطوة التالية مع أويلر عندما عمم مبرهنة فيرمات الصغيرة ، و الخطوة الهامة التالية مع لوكاس الذي وضع النظرية في أواخر 1870 ، و أخيرا مع لهمر الذي بسطها و جعلها في صورة اختبار بسيط في 1930 ، أما بالنسبة للمتتالية S(n)  فهي تحسب باقي لحفظ الوقت  ، و لن أحاول برهنة الإختبار هنا لحاجة البرهان إلى مقدمات كما أوضحت ، و لكن أشير إلى أنه بناءا على هذه النظرية يمكن استنتاج الإختبار التالي على شكل أكواد :

 Lucas_Lehmer_Test(p):

    S := 4;

    For I from 3 to p do

       s :=  s²-2 mod 2^p-1;

       If s == 0 then

         is prime

       else

         is composite

و هذا الإختبار يناسب الحواسيب الثنائية لأن القسمة على في النظام الثنائي تتم باستخدام الدوران و الإضافة .

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

http://www.utm.edu/research/primes/prove/

برامج وملفات

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

أولا : Perfect1

-         الوظيفة : باحث عن الأعداد التامة باستخدام الصيغة 2^n-1(2ⁿ-1) .

-         اللغة : الإنجليزية .

-         المصدر :

-    العمل : يطلب منك البرنامج إدخال عدد أولي بحيث يكون العدد 2ⁿ-1 من أعداد ميرسين الأولية .

-         الحجم : 427 كيلوبايت

-         نوع الملف : مضغوط على هيئة zip ، و لا يحتاج إلى تنصيب .

-         للتنزيل ( اضغط هنا )

ثانيا : Primef25

-         الوظيفة : محلل و مجزء لأي عدد .

-         اللغة : الإنجليزية .

-         المصدر :

-    العمل : يطلب منك إدخال أي عدد ، ثم يقوم بتحليله و يظهر لك النتيجة على شكل أسس ، فلو أدخلت مثلا : 15 ، فإن نتيجة التحليل تكون كالتالي : 3^1 5^1 = 15 ، مما يعني أنه لدينا عاملان هما 3 ، و 5 و كل منها يتكرر مرة واحدة بدلالة الأس ، و هذا يعني أن العدد 15 ليس أوليا ، و لكن تحليل العدد 29 يعطينا 29^1 أي لا يوجد عوامل غير 29 نفسه و بالتالي 29 عدد أولي ، و يمكن إدخال أي رقم حتى لو كان كبيرا .

-         الحجم : 74 كيلوبايت .

-         نوع الملف : مضغوط على هيئة zip ، و لا يحتاج إلى تنصيب .

-         للتنزيل ( اضغط هنا )

للمشاهدة :

·    اضغط لمشاهدة أول ألف عدد أولي .

·    اضغط هنا لمشاهدة أول عشرة آلاف عدد أولي .

·    اضغط هنا لمشاهدة ملف نصي لأول مائة ألف عدد أولي على نظام txt .

المصادر :بعض المواقع الإنجليزية وصندوق الرياضيات