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

في البداية، هذا المقال يتعلق باختبار لوكاس-ليهمر الذي ينطبق على أعداد ميرسين فقط. من أجل اختبار لوكاس-ليهمر الذي ينطبق على عدد طبيعي ما أيا كان، المرجو النظر إلى اختبار لوكاس لأولية عدد ما. من أجل اختبار لوكاس-ليهمر-غيزل، المرجو النظر إلى اختبار لوكاس-ليهمر-غيزل. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
وفي هذا السياق، في الرياضيات، اختبار لوكاس ليهمر هو اختبار أولية أعداد ميرسين. اخترع هذا الاختبار من طرف إدوارد لوكاس عام 1856، فطوره لوكاس نفسه عام 1878، كما طوره كذلك ديريك هنري ليهمر في ثلاثينات القرن العشرين.
إذن، من خلال المعادلة (1),
ومن ناحية أخرى، إذن، هو موجود في X* وله عنصر معاكس أضف إلى ذلك, the رتبة of يقسم ولكن , إذن، الرتبة لا تقسم إذن، الرتبة هي بالتحديد
كونه ضروريا
هذا يؤدي إلى التناقض . إذن, أولي.
في هذا الإطار، ولكن q هو أصغر عامل أولي من بين الأعداد الأولية اللائي يشكلن تفكيك إلى جداء عوامل أولية. إذن،
من جهة ثانية، رتبة عنصر في زمرة تساوي على الأكثر عدد عانصر تلك الزمرة. إذن،
في X, رفع كلا الحدين إلى المربع يعطي ما يلي:
و
ومن ناحية أخرى، المرحلة الأخيرة تستعمل هذه الصيغة المغلقة مستعملة في كل من البرهان على كونه كافيا وفي البرهان على كونه ضروريا.
كونه كافيا
في هذا الإطار، الهدف هو البرهان على أن تؤدي إلى أوليا. فيما يلي برهان يستعمل نظرية الزمر الابتدائية، جاء به J. W. Bruce كما شهد بذلك Jason Wojciechowski.
ضرب الحدين في يعطي :
in X.
من جانب آخر، من أجل الوصول إلى تناقض، , يفترض أن Mp هو عدد مركب (أي غير أولي), وليكن q أصغر القواسم الأولية ل Mp. أعداد ميرسن فردية , إذن، q > 2. , لتكن مجموعة الأعداد الصحيحة بتردد q, لتكن الضرب في معرف كما يلي
عنصر من X والذي لا يملك عنصرا معاكسا هو 0, إذن،
افترض أن إذن،
في الوقت الحالي and , إذن،
حيث k عدد صحيح ما. إذن،
إذن،
في هذا الإطار، يبدو بشكل واضح أن عملية الضرب مغلقة، أي أن جداء عددين ينتميان إلى المجموعة X هو بذاته ينتمي إلى X. يرمز إلى عدد عناصر المجموعة X ب
في هذا الإطار، بما أن q > 2, فإن و هي في X. المجموعة الجزئية من X المكونة من العناصر التي تملك عنصرا معاكسا، تكون زمرة، يرمز إليها ب X*، ويرمز إلى عدد عناصرها ب .
تطبيقات
وعلى صعيد آخر، يستعمل اختبار لوكاس-ليهمر لأولية عدد ما البحث الكبير عن أعداد ميرسين الأولية في الإنترنت من أجل البحث عن الأعداد الأولية الكبيرة. انظر إلى أعداد فيرما.
البرهان على الصحة
الهدف هو البرهان على أن Mp أولي إذا وفقط إذا توفر
علاوةً على ذلك، المتتالية معرفة بعلاقة استدعاء ذاتي يمكن تعريفها بتعبير منغلق الشكل. ليكن و . يأتي من ذلك باستعمال البرهان بالترجح ما يلي: أن لجميع قيم i:
من جانب آخر، برهان الصحة المقدم هنا أبسط من البرهان الأصلي الذي جاء به ليهمر. تذكر التعريف
أمثلة
إضافةً إلى ذلك، بما أن القيمة النهائية ل s هي الصفر، فإن الاستنتاج هو أن M3 أولي.
وفي هذا الصدد، من ناحية أخرى، M11 = 2047 = 23 × 89 عدد غير أولي. مجددا، تُعطى القيمة أربعة ل s. ولكن قيمته تُبدل 11−2 = 9 مرةً :
s ← ((4 × 4) − 2) mod 7 = 0.
- s ← ((4 × 4) − 2) mod 2047 = 14
- s ← ((14 × 14) − 2) mod 2047 = 194
- s ← ((194 × 194) − 2) mod 2047 = 788
- s ← ((788 × 788) − 2) mod 2047 = 701
- s ← ((701 × 701) − 2) mod 2047 = 119
- s ← ((119 × 119) − 2) mod 2047 = 1877
- s ← ((1877 × 1877) − 2) mod 2047 = 240
- s ← ((240 × 240) − 2) mod 2047 = 282
- s ← ((282 × 282) − 2) mod 2047 = 1736
وفي السياق ذاته، بما أن القيمة النهائية ل s لا تساوي الصفر، الاستنتاج هو M11 = 2047 عدد ليس بأولي. رغم أن M11 = 2047 لا يملك معاملات بديهية، اختبار لوكاس-ليهمر لا يعطي أي إشارة إلى قيمة هذه العوامل.
وفي السياق ذاته، عدد ميرسن M3 = 23−1 = 7 أولي. اختبار لوكاس-ليهمر يتحقق من ذلك كما يلي. بدايةً، تُعطى القيمة 4 للمتغير s. ولاحقًا تُغير قيمته. 3−2 = 1 مرةً:
الاختبار
ومن ناحية أخرى، الحدود الأولى القليلة من هذه المتتالية هن 4، 14، 194، 37634، ...(انظر إلى موسوعة المتتاليات الصحيحة على الإنترنت). يكون العدد Mp أوليا إذا وفقط إذا توفر ما يلي :
وفي هذا السياق، يعمل اختبار لوكاس-ليهمر كما يلي. ليكن Mp = 2p − 1 عدد ميرسن حيث p عدد أولي فردي. لنعرف المتتالية كما يلي حيث i عدد طبيعي أكبر من الصفر:
يسمى العدد sp − 2 mod Mp باقي لوكاس-ليهمر للعدد p.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟