عالم الأعداد الأولية
تقديم موجز
لقد كانت الأعداد هي أول ما ظهر من علوم الرياضيات لكونها أقرب هذه العلوم إلى واقع الإنسان ، و تمتلك بعض الأعداد خصائص سحرية و غريبة جعلتها تجذب بال العلماء و الرياضيين و منها الأعداد الأولية .
تمتلك الأعداد الأولية خصائص فريدة من نوعها من كونها غير منتظمة و بالتالي عدم إمكانية التخمين بها ، و لكونها أصل جميع الأعداد حسب النظرية الأساسية في الحساب ، بل إن لها تأثير أكبر من ذلك حيث وسعت خيال الرياضيين للإبحار فيما عرف بالأعداد الأولية الكبيرة و التي يقف العقل أمامها منذهلا من ضخامة هذه الأعداد و كيف توصل إليها العقل بنوعيه البشري و الآلي ، فيكفي أن نقول أن أكبر عدد أولي تم اكتشافه مؤخرا يحتاج لكتابته بخط صغير إلى ورقة طولها يقارب خمسة كيلومترات !!!
موقع الأرقام يتقدم بالشكر إلى أصحاب العديد من المواقع الإنجليزية وإلى صاحب موقع صندوق الرياضيات ، ونرجو أن نكون قد وفقنا بعض الشيء لمنفعة المتابع والباحث والطالب .
أعداد ميرسين الأولية
يتكرر هذا الإسم كثيرا في عالم الأعداد الأولية ، و هي الأعداد من الصورة : ، و لعل الذي جذب الأنظار إلى هذه الأعداد هو سهولة التحقق من أوليتها في الحواسيب الثنائية ، لذلك أكبر الأعداد الأولية المعروفة حاليا من هذه الصورة من الأعداد .
لقد كان عدد من الرياضيين السابقين يعتقدون أن العدد من الصورة يكون أوليا كلما كان 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 ) ، أما بالنسبة لبقية أعداد ميرسين فقد تم اكتشافها مع ظهور الحاسب الحالي .
( أنظر : قائمة بأعداد ميرسين )
أعداد ميرسين المعروفة ( Mp= 2p-1 ) :
المكتشف
سنة الإكتشاف
عدد أرقام العدد ( Mp )
الأس (P)
م
----
----
1
2
1
----
----
1
3
2
----
----
2
5
3
----
----
3
7
4
anonymous
1456
4
13
5
Cataldi
1588
6
17
6
Cataldi
1588
6
19
7
Euler
1772
10
31
8
Pervushin
1883
19
61
9
Powers
1911
27
89
10
Powers
1914
33
107
11
Lucas
1876
39
127
12
Robinson
1952
157
521
13
Robinson
1952
183
607
14
Robinson
1952
386
1279
15
Robinson
1952
664
2203
16
Robinson
1952
687
2281
17
Riesel
1957
969
3217
18
Hurwitz
1961
1281
4253
19
Hurwitz
1961
1332
4423
20
Gillies
1963
2917
9689
21
Gillies
1963
2993
9941
22
Gillies
1963
3376
11213
23
Tuckerman
1971
6002
19937
24
Noll & Nickel
1978
6533
21701
25
Noll
1979
6987
23209
26
Nelson & Slowinski
1979
13395
44497
27
Slowinski
1982
25962
86243
28
Colquitt & Welsh
1988
33265
110503
29
Slowinski
1983
39751
132049
30
Slowinski
1985
65050
216091
31
Slowinski & Gage
1992
227832
756839
32
Slowinski & Gage
1994
258716
859433
33
Slowinski & Gage
1996
378632
1257787
34
Armengaud, Woltman,
et. al. (GIMPS)
1996
420921
1398269
35
Spence, Woltman,
et. al. (GIMPS)
1997
895932
2976221
36
Clarkson, Woltman, Kurowski
et. al. (GIMPS, PrimeNet)
1998
909526
3021377
37
Hajratwala, Woltman, Kurowski
et. al. (GIMPS, PrimeNet)
1999
2098960
6972593
38
( المصدر : http://www.utm.edu/research/primes/mersenne.shtml )
العدد التام ونظريات هامة
نظرا لوجود ارتباط بين الأعداد الأولية و الأعداد التامة فارتأيت توضيح مفهوم العدد التام قبل الدخول في النظريات و الإختبارات التي وضعها العلماء لفحص الأعداد و معرفة أوليتها .
عدد من الحضارات القديمة كانت مهتمة بالعلاقات بين العدد و مجموع عوامله ، و غالبا ما تقدم تفسيرات سحرية ، و أحد هذه العلاقات أفرزت ما يسمى بالعدد التام . ( انظر تعريف العدد التام )
أول عدد تام هو 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 أنه تاما إذا و فقط إذا كان على الصورة ، و عدد أولي .
( البرهان )
نظرية 1 : يقال للعدد n أنه تاما إذا و فقط إذا كان على الصورة 2k-1(2k-1) ، و 2k-1 عدد أولي
( البرهان )
نفرض أولا أن p = 2k-1 عددا أوليا ، و n = 2k-1(2k-1) . لإثبات أن العدد nتاما يجب أن نثبت أن : sigma(n)=2n . ( انظر معنى sigma)
بما أن دالة السيجما ضربية (multiplicative ) ، و s(p) = p+1=2k ، بالتالي نستطيع أن نعرف أن : s(n) = s(2k-1). s(p) = (2k-1)2k = 2n ، و هذا يثبت أن n عدد تام .
و على الجانب الآخر ، لنفرض أن n عددا تاما زوجيا ، و ليكن n = 2k-1.mn حيث m عدد فردي ، k ³ 2. و بما أن دالة السيجما ضربية ، إذن :
s(2k-1.m) = s(2k-1). s(m)=2k-1). s(m) -------> (1)
، و بما أن n عددا تاما ، فإنه أيضا نعرف أن :
s(n)=2n = 2k.m -------> (2)
من 1 ، 2 نستنتج أن :
2k.m = (2k-1). s(m) -------> (3)
أي إن 2k-1 يقسم 2k.m و من هنا 2k-1 يقسم m ، أي إن : m = (2k-1)M ، و بتعويض هذا الأخير في المعادلة (3) ، و بقسمة الطرفين على 2k-1 نحصل على 2k.M=s(m) .
بما أن كلا من m,M هما قواسم لـ m إذا من السهولة أن نعرف أن :
2k.M=s(m)³ m+M = 2k.M ، و بالتالي : s(m) = m+M .
و هذا يعني أن m عدد أولي له عاملان فقط و هما نفسه m و الواحد M ، و هكذا يكون :
m = 2k-1 عددا أوليا .
نظرية 2 : إذا كان العدد أولي فإن n يكون أوليا أيضا .
( البرهان )
نظرية 2 : إذا كان العدد 2n-1 أولي فإن n يكون أوليا أيضا .
( البرهان )
نفرض أن r , s عددان صحيحان موجبان ، بالتالي الحدودية xrs-1 تساوي :
xrs-1 = (xs-1)(xs(r-1) + xs(r-2)+ ... + xs + 1 ) ،
أي إنه إذا كانت n مركبة ( و لتكن تساوي r.s بحيث 1 < s £ n ) فإن 2n-1 تكون أيضا مركبة لأنها تقبل القسمة على 2s-1 .
نعود الآن للأعداد التامة حيث أنه لعلك لاحظت أيضا أن الأعداد التامة المذكورة و هي :
(6 , 28 , 496 , 8128 ) كلها تنتهي إما بالعدد 6 أو العدد 8 ، و هذا يمكن إثباته بسهولة ، و لكنها لا تنتهي بالكيفية المتغيرة (6 , 8 , 6 , 8 ,.. ) ، و لو كتبنا الأعداد التامة الأربعة السابقة بالنظام الثنائي فسنجد انها كالتالي :
110
11100
1111110000
111111100000
من غير المعروف حتى الآن هل هناك عدد تام فردي ، و لكن إذا كان موجودا فحتما أنه سيكون كبيرا جدا ، و الحقيقة أن هذه المسألة هي أقدم مسألة غير محلولة لحد الآن في الرياضيات .
عندما نريد النظر في أعداد ميرسن و التحقق من كونها أولية نبحث في العادة عن أي قواسم صغيرة ، و النظرية التالية لفيرمات و أويلر مهمة جدا بهذا الخصوص و هي :
نظرية 3 : لو فرضنا أن العددان p,q ، فإذا كان q يقسم Mp= ، فإن
q = +/-1(mod
و q = 2kp + 1 لبعض الأعداد الصحيحة k .
( البرهان باللغة الإنجليزية )
The point of this "footnote" is to prove the following theorem which we use on our page about Mersenne primes and the historical note "the Largest Known Prime by Year". Fermat discovered and use the first part of this theorem (p = 1 modulo q) and Euler discovered the second.
Theorem.
Let p and q be odd primes. If p divides Mq, then p = 1 (mod q) and p = +/-1 (mod.
Below we give a proof and an example.
Proof.
If p divides Mq, then 2q = 1 (mod p) and the order of 2 (mod p) divides the prime q, so it must be q. By Fermat's Little Theorem the order of 2 also divides p-1, so p-1 = 2kq. This gives
2(p-1)/2 = 2qk = 1 (mod p)
so 2 is a quadratic residue mod p and it follows p = +/-1 (mod, which completes the proof.
Example: Suppose p divides M31, then the two parts of the theorem together show p = 1 or 63 (mod 248). By 1772 Euler had used this to show M31 was prime.
أخيرا ، نقدم النظريات التالية لتمعن النظر فيها :
نظرية 4 : بفرض أن p=3(mod 4) عدد أولي ، فإن أيضا أولي إذا و فقط إذا 2p+1 يقسم Mp .
( البرهان باللغة الإنجليزية )
The point of this "footnote" is to prove the following theorem stated by Euler in 1750 and proved by Lagrange in 1775. We use this theorem on our page about Mersenne primes.
Theorem.
Let p = 3 (mod 4) be prime. 2p+1 is also prime if and only if 2p+1 divides Mp.
Proof.
Suppose q = 2p+1 is prime. q = 7 (mod so 2 is a quadratic residue modulo q and it follows that there is an integer n such that n2 = 2 (mod q). This shows
2p = 2(q-1)/2 = nq-1 = 1 (mod q),
showing q divides Mp.
Conversely, let 2p+1 be a factor of Mp. Suppose, for proof by contradiction, that 2p+1 is composite and let q be its least prime factor. Then 2p = 1 (mod q) and the order of 2 modulo q divides both p and q-1, hence p divides q-1. This shows q > p and it follows
(2p+1) + 1 > q2 > p2
which is a contradiction since p > 2.
Note.
This means that if p = 3 (mod 4) and 2p+1 are both prime, then either p is 3 or Mp is composite.
نظرية 5 : إذا جمعت أرقام أي عدد تام زوجي ( غير 6 ) ، ثم جمعت أرقام الناتج و بتكرار العملية حتى تحصل على رقم واحد فإن ذلك الرقم سيكون 1 .
( البرهان باللغة الإنجليزية )
To test for divisibility by three (or nine), we often sum the digits and test the resulting sum. If the resulting sum has several digits, then sum again. Edwin O'Sullivan pointed that if we repeatedly sum the digits of an even perfect number (other than six), we always get one. Conrad Curry later poined out that this result can be found in [Gardner68].
Theorem.
If you sum the digits of any even perfect number (except 6), then sum the digits of the resulting number, and repeat this process until you get a single digit, that digit will be one.
Examples.
28
10 1, 496 19 10 1, and 8128 19 10 1
Proof.
Let s(n) be the sum of the digits of n. It is easy to see that s(n) = n (mod 9). So to prove the theorem, we need only show that perfect numbers are congruent to one modulo nine. If n is a perfect number, then n has the form 2p-1(2p-1) where p is prime (see theorem one). So p is either 2, 3, or is congruent to 1 or 5 modulo 6. Note that we have excluded the case p=2 (n=6). Finally, modulo nine, the powers of 2 repeat with period 6 (that is, 26 = 1 (mod 9)), so modulo nine n is congruent to one of the three numbers 21-1(21-1), 23-1(23-1), or 25-1(25-1), which are all 1 (mod 9).
كيف تتم معرفة الأعداد الأولية
بعد استعراضنا للأعداد التامة و أهم النظريات التي تربط بينها و بين الأعداد الأولية ، يبقى السؤال الذي اخترناه لهذا الفصل بدون إجابة ، و هو : كيف يتم الكشف عن الأعداد الأولية ؟
و يجدر بنا هنا أن نشير إلى أن الأعداد الأولية يمكن أن نقسمها على قسمين الأعداد الأولية الصغيرة ( الأقل من 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-2 و S(1)=4 .
لقد مرت هذه النظرية بعدة مراحل حتى وصل إلى هذه الصورة حيث كانت بدايتها مع مبرهنة فيرمات الصغيرة ، و الخطوة التالية مع أويلر عندما عمم مبرهنة فيرمات الصغيرة ، و الخطوة الهامة التالية مع لوكاس الذي وضع النظرية في أواخر 1870 ، و أخيرا مع لهمر الذي بسطها و جعلها في صورة اختبار بسيط في 1930 ، أما بالنسبة للمتتالية S(n) فهي تحسب باقي لحفظ الوقت ، و لن أحاول برهنة الإختبار هنا لحاجة البرهان إلى مقدمات كما أوضحت ، و لكن أشير إلى أنه بناءا على هذه النظرية يمكن استنتاج الإختبار التالي على شكل أكواد :
Lucas_Lehmer_Test(p):
S := 4;
For I from 3 to p do
s := s2-2 mod 2p-1;
If s == 0 then
is prime
else
is composite
و هذا الإختبار يناسب الحواسيب الثنائية لأن القسمة على في النظام الثنائي تتم باستخدام الدوران و الإضافة .
هذا ما أستطيع الإشارة إليه فيما يخص الكشف عن الأعداد الأولية الكبيرة ، و كما قلت إن النظريات و الإختبارات المستخدمة في الكشف عن الأعداد الأولية كثيرة ، و قد حولها العلماء إلى برامج وفق لغات الكمبيوتر لتسهيل حسابها كما هو الحال في اختبار لوكاس- لهمر ، و الأمر الذي جعلني أغض النظر عن تلك النظريات هو كونها نظريات متخصصة بحيث يتطلب فهمها عدة مقدمات قد يصعب على مثلي استيعابها ، و لكن يستطيع الباحث المتخصص في ذلك أن يجدها و باللغة الإنجليزية على الرابط :
http://www.utm.edu/research/primes/prove/
تقديم موجز
لقد كانت الأعداد هي أول ما ظهر من علوم الرياضيات لكونها أقرب هذه العلوم إلى واقع الإنسان ، و تمتلك بعض الأعداد خصائص سحرية و غريبة جعلتها تجذب بال العلماء و الرياضيين و منها الأعداد الأولية .
تمتلك الأعداد الأولية خصائص فريدة من نوعها من كونها غير منتظمة و بالتالي عدم إمكانية التخمين بها ، و لكونها أصل جميع الأعداد حسب النظرية الأساسية في الحساب ، بل إن لها تأثير أكبر من ذلك حيث وسعت خيال الرياضيين للإبحار فيما عرف بالأعداد الأولية الكبيرة و التي يقف العقل أمامها منذهلا من ضخامة هذه الأعداد و كيف توصل إليها العقل بنوعيه البشري و الآلي ، فيكفي أن نقول أن أكبر عدد أولي تم اكتشافه مؤخرا يحتاج لكتابته بخط صغير إلى ورقة طولها يقارب خمسة كيلومترات !!!
موقع الأرقام يتقدم بالشكر إلى أصحاب العديد من المواقع الإنجليزية وإلى صاحب موقع صندوق الرياضيات ، ونرجو أن نكون قد وفقنا بعض الشيء لمنفعة المتابع والباحث والطالب .
أعداد ميرسين الأولية
يتكرر هذا الإسم كثيرا في عالم الأعداد الأولية ، و هي الأعداد من الصورة : ، و لعل الذي جذب الأنظار إلى هذه الأعداد هو سهولة التحقق من أوليتها في الحواسيب الثنائية ، لذلك أكبر الأعداد الأولية المعروفة حاليا من هذه الصورة من الأعداد .
لقد كان عدد من الرياضيين السابقين يعتقدون أن العدد من الصورة يكون أوليا كلما كان 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 ) ، أما بالنسبة لبقية أعداد ميرسين فقد تم اكتشافها مع ظهور الحاسب الحالي .
( أنظر : قائمة بأعداد ميرسين )
أعداد ميرسين المعروفة ( Mp= 2p-1 ) :
المكتشف
سنة الإكتشاف
عدد أرقام العدد ( Mp )
الأس (P)
م
----
----
1
2
1
----
----
1
3
2
----
----
2
5
3
----
----
3
7
4
anonymous
1456
4
13
5
Cataldi
1588
6
17
6
Cataldi
1588
6
19
7
Euler
1772
10
31
8
Pervushin
1883
19
61
9
Powers
1911
27
89
10
Powers
1914
33
107
11
Lucas
1876
39
127
12
Robinson
1952
157
521
13
Robinson
1952
183
607
14
Robinson
1952
386
1279
15
Robinson
1952
664
2203
16
Robinson
1952
687
2281
17
Riesel
1957
969
3217
18
Hurwitz
1961
1281
4253
19
Hurwitz
1961
1332
4423
20
Gillies
1963
2917
9689
21
Gillies
1963
2993
9941
22
Gillies
1963
3376
11213
23
Tuckerman
1971
6002
19937
24
Noll & Nickel
1978
6533
21701
25
Noll
1979
6987
23209
26
Nelson & Slowinski
1979
13395
44497
27
Slowinski
1982
25962
86243
28
Colquitt & Welsh
1988
33265
110503
29
Slowinski
1983
39751
132049
30
Slowinski
1985
65050
216091
31
Slowinski & Gage
1992
227832
756839
32
Slowinski & Gage
1994
258716
859433
33
Slowinski & Gage
1996
378632
1257787
34
Armengaud, Woltman,
et. al. (GIMPS)
1996
420921
1398269
35
Spence, Woltman,
et. al. (GIMPS)
1997
895932
2976221
36
Clarkson, Woltman, Kurowski
et. al. (GIMPS, PrimeNet)
1998
909526
3021377
37
Hajratwala, Woltman, Kurowski
et. al. (GIMPS, PrimeNet)
1999
2098960
6972593
38
( المصدر : http://www.utm.edu/research/primes/mersenne.shtml )
العدد التام ونظريات هامة
نظرا لوجود ارتباط بين الأعداد الأولية و الأعداد التامة فارتأيت توضيح مفهوم العدد التام قبل الدخول في النظريات و الإختبارات التي وضعها العلماء لفحص الأعداد و معرفة أوليتها .
عدد من الحضارات القديمة كانت مهتمة بالعلاقات بين العدد و مجموع عوامله ، و غالبا ما تقدم تفسيرات سحرية ، و أحد هذه العلاقات أفرزت ما يسمى بالعدد التام . ( انظر تعريف العدد التام )
أول عدد تام هو 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 أنه تاما إذا و فقط إذا كان على الصورة ، و عدد أولي .
( البرهان )
نظرية 1 : يقال للعدد n أنه تاما إذا و فقط إذا كان على الصورة 2k-1(2k-1) ، و 2k-1 عدد أولي
( البرهان )
نفرض أولا أن p = 2k-1 عددا أوليا ، و n = 2k-1(2k-1) . لإثبات أن العدد nتاما يجب أن نثبت أن : sigma(n)=2n . ( انظر معنى sigma)
بما أن دالة السيجما ضربية (multiplicative ) ، و s(p) = p+1=2k ، بالتالي نستطيع أن نعرف أن : s(n) = s(2k-1). s(p) = (2k-1)2k = 2n ، و هذا يثبت أن n عدد تام .
و على الجانب الآخر ، لنفرض أن n عددا تاما زوجيا ، و ليكن n = 2k-1.mn حيث m عدد فردي ، k ³ 2. و بما أن دالة السيجما ضربية ، إذن :
s(2k-1.m) = s(2k-1). s(m)=2k-1). s(m) -------> (1)
، و بما أن n عددا تاما ، فإنه أيضا نعرف أن :
s(n)=2n = 2k.m -------> (2)
من 1 ، 2 نستنتج أن :
2k.m = (2k-1). s(m) -------> (3)
أي إن 2k-1 يقسم 2k.m و من هنا 2k-1 يقسم m ، أي إن : m = (2k-1)M ، و بتعويض هذا الأخير في المعادلة (3) ، و بقسمة الطرفين على 2k-1 نحصل على 2k.M=s(m) .
بما أن كلا من m,M هما قواسم لـ m إذا من السهولة أن نعرف أن :
2k.M=s(m)³ m+M = 2k.M ، و بالتالي : s(m) = m+M .
و هذا يعني أن m عدد أولي له عاملان فقط و هما نفسه m و الواحد M ، و هكذا يكون :
m = 2k-1 عددا أوليا .
نظرية 2 : إذا كان العدد أولي فإن n يكون أوليا أيضا .
( البرهان )
نظرية 2 : إذا كان العدد 2n-1 أولي فإن n يكون أوليا أيضا .
( البرهان )
نفرض أن r , s عددان صحيحان موجبان ، بالتالي الحدودية xrs-1 تساوي :
xrs-1 = (xs-1)(xs(r-1) + xs(r-2)+ ... + xs + 1 ) ،
أي إنه إذا كانت n مركبة ( و لتكن تساوي r.s بحيث 1 < s £ n ) فإن 2n-1 تكون أيضا مركبة لأنها تقبل القسمة على 2s-1 .
نعود الآن للأعداد التامة حيث أنه لعلك لاحظت أيضا أن الأعداد التامة المذكورة و هي :
(6 , 28 , 496 , 8128 ) كلها تنتهي إما بالعدد 6 أو العدد 8 ، و هذا يمكن إثباته بسهولة ، و لكنها لا تنتهي بالكيفية المتغيرة (6 , 8 , 6 , 8 ,.. ) ، و لو كتبنا الأعداد التامة الأربعة السابقة بالنظام الثنائي فسنجد انها كالتالي :
110
11100
1111110000
111111100000
من غير المعروف حتى الآن هل هناك عدد تام فردي ، و لكن إذا كان موجودا فحتما أنه سيكون كبيرا جدا ، و الحقيقة أن هذه المسألة هي أقدم مسألة غير محلولة لحد الآن في الرياضيات .
عندما نريد النظر في أعداد ميرسن و التحقق من كونها أولية نبحث في العادة عن أي قواسم صغيرة ، و النظرية التالية لفيرمات و أويلر مهمة جدا بهذا الخصوص و هي :
نظرية 3 : لو فرضنا أن العددان p,q ، فإذا كان q يقسم Mp= ، فإن
q = +/-1(mod
و q = 2kp + 1 لبعض الأعداد الصحيحة k .( البرهان باللغة الإنجليزية )
The point of this "footnote" is to prove the following theorem which we use on our page about Mersenne primes and the historical note "the Largest Known Prime by Year". Fermat discovered and use the first part of this theorem (p = 1 modulo q) and Euler discovered the second.
Theorem.
Let p and q be odd primes. If p divides Mq, then p = 1 (mod q) and p = +/-1 (mod
. Below we give a proof and an example.
Proof.
If p divides Mq, then 2q = 1 (mod p) and the order of 2 (mod p) divides the prime q, so it must be q. By Fermat's Little Theorem the order of 2 also divides p-1, so p-1 = 2kq. This gives
2(p-1)/2 = 2qk = 1 (mod p)
so 2 is a quadratic residue mod p and it follows p = +/-1 (mod
, which completes the proof. Example: Suppose p divides M31, then the two parts of the theorem together show p = 1 or 63 (mod 248). By 1772 Euler had used this to show M31 was prime.
أخيرا ، نقدم النظريات التالية لتمعن النظر فيها :
نظرية 4 : بفرض أن p=3(mod 4) عدد أولي ، فإن أيضا أولي إذا و فقط إذا 2p+1 يقسم Mp .
( البرهان باللغة الإنجليزية )
The point of this "footnote" is to prove the following theorem stated by Euler in 1750 and proved by Lagrange in 1775. We use this theorem on our page about Mersenne primes.
Theorem.
Let p = 3 (mod 4) be prime. 2p+1 is also prime if and only if 2p+1 divides Mp.
Proof.
Suppose q = 2p+1 is prime. q = 7 (mod
so 2 is a quadratic residue modulo q and it follows that there is an integer n such that n2 = 2 (mod q). This shows 2p = 2(q-1)/2 = nq-1 = 1 (mod q),
showing q divides Mp.
Conversely, let 2p+1 be a factor of Mp. Suppose, for proof by contradiction, that 2p+1 is composite and let q be its least prime factor. Then 2p = 1 (mod q) and the order of 2 modulo q divides both p and q-1, hence p divides q-1. This shows q > p and it follows
(2p+1) + 1 > q2 > p2
which is a contradiction since p > 2.
Note.
This means that if p = 3 (mod 4) and 2p+1 are both prime, then either p is 3 or Mp is composite.
نظرية 5 : إذا جمعت أرقام أي عدد تام زوجي ( غير 6 ) ، ثم جمعت أرقام الناتج و بتكرار العملية حتى تحصل على رقم واحد فإن ذلك الرقم سيكون 1 .
( البرهان باللغة الإنجليزية )
To test for divisibility by three (or nine), we often sum the digits and test the resulting sum. If the resulting sum has several digits, then sum again. Edwin O'Sullivan pointed that if we repeatedly sum the digits of an even perfect number (other than six), we always get one. Conrad Curry later poined out that this result can be found in [Gardner68].
Theorem.
If you sum the digits of any even perfect number (except 6), then sum the digits of the resulting number, and repeat this process until you get a single digit, that digit will be one.
Examples.
28
10 1, 496 19 10 1, and 8128 19 10 1 Proof.
Let s(n) be the sum of the digits of n. It is easy to see that s(n) = n (mod 9). So to prove the theorem, we need only show that perfect numbers are congruent to one modulo nine. If n is a perfect number, then n has the form 2p-1(2p-1) where p is prime (see theorem one). So p is either 2, 3, or is congruent to 1 or 5 modulo 6. Note that we have excluded the case p=2 (n=6). Finally, modulo nine, the powers of 2 repeat with period 6 (that is, 26 = 1 (mod 9)), so modulo nine n is congruent to one of the three numbers 21-1(21-1), 23-1(23-1), or 25-1(25-1), which are all 1 (mod 9).
كيف تتم معرفة الأعداد الأولية
بعد استعراضنا للأعداد التامة و أهم النظريات التي تربط بينها و بين الأعداد الأولية ، يبقى السؤال الذي اخترناه لهذا الفصل بدون إجابة ، و هو : كيف يتم الكشف عن الأعداد الأولية ؟
و يجدر بنا هنا أن نشير إلى أن الأعداد الأولية يمكن أن نقسمها على قسمين الأعداد الأولية الصغيرة ( الأقل من 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-2 و S(1)=4 .
لقد مرت هذه النظرية بعدة مراحل حتى وصل إلى هذه الصورة حيث كانت بدايتها مع مبرهنة فيرمات الصغيرة ، و الخطوة التالية مع أويلر عندما عمم مبرهنة فيرمات الصغيرة ، و الخطوة الهامة التالية مع لوكاس الذي وضع النظرية في أواخر 1870 ، و أخيرا مع لهمر الذي بسطها و جعلها في صورة اختبار بسيط في 1930 ، أما بالنسبة للمتتالية S(n) فهي تحسب باقي لحفظ الوقت ، و لن أحاول برهنة الإختبار هنا لحاجة البرهان إلى مقدمات كما أوضحت ، و لكن أشير إلى أنه بناءا على هذه النظرية يمكن استنتاج الإختبار التالي على شكل أكواد :
Lucas_Lehmer_Test(p):
S := 4;
For I from 3 to p do
s := s2-2 mod 2p-1;
If s == 0 then
is prime
else
is composite
و هذا الإختبار يناسب الحواسيب الثنائية لأن القسمة على في النظام الثنائي تتم باستخدام الدوران و الإضافة .
هذا ما أستطيع الإشارة إليه فيما يخص الكشف عن الأعداد الأولية الكبيرة ، و كما قلت إن النظريات و الإختبارات المستخدمة في الكشف عن الأعداد الأولية كثيرة ، و قد حولها العلماء إلى برامج وفق لغات الكمبيوتر لتسهيل حسابها كما هو الحال في اختبار لوكاس- لهمر ، و الأمر الذي جعلني أغض النظر عن تلك النظريات هو كونها نظريات متخصصة بحيث يتطلب فهمها عدة مقدمات قد يصعب على مثلي استيعابها ، و لكن يستطيع الباحث المتخصص في ذلك أن يجدها و باللغة الإنجليزية على الرابط :
http://www.utm.edu/research/primes/prove/
