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

تصغير|200بك|يسار
*هذا المقال يتعلق باختبار لوكاس-ليهمر الذي ينطبق على أعداد ميرسين فقط. من أجل اختبار لوكاس-ليهمر الذي ينطبق على عدد طبيعي ما أيا كان، المرجو النظر إلى [[اختبار لوكاس لأولية عدد ما]]. من أجل اختبار لوكاس-ليهمر-غيزل، المرجو النظر إلى [[اختبار لوكاس-ليهمر-غيزل]].*

في الرياضيات، **اختبار لوكاس ليهمر** هو اختبار أولية أعداد ميرسين. اخترع هذا الاختبار من طرف إدوارد لوكاس عام 1856، فطوره لوكاس نفسه عام 1878، كما طوره أيضا ديريك هنري ليهمر في ثلاثينات القرن العشرين.

## الاختبار
يعمل اختبار لوكاس-ليهمر كما يلي. ليكن *M**p*&nbsp;=&nbsp;2*p*&nbsp;−&nbsp;1 عدد ميرسن حيث p عدد أولي فردي. لنعرف المتتالية \{s_i\} كما يلي حيث i عدد طبيعي أكبر من الصفر:
:
  s_i=
   \begin{cases}
    4 & \text{if }i=0;
   \\
    s_{i-1}^2-2 & \text{otherwise.}
   \end{cases}
 

الحدود الأولى القليلة من هذه المتتالية هن 4، 14، 194، 37634، ...(انظر إلى موسوعة المتتاليات الصحيحة على الإنترنت). يكون العدد *M**p* أوليا إذا وفقط إذا توفر ما يلي :
:s_{p-2} \equiv 0 \pmod{M_p}

يسمى العدد *s**p*&nbsp;−&nbsp;2&nbsp;mod&nbsp;*M**p* *باقي لوكاس-ليهمر للعدد p*.

## أمثلة
عدد ميرسن M3 = 23−1 = 7 أولي. اختبار لوكاس-ليهمر يتحقق من ذلك كما يلي. بدايةً، تُعطى القيمة 4 للمتغير s. وبعد ذلك تُغير قيمته. 3−2&nbsp;=&nbsp;1 مرةً:

* s ← ((4 × 4) − 2) mod 7 = 0.

بما أن القيمة النهائية ل s هي الصفر، فإن الاستنتاج هو أن M3 أولي.

من ناحية أخرى، M11&nbsp;=&nbsp;2047&nbsp;=&nbsp;23&nbsp;×&nbsp;89 عدد غير أولي. مجددا، *تُعطى القيمة أربعة ل s. ولكن قيمته تُبدل 11−2&nbsp;=&nbsp;9 مرةً :

* 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&nbsp;=&nbsp;2047 عدد ليس بأولي. رغم أن M11&nbsp;=&nbsp;2047 لا يملك معاملات بديهية، اختبار لوكاس-ليهمر لا يعطي أي إشارة إلى قيمة هذه العوامل.

## البرهان على الصحة
برهان الصحة المقدم هنا أبسط من البرهان الأصلي الذي جاء به ليهمر. تذكر التعريف
:
  s_i=
   \begin{cases}
    4 & \text{if }i=0;\\
    s_{i-1}^2-2 & \text{otherwise.}
   \end{cases}
 
الهدف هو البرهان على أن *M**p* أولي إذا وفقط إذا توفر s_{p-2} \equiv 0 \pmod{M_p}.

المتتالية {\langle}s_i{\rangle} معرفة بعلاقة استدعاء ذاتي يمكن تعريفها بتعبير منغلق الشكل. ليكن \omega = 2 + \sqrt{3} و \bar{\omega} = 2 - \sqrt{3}. يأتي من ذلك باستعمال البرهان بالترجح ما يلي: أن s_i = \omega^{2^i} + \bar{\omega}^{2^i} لجميع قيم *i*:

:s_0 = \omega^{2^0} + \bar{\omega}^{2^0} = \left(2 + \sqrt{3}\right) + \left(2 - \sqrt{3}\right) = 4
و
:
\begin{align}
 s_n
 &= s_{n-1}^2 - 2 \\
 &= \left(\omega^{2^{n-1}} + \bar{\omega}^{2^{n-1}}\right)^2 - 2 \\
 &= \omega^{2^n} + \bar{\omega}^{2^n} + 2(\omega\bar{\omega})^{2^{n-1}} - 2 \\
 &= \omega^{2^n} + \bar{\omega}^{2^n}.
\end{align}

المرحلة الأخيرة تستعمل \omega\bar{\omega} = \left(2 + \sqrt{3}\right) \left(2 - \sqrt{3}\right) = 1. هذه الصيغة المغلقة مستعملة في كل من البرهان على كونه كافيا وفي البرهان على كونه ضروريا.

### كونه كافيا

الهدف هو البرهان على أن s_{p-2} \equiv 0 \pmod{M_p} تؤدي إلى M_p أوليا. فيما يلي برهان يستعمل نظرية الزمر الابتدائية، جاء به J. W. Bruce كما شهد بذلك Jason Wojciechowski.

افترض أن s_{p-2} \equiv 0 \pmod{M_p}. إذن،
:\omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} = k M_p
حيث *k* عدد صحيح ما. إذن،
:\omega^{2^{p-2}} = k M_p - \bar{\omega}^{2^{p-2}}.
ضرب الحدين في \omega^{2^{p - 2}} يعطي :
:\left(\omega^{2^{p-2}}\right)^2 = k M_p\omega^{2^{p-2}} - (\omega \bar{\omega})^{2^{p-2}}.
إذن،
:\omega^{2^{p-1}} = k M_p\omega^{2^{p-2}} - 1.\qquad\qquad(1)

من أجل الوصول إلى تناقض، , يفترض أن *M**p* هو عدد مركب (أي غير أولي), وليكن *q* أصغر القواسم الأولية ل *M**p*. أعداد ميرسن فردية , إذن، *q*&nbsp;>&nbsp;2. , لتكن \mathbb{Z}_q مجموعة الأعداد الصحيحة بتردد *q*, لتكن X = \left\{a + b \sqrt{3} \mid a, b \in \mathbb{Z}_q\right\}. الضرب في X معرف كما يلي

:\left(a + \sqrt{3} b\right) \left(c + \sqrt{3} d\right) = [(a c + 3 b d) \,\bmod\,q] + \sqrt{3} [(a d + b c) \,\bmod\,q].

يبدو بشكل واضح أن عملية الضرب مغلقة، أي أن جداء عددين ينتميان إلى المجموعة *X* هو بذاته ينتمي إلى *X*. يرمز إلى عدد عناصر المجموعة *X* ب |X|.

بما أن *q*&nbsp;>&nbsp;2, فإن \omega و \bar{\omega} هي في *X*. المجموعة الجزئية من *X* المكونة من العناصر التي تملك عنصرا معاكسا، تكون زمرة، يرمز إليها ب *X**، ويرمز إلى عدد عناصرها ب |X^*|.

عنصر من *X* والذي لا يملك عنصرا معاكسا هو 0, إذن، |X^*| \leq |X| - 1 = q^2 - 1.

حاليا M_p \equiv 0 \pmod{q} and \omega \in X, إذن،
:kM_p\omega^{2^{p-2}} = 0
in *X*.
إذن، من خلال المعادلة (1),
:\omega^{2^{p-1}} = -1
في *X*, رفع كلا الحدين إلى المربع يعطي ما يلي:
:\omega^{2^p} = 1.
إذن، \omega هو موجود في *X** وله عنصر معاكس \omega^{2^{p}-1}. أضف إلى ذلك, the رتبة of \omega يقسم 2^p. ولكن \omega^{2^{p-1}} \neq 1, إذن، الرتبة لا تقسم 2^{p-1}. إذن، الرتبة هي بالتحديد 2^p.

رتبة عنصر في زمرة تساوي على الأكثر عدد عانصر تلك الزمرة. إذن،
:2^p \leq |X^*| \leq q^2 - 1 
ولكن q هو أصغر عامل أولي من بين الأعداد الأولية اللائي يشكلن تفكيك M_p إلى جداء عوامل أولية. إذن،
:q^2 \leq M_p = 2^p-1.
هذا يؤدي إلى التناقض 2^p . إذن, M_p أولي.

### كونه ضروريا

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

## انظر أيضا
* البحث الكبير عن أعداد ميرسين الأولية في الإنترنت.

## ملاحظات

## مراجع

تصنيف:أعداد مرسين الأولية
تصنيف:اختبارات أولية العدد